Ordenar cuatro puntos en el orden 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 poner esto formalmente.

Edit: 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 tener una perspectiva más matemática, podemos considerar las permutaciones de 4 puntos

En nuestro caso, hay 4 permutaciones en el sentido de las agujas del reloj

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

Todas las demás permutaciones posibles se pueden convertir en una de estas formas con 0 o 1 swaps. (Solo consideraré permutaciones que comiencen con A, ya que es simétrica)

1. A B C D - hecho
2. A B D C - swap C y D
3. A C B D - swap B y C
4. A C D B - intercambiar A y B
5. A D B C - intercambiar A y D
6. A D C B - intercambiar B y D

Por lo tanto, solo se necesita un intercambio, pero puede tomar algo de trabajo identificar cuál.

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

para distinguir entre estos casos, tenemos que revisar dos triángulos más: si ACD es en el sentido de las agujas del reloj, entonces podemos reducirlo al caso 1, de lo contrario, debemos estar en el caso 2 o 5.

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

Podemos verificar el caso de ABC en sentido contrario a las agujas del reloj de manera similar.

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

Si sus puntos no son convexos, encontrará el punto interior, ordenará el resto y luego lo agregará en cualquier borde. Tenga en cuenta que si el quad es convexo, entonces 4 puntos ya no determinan de forma única el quad, hay 3 quads igualmente válidos.

Answer 2

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

• Clockwise solo tiene sentido con respecto a un origen. Tendría a pensar en el origen como el centro de gravedad de un conjunto de puntos. p.ej. En el sentido de las agujas del reloj en relación con un punto en la posición media de los cuatro puntos, en lugar del posible origen 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) formara 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í, es una cuestión de verificar y revertir el devanado en lugar de ordenar los puntos, por ejemplo. a, b, c, d se convierte en d, c, b, a. De lo contrario, clasificaría según la orientación de unión entre cada punto y el origen, según la respuesta de Wedges.

Editar: con respecto a tus comentarios sobre qué puntos intercambiar;

En el caso de un triángulo (a, b, c), podemos decir que es hacia la derecha si el tercer punto c está en el lado derecho de la línea ab . Utilizo la siguiente función lateral 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 en su conjunto a sentido horario.

Sugiero fuertemente dibujar esto con algunos puntos de muestra, para ver de qué estoy hablando. Tenga en cuenta que tiene una gran cantidad de casos excepcionales con los que lidiar, como polígonos cóncavos, puntos colineales, puntos coincidentes, etc ...

Answer 3

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

Mi problema era tener las esquinas de mis rectángulos ordenadas en el siguiente orden:

  

arriba a la izquierda > arriba a la derecha > abajo a la derecha > abajo a la izquierda

Básicamente es un orden en el sentido de las agujas del reloj a partir de la esquina superior izquierda.

La idea para el algoritmo es:

Ordene las esquinas por filas y luego ordene los pares de esquinas por columnas.

// 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 4

Oliver tiene razón. 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 5

Calcule el área a partir de las coordenadas con la fórmula del cordón de zapato (sin el valor absoluto, de manera que el área puede ser positiva o negativa) para cada permutación de puntos. Los valores de área máxima parecen corresponder a cuadriláteros simples directos: Simples cuadriláteros directos encontrados con la fórmula de cordones de los zapatos

Answer 6

Resuélvelo a lo largo y luego optimízalo.

Un problema más específico sería ordenar las coordenadas al reducir el ángulo con respecto al eje x positivo. Este ángulo, en radianes, estará dado 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

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

La clasificación de tal manera que el ángulo esté disminuyendo monótonamente sobre una ventana (o que aumente a lo sumo una vez) es un poco diferente.

En lugar de una extensa prueba, 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 7

Tengo una mejora adicional que agregar a mi respuesta anterior

recuerda: estos son los casos en los que podemos estar.

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

Si ABC es en sentido antihorario (tiene un área con signo negativo), entonces estamos en los casos 3, 4, 6. Si cambiamos B & amp; C en este caso, entonces nos quedan las siguientes posibilidades:

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

A continuación, podemos verificar ABD e intercambiar B & amp; D si es en sentido contrario a las agujas del reloj (casos 5, 6)

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

Finalmente, debemos verificar ACD e intercambiar C & amp; D si ACD es en sentido antihorario. Ahora sabemos que todos nuestros puntos están en orden.

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

Answer 8

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

Donde el punto de referencia se encuentra dentro del polígono.

Más información en este site

Answer 9

Si solo necesitas lidiar con 4 puntos, hay una forma más fácil de hacerlo

1. ordenar por y valor

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

3. para las filas superior e inferior, ordénelas 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]]

Answer 10

Creo que tienes 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:

• ¿Este conjunto de cuatro puntos es un polígono convexo?
• En caso negativo, ¿qué dos puntos deben intercambiarse?
• ¿Qué dirección es en el sentido de las agujas del reloj?

Tras una reflexión más profunda, creo que la única respuesta a la segunda pregunta anterior es "las dos del medio".

Answer 11

¿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 12

Deberías echar un vistazo a la exploración de Graham. Por supuesto, deberá adaptarlo, ya que se encuentra en los puntos en sentido contrario a las agujas del reloj.

p.s: Esto podría ser una exageración de 4 puntos, pero si el número de puntos aumenta, podría ser interesante

Answer 13

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 'if / elif' trae los cuatro puntos en el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj. (Dado que su polígono es convexo, la otra alternativa de "cruce" es "AC cruza BD", lo que significa que los cuatro puntos ya están ordenados). El último 'if' invierte la orientación siempre que sea en sentido contrario a las agujas del reloj.

Answer 14

si asumimos que el punto x es mayor que el punto y si el ángulo que tiene con el punto (0,0) es mayor, podemos implementar esto 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 15

La respuesta de Wedge & # 8217; s es correcta.

Para implementarlo fácilmente, pienso de la misma manera que smacl: necesitas encontrar el centro de los límites y # 8217; y traducir tus puntos a ese centro.

Me gusta esto:

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

Luego, reduzca centerPointX y centerPointY de cada punto para 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 (funcionó de esa manera).

Answer 16

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

El '>' Es posible que se esté enfrentando de manera incorrecta, pero entiendes la idea.