¿Cómo determinar si una lista de puntos poligonales está en el sentido de las agujas del reloj?

Al tener una lista de puntos, ¿cómo puedo saber si están en el sentido de las agujas del reloj?

Por ejemplo:

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

Diría que es antihorario (o en sentido antihorario, para algunas personas).

Algunos de los métodos sugeridos fallarán en el caso de un polígono no convexo, como una media luna. Aquí hay uno simple que funcionará con polígonos no convexos (incluso funcionará con un polígono que se intersecta a sí mismo, como un ocho en forma de figura, que le indica si es mayormente en el sentido de las agujas del reloj).

Suma sobre los bordes, (x 2 – x 1 ) (y 2 + y 1 ). Si el resultado es positivo, la curva es hacia la derecha, si es negativa, la curva es hacia la izquierda. (El resultado es dos veces el área cerrada, con una convención +/-)

 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 

El producto cruzado mide el grado de perpendicularidad de dos vectores. Imagine que cada borde de su polígono es un vector en el plano xy de un espacio tridimensional (3-D) xyz. Entonces, el producto cruzado de dos bordes sucesivos es un vector en la dirección z, (dirección z positiva si el segundo segmento es en sentido horario, menos dirección z si es en sentido antihorario). La magnitud de este vector es proporcional al seno del ángulo entre los dos bordes originales, por lo que alcanza un máximo cuando son perpendiculares, y se estrecha para desaparecer cuando los bordes son colineales (paralelos).

Por lo tanto, para cada vértice (punto) del polígono, calcule la magnitud del producto cruzado de los dos bordes adyacentes:

 Using your data: point[0] = (5, 0) point[1] = (6, 4) point[2] = (4, 5) point[3] = (1, 5) point[4] = (1, 0) 

Así que etiquete los bordes consecutivamente como
edgeA es el segmento desde el punto point0 al point1 y
edgeB entre el point1 al point2

edgeE está entre point4 y point0 .

