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
ipairs(tbl)
, die die Indizes und Werte von tbl von 1 bis #tbl durchläuft. Für diefor _, p in ipairs(points) do pointsSum.x = pointsSum.x + p.x; pointsSum.y = pointsSum.y + p.y end
ipairs
deutlich langsamer als numerisch für Schleife.Antworten:
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:
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:
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ückkehrena.y > b.y
.Die ersten if-Anweisungen wurden durch Hinzufügen von
-center.x
und 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.quelle
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.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.
quelle
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.
quelle
Eine andere Version (return true, wenn a gegen b gegen den Uhrzeigersinn vor b steht):
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:
Genießen.
quelle
Schließlich erhalten Sie Anticlockwize sortierte Verts
list.Reverse () .................. Clockwise_order
quelle