Ordenar los puntos en el sentido de las agujas del reloj?

Dado un conjunto de puntos x, y, ¿cómo puedo ordenar los puntos de esta matriz en el sentido de las agujas del reloj (alrededor de su punto central promedio general)? Mi objective es pasar los puntos a una función de creación de línea para terminar con algo que parece más bien “sólido”, tan convexo como sea posible sin líneas que se cruzan.

Por lo que vale, estoy usando Lua, pero cualquier pseudocódigo sería apreciado. ¡Muchas gracias por cualquier ayuda!

Actualización: como referencia, este es el código Lua basado en la excelente respuesta de Ciamej (ignore mi prefijo de “aplicación”):

function appSortPointsClockwise(points) local centerPoint = appGetCenterPointOfPoints(points) app.pointsCenterPoint = centerPoint table.sort(points, appGetIsLess) return points end function appGetIsLess(a, b) local center = app.pointsCenterPoint if ax >= 0 and bx  by end local det = (ax - center.x) * (by - center.y) - (bx - center.x) * (ay - center.y) if det  0 then return false end local d1 = (ax - center.x) * (ax - center.x) + (ay - center.y) * (ay - center.y) local d2 = (bx - center.x) * (bx - center.x) + (by - center.y) * (by - center.y) return d1 > d2 end function appGetCenterPointOfPoints(points) local pointsSum = {x = 0, y = 0} for i = 1, #points do pointsSum.x = pointsSum.x + points[i].x; pointsSum.y = pointsSum.y + points[i].y end return {x = pointsSum.x / #points, y = pointsSum.y / #points} end 

Primero, calcule el punto central. Luego, clasifique los puntos usando el algoritmo de clasificación que desee, pero use una rutina de comparación especial para determinar si un punto es menor que el otro.

Puede verificar si un punto (a) está a la izquierda o a la derecha del otro (b) en relación con el centro con este simple cálculo:

 det = (ax - center.x) * (by - center.y) - (bx - center.x) * (ay - center.y) 

si el resultado es cero, entonces están en la misma línea desde el centro, si es positivo o negativo, entonces está en un lado u otro, de modo que un punto precederá al otro. Utilizándolo, puede construir una relación menor que la de comparar puntos y determinar el orden en que deberían aparecer en la matriz ordenada. Pero tiene que definir dónde está el comienzo de ese orden, quiero decir qué ángulo será el de partida (por ejemplo, la mitad positiva del eje x).

