STC-S to S-MOC implementation

[Arnold Rots]

FWIW
 XOR(R1,R2) = Difference (Union(R1, R2), Intersection(R1,R2))

Arnold H Rots

Research Associate

SAO/HEAD

Center for Astrophysics | Harvard & Smithsonian

Email: arots at cfa.harvard.edu

Office: +1 617 496 7701 | Cell: +1 617 721 6756

60 Garden Street | MS 69 | Cambridge, MA 02138 | USA


cfa.harvard.edu | Facebook <http://cfa.harvard.edu/facebook> | Twitter
<http://cfa.harvard.edu/twitter> | YouTube <http://cfa.harvard.edu/youtube>
| Newsletter <http://cfa.harvard.edu/newsletter>


On Thu, Dec 14, 2023 at 1:10 PM Arnold Rots <arots at cfa.harvard.edu> wrote:

> This discussion sent me down a rabbit hole. So, here is some historical
> context.
> I developed STC-S at the request of Jim Gray who was interested  in using
> it for his indexing scheme in MS SQLServer.
> Indexing spherical coordinates in SQL.
> See: https://arxiv.org/abs/cs/0701171 and references therein.
>
> Tamas Budavari had a parser for SkyQuery that converted STC-S to a series
> of half-spaces to describe regions.
> But that, of course, worked with HTM, not HealPix.
> However, the half-spaces scheme was very clever, since it allowed
> describing polynomials not only using great circles, but also parallels,
> using the sides, rather than the vertices; and it discriminated in a
> natural way between inside and outside.
> It's described in an ADASS 2006 talk, attached.
>
> Cheers,
>
>   - Arnold
>
> Arnold H Rots
>
> Research Associate
>
> SAO/HEAD
>
> Center for Astrophysics | Harvard & Smithsonian
>
> Email: arots at cfa.harvard.edu
>
> Office: +1 617 496 7701 | Cell: +1 617 721 6756
>
> 60 Garden Street | MS 69 | Cambridge, MA 02138 | USA
>
>
> cfa.harvard.edu | Facebook <http://cfa.harvard.edu/facebook> | Twitter
> <http://cfa.harvard.edu/twitter> | YouTube
> <http://cfa.harvard.edu/youtube> | Newsletter
> <http://cfa.harvard.edu/newsletter>
>
>
> On Wed, Dec 13, 2023 at 6:49 AM F.-X. Pineau <
> francois-xavier.pineau at astro.unistra.fr> wrote:
>
>> Dear all,
>>
>> Whatever the future of the STC-S working draft is, having -- even partial
>> --
>> implementations may help the debate.
>>
>> A few MOCPy users have asked for a S-MOCs from STC-String feature.
>> And it seems that S-MOCs are considered to replace (at least in some
>> places) STC.
>> I am curious to know where exactly since MOCs and STC-S are complementary:
>> * STC-S is compact -- as far as it does not contains  unions/intersection
>> of hundreds
>>   of shapes -- and precise, but not indexation oriented
>> * MOCs are approximations, not compact -- except at low resolutions --
>>   but fast and indexation oriented
>> I believe that efficient STC-S queries must rely (internally) on MOCs
>> (or other similar mechanisms), but should not be replaced by MOC queries
>> (even if MOC queries are interesting too and can help in STC-S queries).
>>
>>
>> ## STC-S Parser
>>
>> So, as previously announced, I implemented a STC-S parser available on
>> both
>>  github and crates.io:
>> * https://github.com/cds-astro/cds-stc-rust
>> * https://crates.io/crates/stc-s
>> There is still room for improvement and feeback/comments from people
>> with STC experience would be much appreciated.
>>
>>
>> ## STC-S to S-MOC
>>
>> This email to announced that I now have also implemented a *first
>> version of*
>> *the STC-S to S-MOC feature* in MOCLibRust and in:
>> * *moc-cli*: already available in pypi and github release
>>     + https://pypi.org/project/moc-cli/
>>     + https://github.com/cds-astro/cds-moc-rust/tree/main/crates/cli
>>     + Example: echo "Circle ICRS 147.6 69.9 0.4" | moc from stcs 14 -
>> fits stcs.moc.fits --force-u64
>> * moc-wasm: already available in github release
>>     + https://github.com/cds-astro/cds-moc-rust/tree/main/crates/wasm
>> * *MOCPy*: implemented in the github source code, but not released yet
>>     +  https://github.com/cds-astro/mocpy
>> The feature has been put in place but now have to be tested more
>> thoroughly.
>> So far the limitations are:
>> * it *supports only frame=ICRS, flavor=SPHER2 and units=deg*
>> * it wrongly considers the* DIFFERENCE to be a SYMMETRIC DIFFERENCE*
>> (XOR)
>>   instead of a "MINUS".
>>   Note that for a single polygon whith a hole inside it, the result is
>> the same,
>>   except that:
>> * it does not adopt the STC definition of a polygon:
>>   + it *supports self-intersecting polygons*
>>   + the polygon interior is (kind of) the part having the smallest area,
>> i.e.
>>     the order of the vertices does not matter
>> We do support nested UNION/NOT/INTERSECTION/XOR operations.
>> To do so, we rely on BMOCs implemented in the CDS HEALPix Rust
>> library.
>> BMOCs are S-MOCs storing in each cell a boolean flag telling if the cell
>> is for
>> sure fully inside the geometrical shape or not.
>> For example, the NOT operation removes all cells having the boolean set
>> to 'true'
>> but preserves the cells having the boolean set to 'false' (and add
>> missing cells
>> setting their flag to 'true').
>> BMOCs have so far two drawback:
>> * operations on BMOCs has not yet been thoroughly tested
>> * operations on BMOCs are -- at least in the current implementation --
>> much slower
>>   than operations on MOCs
>> In the future, we may first detect the operations in a STC-String to
>> switch
>> between MOCs (neither NOT or DIFFERENCE operations) and BMOCs.
>> Except that BMOCs have also one big advantage: they can be spitted into 2
>> sub-MOCs
>> * one fully inside the STC region (no additional test needed, e.g. when
>> retrieving sources)
>> * one "edges" MOC: additional tests needed to determine if a source in
>> this MOC
>>   is in or out of the STC region.
>>
>>
>> *If you have example of STC-String, especially with operations
>> (Alberto?),      please send them to us so we can add them to our tests.*
>>
>> Even if STC-S is dropped in the future, it should not be that complex to
>> adapt to another standard like DALI "shape".
>> (Although STC-S is complex, it is quite complete and self-consistent
>> since it contains
>> information such as the frame: the two sides of a medal).
>>
>>
>> ## About polygons:
>>
>> We support self-intersecting polygons.
>>
>> Although it is useless when describing footprints, I do think it makes
>> sense
>> when you let a user create a polygon by clicking in interfaces such as
>> Aladin/Aladin Lite or TOPCAT.
>> In addition, the existing algorithm to deal with self-intersecting
>> polygons is
>> simple (at least in the plane, with some complications on the sphere)
>> and fast (see https://wrfranklin.org/Research/Short_Notes/pnpoly.html).
>>
>> The best option to define the interior/exterior of a self-intersecting
>> polygon
>>  may be to provide a control point, provided it is not a vertex and is
>> not part
>> of an edge. (It's on of the several options that has been implemented in
>> the
>>  CDS Healpix Lib).
>> The control point can be automatically computed from the current standard
>> for
>> non-intersecting polygons:
>> * for convex polygons: we can use the gravity center (or its opposite) by
>> testing it
>>   with the current convention (if the gravity center is (0, 0, 0),
>>   remove recursively one vertex, starting from the first one).
>> * concave polygons: by testing the gravity center of 3 successive
>> non-aligned vertices,
>>   iterating till one lies inside the polygon by the current standard
>> (also ensuring
>>   the point is not a vertex or on an edge).
>> * self-intersecting: the control point would have to be provided, i.e.
>> after the last
>>   vertex (unless we all agree on a same algorithm, using the NOT
>> operation to define
>>   the complement polygon).
>>
>> Alberto:
>> If I understand correctly, a polygon with a hole is the intersection
>> of a CCW polygon with a (smaller) CW polygon, right?
>> Why not having used the difference between two CCW polygons?
>> Is it because the difference in STC-S is not a symmetric difference and
>> hence
>> you cannot use the logical XOR operation in a database expression?
>> (
>> *That may advocate to replace the DIFFERENCE by/ or at least to add a
>>  SYMMETRIC DIFFERENCE in STC :)* ).
>>
>>
>> fx
>>
>>
>>
>>
>>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.ivoa.net/pipermail/dm/attachments/20231214/bac76d4b/attachment-0001.htm>