algorithm - sentido - porque las manillas del reloj giran siempre a la derecha

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

Question

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 objetivo 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 a.x >= 0 and b.x < 0 then return true
elseif a.x == 0 and b.x == 0 then return a.y > b.y
end
local det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
if det < 0 then return true
elseif det > 0 then return false
end
local d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)
local d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - 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

Answer 1

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.

Answer 2

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 = ((a.x() - center.x()) > 0) ? 1 : 0;
const int day = ((a.y() - center.y()) > 0) ? 1 : 0;
const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);
/* The previous computes the following:
const int qa =
( (a.x() > center.x())
? ((a.y() > center.y())
? 0 : 3)
: ((a.y() > center.y())
? 1 : 2)); */
const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;
const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;
const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);
if (qa == qb)
{
switch (qa)
{
case 0:
case 3:
return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());
default:
return (center.x() - b.x()) * (a.y() - center.y()) > (b.y() - center.y()) * (center.x() - a.x());
}
}
else
{
return qa < qb;
}
}

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

; 345 : const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;
mov eax, DWORD PTR _center$[esp-4]
xor edx, edx
push ebx
push ebp
push esi
mov esi, DWORD PTR _a$[esp+8]
; 346 : const int day = ((a.y() - center.y()) > 0) ? 1 : 0;
; 347 : const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);
mov ebp, 2
vmovsd xmm3, QWORD PTR [eax]
vmovsd xmm1, QWORD PTR [eax+8]
vxorpd xmm2, xmm2, xmm2
vmovsd xmm0, QWORD PTR [esi]
vsubsd xmm6, xmm0, xmm3
vmovsd xmm0, QWORD PTR [esi+8]
vcomisd xmm6, xmm2
vsubsd xmm4, xmm0, xmm1
seta dl
xor ecx, ecx
vcomisd xmm4, xmm2
push edi
seta cl
mov edi, ebp
; 348 : /*const int qa =
; 349 : ( (a.x() > center.x())
; 350 : ? ((a.y() > center.y())
; 351 : ? 0 : 3)
; 352 : : ((a.y() > center.y())
; 353 : ? 1 : 2));*/
; 354 : const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;
xor ebx, ebx
lea eax, DWORD PTR [ecx+ecx]
sub edi, eax
lea eax, DWORD PTR [edx+edx]
and edi, eax
sub edi, ecx
sub edi, edx
mov edx, DWORD PTR _b$[esp+12]
add edi, ebp
vmovsd xmm0, QWORD PTR [edx]
vsubsd xmm7, xmm0, xmm3
; 355 : const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;
vmovsd xmm0, QWORD PTR [edx+8]
vcomisd xmm7, xmm2
vsubsd xmm5, xmm0, xmm1
seta bl
xor ecx, ecx
vcomisd xmm5, xmm2
seta cl
; 356 : const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);
lea eax, DWORD PTR [ecx+ecx]
sub ebp, eax
lea eax, DWORD PTR [ebx+ebx]
and ebp, eax
sub ebp, ecx
sub ebp, ebx
add ebp, 2
; 357 : /*const int qb =
; 358 : ((b.x() > center.x())
; 359 : ? ((b.y() > center.y())
; 360 : ? 0 : 3)
; 361 : : ((b.y() > center.y())
; 362 : ? 1 : 2));*/
; 363 : if (qa == qb)
cmp edi, ebp
jne SHORT $LN57@lessCw
; 364 : {
; 365 : switch (qa)
test edi, edi
je SHORT $LN6@lessCw
cmp edi, 3
je SHORT $LN6@lessCw
; 370 : default:
; 371 : return (center.x() - b.x()) * (a.y() - center.y()) > (b.y() - center.y()) * (center.x() - a.x());
vsubsd xmm0, xmm3, QWORD PTR [edx]
vmulsd xmm1, xmm0, xmm4
vsubsd xmm0, xmm3, QWORD PTR [esi]
pop edi
vmulsd xmm0, xmm0, xmm5
xor eax, eax
pop esi
vcomisd xmm1, xmm0
pop ebp
seta al
pop ebx
; 372 : }
; 373 : }
; 374 : else
; 375 : {
; 376 : return qa < qb;
; 377 : }
; 378 : }
ret 12 ; 0000000cH
$LN6@lessCw:
pop edi
; 366 : {
; 367 : case 0:
; 368 : case 3:
; 369 : return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());
vmulsd xmm1, xmm7, xmm4
vmulsd xmm0, xmm5, xmm6
xor eax, eax
pop esi
vcomisd xmm0, xmm1
pop ebp
seta al
pop ebx
; 372 : }
; 373 : }
; 374 : else
; 375 : {
; 376 : return qa < qb;
; 377 : }
; 378 : }
ret 12 ; 0000000cH
$LN57@lessCw:
pop edi
pop esi
pop ebp
setl al
pop ebx
ret 12 ; 0000000cH

Disfrutar.

Answer 3

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 = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - 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 (a.x - center.x >= 0 && b.x - center.x < 0)
return true;
if (a.x - center.x < 0 && b.x - center.x >= 0)
return false;
if (a.x - center.x == 0 && b.x - center.x == 0) {
if (a.y - center.y >= 0 || b.y - center.y >= 0)
return a.y > b.y;
return b.y > a.y;
}
// compute the cross product of vectors (center -> a) x (center -> b)
int det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - 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 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
int d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - 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 declaración 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 declaración 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 declaración 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 compilador optimice el código y produzca el mismo resultado de todos modos.

Answer 4

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.