Punkte gegen den Uhrzeigersinn sortieren
0 0 
Claudius L.
0 0 0 Claudius L.
0
Punkte gegen den Uhrzeigersinn sortieren
Hallo,
bin noch anfänger im Programmieren.
Hoffe mir kann jemand helfen:
Ich habe X und Y Koordinaten von drei Punkten eines Dreieckes.
Nun soll eine Liste der Punkte erstellt werden und zwar so dass sie hintereinander in der Reihenfolge gegen den Uhrzeigersinn aufgelistet werden.
Also folgendes Beispiel:
Dreieck 1 besteht aus Punkt 1 mit X = 2,2 und Y = 5,5
Punkt 2 mit X = 3,2 und Y = 7,3
Punkt 3 mit X = 3,2 und Y = 1,5
Dann sollte die richtige Reihenfolge der Punkte gegen den Uhrzeigersinn sein also z.B.:
3 2 1 oder 2 1 3 oder 1 3 2
Weiß jemand wie man das machen kann? Hab schon irgendwas mit Quicksort überlegt, aber ich komme irgendwie auf keine Lösung.
Bitte helft mir!
-
Hi,
Nun soll eine Liste der Punkte erstellt werden und zwar so dass sie hintereinander in der Reihenfolge gegen den Uhrzeigersinn aufgelistet werden.
Dann bietet es sich wohl an, die X/Y-Koordinaten erst mal in einen Winkel (auf einem Kreis um den Mittelpunkt 0/0) umzurechnen.
MfG ChrisB
--
„This is the author's opinion, not necessarily that of Starbucks.“ -
Hallo monty!
Nur mal eine Überlegung: Ermittle den Punkt mit dem größten X-Wert, der also ganz rechts steht. Von dort aus kommt als nächstes derjenige der übrigen beiden Punkte, der den größeren Y-Wert hat. Der dritte Punkt ergibt sich dann natürlich von selbst.
Diese Abfolge kannst du dann noch beliebig durchrotieren, je nachdem welchen Punkt du als „Anfangspunkt“ bezeichnen möchtest.Das ist allerdings nur so eine spontane Überlegung, ich mag mich täuschen. Wenn allerdings nicht, dürfte das ziemlich leicht umzusetzen sein.
Gruß,
Claudius
-
Hallo Claudius,
Beispiel:
A = (3,0)
B = (2,2)
C = (0,3)Punkt mit größtem X-Wert: A
Punkt mit dem größten Y-Wert: C
Ergebnis: A, C, B
Richtig wäre aber: A, B, CMeine spontane Idee wäre:
Baue aus A und B eine Geradengleichung der Form:
ax+c-y=0
Für Punkte "rechts" gilt dann ax+c-y>0 für die "links" ax+c-y<0Das gibt also folgendes Programm:
f(x,y) = ((B.Y-A.Y)/(B.X-A.X))*(x-A.X)+B.X
if (f(C.X, C.Y) > 0) {
return [A, C, B];
} else if (f(C.X, C.Y) < 0) {
return [A, B, C];
} else {
return null; // kein Dreieck.
}Grüße
Daniel
-
Ok, da sind noch einige Fehler drin. (Ein Flüchtigkeitsfehler, ein Sonderfall und ein konzeptioneller).
Baue aus A und B eine Geradengleichung der Form:
ax+c-y=0
Für Punkte "rechts" gilt dann ax+c-y>0 für die "links" ax+c-y<0Dabei ist es natürlich entscheidend, welche Reihenfolge A und B haben, da davon abhängt, was "links" ist. Das gilt nur wenn A.X < B.X sonst ist es gerade umgekeht.
Das Programm sieht dann also so aus:
if (A.X == B.X) {
// Sonderfall
if (A.X == C.X) {
return null; // kein Dreieck
}
(B, C) = (C, B);
}
if (A.X > B.X) {
(A, B) = (B, A);
}
f(x,y) = ((B.Y-A.Y)/(B.X-A.X))*(x-A.X)+A.Y-y
if (f(C.X, C.Y) > 0) {
return [A, C, B];
} else if (f(C.X, C.Y) < 0) {
return [A, B, C];
} else {
return null; // kein Dreieck.
}Das sollte jetzt zu mindest konzeptionell stimmen. Solche geometrischen Probleme werden schnell eklig, selbst wenn die Idee wie hier sehr einfach ist.
Grüße
Daniel
-
Hui das ist ja wirklich schwieriger als gedacht. Geht es nicht irgendwie das man sich erstmal einen Punkt der in beiden Koodinaten das Minimum oder Max hat nimmt und dann die beiden anderen Punkte mit ihm vergleicht?
-
Hallo monty,
Hui das ist ja wirklich schwieriger als gedacht.
Die Implementierung ist komplizert, die Idee ist eigentlich recht einfach.
Geht es nicht irgendwie das man sich erstmal einen Punkt der in beiden Koodinaten das Minimum oder Max hat nimmt und dann die beiden anderen Punkte mit ihm vergleicht?
Klar man kann einen bestimmten Punkt als Ausgangspunkt wählen.
Aber male Dir das einfach auf: Du hast zwei Punkte A und B. Nun kannst Du noch C irgendwo platzieren. Wovon hängt es nun ab, welche Reihenfolge die Punkte bekommen sollen?
Offensichtlich doch davon, auf welcher Seite von AB C eben liegt. Um das zu entscheiden, reicht es nicht aus, die einzelnen Koordinaten zu vergleichen. Da muss man irgendwie den Winkel bzw. Abstand berücksichtigen.
Das macht der Teil:
f(x,y) = ((B.Y-A.Y)/(B.X-A.X))*(x-A.X)+A.Y-y
if (f(C.X, C.Y) > 0) {
return [A, C, B];
} else if (f(C.X, C.Y) < 0) {
return [A, B, C];
} else {
return null; // kein Dreieck.
}
Das sieht kompliziert aus, f(x,y) = 0 ist aber nur die Geradengleichung, setzt man einen Punkt in diese ein, bekommt man einen Wert proportional zum Abstand. Uns interessiert nur das Vorzeichen, also reicht das.Der restliche Code wählt nur die Punkte A, B so aus, dass die Annahmen stimmen. A und B dürfen nicht übereinander liegen, da die Steigung sonst undefiniert ist (division durch Null).
A.X < B.X muss gelten, damit das rechts/links von AB eindeutig definiert ist.Ich denke nicht, dass es wesentlich einfacher geht. Der Algorithmus berechnet nur Informationen, die notwendig sind, um das zu entscheiden.
Grüße
Daniel
-
Hallo,
Wofür brauchst du das eigentlich?
mfg, Flo
--
Developers are dying. Computers are getting trash. CEO's become forgetten. The only remaining things are ideas, lies and crises. So if you want to be immortal, first think, than stop it and go to microsoft and become later a manager at Lehman Brothers...
sh:) fo:| ch:? rl:( br:^ n4:| ie:{ mo:| va:} de:> zu:} fl:{ ss:) ls:< js:|
*Zu dem de:> Ich benutze wegen IE im moment noch tabellen, weil dieser display:table noch nicht versteht. Ich werde aber, wenn IE 6 & IE 7 < 10% mein neues CSS-Layout einspielen...
-
-
-
Hallo Claudius,
Beispiel:
A = (3,0)
B = (2,2)
C = (0,3)Punkt mit größtem X-Wert: A
Punkt mit dem größten Y-Wert: C
Ergebnis: A, C, B
Richtig wäre aber: A, B, CHallo!
Jop, da hast du eindeutig Recht. Dass das Dreieck auch so liegen kann hatte ich garnicht in Betracht gezogen … danke für die Richtigstellung. Auch wenn’s irgendwie schade ist, dass es nicht „einfach einfach“ geht.
Gruß,
Claudius
-
-
-
Hallo!
Danke für die Hinweise. Clausius, das klingt gut. Nur leider fehlt mir eben noch die Erfahrung soetwas umzusetzen. Hat jemand einen Code? Oder Ausschnitte oder ein Beispiel?Vielen Dank schonmal!
Monty