Punkte im Uhrzeigersinn sortieren?

156

Wie sortiere ich bei einem Array von x- und y-Punkten die Punkte dieses Arrays im Uhrzeigersinn (um ihren durchschnittlichen Gesamtmittelpunkt)? Mein Ziel ist es, die Punkte an eine Linienerstellungsfunktion zu übergeben, um etwas zu erhalten, das ziemlich "solide" aussieht, so konvex wie möglich, ohne dass sich Linien schneiden.

Für das, was es wert ist, benutze ich Lua, aber jeder Pseudocode wäre willkommen.

Update: Als Referenz ist dies der Lua-Code, der auf Ciamejs hervorragender Antwort basiert (ignoriere mein "App" -Präfix):

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
quelle
1
Denken Sie daran, den Winkel der radialen Linie durch diesen Punkt zu berechnen. Dann nach Winkel sortieren.
Präsident James K. Polk
Falls Sie es nicht wussten, hat lua eine eingebaute Funktion ipairs(tbl), die die Indizes und Werte von tbl von 1 bis #tbl durchläuft. Für die for _, p in ipairs(points) do pointsSum.x = pointsSum.x + p.x; pointsSum.y = pointsSum.y + p.y end
Summenberechnung
2
@ Wallacoloo Das ist sehr umstritten. Auch in Vanille ist Lua ipairsdeutlich langsamer als numerisch für Schleife.
Alexander Gladysh
Ich musste einige kleine Änderungen vornehmen, damit es für meinen Fall funktioniert (nur zwei Punkte relativ zu einem Zentrum vergleichen). gist.github.com/personalnadir/6624172 Alle diese Vergleiche mit 0 im Code scheinen davon auszugehen, dass die Punkte im Gegensatz zu einem beliebigen Punkt um den Ursprung verteilt sind. Ich denke auch, dass die erste Bedingung Punkte unterhalb des Mittelpunkts falsch sortiert. Vielen Dank für den Code, er war wirklich hilfreich!
Personalnadir

Antworten:

192

Berechnen Sie zunächst den Mittelpunkt. Sortieren Sie dann die Punkte mit einem beliebigen Sortieralgorithmus. Verwenden Sie jedoch eine spezielle Vergleichsroutine, um festzustellen, ob ein Punkt kleiner als der andere ist.

Mit dieser einfachen Berechnung können Sie überprüfen, ob ein Punkt (a) links oder rechts vom anderen (b) in Bezug auf die Mitte liegt:

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

Wenn das Ergebnis Null ist, befinden sie sich auf derselben Linie von der Mitte. Wenn es positiv oder negativ ist, befindet es sich auf der einen oder anderen Seite, sodass ein Punkt vor dem anderen liegt. Mit dieser Funktion können Sie eine Beziehung erstellen, die kleiner als ist, um Punkte zu vergleichen und die Reihenfolge zu bestimmen, in der sie im sortierten Array angezeigt werden sollen. Aber Sie müssen definieren, wo der Anfang dieser Reihenfolge ist. Ich meine, welcher Winkel der Startwinkel sein wird (z. B. die positive Hälfte der x-Achse).

Der Code für die Vergleichsfunktion kann folgendermaßen aussehen:

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

Dadurch werden die Punkte ab 12 Uhr im Uhrzeigersinn sortiert. Punkte zur selben "Stunde" werden ab denjenigen bestellt, die weiter vom Zentrum entfernt sind.

Wenn Sie ganzzahlige Typen verwenden (die in Lua nicht wirklich vorhanden sind), müssen Sie sicherstellen, dass die Variablen det, d1 und d2 von einem Typ sind, der das Ergebnis der durchgeführten Berechnungen enthalten kann.

Wenn Sie etwas erreichen möchten, das solide und so konvex wie möglich aussieht, dann suchen Sie wahrscheinlich einen konvexen Rumpf . Sie können es mit dem Graham Scan berechnen . In diesem Algorithmus müssen Sie die Punkte auch im Uhrzeigersinn (oder gegen den Uhrzeigersinn) ab einem speziellen Drehpunkt sortieren. Dann wiederholen Sie jedes Mal einfache Schleifenschritte, wenn Sie prüfen, ob Sie nach links oder rechts abbiegen und der konvexen Hülle neue Punkte hinzufügen. Diese Prüfung basiert auf einem Kreuzprodukt wie in der obigen Vergleichsfunktion.