El código para la función de comparación puede verse así:

 bool less(point a, point b) { if (ax - center.x >= 0 && bx - center.x < 0) return true; if (ax - center.x < 0 && bx - center.x >= 0) return false; if (ax - center.x == 0 && bx - center.x == 0) { if (ay - center.y >= 0 || by - center.y >= 0) return ay > by; return by > ay; } // compute the cross product of vectors (center -> a) x (center -> b) int det = (ax - center.x) * (by - center.y) - (bx - center.x) * (ay - center.y); if (det < 0) return true; if (det > 0) return false; // points a and b are on the same line from the center // check which point is closer to the center int d1 = (ax - center.x) * (ax - center.x) + (ay - center.y) * (ay - center.y); int d2 = (bx - center.x) * (bx - center.x) + (by - center.y) * (by - center.y); return d1 > d2; } 

Esto ordenará los puntos en sentido horario a partir de las 12 en punto. Los puntos en la misma “hora” se ordenarán a partir de los que están más alejados del centro.

Si usa tipos enteros (que no están realmente presentes en Lua), debe asegurarse de que las variables det, d1 y d2 sean de un tipo que pueda contener el resultado de los cálculos realizados.

Si quieres lograr algo que se vea sólido, lo más convexo posible, entonces supongo que estás buscando un casco convexo . Puede calcularlo usando Graham Scan . En este algoritmo, también debe ordenar los puntos en el sentido de las agujas del reloj (o en sentido antihorario) comenzando desde un punto de pivote especial. Luego, repite simples pasos de bucle cada vez que comprueba si gira hacia la izquierda o hacia la derecha para agregar nuevos puntos al casco convexo, esta comprobación se basa en un producto cruzado como en la función de comparación anterior.

Editar:

Se agregó una statement if (ay - center.y >= 0 || by - center.y >=0) más si if (ay - center.y >= 0 || by - center.y >=0) para asegurarse de que los puntos que tienen x = 0 y negativo y se ordenan comenzando por los que están más lejos del centrar. Si no le importa el orden de los puntos en la misma “hora”, puede omitir esta statement if y siempre devolver ay > by .

Se corrigió la primera instrucción if con la adición de -center.x y -center.y .

Se agregó la segunda instrucción if (ax - center.x < 0 && bx - center.x >= 0) . Era un descuido obvio que faltaba. Las sentencias if se pueden reorganizar ahora porque algunas comprobaciones son redundantes. Por ejemplo, si la primera condición en la primera statement if es falsa, entonces la primera condición de la segunda if debe ser verdadera. Decidí, sin embargo, dejar el código como está por simplicidad. Es muy posible que el comstackdor optimice el código y produzca el mismo resultado de todos modos.

Lo que estás pidiendo es un sistema conocido como coordenadas polares . La conversión de coordenadas cartesianas a coordenadas polares se realiza fácilmente en cualquier idioma. Las fórmulas se pueden encontrar en esta sección .

No sé Lua, pero esta página parece ofrecer fragmentos de código para esta conversión.

Después de convertir a coordenadas polares, solo ordena por el ángulo, theta.

Un enfoque alternativo interesante para su problema sería encontrar el mínimo aproximado al Problema del Vendedor Viajero (TSP), es decir. la ruta más corta que une todos tus puntos. Si sus puntos forman una forma convexa, debería ser la solución correcta, de lo contrario, debería verse bien (una forma “sólida” se puede definir como una que tiene una relación de perímetro / área baja, que es lo que estamos optimizando aquí) .

Puede utilizar cualquier implementación de un optimizador para el TSP, de la cual estoy bastante seguro de que puede encontrar una tonelada en el idioma de su elección.

Otra versión (devuelve true si a viene antes de b en sentido antihorario):

  bool lessCcw(const Vector2D &center, const Vector2D &a, const Vector2D &b) const { // Computes the quadrant for a and b (0-3): // ^ // 1 | 0 // ---+--> // 2 | 3 const int dax = ((ax() - center.x()) > 0) ? 1 : 0; const int day = ((ay() - center.y()) > 0) ? 1 : 0; const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) < < 1); /* The previous computes the following: const int qa = ( (ax() > center.x()) ? ((ay() > center.y()) ? 0 : 3) : ((ay() > center.y()) ? 1 : 2)); */ const int dbx = ((bx() - center.x()) > 0) ? 1 : 0; const int dby = ((by() - center.y()) > 0) ? 1 : 0; const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) < < 1); if (qa == qb) { return (bx() - center.x()) * (ay() - center.y()) < (by() - center.y()) * (ax() - center.x()); } else { return qa < qb; } } 

Esto es más rápido, porque el comstackdor (probado en Visual C ++ 2015) no genera salto para calcular dax, day, dbx, dby. Aquí el ensamblaje de salida del comstackdor:

 ; 28 : const int dax = ((ax() - center.x()) > 0) ? 1 : 0; vmovss xmm2, DWORD PTR [ecx] vmovss xmm0, DWORD PTR [edx] ; 29 : const int day = ((ay() - center.y()) > 0) ? 1 : 0; vmovss xmm1, DWORD PTR [ecx+4] vsubss xmm4, xmm0, xmm2 vmovss xmm0, DWORD PTR [edx+4] push ebx xor ebx, ebx vxorps xmm3, xmm3, xmm3 vcomiss xmm4, xmm3 vsubss xmm5, xmm0, xmm1 seta bl xor ecx, ecx vcomiss xmm5, xmm3 push esi seta cl ; 30 : const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) < < 1); mov esi, 2 push edi mov edi, esi ; 31 : ; 32 : /* The previous computes the following: ; 33 : ; 34 : const int qa = ; 35 : ( (ax() > center.x()) ; 36 : ? ((ay() > center.y()) ? 0 : 3) ; 37 : : ((ay() > center.y()) ? 1 : 2)); ; 38 : */ ; 39 : ; 40 : const int dbx = ((bx() - center.x()) > 0) ? 1 : 0; xor edx, edx lea eax, DWORD PTR [ecx+ecx] sub edi, eax lea eax, DWORD PTR [ebx+ebx] and edi, eax mov eax, DWORD PTR _b$[esp+8] sub edi, ecx sub edi, ebx add edi, esi vmovss xmm0, DWORD PTR [eax] vsubss xmm2, xmm0, xmm2 ; 41 : const int dby = ((by() - center.y()) > 0) ? 1 : 0; vmovss xmm0, DWORD PTR [eax+4] vcomiss xmm2, xmm3 vsubss xmm0, xmm0, xmm1 seta dl xor ecx, ecx vcomiss xmm0, xmm3 seta cl ; 42 : const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) < < 1); lea eax, DWORD PTR [ecx+ecx] sub esi, eax lea eax, DWORD PTR [edx+edx] and esi, eax sub esi, ecx sub esi, edx add esi, 2 ; 43 : ; 44 : if (qa == qb) { cmp edi, esi jne SHORT $LN37@lessCcw ; 45 : return (bx() - center.x()) * (ay() - center.y()) < (by() - center.y()) * (ax() - center.x()); vmulss xmm1, xmm2, xmm5 vmulss xmm0, xmm0, xmm4 xor eax, eax pop edi vcomiss xmm0, xmm1 pop esi seta al pop ebx ; 46 : } else { ; 47 : return qa < qb; ; 48 : } ; 49 : } ret 0 $LN37@lessCcw: pop edi pop esi setl al pop ebx ret 0 ?lessCcw@@YA_NABVVector2D@@00@Z ENDP ; lessCcw 

Disfrutar.