Wie sortiere ich die Punkte dieses Arrays im Uhrzeigersinn (um ihren gesamten durchschnittlichen Mittelpunkt herum), wenn Sie ein Array von x, y Punkten angeben? Mein Ziel ist es, die Punkte an eine Linienerstellungsfunktion zu übergeben, damit etwas ziemlich "fest" aussieht, so konvex wie möglich, ohne dass sich Linien schneiden.
Für das, was es wert ist, verwende ich Lua, aber jeder Pseudocode wäre willkommen. Vielen Dank für jede Hilfe!
Update: Dies ist der Lua-Code, der auf Ciamejs hervorragender Antwort basiert (ignorieren Sie das Präfix "app"):
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
Berechnen Sie zuerst den Mittelpunkt . Sortieren Sie dann die Punkte mit dem gewünschten Sortieralgorithmus. Verwenden Sie eine spezielle Vergleichsroutine, um zu bestimmen, ob ein Punkt kleiner als der andere ist.
Mit dieser einfachen Berechnung können Sie überprüfen, ob ein Punkt (a) in Bezug auf die Mitte links oder rechts vom anderen (b) liegt:
det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
wenn das Ergebnis gleich Null ist, befinden sie sich auf derselben Linie von der Mitte, wenn es positiv oder negativ ist, dann liegt es auf der einen oder der anderen Seite, sodass ein Punkt vor dem anderen liegt weniger als als Beziehung, um Vergleichspunkte zu bestimmen und die Reihenfolge zu bestimmen, in der sie im sortierten Array erscheinen 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 angeordnet. Punkte zu derselben "Stunde" werden ausgehend von den weiter entfernten Punkten geordnet.
Wenn Sie Integer-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 wollen, das solide und so konvex wie möglich aussieht, dann suchen Sie wahrscheinlich nach einem Convex Hull . Sie können es mit Graham Scan ..__ berechnen. Bei diesem Algorithmus müssen Sie die Punkte auch im Uhrzeigersinn (oder entgegen dem Uhrzeigersinn) beginnend mit einem speziellen Drehpunkt sortieren. Dann wiederholen Sie einfache Schleifschritte, um zu überprüfen, ob Sie nach links oder rechts abbiegen und der konvexen Hülle neue Punkte hinzufügen. Diese Prüfung basiert auf einem Kreuzprodukt, genau wie in der obigen Vergleichsfunktion.
Bearbeiten:
Eine weitere if-Anweisung if (a.y - center.y >= 0 || b.y - center.y >=0)
wurde hinzugefügt, um sicherzustellen, dass Punkte mit x = 0 und negativem y beginnend mit denjenigen sortiert werden, die weiter vom Zentrum entfernt sind. Wenn Sie sich nicht für die Reihenfolge der Punkte auf derselben "Stunde" interessieren, können Sie diese if-Anweisung weglassen und immer a.y > b.y
zurückgeben.
Die ersten if-Anweisungen wurden durch Hinzufügen von -center.x
und -center.y
korrigiert.
Die zweite if-Anweisung (a.x - center.x < 0 && b.x - center.x >= 0)
wurde hinzugefügt. Es war ein offensichtliches Versehen, dass es fehlte. Die if -Anweisungen könnten jetzt reorganisiert werden, da einige Überprüfungen überflüssig sind. Wenn zum Beispiel die erste Bedingung in der ersten if-Anweisung falsch ist, muss die erste Bedingung des zweiten if wahr sein. Ich entschied mich jedoch, den Code der Einfachheit halber so zu belassen. Es ist durchaus möglich, dass der Compiler den Code optimiert und trotzdem das gleiche Ergebnis liefert.
Sie fragen nach einem 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 .
Ich kenne Lua nicht, aber diese Seite scheint Codeausschnitte für diese Konvertierung anzubieten.
Nach dem Konvertieren in Polarkoordinaten sortieren Sie einfach nach dem Winkel Theta.
Ein interessanter alternativer Ansatz für Ihr Problem wäre, das ungefähre Minimum für das Traveling 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 dennoch gut aussehen (eine "durchgehende" Form kann als eine Form definiert werden, die ein geringes Verhältnis von Umfang/Fläche aufweist, was wir hier optimieren) .
Sie können eine beliebige Implementierung eines Optimierers für den TSP verwenden, von der ich ziemlich sicher bin, dass Sie eine Tonne in Ihrer bevorzugten Sprache finden können.
Eine andere Version (true zurückgeben, wenn a vor b im Gegenuhrzeigersinn kommt):
bool lessCcw(const Vector2D ¢er, 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 zur Berechnung von Dax, Day, Dbx, Dby erzeugt. Hier die Ausgabe Assembly 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 [email protected]
; 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
[email protected]:
pop edi
pop esi
setl al
pop ebx
ret 0
[email protected]@[email protected]@[email protected] ENDP ; lessCcw
Genießen.
- 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
Zum Schluss erhalten Sie Anticlockwize-sortierte Verts
list.Reverse () .................. Clockwise_order