Polygon CCW winding check request

[Markus Nullmeier]

Hello list,

On 13/06/18 10:05, Francois-Xavier PINEAU wrote:
> 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.

Well, a definition that allows polygon edges to intersect would be
unsound, probably in several ways. One of them is the mentioned
inability to describe the complement of a polygon as a single polygon.

> How to deal easily with such a case while remaining compatible with the
> STC definition?

The obvious solution would be allowing for sets of polygons as another
data type, where intersecting edges your kind of polygons would have to
be split, as has been already mentioned today.
However, at the end of the day, this is not sufficiently general:

> 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?

Very much so. For, to maximise the usefulness of polygons in ADQL, at
some point in time (OK, just today, see below ;-) people will ask for
a data type that is able to hold the results of all basic set operations
of polygons. Using some kind of unnatural polygon definition will render
such a data type unbelievable messy.

On 13/06/18 18:47, Marco Molinaro wrote:
> I agree support for complex morphology has to be taken into account. 
> For example I'm not sure how a donut-like shape can be represented,
> or how half a donut with a detached bite would be describable.>
> What I wonder is: where do this will lead to. I must say that I
> usually considered my ~complex uses case of this kind to be solved by
> a tessellation approach. But if we need an analytical approach, then
> we have to figure it out.
Well, I think this naturally leads to the data type of which I wrote
about above, i. e., shapes that are delimited by a set of 'polygon-
shaped borders'. The winding order of these borders naturally leads
to the definition of the inside and outside: as one travels from one
edge to the next, the inside of the shape is always on the left hand
side.
All of this has of course been used for computational geometry in the
plane, for a long time.
Seemingly the only tricky bit on the sphere is that there is no kind of
meaningful bounding box definition for these kinds of shapes -- but that
is actually not necessary to perform efficient calculations such as
membership of a point in a given shape.

But as today's request for having arbitrary circles as "polygon" edges
has already shown, great circles, i. e., the equivalents of straight
lines, will hardly be an efficient means to satisfactorily approximate
arbitrarily curved shapes on the sphere. Another use case is the
efficient approximation of MOC (i. e., Healpix) boundaries -- and there
should be other extant tessellations of interest for similar use cases.

Again, efficient solutions are standard fare in plane geometry. Each and
every of today's 2D vector drawing programme uses third-order Bézier
curves, for example.

It is tempting to just use Bézier curves that 'live' on the sphere
(using great circles as a replacement of straight lines for their
 definition). However, as these curves cannot exactly represent
arbitrary circles, we should directly go to non-uniform rational
basis splines (NURBS) on the sphere.

Best regards,
Markus Nullmeier