Ordene cuatro puntos en el sentido de las agujas del reloj

Question

Cuatro puntos 2D en una matriz. Necesito ordenarlos en el sentido de las agujas del reloj. Creo que se puede hacer con una sola operación de intercambio, pero no he podido dejar esto formalmente.

Editar: Los cuatro puntos son un polígono convexo en mi caso.

Editar: Los cuatro puntos son los vértices de un polígono convexo. No necesitan estar en orden.

Answer 1

Si desea adoptar una perspectiva más matemático, podemos considerar las permutaciones de 4 puntos

en nuestro caso hay 4 permutaciones que se encuentran en orden a la derecha

A B C D 
B C D A 
C D A B 
D A B C 

Todos los otros posibles permutaciones se puede convertir a una de estas formas con 0 o 1 swaps.(I sólo tendrá en cuenta las permutaciones que empiecen con A, ya que es simétrico)

1. ABCD - hecho
2. ABDC - intercambiable C y D
3. ACBD - SWAP B y C
4. ACDB - SWAP A y B
5. ADBC ​​- SWAP A y D
6. ADCB - SWAP B y D

lo tanto sólo una sw se necesita alguna vez, pero puede tomar algún trabajo identificar cuál.

Al observar los primeros tres puntos y verificar el signo del área firmada de ABC, podemos determinar si son en sentido horario o no. Si están en el sentido de las agujas del reloj, estamos en el caso 1 2 o 5

para distinguir entre estos casos tenemos que verificar dos triángulos más. Si ACD es en el sentido de las agujas del reloj, podemos reducirlo al caso 1; 2 ó 5.

que elegir entre los casos 2 y 5, podemos probar ABD

podemos comprobar el caso de ABC en sentido antihorario de manera similar.

En el peor de los casos, tenemos que probar 3 triángulos.

Si sus puntos no son convexos, debería encontrar el punto interno, ordenar el resto y luego agregarlo en cualquier borde. Tenga en cuenta que si el cuádruple es convexo, entonces 4 puntos ya no determinan de manera única el cuádruple, hay 3 cuadrantes igualmente válidos.

Answer 2

Creo que tiene razón en que un solo intercambio puede garantizar que un polígono representado por cuatro puntos en el plano sea convexo. Las preguntas que quedan por responder son:

• ¿Es este conjunto de cuatro puntos un polígono convexo?
• Si no, ¿qué dos puntos deben intercambiarse?
• ¿Qué dirección es en el sentido de las agujas del reloj?

En una reflexión más profunda, creo que la única respuesta a la segunda pregunta anterior es "los dos medios".

Answer 3

¿Qué tal esto?

// Take signed area of ABC. 
// If negative, 
//  Swap B and C. 
// Otherwise, 
//  Take signed area of ACD. 
//  If negative, swap C and D. 

Ideas?

Answer 4

Trabaja por mucho tiempo y luego optimízalo.

Un problema más específico sería ordenar las coordenadas disminuyendo el ángulo relativo al eje x positivo. Este ángulo, en radianes, se dará por esta función:

x>0 
    AND y >= 0 
     angle = arctan(y/x) 
    AND y < 0 
     angle = arctan(y/x) + 2*pi 
x==0 
    AND y >= 0 
     angle = 0 
    AND y < 0 
     angle = 3*pi/2 
x<0 
    angle = arctan(y/x) + pi 

Luego, por supuesto, es sólo una cuestión de clasificación de las coordenadas por el ángulo. Tenga en cuenta que arctan (w)> arctan (z) si y solo si x> z, por lo que puede optimizar una función que compara ángulos entre sí con bastante facilidad.

La ordenación de tal forma que el ángulo disminuye monótonamente sobre una ventana (o tal que aumenta a lo sumo una vez) es un poco diferente.

En lugar de una prueba exhaustiva mencionaré que verifiqué que una sola operación de intercambio ordenará 4 puntos 2D en el sentido de las agujas del reloj. Determinar qué operación de intercambio es necesaria es el truco, por supuesto.

Answer 5

Un par de consideraciones que vale la pena considerar aquí;

