Polygon CCW winding check request

[Francois-Xavier PINEAU]

Markus,

I am no sure to understand the problem.

Using the following polygon in Aladin:

draw polygon(10.0, 0.0, 0.0, -2.0, 2.0, 10.0, 10.0, 0.0, 2.5, 0.0, 4.0, 
5.0, 10.0, 0.0, 3.0, 0.0 ,3.5, 1.0, 4.5, 0.0)

I get a result which seems correct (see below).

I suspect that the problem you mention (on the need for rational 
arithmetic) as no consequence in practice: the areas between two very 
close edges (which are supposed to overlap) is going to be very very 
close from 0 (I may be missing something, let's discuss this off list if 
you want).


It seems that there is a large consensus to support only 
non-self-intersecting polygons, so I am not going to push any further.

I suppose that VO documents should be updated to state explicitly that 
self-intersecting polygons are not supported.

Kind regards,


François-Xavier



Le 15/06/2018 à 18:47, Markus Nullmeier a écrit :
> 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 --------------
An HTML attachment was scrubbed...
URL: <http://mail.ivoa.net/pipermail/dal/attachments/20180618/2959b3ed/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ocdicfhbeplahhlf.png
Type: image/png
Size: 640413 bytes
Desc: not available
URL: <http://mail.ivoa.net/pipermail/dal/attachments/20180618/2959b3ed/attachment-0001.png>