Clasificación de matriz de puntos en el sentido de las agujas del reloj

16

¿Existe tal algoritmo para ordenar una matriz de puntos 2D en el sentido de las agujas del reloj?
Estoy tratando específicamente con el triángulo rectángulo en mi caso, así que solo 3 puntos.

Sin embargo, estoy interesado en saber si existe dicho algoritmo, si no, ¿cuál es una manera simple de devolver los 3 puntos de mi triángulo en el sentido de las agujas del reloj?

Editar: estoy tratando de calcular los puntos en el sentido de las agujas del reloj en relación con el centroide del polígono, que es convexo.

Actualización: Esta es la implementación que terminé usando según la respuesta elegida, no es crítica para el rendimiento y solo ocurre de vez en cuando, así que funciona.

ArrayList<PVector> pointList = new ArrayList<PVector>();
pointList.add(A);
pointList.add(B);
pointList.add(C);
Collections.sort( pointList, new TriangleVectorComparator(origin) );

return pointList;

// Comparator
package triangleeditor;

import java.util.Comparator;

import processing.core.PVector;

public class TriangleVectorComparator implements Comparator<PVector>  {
    private PVector M; 
    public TriangleVectorComparator(PVector origin) {
        M = origin;
    }

    public int compare(PVector o1, PVector o2) {
        double angle1 = Math.atan2(o1.y - M.y, o1.x - M.x);
        double angle2 = Math.atan2(o2.y - M.y, o2.x - M.x);

        //For counter-clockwise, just reverse the signs of the return values
        if(angle1 < angle2) return 1;
        else if (angle2 < angle1) return -1;
        return 0;
    }

}
onedayitwillmake
fuente
1
retorno puede ser retorno angle1 <angle2? 1: ángulo2> ángulo1? -1: 0;
ademar111190
2
Se puede expresar de muchas maneras, pero tiendo a evitar operadores ternarios anidados, especialmente al dar ejemplos.
onedayitwillmake
@onedayitwillmake ¿Podría mover el código que terminó usando en una respuesta? Realmente no pertenece a la pregunta, pero es muy valioso para los futuros lectores.
Anko
@ Annko Creo que tienes razón, pero al mismo tiempo creo que será más fácil para las personas encontrarlo de esta manera. También ayuda a asegurarme de no quitar la respuesta de samhocevar en la que se basa la mía.
onedayitwillmake

Respuestas:

19

Tu pregunta no es lo suficientemente precisa. Un conjunto de puntos es solo «en sentido horario» o «en sentido antihorario» en relación con un punto de referencia. De lo contrario, cualquier conjunto de tres puntos siempre puede ser CW o CCW. Vea la siguiente imagen: a la izquierda, los puntos están ordenados en sentido horario; a la derecha, los mismos puntos exactos se ordenan en sentido antihorario.

en sentido horario o antihorario

En su caso, creo que usar el baricentro de los puntos como punto de referencia es razonable.

Un buen método para un número desconocido de puntos podría ser el siguiente:

  • deja P[0], P[1], ... P[n-1]ser la lista de puntos para ordenar
  • deja que M sea el baricentro de todos los puntos
  • calcular de a[0], a[1], ... a[n-1]tal maneraa[i] = atan2(P[i].y - M.y, P[i].x - M.x);
  • ordenar puntos relativos a su avalor, utilizando qsortpor ejemplo.

Sin embargo, puede estar seguro de que un buen algoritmo de clasificación funcionará mal con tres valores de entrada en comparación con un método ad-hoc. El uso atan2sigue siendo válido, pero simplemente no lo use qsort.

sam hocevar
fuente
Esto funcionó perfectamente :)
onedayitwillmake
1
¿Este método tiene un nombre?
onedayitwillmake
1
Creo que esto simplemente se llama «ordenar por ángulo polar». Es un componente del Graham Scan , por ejemplo.
sam hocevar
El éxito de rendimiento de qsortaquí es pequeño en comparación con atan2.
Pequeña advertencia: esto podría bloquearse y quemarse (dependiendo del lenguaje de programación y las bibliotecas utilizadas) si alguno de los puntos está exactamente en el baricentro (o cualquier otro punto de orientación que utilice). Es posible que desee excluir dichos puntos entre el segundo y el tercer paso.
Martin Sojka
3

Creo que lo que realmente estás preguntando aquí es el orden de giro del triángulo, que en realidad es bastante simple de probar.

Como solo hay tres puntos en su triángulo, su triángulo ya está en el sentido horario o antihorario, por lo que todo lo que necesita hacer es verificar cuál de esos dos es, e invertir el orden de los índices si el devanado no es el que quieres

Aquí está la idea general, suponiendo que los tres vértices de un triángulo son una , b , y c , y que tiene una simple operación de sustracción de vectores:

Vector2 AToB = b - a;
Vector2 BToC = c - b;
float crossz = AToB.x * BToC.y - AToB.y * BToC.x;
if ( crossz > 0.0f )
{
  // clockwise
}
else
{
  // counter-clockwise.  Need to reverse the order of our vertices.
}

Tenga en cuenta que dependiendo de la forma en que haya orientado su eje + y (arriba o abajo), los casos "en sentido horario" y "en sentido antihorario" pueden revertirse de la forma en que los he etiquetado en los comentarios en este código de muestra.

Trevor Powell
fuente
Necesito pasar estos puntos a Box2D (implementación de Java) para crear un polígono. aunque no es lo que estaba preguntando, muy buena idea :)
onedayitwillmake
2

¿Puedes dar más información? Desea el orden de los puntos CCW, pero ¿qué punto debería ser el centro del orden?

Si solo tiene un triángulo (3 puntos) en el plano, puede calcular el determinante a partir de la matriz, donde las líneas son coordenadas de puntos (la tercera coordenada es 1). Si el determinante es> 0, los puntos están en orden CCW. Si no, puede cambiar por ejemplo los últimos dos puntos y obtendrá el orden CCW.

Si tiene los puntos A, B, C, entonces su matriz se ve así:

|xA, yA, 1|
|xB, yB, 1|
|xC, yC, 1|

El determinante es: xA * yB + xB * yC + xC * yA - yB * xC - yC * xA - yA * xB. Entonces puedes compararlo con cero. Si es> 0, devuelve los puntos A, B, C, si no lo es, devuelve A, C, B.

Si tiene un conjunto de puntos y sabe que forman un polígono convexo (todos son parte del casco convexo) y desea obtener su orden, puede usar Graham Scan o Jarvis's March (estos son algoritmos para encontrar el casco convexo desde muchos puntos, pero También debería funcionar aquí :))

zacharmarz
fuente
para completar lo que dijo zacharmarz si solo desea ordenar sus puntos en el sentido de las agujas del reloj alrededor de un punto específico, puede crear una matriz a partir de pares de flotador y punto en el que almacene todos los puntos con su ángulo correspondiente desde ese punto específico, y luego ordenar Esa matriz.
Ali1S232