• Las agujas del reloj solo son significativas con respecto a un origen. Tiendo a pensar en el origen como el centro de gravedad de un conjunto de puntos. p.ej. En sentido horario relativo a un punto en la posición media de los cuatro puntos, en lugar del origen posiblemente muy distante.

• Si tiene cuatro puntos, a, b, c, d, existen múltiples ordenamientos en el sentido de las agujas del reloj de esos puntos alrededor de su origen. Por ejemplo, si (a, b, c, d) formó un orden en el sentido de las agujas del reloj, también lo haría (b, c, d, a), (c, d, a, b) y (d, a, b, c)

• ¿Sus cuatro puntos ya forman un polígono? Si es así, se trata de verificar e invertir el devanado en lugar de ordenar los puntos, p. a, b, c, d se convierte en d, c, b, a. De lo contrario, ordenaría en función del rumbo de unión entre cada punto y el origen, según la respuesta de Wedges.

Editar: con respecto a sus comentarios sobre lo que apunta a cambiar;

En el caso de un triángulo (a, b, c), podemos decir que se trata de las agujas del reloj si el tercer punto c, está en el lado derecho de la línea ab . Uso la siguiente función secundaria para determinar esto en función de las coordenadas del punto;

int side(double x1,double y1,double x2,double y2,double px,double py) 
{ 
double dx1,dx2,dy1,dy2; 
double o; 

dx1 = x2 - x1; 
dy1 = y2 - y1; 
dx2 = px - x1; 
dy2 = py - y1; 
o = (dx1*dy2)-(dy1*dx2); 
if (o > 0.0) return(LEFT_SIDE); 
if (o < 0.0) return(RIGHT_SIDE); 
return(COLINEAR); 
} 

Si tengo un polígono convexo de cuatro puntos, (a, b, c, d), puedo considerar esto como dos triángulos, (a, b, c) y (c, d, A). Si (a, b, c) es en sentido contrario a las agujas del reloj, cambio el devanado (a, b, c, d) a (a, d, c, b) para cambiar el devanado del polígono como un todo hacia la derecha.

Sugiero dibujar esto con algunos puntos de muestra, para ver de lo que estoy hablando. Tenga en cuenta que tiene que lidiar con muchos casos excepcionales, como polígonos cóncavos, puntos colineales, puntos coincidentes, etc.

Answer 6

La respuesta de la cuña es correcta.

Para implementarlo fácilmente, creo que de la misma manera que smacl: necesita encontrar el centro del límite y traducir sus puntos a ese centro.

De esta manera:

centerPonintX = Min(x) + ( (Max(x) – Min(x))/2 ) 
centerPonintY = Min(y) + ( (Max(y) – Min(y))/2 ) 

Entonces, disminuir centerPointX y centerPointY de cada poin con el fin de traducirlo al origen del límite.

Finalmente, aplique la solución de Wedge con un solo giro: Obtenga el valor Absoluto de arctan (x/y) para cada instancia (trabajó para mí de esa manera).

Answer 7

if((p2.x-p1.x)*(p3.y-p1.y) > (p3.x-p1.x)*(p2.y-p1.y)) 
    swap(&p1, &p3); 

El '>' podría estar mirando hacia el lado equivocado, pero se entiende.

Answer 8

si asumimos que el punto x es más grande que el punto Y si el ángulo que tiene con el punto (0,0) es más grande que podemos poner en práctica esta de esta manera en C#

class Point : IComparable<Point> 
    { 
     public int X { set; get; } 
     public int Y { set; get; } 

     public double Angle 
     { 
      get 
      { 
       return Math.Atan2(X, Y); 
      } 
     } 

     #region IComparable<Point> Members 

     public int CompareTo(Point other) 
     { 
      return this.Angle.CompareTo(other.Angle); 
     } 

     #endregion 

     public static List<Point> Sort(List<Point> points) 
     { 
      return points.Sort(); 
     } 
} 

Answer 9

if AB crosses CD 
    swap B,C 
elif AD crosses BC 
    swap C,D 

if area (ABC) > 0 
    swap B,D 

