Polygon CCW winding check request

Wed Jun 13 18:48:21 CEST 2018

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/a62ec1ff/attachment-0001.html>