Polygon CCW winding check request

[Markus Nullmeier]

Hello list,

On 15/06/18 16:41, Francois-Xavier PINEAU wrote:
>> 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.

> Yes, and this work just the same for self-intersecting polygons.

Only if you disallow edges that (partly) overlap. But you cannot
detect them reliably unless you require everybody to use exact
rational arithmetic instead of customary floating-point arithmetic.
(This of course additionally includes exactly prescribing the
 approximations, i. e., the implementations, that are used for
 the trigonometric functions.
 [Otherwise some polygons would be allowed for one service and illegal
  for another.]
 A minor investment compared to using rational arithmetic in the first
 place, but probably still highly annoying for many.)

See the attached image (do attachments work on the IVOA lists?
otherwise, use http://www.g-vo.org/edp-forum-2018/collinear-edges.png )
for a counterexample with overlapping edges, where 'inside' and
'outside' is no longer well-defined for self-intersecting polygons.

And while overlapping edges are obviously something that one also wants
to disallow for non-intersecting polygons, they are less of a problem
there because they are
a) less likely to emerge because of non-existent intersecting edges
b) the algorithm above may be made quite robust by allowing a certain
   "slack margin" for "in-"/"out-" crossing of (quasi-) collinear edges
   that exhibit an inconsistent order.

The "slack margin" argument also works for the task of validating non-
intersecting polygons effectively, rendering them much more easily
interoperable than the self-intersecting variant by the simple virtue of
assigning the burden of defining 'inside' and 'outside' to client
applications.

Best regards,
Markus Nullmeier
-------------- next part --------------
A non-text attachment was scrubbed...
Name: collinear-edges.png
Type: image/png
Size: 2304 bytes
Desc: not available
URL: <http://mail.ivoa.net/pipermail/dal/attachments/20180615/072025b7/attachment.png>