Polygon CCW winding check request

[Markus Nullmeier]

Hello list,

On 18/06/18 09:44, Francois-Xavier PINEAU wrote:
> 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).

Well, I think the screenshot wonderfully highlights the exact problem I
was beating on. For, if (as I understand the definition given for self-
intersecting polygons) one defines "inside" and "outside" for
overlapping polygons via some reference point that is supposed to be
outside of the polygon and then calculates
(number of crossings of edges from reference point to test point) mod 2,
with a result of 0 and 1 meaning "outside" and "inside", respectively,
the self-intersecting polygon shown must be rejected as illegal:

Let's assume that the reference point is the small turquoise "x" in
the middle of the bottom of the image. It is easy to see that there are
paths from there to the inside of the self-intersecting polygon that
would render the small inner polygon as being outside (while it is
inside in the image), as well as there are paths that would render
the bigger inner polygon as outside -- that is what the image shows,
but it is essentially a random result.
Hence, we see that this particular example is _not_ well-defined and
must not be allowed.

> I suspect that the problem you mention (on the need for rational

The problem is the reliable detection of collinear edges (apparently
the root cause of problems such as the one described above), rational
arithmetic is the only known (and absurdly expensive) cure for it.

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

Now as far as I can see, the case for a larger class of "polygon-like"
geometries has been made by many. Alberto Micol made a very explicit
plea for a union of polygons as a single datum in Santiago last year,
then the self-intersecting polygons came up, and Marco Molinaro
mentioned shapes with holes. I proposed a data type that is able to
cater for all these use cases. But I also perceive an general
understanding that whatever will be the result of that, it will not
be called 'polygon'.

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

A very good point, IMHO. And I think (if this should not be already
the case) it should be also made clear that the paths of polygons are
expected to be closed.

Best regards,
Markus Nullmeier
-------------- 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/948e000b/attachment-0001.png>