Polygone : Détecter le sens de déclaration des points !

Salut à tous !

Je créer un petit module qui prend en charge la conversion des géométries de NetTopologySuite vers MapWinGIS. Si vous ne connaissez pas, cela n'a aucune importance.
Un polygone est composé d'une seule (et obligatoire) ligne décrivant l'extérieur et de zéro, une ou plusieures ligne décrivant d'éventuels polygones intérieures.
Il existe une convention qui dit que les points de la ligne extérieure d'un polygone doivent être déclarés dans le sens inverse des aiguilles d'une montre alors que les points décrivant une ligne intérieure doivent être déclarés dans le sens des aiguilles d'une montre. (Voir pièce jointe)
Savez-vous, à partir d'une liste de points, comment "détecter" leurs sens de déclaration, sachant qu'on ne peux pas se baser sur les quelques premier points mais, il me semble, sur l'ensemble des points.
Quand je dis liste de points, c'est la liste pour un seul polygone mais j'aimerai pouvoir savoir si il est extérieur ou intérieur !

Merci de vos réponse et @ très vite !
Antoine

Bonjour

Essaye le signe du produit vectoriel de 3 points consecutifs ;)

Est-ce que les polygones sont convexes ? Si oui, pseudocode a une solution parfaite.

Si non, il faudrait trouver un point O à l'intérieur du polygone, et faire la somme des angles orientés Pn->O->Pn+1. Le signe de la somme de donne l'orientation du polygone (avec Pn points du polygone évidemment).

Une méthode pour tester si un point est à l'intérieur d'un polygone : faire de nouveau la somme des angles orientés par rapport à ce point. Si c'est nul, tu es à l'extérieur du polygone.

Et enfin, comment trouver un point dans un polygone à coup sûr ? Ben là, je ne vois pas trop de méthode directe. Tester deux points à une distance d de par et d'autre d'un segment du polygone. Si les deux sont à l'extérieur, recommencer avec d/2. On finira forcement par tomber sur un point à l'intérieur du poly. Encore faut-il prendre en compte des cas particuliers du genre deux segments superposés, ou des segments qui se coupent. :aie: Ca ne me semble pas si évident que ça. Je ne vois rien de mieux là tout de suite... Mais il existe surement une solution plus élégante.

salut,

une solution : calculer l'aire signée du polygone (cf formule donnee dans http://local.wasp.uwa.edu.au/~pbourk...try/polyarea/).
Si l'aire est positive, le polygone est oriente dans le sens inverse des aiguilles d'une montre.

Citation:

---

Envoyé par fumidu

Et enfin, comment trouver un point dans un polygone à coup sûr ? Ben là, je ne vois pas trop de méthode directe. Tester deux points à une distance d de par et d'autre d'un segment du polygone. Si les deux sont à l'extérieur, recommencer avec d/2. On finira forcement par tomber sur un point à l'intérieur du poly. Encore faut-il prendre en compte des cas particuliers du genre deux segments superposés, ou des segments qui se coupent. :aie: Ca ne me semble pas si évident que ça. Je ne vois rien de mieux là tout de suite... Mais il existe surement une solution plus élégante.

---

Trouver le point le plus bas à droite (par exemple) : P0.

P1 et P2 les 2 sommets adjacents. d1 et d2 les 2 distances P0P1 et P0P2. Alpha angle P1P0P2.

Prendre le point situé à alpha/2, (d1+d2)/2 ;) (ou d2/2)

Salut.
Soient i, j et k les vecteurs unités sur les axes Ox, Oy, Oz d'un repère cartésien direct, Oxy étant le plan de ta figure. Tu définis un champ vectoriel V=x*j. Son rotationnel est partout égal à 1*k, puis tu appliques le théorème d'Ampère-Stokes.
Bonne chance!
Jean-Marc Blanc

<HS> Je propose d'organiser un concours sur les methodes permettant de determiner l'orientation d'un polygone :mrgreen: </HS>

Citation:

---

Envoyé par souviron34

Trouver le point le plus bas à droite (par exemple) : P0.

P1 et P2 les 2 sommets adjacents. d1 et d2 les 2 distances P0P1 et P0P2. Alpha angle P1P0P2.

Prendre le point situé à alpha/2, (d1+d2)/2 (ou d2/2)

---

Si j'ai bien compris ton idée, j'ai un contre exemple en pièce jointe :
Pièce jointe 17335

Citation:

---

Envoyé par Kangourou

une solution : calculer l'aire signée du polygone (cf formule donnee dans http://local.wasp.uwa.edu.au/~pbourk...try/polyarea/).
Si l'aire est positive, le polygone est oriente dans le sens inverse des aiguilles d'une montre.

---

+1

Citation:

---

Envoyé par fumidu

Si j'ai bien compris ton idée, j'ai un contre exemple en pièce jointe :

---

ok, mais si tu veux à ce compte-là tu prend une distance égale à ta résolution... Forcément au max tu auras ton 4ième sommet...

Citation:

---

Envoyé par pseudocode

<HS> Je propose d'organiser un concours sur les methodes permettant de determiner l'orientation d'un polygone :mrgreen: </HS>

---

Sachant que les deux seules méthodes correctes qui ont été données (Amper-Strokes et calcul de l'aire signée) sont en fait une seule et même méthode, calculant la même valeure, le concours n'est pas très intéressant :P

pseudocode tu vas dire que j'y tiens ;) mais ya encore et toujours l'algo du "gift-wrapping" :P (enfin une dérivée de l'idée)

L'algo répondant à la question initiale du PO :

• ranger toutes les adresses (indices) des points en angle croissant par rapport à 1 des points extrêmes (le plus bas à droite)
  
  
• explorer.
  
  
  • Dès que les indices ne se suivent pas (à part le passage par zéro) : polygone complexe.
  • Si les indices croissent : sens contraire des aiguilles d'une montre
  • Si les indices décroissent : sens des aiguilles d'une montre..
  
  

:P