Comment faire pour déterminer si une liste de polygones points sont dans le sens horaire?

Avoir une liste de points, comment savoir si ils sont dans le sens horaire?

Par exemple:

point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)

dirais qu'il est anti-horaire (ou l'inverse, pour certaines personnes).

VEUILLEZ NOTER: La accepté de répondre, et beaucoup de réponses après elle, ont besoin de beaucoup d'additions et de multiplications (ils sont basés sur des calculs de la zone cette fin, positif ou négatif; par exemple, "lacet formule"). Avant de mettre en œuvre l'un de ces, envisagez de de lhf réponse, ce qui est plus simple/rapide basé sur wiki - orientation de la simple polygone.
Je pense toujours en termes de produit vectoriel de deux vecteurs adjacents. Si je marche autour du périmètre du polygone ma tête les points de sortie de l'avion. Je traverse le plan de vecteur dans ma marche vecteur de direction pour obtenir la troisième direction dans mon système de coordonnées. Si ce vecteur de points, de sorte que l'intérieur est sur ma gauche c'est dans le sens antihoraire; si l'intérieur est à ma droite, c'est dans le sens horaire.

InformationsquelleAutor Stécy | 2009-07-22

398

Certaines des méthodes proposées échoue dans le cas d'un non-polygone convexe, comme un croissant. Voici un exemple simple qui va travailler avec des non-polygones convexes (il va même travailler avec une auto-intersection polygone comme une figure-huit, en vous disant que c'est surtout dans le sens horaire).