Bearbeiten:

Es wurde eine weitere if-Anweisung hinzugefügt if (a.y - center.y >= 0 || b.y - center.y >=0), um sicherzustellen, dass Punkte mit x = 0 und negativem y beginnend mit denjenigen sortiert werden, die weiter von der Mitte entfernt sind. Wenn Sie sich nicht um die Reihenfolge der Punkte in derselben 'Stunde' kümmern, können Sie diese if-Anweisung weglassen und immer zurückkehren a.y > b.y.

Die ersten if-Anweisungen wurden durch Hinzufügen von -center.xund korrigiert -center.y.

Die zweite if-Anweisung wurde hinzugefügt (a.x - center.x < 0 && b.x - center.x >= 0). Es war ein offensichtliches Versehen, dass es fehlte. Die if-Anweisungen könnten jetzt neu organisiert werden, da einige Überprüfungen redundant sind. Wenn beispielsweise die erste Bedingung in der ersten if-Anweisung falsch ist, muss die erste Bedingung der zweiten if-Anweisung wahr sein. Ich habe mich jedoch der Einfachheit halber entschlossen, den Code so zu belassen, wie er ist. Es ist durchaus möglich, dass der Compiler den Code optimiert und trotzdem das gleiche Ergebnis erzielt.

ciamej
quelle
25
+1: Nein atan(), keine Quadratwurzel und sogar keine Unterteilungen. Dies ist ein gutes Beispiel für Computergrafikdenken. Entfernen Sie alle einfachen Fälle so schnell wie möglich und berechnen Sie selbst in den schwierigen Fällen so wenig wie möglich, um die erforderliche Antwort zu erhalten.
RBerteig
Es erfordert jedoch den Vergleich aller Punkte mit allen anderen. Gibt es eine einfache Methode zum Einfügen neuer Punkte?
Iterator
2
Wenn die Menge der Punkte a priori bekannt ist, werden nur O (n * log n) Vergleiche durchgeführt. Wenn Sie in der Zwischenzeit Punkte hinzufügen möchten, müssen Sie diese in einer sortierten Menge wie einem ausgeglichenen binären Suchbaum aufbewahren. In einem solchen Fall erfordert das Hinzufügen eines neuen Punkts O (log n) -Vergleiche, und dies gilt auch für die Lösung mit Polarkoordinaten.
Ciamej
2
Fehlt dies der Fall: if (ax - center.x <0 && bx - center.x> = 0) return false;
Tom Martin
2
Sie da. Es ist ziemlich alt, aber: "Dadurch werden die Punkte ab 12 Uhr im Uhrzeigersinn sortiert." Warum 12 Uhr und wie kann ich es auf 6 ändern? Kann mir jemand sagen?
Ismoh
20

Ein interessanter alternativer Ansatz für Ihr Problem wäre, das ungefähre Minimum für das Travelling Salesman Problem (TSP) zu finden, d. H. Die kürzeste Route, die alle Ihre Punkte verbindet. Wenn Ihre Punkte eine konvexe Form bilden, sollte dies die richtige Lösung sein, andernfalls sollte sie immer noch gut aussehen (eine "feste" Form kann als eine Form mit einem niedrigen Verhältnis von Umfang zu Fläche definiert werden, die wir hier optimieren). .

Sie können jede Implementierung eines Optimierers für den TSP verwenden, von dem ich mir ziemlich sicher bin, dass Sie eine Tonne in der Sprache Ihrer Wahl finden können.

