Polygon CCW winding check request

[Arnold Rots]

And yes, I should have said that STC 1.33 got it wrong and needs an
erratum, but just changing the sign does not really solve the problem,
because of what I just wrote.

Cheers,

  - Arnold

-------------------------------------------------------------------------------------------------------------
Arnold H. Rots                                          Chandra X-ray
Science Center
Smithsonian Astrophysical Observatory                   tel:  +1 617 496
7701
60 Garden Street, MS 67                                      fax:  +1 617
495 7356
Cambridge, MA 02138
arots at cfa.harvard.edu
USA
http://hea-www.harvard.edu/~arots/
--------------------------------------------------------------------------------------------------------------


On Wed, Jun 13, 2018 at 12:53 PM, Arnold Rots <arots at cfa.harvard.edu> wrote:

> I meant to send this to DM as well.
>
> Cheers,
>
>   - Arnold
>
> ------------------------------------------------------------
> -------------------------------------------------
> Arnold H. Rots                                          Chandra X-ray
> Science Center
> Smithsonian Astrophysical Observatory                   tel:  +1 617 496
> 7701
> 60 Garden Street, MS 67                                      fax:  +1 617
> 495 7356
> Cambridge, MA 02138
> arots at cfa.harvard.edu
> USA
> http://hea-www.harvard.edu/~arots/
> ------------------------------------------------------------
> --------------------------------------------------
>
>
> On Wed, Jun 13, 2018 at 12:48 PM, Arnold Rots <arots at cfa.harvard.edu>
> wrote:
>
>> The situation is more complicated.
>> Recently I had a discussion with Felix Stoehr where we arrived at a
>> fairly decent conclusion.
>>
>> As an aside, if one uses unitsphere coordinates, the halfspaces used by
>> the SDSS people provide a perfect and unambiguous way to specify any shape,
>> with the exception of ellipses. The only drawback is that it only allows
>> convex polynomials; that means that concave polynomials need to be built
>> from unions of convex polynomials. Significantly, it also allows for shapes
>> with parallel (in addition to great circle) sides. A circle is a single
>> halfspace, a polygon is the intersection of a collection of halfspaces, etc.
>>
>> In terms of the shapes we need to accommodate, I think it is sufficient
>> to require that we cover polygons (convex and concave) and circles.
>> With the exception of ellipses, all other shapes can be described by
>> these two.
>> As far as ellipses are concerned, there are problems in spherical
>> coordinate systems, but to first order they can be handled analogously to
>> circles.
>> There is an issue with polygon sides in spherical systems that are
>> segments of parallels, rather than great circles, but for now we will gloss
>> over that.
>> In spherical systems we will require that polygon sides are less < pi.
>> Any side larger than that can be built up by inserting an intermediate
>> vertex.
>> But we will require that polygon sides do not intersect. If one really
>> needs to represent a butterfly shape, it should be effected as the union of
>> two polygons.
>>
>> The handedness of spherical coordinate systems is always determined from
>> the viewpoint of the observer. For celestial systems this means from the
>> inside; for systems on a spherical body (earth, sun, planets, etc.) from
>> the outside.
>>
>> Here come the complications:
>> There is a fundamental difference between shapes in spherical coordinate
>> systems and shapes in Cartesian 2-D coordinate systems.
>> [We do have to cover both cases, since people will be working on the
>> celestial sphere, as well as in tangent planes. Of course, using a
>> Cartesian approximation in a tangent plane does not give one the most
>> accurate result in terms of spherical area, but I am sure people will do
>> it, contending that it is good enough for their purpose in small fields.]
>> First, in both cases the shape divides the space into two parts, but in
>> the Cartesian case the area of one part is finite, the other infinite,
>> while in the spherical case both are finite.
>> Second, in the Cartesian case the area of the finite part of a polygon is
>> calculated by summing the determinants of the outer products of all
>> adjacent vertex pairs and divide by 2, while in the spherical case it is
>> the sum of the angles at the vertices minus (n-2)*pi. For the circle the
>> expressions are pi*r^2 and 2*pi*(1-cos(r)), respectively.
>>
>> Where does the handedness of the coordinate system come in?
>> Only for polygons.
>> For Cartesian systems it is simple. The sum of determinants is positive
>> if one goes around CCW in a right handed system, negative in a left handed
>> system.
>> For spherical systems you need to know which angle to choose at each
>> vertex: the angle at your left or at your right.
>>
>> What Felix and I gravitated toward was:
>> Polygons
>> Regardless of whether your coordinate system is right- or left-handed,
>> take the vertex coordinates in the order provided, pretend that the system
>> is right-handed, and the area that is circled on your left (I.e., CCW) is
>> the polygon area specified.
>> For Cartesian systems it is simple: just calculate the sum of
>> determinants divided by 2; if the result is positive, the finite area is
>> selected; if it is negative, the finite area is excluded.
>> For spherical systems it should tell you which angles to sum.
>> The only caveat is that if one transforms a series of vertices in RA and
>> Dec to a right-handed Cartesian system in the tangent plane (or the
>> reverse), one has to invert the order of the vertices.
>>
>> Circles
>> In spherical systems there is no ambiguity if one allows the radius to be
>> < pi.
>> In Cartesian systems we propose that a negative value r for the radius
>> indicates that the area outside the circle with radius |r| is selected;
>> i.e., the circle is excluded.
>>
>>
>> This definition appears to be consistent with the usage of regions in
>> several major observatory archives.
>>
>> One could, of course, provide more flexibility (and clarity!) by using
>> the four operators Union, Intersection, Not, and Difference, as allowed in
>> STC-S.
>>
>> Cheers,
>>
>>   - Arnold
>>
>> ------------------------------------------------------------
>> -------------------------------------------------
>> Arnold H. Rots                                          Chandra X-ray
>> Science Center
>> Smithsonian Astrophysical Observatory                   tel:  +1 617 496
>> 7701
>> 60 Garden Street, MS 67                                      fax:  +1 617
>> 495 7356
>> Cambridge, MA 02138
>> arots at cfa.harvard.edu
>> USA
>> http://hea-www.harvard.edu/~arots/
>> ------------------------------------------------------------
>> --------------------------------------------------
>>
>>
>> On Wed, Jun 13, 2018 at 4:05 AM, Francois-Xavier PINEAU <
>> francois-xavier.pineau at astro.unistra.fr> wrote:
>>
>>> Dear Marco, DAL,
>>>
>>> I may be wrong, but I think that the STC definition of the inside of a
>>> polygon is not compatible with "complex" shapes.
>>>
>>> Example: if we take the case of a simple 4 vertices's polygon having a
>>> butterfly shape (i.e. having two crossing great-circle arcs), then the
>>> inside of one "wing" is in the counter-clockwise sense while the inside of
>>> the other "wing" is in the clockwise sense.
>>>
>>> How to deal easily with such a case while remaining compatible with the
>>> STC definition?
>>>
>>>
>>> A polygon is just a sequence of vertices with great-circle arcs
>>> connecting the consecutive vertices (plus the last vertex connection the
>>> first one).
>>>
>>> The great-circle arc connecting two vertices's is the smallest of the
>>> two complementary great-arcs (and hence is always <= pi (we have a
>>> degeneracy with vertices having an angular separation of pi)).
>>>
>>> There is no ambiguity on the inside and we have fast implementations for
>>> polygons having possibly very complex shapes (ray-tracing method).
>>>
>>> It is true that then the definition does not allow to describe the
>>> "exterior" (the complement on the sphere) of a polygon as being itself a
>>> polygon. Is it a problem in practice?
>>>
>>> From my (biased) point-of-view, it is more important to support complex
>>> polygons (with a simple and fast algorithm), and to possibly ask for an
>>> extra boolean parameter in use cases requiring the complement of a polygon.
>>>
>>> Do you agree / disagree?
>>>
>>>
>>> Kind regards,
>>>
>>>
>>> François-Xavier
>>>
>>>
>>>
>>> Le 12/06/2018 à 17:45, Marco Molinaro a écrit :
>>>
>>> Dear DAL members,
>>> at the recent IVOA Interop in Victoria it was pointed out
>>> by Alberto
>>>
>>> http://wiki.ivoa.net/internal/IVOA/InterOpMayy2018DAL/ivoa_2
>>> 01805_micol_polygons.pdf
>>>
>>> that not all the data providers follow the STC specification
>>> about the winding direction of polygons stored in their
>>> archives.
>>>
>>> STC states that "The inside of the region is defined as
>>> that part of coordinate space that is encircled by the
>>> polygon in a counter-clockwise sense".
>>> And this is to be considered when looking at the
>>> celestial sphere from the inside.
>>>
>>> The different behaviour of the polygons stored at
>>> different sites creates an interoperability issue.
>>>
>>> This email is a request on data providers to check
>>> on their data and implementations (when dealing
>>> with polygons) to solve the presented issue.
>>>
>>> James also put together a python code snippet
>>> implementing a simple test, it is available here:
>>>
>>> https://gist.github.com/jd-au/45d1cdc0c6e2a7bc848a4be8f46c8958
>>>
>>> Thank you in advance!
>>> Cheers,
>>>        Marco & James
>>>       (your DAL chair & vice)
>>>
>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.ivoa.net/pipermail/dal/attachments/20180613/f1b6f3f5/attachment-0001.html>