STC-S to S-MOC implementation
F.-X. Pineau
francois-xavier.pineau at astro.unistra.fr
Thu Dec 14 20:34:36 CET 2023
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 <http://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 <http://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 <http://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/apps/attachments/20231214/e263f690/attachment-0001.htm>
More information about the apps
mailing list