Sortuj punkty w kolejności zgodnej z ruchem wskazówek zegara?

Biorąc pod uwagę tablicę punktów x, y, jak posortować punkty tej tablicy w kolejności zgodnej z ruchem wskazówek zegara (wokół ich ogólnego średniego punktu środkowego)? Moim celem jest przekazanie punktów do funkcji tworzenia linii, tak aby otrzymać coś, co wygląda raczej na „solidne”, jak najbardziej wypukłe, bez przecinania się linii.

Co jest warte, używam Lua, ale każdy pseudokod byłby doceniony.

Aktualizacja: dla porównania, oto kod Lua oparty na doskonałej odpowiedzi Ciamej (zignoruj ​​mój prefiks „aplikacja”):

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

Najpierw oblicz punkt środkowy. Następnie posortuj punkty za pomocą dowolnego algorytmu sortowania, ale użyj specjalnej procedury porównywania, aby określić, czy jeden punkt jest mniejszy od drugiego.

Możesz sprawdzić, czy jeden punkt (a) znajduje się na lewo czy na prawo od drugiego (b) w stosunku do środka, wykonując to proste obliczenie:

det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)

jeśli wynik wynosi zero, to znajdują się w tej samej linii od środka, jeśli jest dodatni lub ujemny, to jest po jednej lub drugiej stronie, więc jeden punkt będzie poprzedzał drugi. Używając go, możesz skonstruować relację mniej niż w celu porównania punktów i określenia kolejności, w jakiej powinny się pojawiać w posortowanej tablicy. Ale musisz zdefiniować, gdzie jest początek tego porządku, czyli jaki kąt będzie początkowy (np. Dodatnia połowa osi x).

Kod funkcji porównania może wyglądać następująco:

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

Spowoduje to uporządkowanie punktów zgodnie z ruchem wskazówek zegara, zaczynając od godziny 12. Punkty z tej samej „godziny” zostaną uporządkowane zaczynając od tych, które są dalej od centrum.

Jeśli używasz typów całkowitych (które tak naprawdę nie są obecne w Lua), musisz upewnić się, że zmienne det, d1 i d2 są typu, który będzie w stanie przechowywać wyniki przeprowadzonych obliczeń.

Jeśli chcesz uzyskać coś, co wygląda na solidne, tak wypukłe, jak to tylko możliwe, myślę, że szukasz wypukłego kadłuba . Możesz to obliczyć za pomocą programu Graham Scan . W tym algorytmie musisz także posortować punkty zgodnie z ruchem wskazówek zegara (lub przeciwnie do ruchu wskazówek zegara), zaczynając od specjalnego punktu obrotu. Następnie powtarzasz proste kroki pętli za każdym razem sprawdzając, czy skręcasz w lewo czy w prawo dodając nowe punkty do wypukłego kadłuba, to sprawdzenie opiera się na iloczynu krzyżowym, tak jak w powyższej funkcji porównania.

Edytować:

Dodano jeszcze jedną instrukcję if, if (a.y - center.y >= 0 || b.y - center.y >=0)aby upewnić się, że punkty, które mają x = 0 i ujemne y są sortowane, zaczynając od tych, które są dalej od środka. Jeśli nie zależy Ci na kolejności punktów w tej samej „godzinie” możesz pominąć to oświadczenie if i zawsze zwracać a.y > b.y.

Poprawiono pierwsze instrukcje if z dodaniem -center.xi -center.y.

Dodano drugą instrukcję if (a.x - center.x < 0 && b.x - center.x >= 0). To było oczywiste przeoczenie, że go brakowało. Instrukcje if można teraz zreorganizować, ponieważ niektóre kontrole są zbędne. Na przykład, jeśli pierwszy warunek w pierwszej instrukcji if jest fałszywy, to pierwszy warunek drugiej instrukcji if musi być prawdziwy. Postanowiłem jednak pozostawić kod tak, jak jest dla uproszczenia. Jest całkiem możliwe, że kompilator zoptymalizuje kod i i tak da ten sam wynik.

Ciekawym alternatywnym podejściem do twojego problemu byłoby znalezienie przybliżonego minimum do problemu komiwojażera (TSP), tj. najkrótsza trasa łącząca wszystkie Twoje punkty. Jeśli twoje punkty tworzą wypukły kształt, powinno to być właściwe rozwiązanie, w przeciwnym razie powinno nadal dobrze wyglądać (kształt „pełny” można zdefiniować jako taki, który ma niski stosunek obwodu do powierzchni, co tutaj optymalizujemy) .

Możesz użyć dowolnej implementacji optymalizatora dla TSP, a jestem pewien, że znajdziesz ich mnóstwo w wybranym przez siebie języku.

To, o co prosisz, to układ znany jako współrzędne biegunowe . Konwersję ze współrzędnych kartezjańskich na biegunowe można łatwo przeprowadzić w dowolnym języku. Formuły można znaleźć w tej sekcji .

Po przeliczeniu na współrzędne biegunowe posortuj dane według kąta theta.

Inna wersja (zwraca prawdę, jeśli a występuje przed b w kierunku przeciwnym do ruchu wskazówek zegara):

    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) {
            return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());
        } else {
            return qa < qb;
       } 
    }

Jest to szybsze, ponieważ kompilator (testowany na Visual C ++ 2015) nie generuje skoku do obliczeń dax, day, dbx, dby. Tutaj zestaw wyjściowy z kompilatora:

; 28   :    const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;

    vmovss  xmm2, DWORD PTR [ecx]
    vmovss  xmm0, DWORD PTR [edx]

; 29   :    const int day = ((a.y() - 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   :        (   (a.x() > center.x())
; 36   :         ? ((a.y() > center.y()) ? 0 : 3)
; 37   :         : ((a.y() > center.y()) ? 1 : 2));
; 38   :    */
; 39   : 
; 40   :    const int dbx = ((b.x() - 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 = ((b.y() - 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 (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - 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

Cieszyć się.

• wektor3 a = nowy wektor3 (1, 0, 0) .............. w osi X_
• vector3 b = any_point - Centrum;

- y = |a * b|   ,   x =  a . b

- Atan2(y , x)...............................gives angle between -PI  to  + PI  in radians
- (Input % 360  +  360) % 360................to convert it from  0 to 2PI in radians
- sort by adding_points to list_of_polygon_verts by angle  we got 0  to 360

Wreszcie otrzymujesz posortowane verts Anticlockwize

list.Reverse () .................. Clockwise_order