(I mean area(ABC) > 0 when A->B->C is counter-clockwise). 
Let p*x + q*y + r = 0 be the straight line that joins A and B. 
Then AB crosses CD if p*Cx + q*Cy + r and p*Dx + q*Dy + r 
have different sign, i.e. their product is negative. 

El primer 'si/elif' trae los cuatro puntos en las agujas del reloj o antihorario orden. (Dado que su polígono es convexo, la única alternativa de 'cruce' es 'CA cruza BD', lo que significa que los cuatro puntos ya están ordenados.) La última orientación 'si' invierte siempre que sea en sentido antihorario.

Answer 10

Deberías echarle un vistazo al Graham's Scan. Por supuesto, tendrá que adaptarlo ya que encuentra puntos en el sentido contrario a las agujas del reloj.

p.s: Esto podría ser excesiva para 4 puntos, pero si el número de puntos de incrementar podría ser interesante

Answer 11

Oliver es correcto. Este código (comunidad wikified) genera y ordena todas las combinaciones posibles de una matriz de 4 puntos.

#include <cstdio> 
#include <algorithm> 

struct PointF { 
    float x; 
    float y; 
}; 

// Returns the z-component of the cross product of a and b 
inline double CrossProductZ(const PointF &a, const PointF &b) { 
    return a.x * b.y - a.y * b.x; 
} 

// Orientation is positive if abc is counterclockwise, negative if clockwise. 
// (It is actually twice the area of triangle abc, calculated using the 
// Shoelace formula: http://en.wikipedia.org/wiki/Shoelace_formula .) 
inline double Orientation(const PointF &a, const PointF &b, const PointF &c) { 
    return CrossProductZ(a, b) + CrossProductZ(b, c) + CrossProductZ(c, a); 
} 

void Sort4PointsClockwise(PointF points[4]){ 
    PointF& a = points[0]; 
    PointF& b = points[1]; 
    PointF& c = points[2]; 
    PointF& d = points[3]; 

    if (Orientation(a, b, c) < 0.0) { 
     // Triangle abc is already clockwise. Where does d fit? 
     if (Orientation(a, c, d) < 0.0) { 
      return;   // Cool! 
     } else if (Orientation(a, b, d) < 0.0) { 
      std::swap(d, c); 
     } else { 
      std::swap(a, d); 
     } 
    } else if (Orientation(a, c, d) < 0.0) { 
     // Triangle abc is counterclockwise, i.e. acb is clockwise. 
     // Also, acd is clockwise. 
     if (Orientation(a, b, d) < 0.0) { 
      std::swap(b, c); 
     } else { 
      std::swap(a, b); 
     } 
    } else { 
     // Triangle abc is counterclockwise, and acd is counterclockwise. 
     // Therefore, abcd is counterclockwise. 
     std::swap(a, c); 
    } 
} 

void PrintPoints(const char *caption, const PointF points[4]){ 
    printf("%s: (%f,%f),(%f,%f),(%f,%f),(%f,%f)\n", caption, 
     points[0].x, points[0].y, points[1].x, points[1].y, 
     points[2].x, points[2].y, points[3].x, points[3].y); 
} 

int main(){ 
    PointF points[] = { 
     {5.0f, 20.0f}, 
     {5.0f, 5.0f}, 
     {20.0f, 20.0f}, 
     {20.0f, 5.0f} 
    }; 

    for(int i = 0; i < 4; i++){ 
     for(int j = 0; j < 4; j++){ 
      if(j == i) continue; 
      for(int k = 0; k < 4; k++){ 
       if(j == k || i == k) continue; 
       for(int l = 0; l < 4; l++){ 
        if(j == l || i == l || k == l) continue; 
        PointF sample[4]; 
        sample[0] = points[i]; 
        sample[1] = points[j]; 
        sample[2] = points[k]; 
        sample[3] = points[l]; 

        PrintPoints("input: ", sample); 
        Sort4PointsClockwise(sample); 
        PrintPoints("output: ", sample); 
        printf("\n"); 
       } 
      } 
     } 
    } 

    return 0; 
} 

Answer 12

tengo una nueva mejora para añadir a mi respuesta anterior

recordar - estos son los casos en que podemos ser.

