nicht angemeldet
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