static_rtti
quelle
Huch. "Interessant" ist eine Untertreibung. :)
Iterator
@Iterator: Ich war ziemlich zufrieden mit meiner Idee, ich war ziemlich enttäuscht, dafür herabgestimmt zu werden: - / Glaubst du, dass sie gültig ist?
static_rtti
1
Ich schlug vor, eine der vielen schnellen Näherungen zu verwenden, natürlich nicht den NP-vollständigen Originalalgorithmus.
static_rtti
6
Ich schätze den zusätzlichen Winkel! Mehrere gültige, wenn auch sehr unterschiedliche Antworten zu haben, kann eine große Hilfe sein, wenn in Zukunft jemand über diesen Thread stolpert und nach Brainstorming-Optionen sucht.
Philipp Lenssen
1
Beachten Sie, dass mein Ansatz wahrscheinlich langsamer ist, aber in komplexen Fällen korrekter: Stellen Sie sich den Fall vor, in dem beispielsweise die Punkte für eine "8" angezeigt werden. Polarkoordinaten helfen Ihnen in diesem Fall nicht weiter, und das Ergebnis, das Sie erhalten, hängt stark von dem von Ihnen gewählten Zentrum ab. Die TSP-Lösung ist unabhängig von "heuristischen" Parametern.
static_rtti
19

Was Sie verlangen, ist ein System, das als Polarkoordinaten bekannt ist . Die Konvertierung von kartesischen in Polarkoordinaten ist in jeder Sprache problemlos möglich. Die Formeln finden Sie in diesem Abschnitt .

Sortieren Sie nach der Konvertierung in Polarkoordinaten einfach nach dem Winkel Theta.

Iterator
quelle
4
Dies wird funktionieren, hat aber auch den Fehler, mehr Berechnungen durchzuführen, als zur Beantwortung der Bestellfrage erforderlich sind. In der Praxis kümmern Sie sich weder um die tatsächlichen Winkel noch um die radialen Abstände, sondern nur um deren relative Reihenfolge. Die Lösung von ciamej ist besser, weil sie Teilungen, Quadratwurzeln und Trigger vermeidet.
RBerteig
1
Ich bin mir nicht sicher, was Ihr Kriterium für "besser" ist. Zum Beispiel ist das Vergleichen aller Punkte miteinander eine Art Rechenverschwendung. Trig ist nicht etwas, das Erwachsene erschreckt, oder?
Iterator
3
Es ist nicht so, dass Trig beängstigend ist. Das Problem ist, dass die Berechnung von Triggern teuer ist und nicht zur Bestimmung der relativen Reihenfolge der Winkel benötigt wurde. Ebenso müssen Sie nicht die Quadratwurzeln ziehen, um die Radien in Ordnung zu bringen. Eine vollständige Umwandlung von kartesischen in Polarkoordinaten führt sowohl zu einer Bogen-Tangente als auch zu einer Quadratwurzel. Daher ist Ihre Antwort richtig, aber im Zusammenhang mit Computergrafik oder Computergeometrie ist dies wahrscheinlich nicht der beste Weg , dies zu tun.
RBerteig
Verstanden. Das OP hat jedoch nicht als Comp-Geo gepostet, das war ein Tag von jemand anderem. Trotzdem sieht es so aus, als ob die andere Lösung in der Anzahl der Punkte polynomisch ist, oder irre ich mich? Wenn ja, brennt das mehr Zyklen als Trigger.
Iterator
Ich hatte das Comp-Geo-Tag nicht wirklich bemerkt, sondern nur angenommen, dass die einzige rationale Anwendung für die Frage die eine oder andere sein musste. Immerhin wird die Leistungsfrage strittig, wenn es nur wenige Punkte gibt und / oder die Operation selten genug durchgeführt wird. An diesem Punkt wird es wichtig zu wissen, wie es überhaupt geht, und deshalb stimme ich zu, dass Ihre Antwort richtig ist. Es wird erklärt, wie der Begriff "Ordnung im Uhrzeigersinn" in Begriffen berechnet wird, die nahezu jedem erklärt werden können.
RBerteig
3

Eine andere Version (return true, wenn a gegen b gegen den Uhrzeigersinn vor b steht):

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

Dies ist schneller, da der Compiler (getestet in Visual C ++ 2015) keinen Sprung generiert, um dax, day, dbx, dby zu berechnen. Hier die Ausgabebaugruppe vom Compiler:

; 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

Genießen.

AGPX
quelle
1
Die beiden return-Anweisungen im Schalter sind mathematisch äquivalent. Gibt es einen Grund für den Wechsel?
Unagi
0
  • vector3 a = neuer vector3 (1, 0, 0) .............. wrt X_axis
  • vector3 b = any_point - Center;
- 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

Schließlich erhalten Sie Anticlockwize sortierte Verts

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

Pavan
quelle