Polygon CCW winding check request

[Hervé Wozniak]

Hello,
Having taken the conversation along the way, I had not perceived that 
the discussion concerned the surface of a sphere.

However, this does not change the more general idea that 
self-intersecting polygons should be decomposed into convex polygons first.

Btw, I don't know of a specific library for polygons on a sphere. What 
is used for the meshing of sphere surfaces in numerical simulations is 
quite close to what is already practiced in geography/astronomy.

Cheers
Hervé

Le 15/06/2018 à 18:54, Dobos, László a écrit :
> Hi Hervé,
> 
> Do algorithms exist for spherical polygons also? In the Spherical lib of Budavari et al., (SkyServer, etc.) we don't allow bowties (self-intersecting polygons).
> 
> -Laszlo
> 
> -----Original Message-----
> From: dal-bounces at ivoa.net [mailto:dal-bounces at ivoa.net] On Behalf Of Hervé Wozniak
> Sent: Friday, June 15, 2018 6:32 PM
> To: Francois-Xavier PINEAU <francois-xavier.pineau at astro.unistra.fr>; Markus Nullmeier <mnullmei at ari.uni-heidelberg.de>; DAL mailing list <dal at ivoa.net>
> Cc: Data Models mailing list <dm at ivoa.net>
> Subject: Re: Polygon CCW winding check request
> 
> 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/
> 

-- 
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/