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

156

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

Philipp Lenssen
źródło
1
Pomyśl o obliczeniu kąta linii promieniowej przechodzącej przez ten punkt. Następnie posortuj według kąta.
Prezydent James K. Polk
Jeśli nie wiesz, lua ma wbudowaną funkcję, ipairs(tbl)która iteruje po indeksach i wartościach tbl od 1 do #tbl. Więc do obliczenia sumy, można to, co większość ludzi patrzy czystsze zrobić:for _, p in ipairs(points) do pointsSum.x = pointsSum.x + p.x; pointsSum.y = pointsSum.y + p.y end
Ponkadoodle
2
@Wallacoloo To bardzo dyskusyjne. Również w wanilii Lua ipairsjest znacznie wolniejsza niż numeryczna pętla for.
Alexander Gladysh
Musiałem wprowadzić kilka drobnych zmian, aby działał w moim przypadku (wystarczy porównać dwa punkty względem środka). gist.github.com/personalnadir/6624172 Wszystkie te porównania do 0 w kodzie wydają się zakładać, że punkty są rozmieszczone wokół początku, w przeciwieństwie do dowolnego punktu. Myślę też, że pierwszy warunek niepoprawnie posortuje punkty poniżej punktu środkowego. Dzięki za kod, był naprawdę pomocny!
personalnadir

Odpowiedzi:

192

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.

ciamej
źródło
25
+1: Nie atan(), bez pierwiastka kwadratowego, a nawet bez podziałów. To dobry przykład myślenia o grafice komputerowej. Usuń wszystkie łatwe przypadki tak szybko, jak to możliwe, a nawet w trudnych przypadkach obliczaj jak najmniej, aby znać wymaganą odpowiedź.
RBerteig
Ale wymaga porównania wszystkich punktów ze wszystkimi innymi. Czy istnieje prosta metoda wstawiania nowych punktów?
Iterator
2
jeśli zbiór punktów jest znany a priori, wymaga tylko porównań O (n * log n). Jeśli chcesz w międzyczasie dodać punkty, musisz przechowywać je w posortowanym zestawie, takim jak zrównoważone drzewo wyszukiwania binarnego. W takim przypadku dodanie nowego punktu wymaga porównań O (log n) i jest dokładnie to samo dla rozwiązania ze współrzędnymi biegunowymi.
ciamej
2
Czy ten przypadek nie istnieje: jeśli (ax - center.x <0 && bx - center.x> = 0) return false;
Tom Martin
2
No hej. Jest dość stary, ale: „Spowoduje to uporządkowanie punktów zgodnie z ruchem wskazówek zegara, począwszy od godziny 12”. Dlaczego godzina dwunasta i jak mogę zmienić ją na szóstą? Czy ktoś może mi powiedzieć?
Ismoh
20

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.

static_rtti
źródło
Yikes. „Ciekawe” to mało powiedziane. :)
Iterator
@Iterator: Byłem bardzo zadowolony z mojego pomysłu, byłem dość rozczarowany, że zostałem za niego odrzucony: - / Czy uważasz, że jest ważny?
static_rtti,
1
Sugerowałem użycie jednego z wielu szybkich przybliżeń, a nie oczywiście oryginalnego algorytmu NP-zupełnego.
static_rtti
6
Doceniam dodatkowy kąt! Posiadanie kilku ważnych, choć bardzo różnych odpowiedzi, może być bardzo pomocne, jeśli ktoś w przyszłości natknie się na ten wątek, szukając opcji burzy mózgów.
Philipp Lenssen,
1
Zwróć uwagę, że moje podejście jest prawdopodobnie wolniejsze, ale bardziej poprawne w złożonych przypadkach: wyobraź sobie na przykład przypadek, w którym punkty za „8”. Współrzędne biegunowe nie pomogą Ci w tym przypadku, a wynik, który uzyskasz, będzie w dużej mierze zależał od wybranego środka. Rozwiązanie TSP jest niezależne od jakichkolwiek parametrów „heurystycznych”.
static_rtti
19

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.

Iterator
źródło
4
To zadziała, ale będzie również miało wadę wykonywania większej liczby obliczeń niż potrzeba, aby odpowiedzieć na pytanie dotyczące zamówienia. W praktyce nie obchodzą cię rzeczywiste kąty ani odległości promieniowe, a jedynie ich względna kolejność. Rozwiązanie Ciameja jest lepsze, ponieważ unika podziałów, pierwiastków kwadratowych i trygonometrii.
RBerteig
1
Nie jestem pewien, jakie jest Twoje kryterium „lepszego”. Na przykład porównywanie wszystkich punktów ze sobą jest marnotrawstwem obliczeń. Trig nie jest czymś, co przeraża dorosłych, prawda?
Iterator
3
Nie chodzi o to, że trygon jest przerażający. Problem polega na tym, że obliczenia triggera są drogie i nie były potrzebne do określenia względnej kolejności kątów. Podobnie, nie musisz brać pierwiastków kwadratowych, aby uporządkować promienie. Pełna konwersja ze współrzędnych kartezjańskich na biegunowe spowoduje wykonanie zarówno stycznej łuku, jak i pierwiastka kwadratowego. Dlatego twoja odpowiedź jest poprawna, ale w kontekście grafiki komputerowej lub geometrii obliczeniowej prawdopodobnie nie będzie to najlepszy sposób .
RBerteig
Rozumiem. Jednak OP nie opublikował jako comp-geo, to był tag kogoś innego. Mimo to wygląda na to, że drugie rozwiązanie jest wielomianem w liczbie punktów, czy się mylę? Jeśli tak, to spala więcej cykli niż tryg.
Iterator
Właściwie nie zauważyłem tagu comp-geo, po prostu założyłem, że jedynymi racjonalnymi zastosowaniami dla tego pytania musi być jedno lub drugie. W końcu kwestia wydajności staje się dyskusyjna, jeśli jest tylko kilka punktów i / lub operacja będzie wykonywana rzadko. W tym momencie ważna staje się wiedza, jak to zrobić, i dlatego zgadzam się, że twoja odpowiedź jest poprawna. Wyjaśnia, jak obliczyć pojęcie „porządku zgodnego z ruchem wskazówek zegara” w terminach, które można wyjaśnić prawie każdemu.
RBerteig
3

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

AGPX
źródło
1
Dwie instrukcje return w przełączniku są matematycznie równoważne. Czy jest powód, dla którego warto mieć przełącznik?
unagi
0
  • 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

Pavan
źródło