STC-S to S-MOC implementation

[Arnold Rots]

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/1f11c255/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: adass2006.ppt
Type: application/vnd.ms-powerpoint
Size: 1591296 bytes
Desc: not available
URL: <http://mail.ivoa.net/pipermail/dal/attachments/20231214/1f11c255/attachment-0001.ppt>