Entonces, el vértice A (punto point0 ) está entre
edgeE [Del point4 al point0 ]
edgeA [Del punto point0 al `punto1 ‘

Estos dos bordes son en sí mismos vectores, cuyas coordenadas xey se pueden determinar restando las coordenadas de sus puntos de inicio y fin:

edgeE = point0point4 = (1, 0) - (5, 0) = (-4, 0) y
edgeA = point1point0 = (6, 4) - (1, 0) = (5, 4) y

Y el producto cruzado de estos dos bordes contiguos se calcula usando el determinante de la siguiente matriz, que se construye poniendo las coordenadas de los dos vectores debajo de los símbolos que representan los tres ejes de coordenadas ( i , j , & k ). La tercera coordenada (cero) está ahí porque el concepto de producto cruzado es una construcción 3-D, por lo que ampliamos estos vectores bidimensionales a 3-D para aplicar el producto cruzado:

  ijk -4 0 0 1 4 0 

Dado que todos los productos cruzados producen un vector perpendicular al plano de dos vectores que se multiplican, el determinante de la matriz anterior solo tiene un componente k , (o eje z).
La fórmula para calcular la magnitud del componente del eje kz es
a1*b2 - a2*b1 = -4* 4 - 0* 1 = -16

La magnitud de este valor ( -16 ) es una medida del seno del ángulo entre los 2 vectores originales, multiplicado por el producto de las magnitudes de los 2 vectores.
En realidad, otra fórmula por su valor es
AXB (Cross Product) = |A| * |B| * sin(AB) AXB (Cross Product) = |A| * |B| * sin(AB) .

Entonces, para volver solo a una medida del ángulo, necesita dividir este valor, ( -16 ), por el producto de las magnitudes de los dos vectores.

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

Entonces la medida de sin (AB) = -16 / 16.4924 = -.97014...

Esta es una medida de si el siguiente segmento después del vértice se ha doblado hacia la izquierda o hacia la derecha, y en qué medida. No hay necesidad de tomar arco-seno. ¡Lo único que nos importa es su magnitud y, por supuesto, su signo (positivo o negativo)!

Haga esto para cada uno de los otros 4 puntos alrededor de la ruta cerrada, y sume los valores de este cálculo en cada vértice.

Si la sum final es positiva, se fue en sentido horario, negativo, en sentido antihorario.

Supongo que esta es una pregunta bastante antigua, pero de todos modos voy a arrojar otra solución, porque es sencilla y no matemáticamente intensiva, solo usa álgebra básica. Calcula el área firmada del polígono. Si es negativo, los puntos están en el sentido de las agujas del reloj, si es positivo, están en sentido antihorario. (Esto es muy similar a la solución de Beta).

Calcule el área firmada: 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 )

O en pseudo-código:

 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 

Tenga en cuenta que si solo está revisando el pedido, no necesita molestarse en dividir por 2.

Fuentes: http://mathworld.wolfram.com/PolygonArea.html

Aquí hay una implementación simple de C # del algoritmo basada en esta respuesta .

Supongamos que tenemos un tipo Vector tiene propiedades X e Y de tipo double .

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

Encuentra el vértice con la y más pequeña (y la x más grande si hay vínculos). Deje que el vértice sea A y los siguientes vértices en la lista sean B y C Ahora calcule el signo del producto cruzado de AB y AC .


Referencias

  • ¿Cómo encuentro la orientación de un polígono simple? en Preguntas frecuentes: comp.graphics.algorithms .

  • Orientación de la curva en Wikipedia.

Comience en uno de los vértices y calcule el ángulo subtendido por cada lado.

El primero y el último serán cero (así que sáltelos); para el rest, el seno del ángulo estará dado por el producto cruzado de las normalizaciones a la longitud unitaria de (punto [n] -punto [0]) y (punto [n-1] -punto [0]).

Si la sum de los valores es positiva, entonces su polígono se dibuja en el sentido antihorario.

Por lo que vale, utilicé este mixin para calcular el orden de liquidación de las aplicaciones API de Google Maps v3.

El código aprovecha el efecto secundario de las áreas del polígono: un orden de vértice en espiral en el sentido de las agujas del reloj produce un área positiva, mientras que un orden de enrollamiento en sentido antihorario de los mismos vértices produce la misma área que un valor negativo. El código también usa una especie de API privada en la biblioteca de geometría de Google Maps. Me sentí cómodo al usarlo: hágalo bajo su propio riesgo.

Uso de muestra:

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

Ejemplo completo con pruebas unitarias @ 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 stevejansen_github@icloud.com * * @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; } })(); 

Una implementación de la respuesta de Sean en JavaScript:

 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 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)); 

Si usa Matlab, la función ispolycw devuelve verdadero si los vértices del polígono están en el sentido de las agujas del reloj.

Como también se explica en este artículo de Wikipedia Orientación de la curva , dados 3 puntos p , q en el plano (es decir, con las coordenadas xey), puede calcular el signo del siguiente determinante

enter image description here

Si el determinante es negativo (es decir, Orient(p, q, r) < 0 ), entonces el polígono se orienta en el sentido de las agujas del reloj (CW). Si el determinante es positivo (es decir, Orient(p, q, r) > 0 ), el polígono se orienta en sentido antihorario (CCW). El determinante es cero (es decir, Orient(p, q, r) == 0 ) si los puntos p , q y r son colineales .

En la fórmula anterior, anteponemos las que están delante de las coordenadas de p , q y r porque estamos utilizando coordenadas homogéneas .

Esta es la función implementada para OpenLayers 2 . La condición para tener un polígono en el sentido de las agujas del reloj es el area < 0 , confirmada por esta referencia .

 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); } 

Creo que para que algunos puntos se den en el sentido de las agujas del reloj, todos los bordes deben ser positivos, no solo la sum de los bordes. Si un borde es negativo, al menos 3 puntos se dan en sentido antihorario.

Mi solución C # / LINQ se basa en el asesoramiento de productos cruzados de @charlesbretana que se muestra a continuación. Puede especificar una referencia normal para el devanado. Debería funcionar siempre que la curva esté mayoritariamente en el plano definido por el vector ascendente.

 using System.Collections.Generic; using System.Linq; using System.Numerics; namespace SolidworksAddinFramework.Geometry { public static class PlanePolygon { ///  /// Assumes that polygon is closed, ie first and last points are the same ///  public static bool Orientation (this IEnumerable 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; } } } 

con una prueba de unidad

 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(); } } } 

Esta es mi solución usando las explicaciones en las otras respuestas:

 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 

Un método mucho más simple desde el punto de vista computacional, si ya conoces un punto dentro del polígono :

  1. Elija cualquier segmento de línea del polígono original, los puntos y sus coordenadas en ese orden.

  2. Agregue un punto conocido “dentro” y forme un triángulo.

  3. Calcule CW o CCW como se sugiere aquí con esos tres puntos.

Después de probar varias implementaciones poco confiables, el algoritmo que proporcionó resultados satisfactorios con respecto a la orientación CW / CCW de fábrica fue el publicado por OP en este hilo ( shoelace_formula_3 ).

Como siempre, un número positivo representa una orientación CW, mientras que un número negativo CCW.

Aquí está la solución rápida 3.0 basada en las respuestas anteriores:

  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 

Otra solución para esto;

 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; } 

Toma todos los vértices como una matriz como esta;

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

Solución para R para determinar la dirección e invertir en el sentido de las agujas del reloj (lo encontré necesario para los objetos owin):

 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 

encuentra el centro de masa de estos puntos.

supongamos que hay líneas desde este punto hasta sus puntos.

encontrar el ángulo entre dos líneas para línea0 línea1

que hacerlo para line1 y line2

si este ángulo es monótonamente mayor que en sentido antihorario,

de lo contrario, si disminuye monótonamente es en el sentido de las agujas del reloj

else (no es monotónico)

no puedes decidir, entonces no es sabio