1. ABCD
2. ABDC
3. ACBD
4. ACDB
5. ADBC ​​
6. ADCB

Si ABC es en sentido antihorario (tiene un área negativa firmado) entonces estamos en los casos 3, 4, 6. Si cambiamos B & C en este caso, entonces nos quedamos con el siguiente posibilidades guientes:

1. ABCD
2. ABDC
3. ABCD
4. ABDC
5. ADBC ​​
6. ADBC ​​

A continuación podemos comprobar ABD y de intercambio B & D si es en sentido antihorario (casos 5, 6)

1. A B C D
2. A B D C
3. A B D
4. A B D C
5. A B D C
6. A B D C

Finalmente necesitamos comprobar ACD y de intercambio C & D si ACD es en sentido antihorario C. Ahora sabemos que todos nuestros puntos están en orden.

Este método no es tan eficiente como mi método anterior; esto requiere 3 comprobaciones cada vez y más de un intercambio; pero el código sería mucho más simple.

Answer 13

Si alguien está interesado, aquí está mi solución rápida y sucia a un problema similar.

Mi problema era que mis esquinas del rectángulo ordenados en el orden siguiente:

-arriba a la izquierda> superior derecha> inferior derecha> parte inferior izquierda

Básicamente se trata de orden a la derecha comenzando desde la esquina superior izquierda.

La idea del algoritmo es:

Orden de las esquinas de filas y entonces el orden de las esquinas de pares por cols.

// top-left = 0; top-right = 1; 
// right-bottom = 2; left-bottom = 3; 
List<Point> orderRectCorners(List<Point> corners) {  
    if(corners.size() == 4) {  
     ordCorners = orderPointsByRows(corners); 

     if(ordCorners.get(0).x > ordCorners.get(1).x) { // swap points 
      Point tmp = ordCorners.get(0); 
      ordCorners.set(0, ordCorners.get(1)); 
      ordCorners.set(1, tmp); 
     } 

     if(ordCorners.get(2).x < ordCorners.get(3).x) { // swap points 
      Point tmp = ordCorners.get(2); 
      ordCorners.set(2, ordCorners.get(3)); 
      ordCorners.set(3, tmp); 
     }    
     return ordCorners; 
    }  
    return empty list or something; 
} 

List<Point> orderPointsByRows(List<Point> points) { 
    Collections.sort(points, new Comparator<Point>() { 
     public int compare(Point p1, Point p2) { 
     if (p1.y < p2.y) return -1; 
     if (p1.y > p2.y) return 1; 
     return 0; 
     } 
    }); 
    return points; 
} 

Answer 14

var arr = [{x:3,y:3},{x:4,y:1},{x:0,y:2},{x:5,y:2},{x:1,y:1}]; 
var reference = {x:2,y:2}; 
arr.sort(function(a,b) { 
    var aTanA = Math.atan2((a.y - reference.y),(a.x - reference.x)); 
    var aTanB = Math.atan2((b.y - reference.y),(b.x - reference.x)); 
    if (aTanA < aTanB) return -1; 
    else if (aTanB < aTanA) return 1; 
    return 0; 
}); 
console.log(arr); 

Dónde punto de referencia se encuentra dentro del polígono.

Más información en este site

Answer 15

calcular el área de las coordenadas con la fórmula cordón (desprovisto del valor absoluto de tal manera que la zona puede ser positivo o negativo) por cada puntos permutaciones. Los valores de área máxima parece corresponder a dirigir cuadriláteros simples: Simple direct quadrilaterals found with the shoelace formula

Answer 16

si sólo tiene que lidiar con 4 puntos, entonces hay una manera más fácil de hacer que

1. especie por el valor y

2. fila superior son los dos primeros puntos, fila inferior es el resto 2 puntos

3. para la parte superior y la fila inferior, ordenarlos por valor de x

.

corners.sort(key=lambda ii: ii[1], reverse=True) 
topRow = corners[0:2] 
bottomRow = corners[2:] 

topRow.sort(key=lambda ii: ii[0]) 
bottomRow.sort(key=lambda ii: ii[0]) 
# clockwise 
return [topRow[0], topRow[1], bottomRow[1], bottomRow[0]]