Größenrelation 2er Punkte
-
Mahlzeit ...
ich möchte 2 Punkte in einem 2D kartesischem Koordinatensystem vergleichen um sie zu sortieren. Man könnte die Punkte einfach als Ortsvektoren auffassen und den Betrag berechnen:
1. Es müsste doch für den Vergleich ausreichen, wenn ich einfach die Summen der Quadrate vergleiche ? (ich möchte die Quadratwurzelberechnung vermeiden)
2. Wie kann ich am sinnvollsten die Richtung der Vektoren in die Relation mit einbeziehen?
3. Sicher hat sich dazu schonmal jemand gedanken gemacht, aber ich hab beim googeln nichts gefunden. Hat jemand Links?
Der Vergleicch wird sehr oft ausgeführt, weswegen ich das ganze möglichst effizient brauche ...
-
Ist egal wie, Hauptsache eine strikt schwache Ordnung? Vergleich die erste Dimension, bei Gleichheit fährst du mit der nächst höheren fort.
-
Was ist denn der Sinn von diesen Vergleichen?
-
trolltäch schrieb:
2. Wie kann ich am sinnvollsten die Richtung der Vektoren in die Relation mit einbeziehen?
Bei gleichen Entfernungen?
Das Skalarprodukt mit einem festen Vektor berechnen und je größer das ist, desto ähnlicher sind die Richtungen.
Extrem: Nur den x-Wert nehmen. Je größer, desto genauer zeigt er nach Osten.
-
volkard schrieb:
Das Skalarprodukt mit einem festen Vektor berechnen und je größer das ist, desto ähnlicher sind die Richtungen.
Extrem: Nur den x-Wert nehmen. Je größer, desto genauer zeigt er nach Osten.
Stimmt nur mit vorheriger Normierung.
-
volkard schrieb:
Das Skalarprodukt mit einem festen Vektor berechnen und je größer das ist, desto ähnlicher sind die Richtungen.
Extrem: Nur den x-Wert nehmen. Je größer, desto genauer zeigt er nach Osten.
Sprich: Das Skalarprodukt mit (1,0)
-
SeppJ schrieb:
Ist egal wie, Hauptsache eine strikt schwache Ordnung? Vergleich die erste Dimension, bei Gleichheit fährst du mit der nächst höheren fort.
Auch bekannt als lexikographische Ordnung
-
trolltäch schrieb:
2. Wie kann ich am sinnvollsten die Richtung der Vektoren in die Relation mit einbeziehen?
man kann die Punkte in Polarform (r,phi) speichern mit r = sqrt x2+y2 und phi=arctan y/x.
Ordnung lexikographisch: (r1,phi1) < (r2,phi2) <=> r1 < r2 oder (r1=r2 und phi1<phi2)
-
1. Es müsste doch für den Vergleich ausreichen, wenn ich einfach die Summen der Quadrate vergleiche ? (ich möchte die Quadratwurzelberechnung vermeiden)
Nein, denn wenn du z.B. die Punkte A(3, 5) und B(5, 3) hast, ist die Summe der Quadrate gleich.
2. Wie kann ich am sinnvollsten die Richtung der Vektoren in die Relation mit einbeziehen?
Du könntest einfach den Quotienten (y : x) der beiden Punkte bilden. Je größer dieser Quotient ist, desto näher liegt der Vektor zum Punkt an der y-Achse an. Dies gilt zumindest für den 1. und 3. Quadranten. Beim 2. und 4. Quadranten muss der Quotient möglichst klein sein (negativ).
Bei den Punkten A und B von oben wär der Quotient z.B.:
Q(A) = 0.6
Q(B) = 1.6666
Also liegt der Punkt B näher an der y-Achse an.3. Sicher hat sich dazu schonmal jemand gedanken gemacht, aber ich hab beim googeln nichts gefunden. Hat jemand Links?
Du könntest mal nach dem "Graham Scan Algorithm" googeln. Das ist ein Algorithmus, mit dem du Punkte auf einem kartesischen Koordinatensystem ordnen kannst. Er ordnet die Punkte nach der Richtung des Vektors zum Ursprung.
-
anonym83 schrieb:
Du könntest mal nach dem "Graham Scan Algorithm" googeln. Das ist ein Algorithmus, mit dem du Punkte auf einem kartesischen Koordinatensystem ordnen kannst. Er ordnet die Punkte nach der Richtung des Vektors zum Ursprung.
atan2 und std::sort reichen vollauf.
graham scan macht was viel kompliziertereres.
-
edit:
Natürlich ist die Rechung für die Punkte A und B folgendermaßen:
Q(B) = 0.6
Q(A) = 1.6666
Punkt A hat den höheren Quotienten und deshalb liegt der Vektor vom Ursprung zu A näher an der y-Achse an.
