Ayant une liste de points, comment puis-je savoir s'ils sont dans le sens des aiguilles d'une montre ?
Par exemple :
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)dirait qu'elle est dans le sens inverse des aiguilles d'une montre (ou dans le sens inverse des aiguilles d'une montre, pour certaines personnes).
Certaines des méthodes proposées échoueront dans le cas d'un polygone non convexe, tel qu'un croissant. En voici une simple qui fonctionnera avec les polygones non convexes (elle fonctionnera même avec un polygone à intersection automatique comme un huit, en vous indiquant si c'est principalement dans le sens des aiguilles d'une montre).
Somme sur les bords, (x 2 x 1 )(y 2 + y 1 ). Si le résultat est positif, la courbe est dans le sens des aiguilles d'une montre, s'il est négatif, la courbe est dans le sens inverse des aiguilles d'une montre. (Le résultat est le double de l'aire délimitée, avec une convention +/-).
point[0] = (5,0) edge[0]: (6-5)(4+0) = 4
point[1] = (6,4) edge[1]: (4-6)(5+4) = -18
point[2] = (4,5) edge[2]: (1-4)(5+5) = -30
point[3] = (1,5) edge[3]: (1-1)(0+5) = 0
point[4] = (1,0) edge[4]: (5-1)(0+0) = 0
---
-44 counter-clockwise
C'est du calcul appliqué à un cas simple. (Je n'ai pas la compétence pour afficher des graphiques.) L'aire sous un segment de ligne est égale à sa hauteur moyenne (y2+y1)/2 fois sa longueur horizontale (x2-x1). Remarquez la convention de signe en x. Essayez ceci avec quelques triangles et vous verrez bientôt comment cela fonctionne.
Je suggérerais de le prouver d'abord pour un triangle, puis de montrer que n'importe quel polygone peut être divisé en triangles d'une manière qui ne change pas son caractère "horloger".
Trouvez le sommet ayant le plus petit y (et le plus grand x en cas d'égalité). Soit le sommet A et le sommet précédent dans la liste est B et le sommet suivant dans la liste est C . Calculez maintenant le signe du produit croisé de AB et AC .
Références :
Comment trouver l'orientation d'un polygone simple ? sur Questions fréquemment posées : comp.graphics.algorithms .
Orientation des courbes à Wikipedia.
Ceci est également expliqué dans fr.wikipedia.org/wiki/Curve_orientation . Le fait est que le point trouvé doit se trouver sur la coque convexe, et qu'il suffit de regarder localement un seul point de la coque convexe (et ses voisins immédiats) pour déterminer l'orientation de l'ensemble du polygone.
Je suis choqué et étonné que cela n'ait pas reçu plus de votes positifs. Pour les polygones simples ( qui est la plupart des polygones dans certains domaines ), cette réponse donne un O(1) solution. Toutes les autres réponses donnent O(n) des solutions pour n le nombre de points du polygone. Pour des optimisations encore plus poussées, voir le Considérations pratiques sous-section de la fantastique Wikipedia Orientation des courbes article.
Clarification : cette solution est O(1) seulement si soit (A) ce polygone est convexe (auquel cas tout sommet arbitraire réside sur la coque convexe et suffit donc) ou (B) vous connaissez déjà le sommet avec la plus petite coordonnée Y. Si c'est pas le cas (c'est-à-dire que ce polygone est non convexe et que vous n'en savez rien), un O(n) une recherche est nécessaire. Cependant, comme aucune sommation n'est nécessaire, cette solution est encore beaucoup plus rapide que toute autre solution pour les polygones simples.
Je vais vous proposer une autre solution, car elle est simple et ne nécessite pas de connaissances mathématiques poussées - elle fait simplement appel à l'algèbre de base. Calculez l'aire signée du polygone. Si elle est négative, les points sont placés dans le sens des aiguilles d'une montre, si elle est positive, ils sont placés dans le sens inverse des aiguilles d'une montre. (Cette solution est très similaire à celle de Beta).
Calculez la surface signée : A = 1/2 * (x 1 *y 2 - x 2 *y 1 + x 2 *y 3 - x 3 *y 2 + ... + x n *y 1 - x 1 *y n )
Ou en pseudo-code :
signedArea = 0
for each point in points:
x1 = point[0]
y1 = point[1]
if point is last point
x2 = firstPoint[0]
y2 = firstPoint[1]
else
x2 = nextPoint[0]
y2 = nextPoint[1]
end if
signedArea += (x1 * y2 - x2 * y1)
end for
return signedArea / 2Notez que si vous ne vérifiez que l'ordre, il n'est pas nécessaire de diviser par 2.
Est-ce une faute de frappe dans la formule de la zone signée ci-dessus ? Elle se termine par "xn*y1 - x1*yn" ; alors que je pense qu'elle devrait être "x_n y_{n+1} - y_n x_{n-1}" (en LaTeX, du moins). D'un autre côté, cela fait dix ans que je n'ai pas suivi de cours d'algèbre linéaire.
Non. Si vous vérifiez le source vous verrez que la formule fait de nouveau référence au premier point dans le dernier terme (y1 et x1). (Désolé, je ne suis pas très familier avec LaTeX, mais j'ai formaté les indices pour les rendre plus lisibles).
J'ai utilisé cette solution et elle a parfaitement fonctionné pour mon usage. Notez que si vous pouvez planifier à l'avance et disposer de deux vecteurs supplémentaires dans votre tableau, vous pouvez vous débarrasser de la comparaison (ou du %) en ajoutant le premier vecteur à la fin du tableau. De cette façon, il suffit de boucler sur tous les éléments, sauf le dernier (longueur 2 au lieu de longueur 1).
Le site produit croisé mesure le degré de perpendicularité de deux vecteurs. Imaginez que chaque arête de votre polygone est un vecteur dans le plan x-y d'un espace tridimensionnel (3-D) xyz. Alors le produit croisé de deux arêtes successives est un vecteur dans la direction z, (direction z positive si le second segment est dans le sens des aiguilles d'une montre, direction z négative s'il est dans le sens inverse des aiguilles d'une montre). La magnitude de ce vecteur est proportionnelle au sinus de l'angle entre les deux bords originaux, il atteint donc un maximum lorsqu'ils sont perpendiculaires, et s'amenuise pour disparaître lorsque les bords sont colinéaires (parallèles).
Ainsi, pour chaque sommet (point) du polygone, calculez la grandeur du produit en croix des deux arêtes adjacentes :
Using your data:
point[0] = (5, 0)
point[1] = (6, 4)
point[2] = (4, 5)
point[3] = (1, 5)
point[4] = (1, 0)Étiquette donc les bords consécutivement commeedgeA est le segment de point0 à point1 etedgeB entre point1 à point2
...edgeE est entre point4 et point0 .
Alors le sommet A ( point0 ) se situe entreedgeE [De point4 à point0 ]edgeA [De point0 jusqu'au "point 1".
Ces deux bords sont eux-mêmes des vecteurs, dont les coordonnées x et y peuvent être déterminées en soustrayant les coordonnées de leurs points de départ et d'arrivée :
edgeE = point0 - point4 = (1, 0) - (5, 0) = (-4, 0) etedgeA = point1 - point0 = (6, 4) - (1, 0) = (5, 4) et
Et le produit en croix de ces deux arêtes adjacentes est calculé à l'aide du déterminant de la matrice suivante, qui est construite en plaçant les coordonnées des deux vecteurs sous les symboles représentant les trois axes de coordonnées ( i , j , & k ). La troisième coordonnée (zéro) est présente parce que le concept de produit en croix est une construction 3D, et nous étendons donc ces vecteurs 2D en 3D afin d'appliquer le produit en croix :
i j k
-4 0 0
1 4 0 Étant donné que tous les produits croisés produisent un vecteur perpendiculaire au plan des deux vecteurs multipliés, le déterminant de la matrice ci-dessus n'a qu'une valeur de k (ou axe z).
La formule pour calculer l'ampleur de la k ou la composante de l'axe z esta1*b2 - a2*b1 = -4* 4 - 0* 1 = -16
L'ampleur de cette valeur ( -16 ), est une mesure du sinus de l'angle entre les 2 vecteurs originaux, multiplié par le produit des magnitudes des 2 vecteurs.
En fait, une autre formule pour sa valeur estA X B (Cross Product) = |A| * |B| * sin(AB) .
Donc, pour revenir à une simple mesure de l'angle, vous devez diviser cette valeur, ( -16 ), par le produit des amplitudes des deux vecteurs.
|A| * |B| = 4 * Sqrt(17) = 16.4924...
Donc la mesure de sin(AB) = -16 / 16.4924 = -.97014...
Il s'agit de savoir si le segment suivant le sommet s'est courbé vers la gauche ou la droite, et de combien. Il n'est pas nécessaire de prendre l'arc-sinus. Tout ce qui nous intéresse, c'est sa magnitude, et bien sûr son signe (positif ou négatif) !
Faites de même pour chacun des 4 autres points autour du chemin fermé, et additionnez les valeurs de ce calcul à chaque sommet
Si la somme finale est positive, vous êtes allé dans le sens des aiguilles d'une montre, négative, dans le sens inverse des aiguilles d'une montre.
En fait, cette solution est une solution différente de la solution acceptée. J'étudie actuellement la question de savoir si elles sont équivalentes ou non, mais je soupçonne qu'elles ne le sont pas... La réponse acceptée calcule l'aire du polygone, en prenant la différence entre l'aire sous le bord supérieur du polygone et l'aire sous le bord inférieur du polygone. L'une sera négative (celle où vous vous déplacez de gauche à droite), et l'autre sera négative. Dans le sens des aiguilles d'une montre, le bord supérieur est traversé de gauche à droite et est plus grand, le total est donc positif.
Ma solution mesure la somme des sinus des changements d'angles des bords à chaque sommet. Cette somme sera positive en cas de déplacement dans le sens des aiguilles d'une montre et négative en cas de déplacement dans le sens inverse.
Il semble qu'avec cette approche, vous devez VRAIMENT prendre l'arcsin, sauf si vous supposez la convexité (auquel cas vous ne devez vérifier qu'un seul sommet).
Commencez par l'un des sommets, et calculez l'angle sous-tendu par chaque côté.
Le premier et le dernier seront nuls (il faut donc les ignorer) ; pour les autres, le sinus de l'angle sera donné par le produit croisé des normalisations à l'unité de longueur de (point[n]-point[0]) et (point[n-1]-point[0]).
Si la somme des valeurs est positive, alors votre polygone est dessiné dans le sens inverse des aiguilles d'une montre.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
22 votes
VEUILLEZ NOTER : la réponse acceptée, et de nombreuses réponses après celle-ci, nécessitent beaucoup d'additions et de multiplications (elles sont basées sur des calculs d'aire qui se terminent par des valeurs négatives ou positives ; par exemple, la " formule du lacet "). Avant de mettre en œuvre l'une de ces réponses, pensez à La réponse de lhf qui est le plus simple/rapide - sur la base des éléments suivants wiki - orientation d'un polygone simple .
3 votes
J'y pense toujours en termes de produit croisé de deux vecteurs adjacents. Si je marche autour du périmètre du polygone, ma tête pointe hors du plan. Je croise le vecteur hors du plan avec mon vecteur de direction de la marche pour obtenir la troisième direction dans mon système de coordonnées. Si ce vecteur pointe de manière à ce que l'intérieur soit à ma gauche, c'est le sens inverse des aiguilles d'une montre ; si l'intérieur est à ma droite, c'est le sens des aiguilles d'une montre.