Polygon CCW winding check request
Francois-Xavier PINEAU
francois-xavier.pineau at astro.unistra.fr
Fri Jun 15 16:41:32 CEST 2018
Markus,
Le 15/06/2018 à 15:59, Markus Nullmeier a écrit :
> 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.
Would you please develop because...
>
> 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.
... it really looks like the "ray-tracing" method I mentioned.
> 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".
Yes, and this work just the same for self-intersecting polygons.
Best regards,
François-Xavier
>
>> 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
More information about the dm
mailing list