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.