Somme sur les bords, (x₂ − x₁)(o₂ + y₁). Si le résultat est positif, la courbe est dans le sens horaire, si il est négatif, la courbe est dans le sens antihoraire. (Le résultat est le double de la zone fermée, avec un +/- de la 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
```
- Grand. Mais quelqu'un peut-il expliquer pourquoi cela fonctionne?
- C'est le calcul appliqué à un cas simple. (Je n'ai pas les compétences pour poster des graphiques.) La zone sous un segment de ligne est égale à sa hauteur moyenne (y2+y1)/2 fois sa longueur horizontale (x2-x1). Avis de la convention de signe en x. Essayez cela avec certains des triangles et vous allez bientôt voir comment il fonctionne.
- Comment puis-je essayer une preuve?
- Je vous suggère de le prouver d'abord pour un triangle, puis en montrant que tout polygone peut être divisé en triangles dans un sens qui ne change pas sa "clockwiseness".
- Est-il un nom particulier à cette méthode?
- Maintenant que j'y pense, la méthode de calcul de la superficie à l'aide des aiguilles d'une montre la courbe peut être dérivée de Vert du Théorème. J'ai vu la méthode (sans dérivation) ans, j'ai peut-être venir avec l'idée de l'utiliser comme un clockwiseness de me tester, mais il est assez évident de sauter.
- Est-il une semblable solution élégante pour les polygones dans l'espace 3D?
- Trouvé ici: stackoverflow.com/questions/12642256/...
- Il a également généralise bien pour les 3-D polytopes: pour chaque face de calculer la signature de la zone dans le plan x-y comme décrit dans cette réponse, il faut multiplier par la valeur moyenne de z, et la somme de toutes les faces. La valeur absolue du résultat sera le polytope du volume.
- Un mineur en garde: cette réponse suppose un normal système de coordonnées Cartésiennes. La raison qui en vaut la peine de mentionner est que certains commun contextes, comme le HTML5 canvas, l'utilisation d'inverser l'axe Y de la. Ensuite, la règle doit être retournée: si la zone est négative, la courbe est dans le sens horaire.
- Cette méthode est faux! J'ai mis en place il annonce est dans 98% des cas. Mais pas toujours. Ce qui a fonctionné pour moi (dans tous les cas) est ce lien.
- Merci de nous donner le plus simple contre-exemple que vous connaissez.
- J'ai vérifié mon application pour vous montrer que c'est bien fait et pour vous donner le contre-exemple. Puis j'ai vu votre commentaire "je vous suggère de le prouver pour un triangle" donc je l'ai essayé et ça marche!!! Quand j'ai 3 points (2 bords de mon grand polygone) j'ai besoin de calculer les 3 bords pour bien s'entraîner (ab, bc, ca - imaginaire bord). Mais quand je l'ai essayer seulement pour 2 "réel" des bords (qui appartient vraiment à mon polygone) le résultat est parfois mauvais (il est difficile de donner l'exemple - je calculer les objets 3d et je peux voir le mauvais arc rapidement sur le modèle modifié - parfois à l'arc est fait dans la mauvaise direction).
- Donc ma méthode fonctionne, mais si vous passer une partie vitale, alors il ne fonctionne pas. Ce n'est pas nouvelles.
- Vous avez toujours de lien le dernier point de la première. Si vous avez des N points numérotés de 0 à N-1, alors vous devez calculer: Sum( (x[(i+1) mod N] - x[i]) * (y[i] + y[(i+1) mod N]) ) pour i = 0 à N-1. I. e., doit prendre l'indice Modulo N (N ≡ 0) La formule ne fonctionne que pour les fermé polygones. Les polygones ont pas imaginaire bords.
- Peut être le résultat de zéro? Et s'il le peut, ce que l'orientation est-elle? (Il ressemble à certains cessent).
- Si le résultat est zéro, cela signifie que le positif et le négatif zones annuler, comme dans une figure-huit.
- Btw, Il semble que vous avez seulement besoin de calculer la somme de xi + 1*yi - xi*yi + 1 pour déterminer la réponse.
- Vrai, mais remarquez que ma formule n'a qu'une multiplication, tandis que la vôtre en a deux.
- Je suis en train d'essayer cela avec une des aiguilles d'une montre en diamant, et l'obtention d'un négatif (sens antihoraire) la somme de résultat, et à somme positive pour des aiguilles d'une montre. DES AIGUILLES D'UNE MONTRE EN DIAMANT: point[0] = 0,5 (5-0)(0+5) = 25, point[1] = 5,0 (10-5)(5+0) = 25, point[2] = 10,5 (5-10)(5+10) = -75, point[3] = 5,10 (0-5)(10+5) = -75 == -100. COMPTOIR du DIAMANT: point[0] = 0,5 (5-0)(5+10) = 75, point[1] = 5,10 (10-5)(10+5) = 75, point[2] = 10,5 (5-10)(5+0) = -25, point[3] = 5,0 (0-5)(5+0) = -25 == +100 Est-ce un cas particulier?
- Vous utilisez les mots "sens horaire" et "anti-horaire" dans le sens inverse de tout le monde.
- juste pour que je ne suis pas fou, tout le monde en utilisant des aiguilles d'une montre en tant que contre-affichage du cadran? Voici un lien vers mon schéma avec les calculs. s3-us-west-2.amazonaws.com/mattfiocca/polydirection.png.
- La convention en mathématiques, c'est que la coordonnée Y augmente de bas en haut; votre Y de coordonnées hausse qu'à la baisse.
- ah merci! Je savais qu'il me manquait quelque chose de vital, venus de l'arrière monde du web et des applications.
- Cela ne fonctionne qu'avec tous positifs coordonnées. J'ai essayé avec des Polygones dans X,-Z Avion (Z les valeurs sont négatives dans ce cas.). Seul moyen que j'ai pu obtenir cette logique à l'œuvre dans ce cas est de traduire les polygones à X+Z avion. j'.e, en compensant les valeurs Z de tous les coordonne avec une constante telle que toutes les valeurs sont positives. S'il vous plaît corrigez-moi si me trompe ou si il existe une solution plus simple.
- Vous vous trompez, mais un fil de commentaires n'est pas le lieu pour en discuter. Si j'ai le temps je vais faire une salle de chat.
- Cette blog.element84.com/polygon-winding.html, explique dans un anglais simple pourquoi cette solution fonctionne.
- Alternativement, il peut être calculé comme la somme des (point.x + nextPoint.x) * (point.y - nextPoint.y).
- Serait-ce de travailler pour les coordonnées de latitude/longitude en supposant que vous n'êtes pas à proximité/la traversée d'un pôle, et tous les polygones de la croix-180 sont définis avec des nombres de plus de 180?
- le lien donné par vous est cassé, archive: web.archive.org/web/20171212175910/blog.element84.com/...
- Ah, avec une approche astucieuse qui annule l'extra XnYn cours de la somme, c'est un produit croisé. Sweet!
InformationsquelleAutor Beta
49

La la croix du produit mesure le degré de la perpendiculaire-ness de deux vecteurs. Imaginez que chaque bord de votre polygone est un vecteur dans le plan x-y de un à trois dimensions (3-D) de l'espace xyz. Alors le produit vectoriel de deux successives bords est un vecteur dans la direction z, (z positif la direction, si le second segment est dans le sens horaire, moins z-direction, si c'est dans le sens antihoraire). L'ampleur de ce vecteur est proportionnelle au sinus de l'angle entre les deux bords, de sorte qu'il atteint un maximum quand ils sont perpendiculaires, et s'estompe pour disparaître lorsque les bords sont colinéaires (parallèle).

Donc, pour chaque vertex (point) du polygone, calculer la croix-produit de l'ampleur des deux bords contigus:
```
Using your data:
point[0] = (5, 0)
point[1] = (6, 4)
point[2] = (4, 5)
point[3] = (1, 5)
point[4] = (1, 0)
```
Donc étiqueter les bords de façon consécutive comme

edgeA est le segment de point0 à point1 et

edgeB entre point1 à point2

...

edgeE est entre point4 et point0.

Alors le Sommet A (point0) est entre

edgeE [De point4 à point0]

edgeA [De point0 à "point1'

Ces deux bords sont eux-mêmes des vecteurs, dont les coordonnées x et y peut être déterminé en soustrayant les coordonnées de leurs points de début et fin:

edgeE = point0 - point4 = (1, 0) - (5, 0) = (-4, 0)

edgeA = point1 - point0 = (6, 4) - (1, 0) = (5, 4) et

Et le produit vectoriel de ces deux bords contigus est calculé en utilisant le déterminant de la matrice suivante, qui est construit en mettant les coordonnées des deux vecteurs ci-dessous les symboles représentant les trois axes des coordonnées (i, j, & k). La troisième (zéro)-valeur de coordonnées est là parce que la croix concept de produit est un 3-D de construire, et donc, nous prolongeons ces 2-D vecteurs en 3-D afin d'appliquer le produit croisé:
```
 i    j    k 
-4    0    0
 1    4    0    
```
Étant donné que tous les produits de produire un vecteur perpendiculaire au plan des deux vecteurs étant multipliés, le déterminant de la matrice ci-dessus n'a qu'une k, (ou de l'axe z) du composant.

La formule pour le calcul de l'ampleur de la k ou composant axe z est

a1*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 d'origine, multiplié par le produit de la grandeur de l'2 vecteurs.

En fait, une autre formule pour sa valeur est

A X B (Cross Product) = |A| * |B| * sin(AB).

Donc, pour en revenir à seulement une mesure de l'angle que vous avez besoin de diviser cette valeur, (-16), par le produit des grandeurs de ces deux vecteurs.

|A| * |B| = 4 * Sqrt(17) = 16.4924...

De sorte que la mesure de sin(AB) = -16 /16.4924 = -.97014...

C'est une mesure de savoir si le segment suivant après le sommet est courbé vers la gauche ou la droite, et de combien. Il n'y a pas besoin de prendre de l'arc-sinus. Tout ce que nous ne se soucient est son ampleur, et bien sûr, son signe (positif ou négatif)!

Le faire pour chacun des 4 autres points autour de la trajectoire fermée, et additionner les valeurs de ce calcul à chaque sommet..

Si la somme finale est positive, vous êtes allé dans le sens horaire, négatif, dans le sens antihoraire.
- En fait, cette solution est une solution différente de la solution retenue. Si elles sont équivalentes ou non est une question que j'étudie, mais je soupçonne qu'ils ne sont pas... La accepté de répondre à calculer l'aire du polygone, en prenant la différence entre la zone sous le bord supérieur du polygone et de la zone sous le bord inférieur du polygone. L'un sera négatif (celui où vous êtes à la traversée de la gauche vers la droite), et l'autre est négative. Lors de la traversée des aiguilles d'une montre, Le bord supérieur est parcouru de gauche à droite et est plus grande, de sorte que le total est positif.
- Ma solution mesures de la somme de sines des changements dans le bord des angles à chaque sommet. Ce sera positif lors de la traversée des aiguilles d'une montre et négatifs lors de la traversée dans le sens antihoraire.
- Il semble avec cette approche, vous devez prendre le arcsin, à moins que vous assumez la convexité (dans ce cas, vous avez seulement besoin de vérifier un sommet)
- Non, vous n'avez pas besoin de prendre de l'arcsinus. Vous avez besoin de diviser par les amplitudes des deux vecteur, pour éliminer mise à l'échelle, (d'où une très grande paire od segments qui se plie d'une manière un petit angle contribue plus tot la somme que de nombreux segments de plus petite taille que plier l'autre sens par un plus grand angle. Mais l'arcsinus juste convertit une mesure d'un angle à l'autre.
- Pourquoi tout le coûteux fonctions mathématiques? Ne serait-il pas plus rapide de seulement calculer le z-partie d'une 3D de la croix-produit en faisant a1 * b2 - a2 * b1 (x - et y-pièces à zéro de toute façon) et en vérifiant le signe du résultat? Pas de fonctions trigonométriques sont nécessaires et ne sqrt.
- Cela ne fonctionne que si tous les vecteurs sont du même ordre de grandeur (ou, de manière équivalente, ont d'abord été normalisée). Si elles sont de longueurs différentes, alors vous obtiendrez une réponse incorrecte., parce que la droite, l'angle entre deux segments du polygone contribuent beaucoup plus à la somme globale que des aiguilles d'une montre de l'angle entre deux très petits segments.
- Mais ne devrait-elle pas être assez à "additionner" les signes de la croix de produits?
- Non, tout ce qui serait de "compter" le nombre de tours pour le droit moins le nombre de virages à gauche. Si vous commencez pointant vers l'Est, et de prendre quatre-vingt-dix d'un degré, se tourne vers la droite, (un total de 90 degrés à droite), chaque pouce de long, vous serez dirigée vers le sud, puis prendre cinq virages à 90 degrés vers la gauche, vous allez être orienté vers l'est à nouveau, et avec le réglage de la longueur de chaque segment, (faire de la lefts plus) se reconnecter au point de départ. L'ensemble de la courbe fermée est clairement dans le sens antihoraire, mais juste de compter les signes comte de 90 à droite et 5 à gauche.
- J'ai reformulé votre réponse (pour le rendre plus précis mathématiquement) jusqu'à ce que votre phrase "L'ampleur de cette valeur est une mesure du sinus de l'angle entre les 2 vecteurs d'origine". Vous devez modifier cette phrase et les autres pour prendre en compte mes modifications. La raison pour laquelle je n'ai pas modifier cette phrase et le reste, c'est que je ne suis pas pleinement comprendre ce que tu veux dire ceux qui.
- Vous devez prendre le arcsin. Essayez-la sur une collection de non-polygones convexes, et vous trouverez le test échoue pour certains polygones si vous ne prenez pas le arcsin.
- Non, Vous ne le font pas. Quel que soit le test, vous êtes en cours d'exécution, vous êtes l'exécution de ce mal. La valeur avant de prendre la arcsinus EST le péché de l'original de l'angle de rotation, la conversion à partir d'une valeur comprise entre -1 et +1 pour un angle entre-Pi et +Pi ne fait rien pour changer la réponse. Et aussi longtemps que vous le divisez par le produit des grandeurs de ces deux vecteurs, les amplitudes seront normalisés, et leur somme indiquer l'orientation générale de la courbure.
- alors que je n'ai pas couru de Luc test, je crois qu'il est correct. C'est la nature de résumant combinés avec un non linéaire échelle [sans arcsin vs avec arcsin]. Considérez ce que marsbear suggéré, que vous avez correctement rejeté. Il a suggéré que vous "compter", et vous l'avez souligné qu'une poignée de grandes valeurs pourrait l'emporter sur un grand nombre de petites valeurs. Considérons maintenant arcsin de chaque valeur vs pas. N'est-ce pas toujours le cas que de ne pas prendre des arcsin donne incorrect poids de chaque valeur, a donc le même défaut (mais beaucoup moins)?
InformationsquelleAutor Charles Bretana
44

Je suppose que c'est une très vieille question, mais je vais jeter une autre solution de toute façon, parce que c'est simple et pas mathématiquement intensif - il utilise juste de base de l'algèbre. Calculer la signature de l'aire du polygone. Si il est négatif, les points sont dans le sens horaire, si elle est positive, ils sont dans le sens antihoraire. (Ceci est très similaire à la Bêta de la solution).

Calculer la signature de la zone:
A = 1/2 * (x₁*y₂ - x₂*y₁ + x₂*y₃ - x₃*y₂ + ... + x_n*y₁ - x₁*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 /2
```
Noter que si vous êtes la seule vérification de la commande, vous n'avez pas besoin de s'embêter en le divisant par 2.

Sources: http://mathworld.wolfram.com/PolygonArea.html
- Était-ce une faute de frappe dans votre signée de la zone de la formule ci-dessus? Il se termine par "xn*y1 - x1*yn"; quand je pense qu'elle doit être "x_n y_{n+1} - y_n x_{n-1}" (en LaTeX, au moins). D'autre part, il est depuis une dizaine d'années, j'ai pris toute algèbre linéaire classes.
- Nope. Si vous consultez le source, vous verrez que la formule ne fait en fait référence au premier point dans le dernier terme de (y1 et x1). (Désolé, je ne suis pas très familier avec le LaTeX, mais j'ai formaté les indices pour les rendre plus lisibles.)
- J'ai utilisé cette solution, et cela a fonctionné parfaitement pour mon utilisation. Notez que si vous pouvez planifier à l'avance et de pièces de rechange et les deux vecteurs dans votre tableau, vous pouvez vous débarrasser de la comparaison (ou %), en ajoutant le premier vecteur à la queue de la matrice. De cette façon, il vous suffit de boucler sur tous les éléments, sauf le dernier (longueur-2 au lieu de la longueur-1).
- FWIW, plutôt que de les redimensionner, éventuellement, un grand tableau, une alternative efficace pour chaque itération pour sauver son point de previousPoint pour la prochaine itération. Avant de commencer la boucle, un jeu de previousPoint à la matrice du dernier point. Compromis est variable locale supplémentaires copie, mais de moins en moins accès à des tableaux. Et surtout, ne touchez pas à l'entrée de tableau.
- il est nécessaire de fermer le polygone, en incluant le segment de ligne à partir du dernier point au premier point. (Un bon calcul sera le même, peu importe à quel point commence le polygone fermé.)
- Bon point. Sauf si vous savez de la taille à l'avance et peuvent créer le tableau avec un élément supplémentaire, votre solution est rapide et empêche le redimensionnement.
InformationsquelleAutor Sean the Bean
32

Trouver le sommet avec le plus petit y (et les plus grands de x s'il existe des liens). Laissez le vertex être A et le précédent sommet de la liste B et le sommet suivant dans la liste C. Maintenant calculer la signe de la croix de produits de AB et AC.

Références:
- Comment puis-je trouver de l'orientation d'un simple polygone? dans
  Foire aux Questions: comp.les graphiques.les algorithmes de.
- La courbe de l'orientation sur Wikipédia.
- C'est aussi expliqué dans en.wikipedia.org/wiki/Curve_orientation. Le point est que le trouve le point doit être sur l'enveloppe convexe, et il est seulement nécessaire de rechercher localement en un point unique sur l'enveloppe convexe (et de ses voisins immédiats) pour déterminer l'orientation de l'ensemble de polygones.
- Choqué et impressionné, il n'a pas reçu plus upvotes. Pour de simples polygones (qui est plus de polygones dans certains champs), cette réponse donne une O(1) solution. Toutes les autres réponses rendement O(n) solutions pour n le nombre de polygone points. Pour encore plus profond des optimisations, voir la Considérations Pratiques paragraphe de Wikipedia est fantastique Courbe d'orientation l'article.
- Précision: cette solution est O(1) seulement si A ce polygone est convexe (dans ce cas, n'importe quel sommet se trouve sur l'enveloppe convexe, et donc suffit) ou B vous savez déjà le sommet avec la plus petite coordonnée Y de la. Si c'est pas dans le cas (c'est à dire, ce polygone est non-convexe et vous ne savez rien à ce sujet), un O(n) de recherche est nécessaire. Depuis pas de sommation est nécessaire, cependant, c'est toujours beaucoup plus rapide que toute autre solution pour de simples polygones.
- Une mise en œuvre de cette réponse: code c# afin de trouver le coin de sommets et de calculer le déterminant de l'angle au sommet.
InformationsquelleAutor lhf

Ici est un simple C# de mise en œuvre de l'algorithme basé sur cette réponse.

Supposons que nous avons un Vector type ayant X et Y les propriétés de type double.

public bool IsClockwise(IList<Vector> vertices)
{
    double sum = 0.0;
    for (int i = 0; i < vertices.Count; i++) {
        Vector v1 = vertices[i];
        Vector v2 = vertices[(i + 1) % vertices.Count];
        sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    }
    return sum > 0.0;
}

% est le modulo ou de ce qui reste de l'opérateur effectuant le modulo qui (selon Wikipedia) trouve le reste après la division d'un nombre par un autre.

InformationsquelleAutor Olivier Jacot-Descombes

6

Commencer à l'un des sommets, et de calculer l'angle sous-tendu par chaque côté.

Le premier et le dernier sera égal à zéro (donc ignorer ces); pour le reste, le sinus de l'angle sera donné par le produit vectoriel des normalisations pour unité de longueur de (point de[n] point[0]) et (point[n-1] point[0]).

Si la somme des valeurs est positif, alors votre polygone est dessiné dans le sens anti-horaire sens.
- Voyant que la façon dont le produit vectoriel se résume essentiellement en un résultat positif à un facteur d'échelle fois le sinus de l'angle, il est probablement mieux de faire juste un produit croisé. Il sera plus rapide et moins compliqué.
InformationsquelleAutor Steve Gilham

Pour ce qu'il vaut, j'ai utilisé ce mixin pour calculer la dissolution de l'ordre pour l'API Google Maps v3 apps.

Le code de démultiplier les effets secondaires de polygone domaines: l'une dans le sens des aiguilles d'enroulement afin de sommets positive alors qu'une des aiguilles d'une montre à remontage afin de les mêmes sommets produit la même zone comme une valeur négative. Le code utilise aussi une sorte d'API privée dans le Google Maps de la géométrie de la bibliothèque. Je me sentais à l'aise de l'utiliser - utiliser à vos propres risques.

Exemple d'utilisation:

var myPolygon = new google.maps.Polygon({/*options*/});
var isCW = myPolygon.isPathClockwise();

Exemple complet avec les tests unitaires @ http://jsfiddle.net/stevejansen/bq2ec/

/** Mixin to extend the behavior of the Google Maps JS API Polygon type
*  to determine if a polygon path has clockwise of counter-clockwise winding order.
*  
*  Tested against v3.14 of the GMaps API.
*
*  @author  [email protected]
*
*  @license http://opensource.org/licenses/MIT
*
*  @version 1.0
*
*  @mixin
*  
*  @param {(number|Array|google.maps.MVCArray)} [path] - an optional polygon path; defaults to the first path of the polygon
*  @returns {boolean} true if the path is clockwise; false if the path is counter-clockwise
*/
(function() {
var category = 'google.maps.Polygon.isPathClockwise';
//check that the GMaps API was already loaded
if (null == google || null == google.maps || null == google.maps.Polygon) {
console.error(category, 'Google Maps API not found');
return;
}
if (typeof(google.maps.geometry.spherical.computeArea) !== 'function') {
console.error(category, 'Google Maps geometry library not found');
return;
}
if (typeof(google.maps.geometry.spherical.computeSignedArea) !== 'function') {
console.error(category, 'Google Maps geometry library private function computeSignedArea() is missing; this may break this mixin');
}
function isPathClockwise(path) {
var self = this,
isCounterClockwise;
if (null === path)
throw new Error('Path is optional, but cannot be null');
//default to the first path
if (arguments.length === 0)
path = self.getPath();
//support for passing an index number to a path
if (typeof(path) === 'number')
path = self.getPaths().getAt(path);
if (!path instanceof Array && !path instanceof google.maps.MVCArray)
throw new Error('Path must be an Array or MVCArray');
//negative polygon areas have counter-clockwise paths
isCounterClockwise = (google.maps.geometry.spherical.computeSignedArea(path) < 0);
return (!isCounterClockwise);
}
if (typeof(google.maps.Polygon.prototype.isPathClockwise) !== 'function') {
google.maps.Polygon.prototype.isPathClockwise = isPathClockwise;
}
})();

Essayé ce que je l'obtenir exactement le résultat inverse, un polygone dessiné dans le sens horaire, les rendements négatifs de la zone, tandis que celui établi dans le sens antihoraire rendements positifs. Dans les deux cas, ce morceau de code est toujours super utile 5 ans sur, je vous remercie.
La norme (voir l'IETF en particulier pour geoJson) est à suivre la "règle de droite'. Je suppose que Google se plaint avec. Dans ce cas, l'anneau externe doit être dans le sens antihoraire (positifs) et les bagues intérieures (trous) sont à remontage dans le sens horaire (zone négative pour être retiré de la zone principale).

InformationsquelleAutor Steve Jansen

De mise en œuvre de Sean répondre en JavaScript:

JS:

function calcArea(poly) {
if(!poly || poly.length < 3) return null;
let end = poly.length - 1;
let sum = poly[end][0]*poly[0][1] - poly[0][0]*poly[end][1];
for(let i=0; i<end; ++i) {
const n=i+1;
sum += poly[i][0]*poly[n][1] - poly[n][0]*poly[i][1];
}
return sum;
}
function isClockwise(poly) {
return calcArea(poly) > 0;
}
let poly = [[352,168],[305,208],[312,256],[366,287],[434,248],[416,186]];
console.log(isClockwise(poly));
let poly2 = [[618,186],[650,170],[701,179],[716,207],[708,247],[666,259],[637,246],[615,219]];
console.log(isClockwise(poly2));

Assez sûr de ce qui est juste. Il semble être au travail 🙂

Ces polygones ressembler à ceci, si vous vous demandez:

Comment faire pour déterminer si une liste de polygones points sont dans le sens horaire?

InformationsquelleAutor mpen

3

C'est la mise en œuvre de la fonction de OpenLayers 2. La condition pour avoir un polygone dans le sens des aiguilles est area < 0, il a confirmé par cette référence.
```
function IsClockwise(feature)
{
if(feature.geometry == null)
return -1;
var vertices = feature.geometry.getVertices();
var area = 0;
for (var i = 0; i < (vertices.length); i++) {
j = (i + 1) % vertices.length;
area += vertices[i].x * vertices[j].y;
area -= vertices[j].x * vertices[i].y;
//console.log(area);
}
return (area < 0);
}
```
- Openlayers est basé sur javascript la gestion de la carte de bibliothèque comme googlemaps et c'est écrit et utilisé dans openlayers 2.
- Pouvez-vous expliquer un peu ce que votre code ne, et pourquoi vous le faites?
- ce code met en œuvre la lhf réponse. Il est facile de garder le non OpenLayer part à une pure fonction javascript par avoir vertices directement comme paramètre. Il fonctionne bien, et pourrait être adaptée au cas de multiPolygon.
InformationsquelleAutor MSS
2

Si vous utilisez Matlab, la fonction ispolycw retourne true si le polygone de sommets sont dans le sens horaire.

InformationsquelleAutor Frederick
1

Comme il est expliqué dans cet article de Wikipédia La courbe de l'orientation, 3 points p, q et r sur le plan (c'est à dire avec des coordonnées x et y), vous pouvez calculer le signe de la suivante déterminant

Si le déterminant est négatif (c'est à dire Orient(p, q, r) < 0), alors le polygone est orientée dans le sens horaire (CW). Si le déterminant est positif (c'est à dire Orient(p, q, r) > 0), le polygone est orientée dans le sens antihoraire (CCW). Le déterminant est égal à zéro (c'est à dire Orient(p, q, r) == 0) si les points p, q et r sont colinéaires.

Dans la formule ci-dessus, on ajoute celles en face de l'coordonnées de p, q et r parce que nous sommes à l'aide de homogène coordonnées.
- Pouvez-vous expliquer pourquoi cette méthode ne fonctionne pas dans beaucoup de situations, si le polygone est concave?
- Veuillez consulter le tableau dans le wiki de l'élément de référence dans votre post. Il est facile pour moi de donner une fausse exemple, mais difficile à prouver.
- Veuillez consulter le tableau dans le wiki de l'élément de référence dans votre post. Il est facile pour moi de donner une fausse exemple, mais difficile à prouver.
- est correcte. Vous ne pouvez pas il suffit de prendre trois points du polygone, vous pourriez être en soit un convexe ou concave région de ce polygone. La lecture du wiki avec soin, on doit prendre les trois points le long de l'enveloppe convexe qui entoure le polygone. De "considérations pratiques": "On n'a pas besoin de construire l'enveloppe convexe d'un polygone à trouver un vertex. Un choix commun est le sommet du polygone avec la plus petite abscisse. Si il y en a plusieurs, celui avec la plus petite coordonnée Y est repris. Il est garanti pour être [un] sommet de l'enveloppe convexe du polygone."
- Donc lhf antérieure de la réponse, ce qui est comparable, et fait référence au même article de wiki, mais spécifie un point. [Apparemment, il n'a pas d'importance si l'on prend le plus petit ou le plus grand, x ou y, tant que l'on évite d'être dans le milieu; effectivement on travaille à partir d'un bord de la zone de sélection autour du polygone, à garantir dans un concave de la région.]
InformationsquelleAutor Ian
0

Je pense que pour certains points dans le sens des aiguilles toutes les arêtes doivent être positifs, non seulement la somme des bords. Si une arête est plus négative que d'au moins 3 points sont donnés dans le sens antihoraire.
- Vrai, mais vous ne comprenez pas le concept d'un polygone de l'enroulement de commande (dans le sens horaire ou anti-horaire). Dans un tout polygone convexe, l'angle à tous les points seront des aiguilles d'une montre ou tout sera dans le sens antihoraire [comme dans ta première phrase]. Dans un polygone concave région(s), les "grottes", sera dans la direction opposée, mais le polygone dans son ensemble a encore bien définie de l'intérieur, et il est considéré dans le sens horaire ou anti-horaire en conséquence. Voir en.wikipedia.org/wiki/...
InformationsquelleAutor daniel

Mon C# /LINQ solution est basée sur la croix, avis sur des produits de @charlesbretana est ci-dessous. Vous pouvez spécifier une référence normale pour le remontage. Il devrait fonctionner aussi longtemps que la courbe est la plupart du temps dans le plan défini par le vecteur up.

using System.Collections.Generic;
using System.Linq;
using System.Numerics;
namespace SolidworksAddinFramework.Geometry
{
public static class PlanePolygon
{
///<summary>
///Assumes that polygon is closed, ie first and last points are the same
///</summary>
public static bool Orientation
(this IEnumerable<Vector3> polygon, Vector3 up)
{
var sum = polygon
.Buffer(2, 1) //from Interactive Extensions Nuget Pkg
.Where(b => b.Count == 2)
.Aggregate
( Vector3.Zero
, (p, b) => p + Vector3.Cross(b[0], b[1])
/b[0].Length()/b[1].Length());
return Vector3.Dot(up, sum) > 0;
} 
}
}

avec un test unitaire

namespace SolidworksAddinFramework.Spec.Geometry
{
public class PlanePolygonSpec
{
[Fact]
public void OrientationShouldWork()
{
var points = Sequences.LinSpace(0, Math.PI*2, 100)
.Select(t => new Vector3((float) Math.Cos(t), (float) Math.Sin(t), 0))
.ToList();
points.Orientation(Vector3.UnitZ).Should().BeTrue();
points.Reverse();
points.Orientation(Vector3.UnitZ).Should().BeFalse();
} 
}
}

InformationsquelleAutor bradgonesurfing

C'est ma solution à l'aide des explications dans les autres réponses:

def segments(poly):
"""A sequence of (x,y) numeric coordinates pairs """
return zip(poly, poly[1:] + [poly[0]])
def check_clockwise(poly):
clockwise = False
if (sum(x0*y1 - x1*y0 for ((x0, y0), (x1, y1)) in segments(poly))) < 0:
clockwise = not clockwise
return clockwise
poly = [(2,2),(6,2),(6,6),(2,6)]
check_clockwise(poly)
False
poly = [(2, 6), (6, 6), (6, 2), (2, 2)]
check_clockwise(poly)
True

Pouvez-vous préciser quelles autres réponses exactement cette réponse est basée sur?

InformationsquelleAutor Gianni Spear

0

Beaucoup de calcul méthode plus simple, si vous connaissez déjà un point à l'intérieur du polygone:
1. Choisir n'importe quel segment de ligne à partir de l'original de polygones, points et leurs coordonnées dans l'ordre.
2. Ajouter un connu "à l'intérieur" point de, et de former un triangle.
3. Calculer CW ou CCW, comme l'a suggéré ici avec ces trois points.
- Peut-être cela fonctionne, si le polygone est entièrement convexe. Il n'est certainement pas fiable si il y a des concave régions, il est facile de choisir un point sur le "mauvais" côté de l'un des bords de la grotte, puis le connecter à ce bord. Obtenez de mauvaise réponse.
- Il fonctionne même si le polygone est concave. Le point doit être à l'intérieur qui polygone concave. Cependant, je ne suis pas sûr de polygone complexe (n'a pas de test.)
- "Il fonctionne même si le polygone est concave." - Contre-exemple: poly (0,0), (1,1), (0,2), (2,2), (2,0). Segment de ligne (1,1), (0, 2). Si vous choisissez un point intérieur à l'intérieur (1,1), (0,2), (1,2) pour former un triangle -> (1,1), (0,2), (0.5,1.5)), vous obtenez face sinueuses que si vous choisissez un point intérieur à l'intérieur (0,0), (1,1), (1,0) > (1,1), (0,2),(0.5,0.5). Ceux qui sont tant à l'intérieur qu'à l'origine polygone, pourtant, ont opposé des enroulements. Par conséquent, l'un d'eux donne la mauvaise réponse.
- En général, si un polygone a tout concave région, choisissez un segment dans le concave de la région. Parce qu'il est concave, vous pouvez trouver deux "de l'intérieur" les points qui sont sur les côtés opposés de la ligne. Parce qu'ils sont sur les côtés opposés de la ligne, les triangles formés ont opposé des enroulements. Fin de la preuve.
InformationsquelleAutor Venkata Goli
0

Après l'essai de plusieurs fiables implémentations de l'algorithme qui a fourni des résultats satisfaisants concernant la CW/CCW orientation de la boîte a été l'un, publié par les OP dans cette fil (shoelace_formula_3).

Comme toujours, un nombre positif représente un CW orientation, alors que d'un nombre négatif CCW.

InformationsquelleAutor Marjan Moderc

Voici swift 3.0 solution basée sur les réponses ci-dessus:

    for (i, point) in allPoints.enumerated() {
let nextPoint = i == allPoints.count - 1 ? allPoints[0] : allPoints[i+1]
signedArea += (point.x * nextPoint.y - nextPoint.x * point.y)
}
let clockwise  = signedArea < 0

InformationsquelleAutor Toby Evetts

Une autre solution pour cela;

const isClockwise = (vertices=[]) => {
const len = vertices.length;
const sum = vertices.map(({x, y}, index) => {
let nextIndex = index + 1;
if (nextIndex === len) nextIndex = 0;
return {
x1: x,
x2: vertices[nextIndex].x,
y1: x,
y2: vertices[nextIndex].x
}
}).map(({ x1, x2, y1, y2}) => ((x2 - x1) * (y1 + y2))).reduce((a, b) => a + b);
if (sum > -1) return true;
if (sum < 0) return false;
}

Prendre tous les sommets comme un tableau comme ceci;

const vertices = [{x: 5, y: 0}, {x: 6, y: 4}, {x: 4, y: 5}, {x: 1, y: 5}, {x: 1, y: 0}];
isClockwise(vertices);

InformationsquelleAutor Ind

Solution pour R pour déterminer la direction et l'inverse si des aiguilles d'une montre (jugé nécessaire pour owin objets):

coords <- cbind(x = c(5,6,4,1,1),y = c(0,4,5,5,0))
a <- numeric()
for (i in 1:dim(coords)[1]){
#print(i)
q <- i + 1
if (i == (dim(coords)[1])) q <- 1
out <- ((coords[q,1]) - (coords[i,1])) * ((coords[q,2]) + (coords[i,2]))
a[q] <- out
rm(q,out)
} #end i loop
rm(i)
a <- sum(a) #-ve is anti-clockwise
b <- cbind(x = rev(coords[,1]), y = rev(coords[,2]))
if (a>0) coords <- b #reverses coords if polygon not traced in anti-clockwise direction

InformationsquelleAutor dez

0

Bien que ces réponses sont correctes, ils sont plus mathématiquement complexes que nécessaire. Assumer les coordonnées de carte, où la plupart des nord-point est le point le plus haut sur la carte. Trouver plus de north point, et si les 2 points de la cravate, c'est le plus au nord, puis plus à l'est (c'est le point que lhf utilise dans sa réponse). Dans vos points,

point[0] = (5,0)

point[1] = (6,4)

point[2] = (4,5)

point[3] = (1,5)

point[4] = (1,0)

Si nous supposons que P2 est la plus au nord puis à l'est point le précédent ou suivant le point de déterminer, dans le sens horaire CW ou CCW. Depuis la plupart des nord-est sur la face nord, si P1 (précédent) pour P2 se déplace de l'est, la direction est à la CW. Dans ce cas, il se déplace à l'ouest, de sorte que la direction est à GAUCHE que l'on a accepté la réponse dit. Si le point précédent n'a pas de mouvement horizontal, puis le même système s'applique pour le point suivant, P3. Si P3 est à l'ouest de P2, il est, alors le mouvement est CCW. Si la P2 à P3 mouvement est à l'est, c'est-ouest dans ce cas, le mouvement est CW. Supposons que nte, P2 dans vos données, est la plus au nord puis à l'est point et le prv est le point précédent, P1 dans vos données, et nxt est le point suivant, le P3 de vos données, et [0] est à l'horizontale ou est/ouest, où l'ouest est inférieure à l'est, et [1] est à la verticale.
```
if (nte[0] >= prv[0] && nxt[0] >= nte[0]) return(CW);
if (nte[0] <= prv[0] && nxt[0] <= nte[0]) return(CCW);
//Okay, it's not easy-peasy, so now, do the math
if (nte[0] * nxt[1] - nte[1] * nxt[0] - prv[0] * (nxt[1] - crt[1]) + prv[1] * (nxt[0] - nte[0]) >= 0) return(CCW); //For quadrant 3 return(CW)
return(CW) //For quadrant 3 return (CCW)
```
- À mon humble avis, il serait mieux de s'en tenir aux fondamentaux de mathématiques indiqué dans le de lhf réponse - merci pour la mention de lui. Le défi en la réduisant à quadrants, c'est que ses une bonne quantité de travail à prouver que votre formule est correcte dans tous les cas. Avez-vous calculer correctement "plus à l'ouest"? Dans un polygone concave où deux [1] et [3] sont "à l'ouest et le sud" [2]? A vous de gérer correctement les différentes longueurs de [1] et [3]. dans cette situation? Je n'ai pas d'idée, alors que si je directement calculer l'angle (ou son déterminant), je suis en utilisant bien connu des formules.
- les si les déclarations sont toujours fonctionner si les 3 points sont convexes. Le si des instructions seront de retour, alors vous aurez le droit de réponse. Les si les déclarations ne seront pas de retour, si la forme est concave et de l'extrême. C'est à ce moment que vous avez à faire le calcul. La plupart des images ont un quadrant, de sorte que la partie est facile. Plus de 99% de ma sous-routine les appels sont gérés par des instructions if.
- Qui n'a pas l'adresse de mon inquiétude. Qu'est-ce que cette formule? Est-ce l'orientation déterminant comme indiqué dans le lien wiki à partir de lhf réponse? Si oui, dites-le. Expliquer que ce que vous faites est en train de faire des vérifications rapides qui gèrent la plupart des cas, pour éviter les mathématiques standard. Si c'est le cas, alors votre réponse maintenant fait sens pour moi. (Mineur nit: serait plus facile à lire si vous avez utilisé .x et .y d'une struct, au lieu de [0] et [1]. Je ne savais pas ce que votre code a été de dire, la première fois j'ai jeté un coup d'oeil à elle.)
- Depuis je n'ai pas confiance dans votre démarche, je en œuvre de lhf approche; formule à partir de son lien. Partie lente est trouver approprié vertex - O(N) de recherche. Une fois trouvé, le déterminant est un O(1) de l'opération, à l'aide de 6 multiplie avec 5 ajoute. La dernière partie est ce que vous avez optimisé; mais vous avez fait en ajoutant d'autres cas-tests. Je ne peux pas personnellement justifier la prise d'une non-standard, l'approche serait nécessaire de vérifier chaque étape est correct, Mais je vous remercie pour une analyse intéressante de quartiers!
InformationsquelleAutor VectorVortec

De code C# pour mettre en œuvre lhf réponse:

//https://en.wikipedia.org/wiki/Curve_orientation#Orientation_of_a_simple_polygon
public static WindingOrder DetermineWindingOrder(IList<Vector2> vertices)
{
int nVerts = vertices.Count;
//If vertices duplicates first as last to represent closed polygon,
//skip last.
Vector2 lastV = vertices[nVerts - 1];
if (lastV.Equals(vertices[0]))
nVerts -= 1;
int iMinVertex = FindCornerVertex(vertices);
//Orientation matrix:
//    [ 1  xa  ya ]
//O = | 1  xb  yb |
//    [ 1  xc  yc ]
Vector2 a = vertices[WrapAt(iMinVertex - 1, nVerts)];
Vector2 b = vertices[iMinVertex];
Vector2 c = vertices[WrapAt(iMinVertex + 1, nVerts)];
//determinant(O) = (xb*yc + xa*yb + ya*xc) - (ya*xb + yb*xc + xa*yc)
double detOrient = (b.X * c.Y + a.X * b.Y + a.Y * c.X) - (a.Y * b.X + b.Y * c.X + a.X * c.Y);
//TBD: check for "==0", in which case is not defined?
//Can that happen?  Do we need to check other vertices /eliminate duplicate vertices?
WindingOrder result = detOrient > 0
? WindingOrder.Clockwise
: WindingOrder.CounterClockwise;
return result;
}
public enum WindingOrder
{
Clockwise,
CounterClockwise
}
//Find vertex along one edge of bounding box.
//In this case, we find smallest y; in case of tie also smallest x.
private static int FindCornerVertex(IList<Vector2> vertices)
{
int iMinVertex = -1;
float minY = float.MaxValue;
float minXAtMinY = float.MaxValue;
for (int i = 0; i < vertices.Count; i++)
{
Vector2 vert = vertices[i];
float y = vert.Y;
if (y > minY)
continue;
if (y == minY)
if (vert.X >= minXAtMinY)
continue;
//Minimum so far.
iMinVertex = i;
minY = y;
minXAtMinY = vert.X;
}
return iMinVertex;
}
//Return value in (0..n-1).
//Works for i in (-n..+infinity).
//If need to allow more negative values, need more complex formula.
private static int WrapAt(int i, int n)
{
//"+n": Moves (-n..) up to (0..).
return (i + n) % n;
}

Cela semble être pour le bas-est-positif Y de coordonnées. Flip CW/CCW pour la norme de coordonnées.

InformationsquelleAutor ToolmakerSteve

-4

trouver le centre de masse de ces points.

supposons qu'il y a des lignes de ce point de vos points.

trouver l'angle entre les deux lignes pour line0 line1

que faire pour ligne1 et ligne2

...

...

si cet angle est de plus en plus monotone que c'est dans le sens antihoraire ,

d'autre si monotone décroissante, c'est dans le sens des aiguilles

d'autre (il n'est pas monotonical)

vous ne pouvez pas décider, de sorte qu'il n'est pas sage
- par "centre de masse", je pense que tu veux dire "centre de gravité"?
- Fonctionne probablement si le polygone est entièrement convexe. Mais mieux utiliser à la place une réponse qui va travailler pour non-polygones convexes.
InformationsquelleAutor ufukgun

Vous devez vous connecter pour publier un commentaire.