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

260

Teniendo una lista de puntos, ¿cómo encuentro 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 en sentido antihorario (o en sentido antihorario, para algunas personas).

Stécy
fuente
66
TENGA EN CUENTA: La respuesta aceptada, y muchas respuestas posteriores, requieren muchas adiciones y multiplicaciones (se basan en cálculos de área que terminan en negativos o positivos; por ejemplo, "fórmula de cordones de los zapatos"). Antes de implementar uno de esos, considere la respuesta de lhf , que es más simple / más rápida, basada en wiki, orientación de polígono simple .
ToolmakerSteve
Siempre pienso en ello en términos del producto cruzado de dos vectores adyacentes. Si camino alrededor del perímetro del polígono, mi cabeza señala el avión. Cruzo el vector fuera del plano en mi vector de dirección de marcha para obtener la tercera dirección en mi sistema de coordenadas. Si ese vector apunta para que el interior esté a mi izquierda, es en sentido antihorario; Si el interior está a mi derecha, es en sentido horario.
duffymo

Respuestas:

416

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 auto intersectante como una figura ocho, que le indica si es principalmente en sentido horario).

Suma sobre los bordes, (x 2 - x 1 ) (y 2 + y 1 ). Si el resultado es positivo, la curva es en sentido horario, si es negativa, la curva es en sentido antihorario. (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
Beta
fuente
28
Es cálculo aplicado a un caso simple. (No tengo la habilidad para publicar gráficos). El área debajo de un segmento de línea es igual a su altura promedio (y2 + y1) / 2 veces su longitud horizontal (x2-x1). Observe la convención de signos en x. Prueba esto con algunos triángulos y pronto verás cómo funciona.
Beta
72
Una advertencia menor: esta respuesta supone un sistema de coordenadas cartesianas normal. La razón que vale la pena mencionar es que algunos contextos comunes, como el lienzo HTML5, usan un eje Y invertido. Entonces la regla tiene que cambiarse: si el área es negativa , la curva es en el sentido de las agujas del reloj.
LarsH
8
@ Mr.Qbs: Entonces mi método funciona, pero si omite una parte vital , entonces no funciona. Esto no es noticia.
Beta
11
@ Mr.Qbs: siempre debe vincular el último punto con el primero. Si tiene N puntos numerados de 0 a N-1, entonces debe calcular: Sum( (x[(i+1) mod N] - x[i]) * (y[i] + y[(i+1) mod N]) )para i = 0 a N-1. Es decir, debe tomar el índice Módulo N ( N ≡ 0) La fórmula funciona solo para polígonos cerrados . Los polígonos no tienen bordes imaginarios.
Olivier Jacot-Descombes
44
Este blog.element84.com/polygon-winding.html explica en inglés simple por qué funciona esta solución.
David Zorychta
49

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 aristas sucesivas 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 disminuye gradualmente 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 adyacentes:

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

Por lo tanto, etiquete los bordes consecutivamente como
edgeAes el segmento de point0a point1y
edgeBentre point1a point2
...
edgeEestá entre point4y point0.

Entonces Vertex A ( point0) está entre
edgeE[De point4a point0]
edgeA[De point0a `punto1 '

Estos dos bordes son en sí mismos vectores, cuyas coordenadas x e y se pueden determinar 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 matriz siguiente, que se construye poniendo las coordenadas de los dos vectores por debajo de los símbolos que representan los tres ejes de coordenadas ( i, j, y k). La tercera coordenada (cero) está ahí porque el concepto de producto cruzado es una construcción tridimensional, por lo que ampliamos estos vectores 2-D a 3-D 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 kcomponente (o eje z).
La fórmula para calcular la magnitud del kcomponente del eje 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, multiplicado por el producto de las magnitudes de los 2 vectores.
En realidad, otra fórmula para su valor es
A X B (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 del pecado (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 por cuánto. No hay necesidad de tomar arco-seno. ¡Lo único que nos importará 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, fue en sentido horario, negativo, en sentido antihorario.

Charles Bretana
fuente
3
En realidad, esta solución es diferente a la solución aceptada. Si son equivalentes o no, es una pregunta que estoy investigando, pero sospecho que no lo son ... La respuesta aceptada calcula el área del polígono, tomando la diferencia entre el área debajo del borde superior del polígono y el área debajo El borde inferior del polígono. Uno será negativo (el que está atravesando de izquierda a derecha), y el otro será negativo. Al recorrer en sentido horario, el borde superior se desplaza de izquierda a derecha y es más grande, por lo que el total es positivo.
Charles Bretana
1
Mi solución mide la suma de los senos de los cambios en los ángulos de los bordes en cada vértice. Esto será positivo cuando atraviese en sentido horario y negativo cuando atraviese en sentido antihorario.
Charles Bretana
2
Parece que con este enfoque USTED necesita tomar el arcosin, a menos que asuma convexidad (en cuyo caso solo necesita verificar un vértice)
agentp
2
Necesitas tomar el arco. Pruébelo en un montón de polígonos no convexos aleatorios, y encontrará que la prueba fallará para algunos polígonos si no toma el arcosin.
Luke Hutchison
1
@CharlesBretana: aunque no he ejecutado la prueba de Luke, creo que es correcto. Esa es la naturaleza de la suma combinada con una escala no lineal [sin arcsin vs. con arcsin]. Considere lo que sugirió marsbear, que rechazó correctamente. Sugirió que "solo cuente", y señaló que un puñado de valores grandes podría superar una gran cantidad de valores pequeños. Ahora considere el arco de cada valor frente a no. ¿No sigue siendo el caso de que no tomar arcsin da un peso incorrecto a cada valor, por lo tanto tiene el mismo defecto (aunque mucho menos)?
ToolmakerSteve
47

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

Calcule el área con signo: 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 seudocó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 por 2.

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

Sean the Bean
fuente
¿Fue un error tipográfico en su fórmula de área firmada arriba? Termina con "xn * y1 - x1 * yn"; cuando creo que debería ser "x_n y_ {n + 1} - y_n x_ {n-1}" (en LaTeX, al menos). Por otro lado, han pasado diez años desde que tomé clases de álgebra lineal.
Michael Eric Oberlin
No Si verifica la fuente , verá que la fórmula de hecho hace referencia al primer punto nuevamente en el último término (y1 y x1). (Lo siento, no estoy muy familiarizado con LaTeX, pero he formateado los subíndices para que sean más legibles.)
Sean the Bean
Usé esta solución y funcionó perfectamente para mi uso. Tenga en cuenta que si puede planificar con anticipación y ahorrar dos vectores adicionales en su matriz, puede deshacerse de la comparación (o%) agregando el primer vector en la cola de la matriz. De esa manera, simplemente recorre todos los elementos, excepto el último (longitud-2 en lugar de longitud-1).
Eric Fortier
2
@EricFortier - FWIW, en lugar de cambiar el tamaño de una matriz posiblemente grande, una alternativa eficiente es que cada iteración guarde su punto como previousPointen la próxima iteración. Antes de comenzar el bucle, establezca previousPointel último punto de la matriz. La compensación es una copia variable local adicional pero menos accesos a la matriz. Y lo más importante, no tiene que tocar la matriz de entrada.
ToolmakerSteve
2
@MichaelEricOberlin: es necesario cerrar el polígono, incluyendo el segmento de línea desde el último punto hasta el primer punto. (Un cálculo correcto será el mismo, sin importar en qué punto comience el polígono cerrado.)
ToolmakerSteve
38

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 Ay el vértice anterior en la lista sea By el siguiente vértice en la lista sea C. Ahora calcule el signo del producto cruzado de ABy AC.


Referencias

lhf
fuente
77
Esto también se explica en en.wikipedia.org/wiki/Curve_orientation . El punto es que el punto encontrado debe estar en el casco convexo, y solo es necesario mirar localmente en un solo punto en el casco convexo (y sus vecinos inmediatos) para determinar la orientación de todo el polígono.
M Katz
1
Sorprendido y asombrado, esto no ha recibido más votos a favor. Para los polígonos simples ( que es la mayoría de los polígonos en algunos campos ), esta respuesta proporciona una O(1)solución. Todas las demás respuestas dan O(n)soluciones para nel número de puntos poligonales. Para optimizaciones aún más profundas, consulte la subsección Consideraciones prácticas del fantástico artículo de orientación Curva de Wikipedia.
Cecil Curry
8
Aclaración: esta solución esO(1)solo si (A) este polígono es convexo (en cuyo caso cualquier vértice arbitrario reside en el casco convexo y, por lo tanto, es suficiente) o (B) ya conoce el vértice con la coordenada Y más pequeña. Si este no esel caso (es decir, este polígono no es convexo y no sabe nada al respecto),O(n)se requiereunabúsqueda. Sin embargo, dado que no se requiere una suma, esto es aún más rápido que cualquier otra solución para polígonos simples.
Cecil Curry
1
@CecilCurry Creo que tu segundo comentario explica por qué esto no ha recibido más votos a favor. Produce respuestas incorrectas en ciertos escenarios, sin mencionar esas limitaciones.
LarsH
24

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

Supongamos que tenemos un Vectortipo que tiene Xy Ypropiedades 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];
        sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    }
    return sum > 0.0;
}

%es el operador de módulo o resto que realiza la operación de módulo que ( según Wikipedia ) encuentra el resto después de la división de un número por otro.

Olivier Jacot-Descombes
fuente
6

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 omítalos); para el resto, el seno del ángulo estará dado por el producto cruzado de las normalizaciones a la unidad de longitud de (punto [n] -punto [0]) y (punto [n-1] -punto [0]).

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

Steve Gilham
fuente
Al ver cómo el producto cruzado básicamente se reduce a un factor de escala positivo multiplicado por el seno del ángulo, probablemente sea mejor hacer un producto cruzado. Será más rápido y menos complicado.
ReaperUnreal
4

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

El código aprovecha el efecto secundario de las áreas de polígono: un orden de vértices en el sentido de las agujas del reloj produce un área positiva, mientras que un orden de devanado en sentido antihorario 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, úselo bajo su 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;
  }
})();
Steve Jansen
fuente
Al intentar esto obtengo exactamente el resultado opuesto, un polígono dibujado en el sentido de las agujas del reloj produce un área negativa, mientras que uno dibujado en sentido contrario a las agujas del reloj produce un resultado positivo. En cualquier caso, este fragmento sigue siendo súper útil 5 años después, gracias.
Cameron Roberts
@CameronRoberts La norma (ver IETF en particular para geoJson) es seguir la 'regla de la mano derecha'. Supongo que Google se está quejando. En ese caso, el anillo exterior debe estar en sentido antihorario (produciendo un área positiva), y los anillos internos (agujeros) están enrollando en el sentido de las agujas del reloj (área negativa que debe eliminarse del área principal).
Allez l'OM
4

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

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

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

mpen
fuente
3

Esta es la función implementada para OpenLayers 2 . La condición para tener un polígono en sentido horario es area < 0confirmada 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);
}
MSS
fuente
Openlayers es una biblioteca de administración de mapas basada en JavaScript como googlemaps y está escrita y utilizada en openlayers 2.
MSS
¿Puedes explicar un poco qué hace tu código y por qué lo estás haciendo?
nbro
@nbro este código implementa la respuesta lhf . Es fácil mantener la parte que no es OpenLayer en una función javascript pura al tener vértices directamente como parámetro. Funciona bien y podría adaptarse al caso de multiPolygon .
Allez l'OM
2

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

Frederick
fuente
1

Como también se explica en este artículo de Wikipedia Orientación de curvas , dados 3 puntos p, qy ren el plano (es decir, con coordenadas x e y), puede calcular el signo del siguiente determinante

ingrese la descripción de la imagen aquí

Si el determinante es negativo (es decir Orient(p, q, r) < 0), entonces el polígono está orientado en sentido horario (CW). Si el determinante es positivo (es decir Orient(p, q, r) > 0), el polígono está orientado en sentido antihorario (CCW). El determinante es cero (es decir Orient(p, q, r) == 0) si puntos p, qy rson colineales .

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

Ian
fuente
@tibetty ¿Puede explicar por qué este método no funcionaría en muchas situaciones si el polígono es cóncavo?
nbro
1
Mire la última tabla en la referencia del elemento wiki en su publicación. Es fácil para mí dar un ejemplo falso pero difícil de demostrar.
tibetty
1
Mire la última tabla en la referencia del elemento wiki en su publicación. Es fácil para mí dar un ejemplo falso pero difícil de demostrar.
tibetty
1
@tibetty es correcto. No puede simplemente tomar tres puntos a lo largo del polígono; puede estar en una región convexa o cóncava de ese polígono. Leyendo wiki cuidadosamente, uno debe tomar tres puntos a lo largo del casco convexo que encierra el polígono . De "consideraciones prácticas": "No es necesario construir el casco convexo de un polígono para encontrar un vértice adecuado. Una opción común es el vértice del polígono con la coordenada X más pequeña. Si hay varios de ellos, el con la coordenada Y más pequeña se elige. Se garantiza que es [a] vértice del casco convexo del polígono ".
ToolmakerSteve
1
De ahí la respuesta anterior de lhf , que es similar, y hace referencia al mismo artículo wiki, pero especifica ese punto. [Aparentemente no importa si uno toma el más pequeño o el más grande, x o y, siempre que uno evite estar en el medio; efectivamente, uno está trabajando desde un borde del cuadro delimitador alrededor del polígono, para garantizar en una región cóncava.]
ToolmakerSteve
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 suma de los bordes. Si un borde es negativo, al menos 3 puntos se dan en sentido antihorario.

daniel
fuente
Es cierto, pero no comprende el concepto del orden de bobinado de un polígono (en sentido horario o antihorario). En un polígono completamente convexo, el ángulo en todos los puntos será en sentido horario o en sentido antihorario [como en su primera oración]. En un polígono con región (s) cóncava (s), las "cuevas" estarán en la dirección opuesta, pero el polígono en su conjunto todavía tiene un interior bien definido, y se considera en sentido horario o antihorario en consecuencia. Ver en.wikipedia.org/wiki/…
ToolmakerSteve
0

Mi solución C # / LINQ se basa en los consejos de productos cruzados de @charlesbretana que se encuentran a continuación. Puede especificar una referencia normal para el devanado. Debería funcionar siempre que la curva esté principalmente 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
    {
        /// <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();



        } 
    }
}
bradgonesurfing
fuente
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
Lanza Gianni
fuente
1
¿Puede especificar en qué otras respuestas se basa exactamente esta respuesta?
nbro
0

Un método mucho más simple desde el punto de vista computacional, si ya conoce 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 "interno" conocido y forme un triángulo.

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

Venkata Goli
fuente
Tal vez esto funcione si el polígono es completamente convexo. Definitivamente no es confiable si hay regiones cóncavas: es fácil elegir un punto que esté en el lado "incorrecto" de uno de los bordes de la cueva y luego conectarlo a ese borde. Recibirá una respuesta incorrecta.
ToolmakerSteve
Funciona incluso si el polígono es cóncavo. El punto debe estar dentro de ese polígono cóncavo. Sin embargo, no estoy seguro sobre el polígono complejo (no se realizó la prueba)
Venkata Goli
"Funciona incluso si el polígono es cóncavo". - Contraejemplo: poli (0,0), (1,1), (0,2), (2,2), (2,0). Segmento de línea (1,1), (0, 2). Si elige un punto interior dentro de (1,1), (0,2), (1,2) para formar un triángulo -> (1,1), (0,2), (0.5,1.5)), obtendrá devanado opuesto que si selecciona un punto interior dentro de (0,0), (1,1), (1,0)> (1,1), (0,2), (0.5,0.5). Ambos son interiores al polígono original, pero tienen bobinados opuestos. Por lo tanto, uno de ellos da la respuesta incorrecta.
ToolmakerSteve
En general, si un polígono tiene alguna región cóncava, elija un segmento en la región cóncava. Debido a que es cóncavo, puede encontrar dos puntos "interiores" que están en lados opuestos de esa línea. Debido a que están en lados opuestos de esa línea, los triángulos formados tienen bobinados opuestos. Fin de la prueba.
ToolmakerSteve
0

Después de probar varias implementaciones poco confiables, el algoritmo que proporcionó resultados satisfactorios con respecto a la orientación CW / CCW fuera de la caja 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.

Marjan Moderc
fuente
0

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
Toby Evetts
fuente
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);
Indiana
fuente
0

Solución para que R determine la dirección e invierta si es en el sentido de las agujas del reloj (lo encontró necesario para los objetos):

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
dez
fuente
0

Si bien estas respuestas son correctas, son matemáticamente más intensas de lo necesario. Asuma las coordenadas del mapa, donde el punto más al norte es el punto más alto del mapa. Encuentre el punto más al norte, y si empatan 2 puntos, es el más al norte que el más al este (este es el punto que lhf usa en su respuesta). En tus puntos

punto [0] = (5,0)

punto [1] = (6,4)

punto [2] = (4,5)

punto [3] = (1,5)

punto [4] = (1,0)

Si suponemos que P2 es el punto más al norte, entonces este, ya sea el punto anterior o el siguiente, determina en sentido horario, CW o CCW. Como el punto más al norte está en la cara norte, si el P1 (anterior) a P2 se mueve hacia el este, la dirección es CW. En este caso, se mueve hacia el oeste, por lo que la dirección es CCW como dice la respuesta aceptada. Si el punto anterior no tiene movimiento horizontal, entonces el mismo sistema se aplica al siguiente punto, P3. Si P3 está al oeste de P2, entonces el movimiento es CCW. Si el movimiento P2 a P3 es hacia el este, en este caso es hacia el oeste, el movimiento es CW. Suponga que nte, P2 en sus datos, es el punto más al norte que este y que prv es el punto anterior, P1 en sus datos, y nxt es el siguiente punto, P3 en sus datos, y [0] es horizontal u este / oeste donde oeste es menor que este, y [1] es vertical.

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)
VectorVortec
fuente
En mi humilde opinión, sería más seguro apegarse a las matemáticas fundamentales que se muestran en la respuesta de lhf : gracias por mencionarlo. El desafío de reducirlo a cuadrantes es que es una buena cantidad de trabajo demostrar que su fórmula es correcta en todos los casos. ¿Calculó correctamente "más oeste"? En un polígono cóncavo donde tanto [1] como [3] son ​​"oeste y sur" de [2]? ¿Manejó correctamente diferentes longitudes de [1] y [3] en esa situación? No tengo idea, mientras que si calculo directamente ese ángulo (o su determinante), estoy usando fórmulas bien conocidas.
ToolmakerSteve
@ToolmakerSteve las declaraciones if siempre funcionan si los 3 puntos son convexos. Las declaraciones if volverán, entonces obtendrá la respuesta correcta. Las declaraciones if no volverán, si la forma es cóncava y extrema. Ahí es cuando tienes que hacer los cálculos. La mayoría de las imágenes tienen un cuadrante, por lo que esa parte es fácil. Las declaraciones if manejan más del 99% de mis llamadas de subrutina.
VectorVortec
Eso no aborda mi preocupación. ¿Cuál es esa fórmula? ¿Es la orientación determinante como se da en el enlace wiki de la respuesta de lhf? Si es así, entonces dilo. Explique que lo que está haciendo es realizar comprobaciones rápidas que manejan la mayoría de los casos, para evitar las matemáticas estándar. Si es así, entonces su respuesta ahora tiene sentido para mí. (NIT Menor: sería más fácil de leer si se ha utilizado .xy .yde una estructura, en lugar de [0]y [1]no sabía lo que estaba diciendo su código, primera vez que eché un vistazo..)
ToolmakerSteve
Como no tenía confianza en su enfoque, implementé el enfoque de lhf ; fórmula de su enlace. La parte lenta es encontrar el vértice apropiado: búsqueda O (N). Una vez encontrado, el determinante es una operación O (1), utilizando 6 multiplicaciones con 5 sumas. Esa última parte es lo que has optimizado; pero lo ha hecho agregando pruebas if adicionales. No puedo justificar personalmente adoptar un enfoque no estándar; necesitaría verificar que cada paso sea correcto. ¡Pero gracias por un interesante análisis de cuadrantes!
ToolmakerSteve
0

Código C # para implementar la respuesta de lhf :

// 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;
}
ToolmakerSteve
fuente
1
Esto parece ser para coordenadas Y positivas. Voltear CW / CCW para coordenadas estándar.
Warwick Allison
0

Aquí hay una implementación simple de Python 3 basada en esta respuesta (que, a su vez, se basa en la solución propuesta en la respuesta aceptada )

def is_clockwise(points):
    # points is your list (or array) of 2d points.
    assert len(points) > 0
    s = 0.0
    for p1, p2 in zip(points, points[1:] + [points[0]]):
        s += (p2[0] - p1[0]) * (p2[1] + p1[1])
    return s > 0.0
nbro
fuente
-4

encuentra el centro de masa de estos puntos.

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

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

que hacerlo para line1 y line2

...

...

si este ángulo está aumentando monotónicamente de lo contrario,

de lo contrario si disminuye monotónicamente es en sentido horario

de lo contrario (no es monotónico)

no puedes decidir, entonces no es sabio

ufukgun
fuente
por "centro de masa" ¿Creo que te refieres a "centroide"?
Vicky Chijwani
Probablemente funciona si el polígono es completamente convexo. Pero es mejor usar una respuesta que funcione para polígonos no convexos.
ToolmakerSteve