Polygon CCW winding check request

[Dobos, László]

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/