Polygon CCW winding check request

[Markus Nullmeier]

Hello list,

On 15/06/18 09:34, Francois-Xavier PINEAU wrote:
> Le 14/06/2018 à 18:22, Arnold Rots a écrit :
>> And I maintain that it is a very bad idea to allow self-intersecting
>> polygons.
> Sorry, but I am not sure to understand why.

One reason is that testing membership of a point with respect to
a polygon becomes necessarily inefficient in any self-intersecting
scheme.

With the "interior to one side of the encircling edges" rule,
a.k.a. 'winding rule', you just look at _one_ path (such as a single
great circle segment -- others are equally feasible), going from
any vertex of the polygon to the point to test, i. e., at the crossings
of the path to the test point with the edges of the polygon.
  This works just the same for the more general class of shapes that
are bounded by any number of paths of great circle segments, such as
shapes with holes or collections of polygons. Maybe we should call
them "polygonal sets".

> If we let a user the possibility to draw a polygon by hand on the
> sphere, why forbidding self-crossing polygons?

Because such things should be normalised to shapes bounded by several
paths of non-intersecting great circle segments, as mentioned above
(and in my first message on this topic to DAL on 13 June [UTC]).
This means that there is of course no point in forbidding anything
denoted by your self-crossing polygons, the question rather is how
to store and process such things in an efficient way. With that comes
the question of how to define the domain of the respective data type
in a mathematically sound way.
I think it is hard to argue against the soundness of the domain of
"polygonal sets" that is virtually closed under finitely many elementary
set operations (probably only ignoring the membership of the edges and
nodes -- but, if deemed necessary, even that can be accounted for).

> And the exception of HEALPix cells, and ...

As I wrote before, ultimately, spherical NURBS will be the way to go.
But then again, having working implementations of "polygonal sets" would
be a great step in that direction.

Best regards,
Markus Nullmeier