Polygon CCW winding check request

[Hervé Wozniak]

Hi all,

Any concave polygon (and self-intersecting polygons are concave) can be 
decomposed into a set of convex polygons. It is then enough to test 
whether a point belong to at least one of the convex polygons, with the 
classic rule already mentioned. This method has fewer special cases than 
the ray-tracing method. Algorithms already exist. This technique is 
widely used in collision detection for video games (and solid physics 
:-) ). They must therefore exist for GPUs for efficiency (maybe less 
accurate...).

https://github.com/kmammou/v-hacd
gives good approximations for games, but maybe not enough accurate for 
your applications...

My two cents...

Hervé


Le 15/06/2018 à 16:41, Francois-Xavier PINEAU a écrit :
> 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
> 

-- 
Herve WOZNIAK
Astronome

Directeur-adjoint
LUPM
UMR5299 Université de Montpellier - CNRS
Place Eugène Bataillon - CC 72
F-34095 Montpellier Cédex 05

Tel/Phone : +33 4 6714 3902   Fax : +33 4 6714 4190

skype : herve.wozniak
http://herve.wozniak.fr/