algorithm graphics sorting geometry

algorithm - Ordenar cuatro puntos en sentido horario



graphics sorting (16)

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

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.

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:

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

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

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.

ps: Esto podría ser excesivo para 4 puntos, pero si el número de puntos aumenta podría ser interesante

La respuesta de Wedge es correcta.

Para implementarlo fácilmente, creo lo mismo que smacl: necesitas encontrar el centro del límite 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, disminuya 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 (trabajó para mí de esa manera).

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

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

Mi problema era ordenar las esquinas rectangulares en el siguiente orden:

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

Básicamente es orden en el sentido de las agujas del reloj comenzando desde la esquina superior izquierda.

La idea para el algoritmo es:

Ordene las esquinas por filas y luego ordene pares de esquinas 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; }

Si quieres tomar una perspectiva más matemática, podemos considerar las permutaciones de 4 puntos

En nuestro caso, hay 4 permutaciones que están 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 a una de estas formas con 0 o 1 swaps. (Solo consideraré las permutaciones que comiencen con A, ya que son simétricas)

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

Por lo tanto, solo se necesita un intercambio, 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 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 verificar dos triángulos más: si el ACD está en el sentido de las agujas del reloj, 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 antihorario de manera similar.

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

Si sus puntos no son convexos, encontrará el punto interno, clasifique el resto y luego agréguelo 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.

Tengo una mejora adicional para agregar a mi respuesta anterior

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

  1. A B C D
  2. ABDC
  3. ACBD
  4. ACDB
  5. ADBC
  6. ADCB

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

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

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

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

Finalmente, debemos verificar ACD e intercambiar C & D si ACD es antihorario. 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 controles cada vez y más de un intercambio; pero el código sería mucho más simple.

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, 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, solo es cuestión de ordenar las coordenadas por á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.

Clasificar de modo tal que el ángulo disminuya monótonamente sobre una ventana (o tal que aumente al menos una vez) es un poco diferente.

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

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

  • En el sentido de las agujas del reloj solo tiene sentido con respecto a un origen. Tiendo a pensar en el origen como el centro de gravedad de un conjunto de puntos. Por ejemplo, en el sentido de las agujas del reloj con respecto 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) 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)

  • ¿Tus cuatro puntos ya forman un polígono? Si es así, se trata de verificar e invertir el devanado en lugar de ordenar los puntos, por ejemplo, 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 qué puntos intercambiar;

En el caso de un triángulo (a, b, c), podemos decir que es en el sentido 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.

Recomiendo 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.

si solo tiene que tratar con 4 puntos, entonces hay una manera más fácil de hacerlo

  1. clasificar por valor y

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

  3. para la fila superior e 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]]

si suponemos que el punto x es más grande que el punto y si el ángulo que tiene con el punto (0,0) es mayor, entonces podemos implementarlo 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(); } }

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. (Dado que su polígono es convexo, la única otra alternativa de ''cruce'' es ''CA cruza BD'', lo que significa que los cuatro puntos ya están clasificados). La última orientación ''si'' invierte siempre que sea hacia la izquierda.

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 entiendes la idea.

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