Polygon CCW winding check request
Arnold Rots
arots at cfa.harvard.edu
Wed Jun 13 18:53:50 CEST 2018
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/dac6ca1a/attachment.html>
More information about the dal
mailing list