STC-S to S-MOC implementation

[Arnold Rots]

Well, very simply, I envisioned a need for donut shaped regions, for a
variety of reasons.
For instance, one might want to get a background signal for a source from
an extended region, excluding a circle around the source itself.
And I didn't add XOR, since I didn't see an obvious need for it. While it
could always be constructed...

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 2:34 PM F.-X. Pineau <
francois-xavier.pineau at astro.unistra.fr> wrote:

> Arnold,
>
> Good to ear from you.
>
> Yes,
> XOR(R1,R2) = Difference (Union(R1, R2), Intersection(R1,R2))
> i.e, if we have neither XOR nor MINUS:
> XOR(R1,R2) = Intersection (Union(R1, R2), Not(Intersection(R1,R2)))
>
> But:
>
> 1.  I wonder why having put the MINUS and not the XOR in the standard.
> When dealing with boolean, the "DIFFERENCE" is the "XOR"
> and is more natural (from my biased perspective) than the "MINUS":
> For a point p,
> A.contains(p) != B.contains(p) <=> (A XOR B).contains(p)
> while
> A.contains(p) && !B.contains(P) <=> (A MINUS B).contains(p)
>
> and the MINUS is easier to build from other operations (A AND NOT(B)),
> as stated in the STC-S document, than the XOR ((A OR B) AND NOT(A AND B)).
> I would thus say that implementing the XOR is more important, especially
> considering...
>
> 2. ...performances. Again, having a built-in XOR is more important
> than having a MINUS in case we have to emulate the not-in-the-standard one.
>
> My personal choice would be to change DIFFERENCE for MINUS and to
> add XOR in the STC-S standard.
>
> You may had good reasons not to do that, please let me know.
>
>
> fx
>
>
>
>
> Le 14/12/2023 à 19:40, Arnold Rots a écrit :
>
> 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/dal/attachments/20231214/a1e81564/attachment-0001.htm>