Polygon CCW winding check request
Francois-Xavier PINEAU
francois-xavier.pineau at astro.unistra.fr
Mon Jun 18 09:44:00 CEST 2018
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/dm/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/dm/attachments/20180618/2959b3ed/attachment-0001.png>
More information about the dm
mailing list