Déterminer l’intérieur / l’extérieur d’une polyligne plane fermée

[invitec4536001]

Définition :

Poly ligne plane fermée :
- C’est une succession de segments de droites et d’arcs de cercle consécutifs.
- Ils sont tous inscrits dans un même plan de l’espace 3D.
- Le premier point et le dernier de la polyligne sont confondus.
- Sur tout le pourtour, il y a continuité de la bordure.
- La polyligne peut être aussi bien concave que convexe.
- Elle permet de définir deux surfaces, l’une intérieure et l’autre extérieure à la bordure.
- Il n’y a pas de coupure dans la polyligne et ses éléments ne s’intersectent pas (exemple de deux segments se coupant est impossible)
- Un point peut appartenir à plusieurs éléments de la polyligne (exemple : un 8 est possible si des portions de la polylignes ne se coupent pas)
- Il n’y a pas de trou dans la polyligne.

Point projeté :
- Point de l’espace 3D projeté sur le plan de la Polyligne

Question :

Comment déterminer si un point projeté est à l’intérieur ou à l’extérieur d’une polyligne plane fermée ?

Réponse recherchée :

- Une aide pour trouver une solution ou
- un algorithme ou
- une indication sur un livre, un article, un lien internet parlant de ce sujet ou
- un code informatique écrit en C
-----

[invite206bb45f]

L'algo classique consiste a prendre une demi-droite qui part du point considere. On peut prendre la demi-droite horizontale pour simplifier les calculs. Ensuite, on compte le nombre d'intersections entre la demi-droite et la polyline en examinant tous les segments. Si ce nombre est pair, le point est en dehors, sinon il est dedans.

[invitea0046ad4]

Bonjour

Cette méthode est théoriquement correcte mais son implémentation est plus compliquée qu'il n'y parait. Une implémentation directe par des calculs en virgule flottante de précision finie ne permet pas d'écrire un programme qui fonctionne : on peut toujours trouver des cas dégénérés qui mettent en défaut l'algorithme.
Dans le cas d'un contour polygonal, le problème se résoud rigoureusement en calculant en arithmétique rationnelle.
Si le contour contient des arcs de degré supérieur, je ne suis pas sur qu'il existe un algorithme mathématiquement prouvé basé sur cette méthode.

Donc: cette méthode est simple à programmer à un niveau élémentaire, mais n'est pas d'une fiabilité absolue dans la pratique. C'est plus ou moins acceptable suivant l'application, mais en général suffisant pour du graphique par exemple, en traitant les cas pathologiques les plus courants.

Autre méthode : décomposition du domaine 2D en quadtree
Cette méthode nécessite un précalcul et un stockage de données, mais l'algorithme de classification d'un point est ensuite très rapide et très stable.

Il existe de nombreux algorithmes. Le choix du meilleur dépend de ce que l'on cherche à optimiser : temps de précalcul, temps de classification d'un point, occupation mémoire, stabilité, etc.
Donc, la bonne réponse dépend de l'application.
Il y a des rapport de recherche sur le sujet sur le site de l'INRIA (entre autre) : www.inria.fr

A+

[invite51f4efbf]

- une indication sur un livre, un article, un lien internet parlant de ce sujet ou

A un niveau avancé, c'est de la topologie différentielle (licence de maths je dirais). Voir Milnor : Topology From the Differentiable Viewpoint. Ca généralise ce que dit Vuibert

[A voir en vidéo sur Futura]

[invitec4536001]

Je remercie toutes les personnes qui auront bien voulu me donner quelques conseil. Je suis en train de tester une méthode en calculant la somme des angles du point à tous les sommets de la polyligne.