math - que - ¿Cómo determinar si una lista de puntos de polígono está en el orden de las agujas del reloj?

que angulo forman las manecillas del reloj a las 4 y media (20)

Al tener una lista de puntos, ¿cómo encuentro si están en el orden 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 en sentido contrario a las agujas del reloj (o en sentido contrario a las agujas del reloj, para algunas personas).

Algunos de los métodos sugeridos fallarán en el caso de un polígono no convexo, como un creciente. Aquí hay uno simple que funcionará con polígonos no convexos (incluso funcionará con un polígono de auto-intersección como una figura de ocho, que le indicará si es mayormente hacia la derecha).

Suma sobre los bordes, (x ₂ - x ₁ ) (y ₂ + y ₁ ). Si el resultado es positivo, la curva es hacia la derecha, si es negativo, la curva es hacia la izquierda. (El resultado es el doble del á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

Aquí está la solución Swift 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

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<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]; // % is the modulo operator sum += (v2.X - v1.X) * (v2.Y + v1.Y); } return sum > 0.0; }

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

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

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

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 x e y), puede calcular el signo del siguiente determinante

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 contrario a las agujas del reloj (CCW). El determinante es cero (es decir, Orient(p, q, r) == 0 ) si los puntos p , q son collinear .

En la fórmula anterior, precedemos a los que están delante de las coordenadas de p , q porque estamos usando coordenadas homogéneas .

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 suma de los bordes. Si un borde es negativo, al menos 3 puntos se dan en sentido antihorario.

Después de probar varias implementaciones no confiables, el algoritmo que proporcionó resultados satisfactorios con respecto a la orientación de CW / CCW fuera de la caja fue el publicado por OP en this hilo ( shoelace_formula_3 ).

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

El producto cruzado mide el grado de perpendicularidad de dos vectores. Imagina que cada borde de tu polígono es un vector en el plano xy de un espacio xyz tridimensional (3-D). Luego, 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 el sentido de las agujas del reloj, menos la dirección z si es en el sentido contrario a las agujas del reloj). 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 desaparece para desaparecer cuando los bordes son colineales (paralelos).

Entonces, para cada vértice (punto) del polígono, calcule la magnitud del producto cruzado de los dos bordes contiguos:

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 etiqueta los bordes consecutivamente como
edgeA es el segmento desde point0 hasta point1 y
edgeB entre point1 a point1
...
edgeE está entre point4 y point0 .

Entonces Vertex A ( point0 ) está entre
edgeE [Del point4 al punto point0 ]
edgeA [Del point0 al `punto1 ''

Estos dos bordes son en sí mismos vectores, cuyas coordenadas x e y pueden determinarse restando las coordenadas de sus puntos inicial y final:

edgeE = point0 - point4 = (1, 0) - (5, 0) = (-4, 0) y
edgeA = point1 - point0 = (6, 4) - (1, 0) = (5, 4) y

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

i j k -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 de la componente del eje k o z 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, multiplicada 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 a una medida del ángulo que necesita para dividir este valor, ( -16 ), por el producto de las magnitudes de los dos vectores.

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

Entonces la medida del pecado (AB) = -16 / 16.4924 = -.97014...

Esta es una medida de si el siguiente segmento después de que el vértice se haya doblado hacia la izquierda o hacia la derecha, y por cuánto. No hay necesidad de tomar arco-seno. ¡Todo lo 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 suma final es positiva, se fue en sentido horario, negativo, en sentido contrario a las agujas del reloj.

Encuentra el centro de masa de estos puntos.

Supongamos que hay líneas desde este punto a tus puntos.

encuentra el ángulo entre dos líneas para line0 line1

que hacerlo para line1 y line2

...

si este ángulo aumenta monotónicamente que en sentido contrario a las agujas del reloj,

de lo contrario si disminuye monótonamente es en sentido horario

otra cosa (no es monotonico)

No puedes decidir, así que no es sabio.

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.

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 area < 0 , confirmada por en.wikipedia.org/wiki/Shoelace_formula .

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

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

Mi solución C # / LINQ se basa en el asesoramiento cruzado de productos de @charlesbretana que se encuentra a continuación. Puede especificar una referencia normal para el devanado. Debería funcionar siempre que la curva se encuentre principalmente en el plano definido por el vector hacia arriba.

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

con una prueba unitaria

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

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

Para lo que vale, utilicé esta mezcla para calcular el orden de liquidación para las aplicaciones de Google Maps API v3.

El código aprovecha el efecto secundario de las áreas poligonales: un orden de enrollamiento de vértices en el sentido de las agujas del reloj produce un área positiva, mientras que un orden de enrollamiento en el sentido contrario a las agujas del reloj de los mismos vértices produce la misma área que un valor negativo. El código también utiliza una especie de API privada en la biblioteca de geometría de Google Maps. Me sentí cómodo usándolo - usalo bajo tu propio riesgo.

Uso de la 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 [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; } })();

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

Solución para que R determine la dirección y retroceda 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

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

Calcule el área firmada: A = 1/2 * (x ₁ * y ₂ - x ₂ * y ₁ + x ₂ * y ₃ - x ₃ * y ₂ + ... + x _n * y ₁ - x ₁ * y _n )

O en pseudocó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á verificando el pedido, no necesita molestarse en dividir entre 2.

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

Un método mucho más simple desde el punto de vista de la computación, si ya conoce un punto dentro del polígono :

Elija cualquier segmento de línea del polígono original, los puntos y sus coordenadas en ese orden.
Agrega un punto "interior" conocido y forma un triángulo.
Calcule CW o CCW como se sugiere aquí con esos tres puntos.

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

Bastante seguro de que esto es correcto. Parece estar funcionando :-)

Esos polígonos se ven así, si te estás preguntando: