Kann ich die Ungleichung "Abstand (p1, p2) <Abstand (p1, p3)" vereinfachen?

14

Ich arbeite an einer Vektorlogik und frage daher: Kann ich Prozessorzeit sparen, indem ich diese Ungleichung vereinfache?

distance(vector1, vector2) < distance(vector1, vector3)

Ich sehe, dass vector1sich das in beiden Fällen wiederholt.

vector Filip Dimitrovski
quelle
10
Nur eine kurze Anmerkung: Ihre aktuelle Methode ist sehr gut lesbar und ihre Funktion kann sofort verstanden werden. Einige dieser Antworten erfüllen möglicherweise die von Ihnen angeforderte Aufgabe, sind jedoch viel weniger klar. Dies ist in Ordnung, wenn die Leistung von entscheidender Bedeutung ist, aber stellen Sie sicher, dass Sie dies ordnungsgemäß kommentieren, um den Verlust an Klarheit zu berücksichtigen.
MikeS
3
Um mit dem Kommentar von @ MikeS fortzufahren, sollte die Leistung in solchen Fällen nur dann von entscheidender Bedeutung sein, wenn Sie bereits Analysen oder Profile erstellt und diesen Aufruf als Engpass identifiziert haben. Die Wartbarkeit übertrifft die Leistung, wenn es um den Unterschied zwischen 305fps und 303fps geht.
Phoshi

Antworten:

24

Ja , Sie können dies vereinfachen. Nennen Sie sie nicht länger Vektoren. Das sind Punkte. Nennen wir sie A, Bund C.

Also, du willst das:

dist(A, B) < dist(A, C)

Ersetzen Sie Entfernungen durch Entfernungen im Quadrat und dann durch Punktprodukte (aus der Definition der euklidischen Länge) . Ersetzen Sie ACdurch AB + BC(jetzt sind dies echte Vektoren). Erweitern, vereinfachen, Faktor:

dist(A, B)² < dist(A, C)²
dot(AB, AB) < dot(AC, AC)
dot(AB, AB) < dot(AB + BC, AB + BC)
dot(AB, AB) < dot(AB, AB) + dot(BC, BC) + 2 dot(AB, BC)
0 < dot(BC, BC) + 2 dot(AB, BC)
0 < dot(BC + 2 AB, BC)

Da bist du ja:

dot(AB + AC, BC) > 0

Mit Ihrer Vektornotation:

dot(v2 - v1 + v3 - v1, v3 - v2) > 0

Das sind ein paar Ergänzungen und ein Skalarprodukt anstelle der beiden vorherigen Skalarprodukte.

sam hocevar
quelle
Können Sie erklären, wie Sie a + b b = a + c c durch die dot-Produktversion ersetzen können ?
TravisG
2
@ TravisG Ich bin nicht sicher, was Sie fragen. Wenn Ihre Frage lautet, warum dist(A, B)²es dasselbe ist wie dot(AB, AB), ergibt sie sich aus der Definition der euklidischen Länge .
Sam Hocevar
2
Dies vereinfacht die Gleichung (etwas) mathematisch, würde aber nicht unbedingt "Prozessorzeit sparen" für das OP. Dies führt zu mehr Komplexität und mehr Berechnungen als nur zum Entfernen der Quadratwurzel aus den ursprünglichen Abstandsgleichungen.
MichaelHouse
1
Korrigieren Sie mich, wenn ich falsch liege, aber die zwei Punktprodukte 5 Operationen pro Punktprodukt plus die zwei vec3-Subtraktionen sind, was insgesamt 16 Operationen entspricht. Ihr Weg hat 3 vec3-Subtraktionen plus eine Addition, die 12 Operationen plus das Punktprodukt ergibt macht 17.
Luis W
2
Interessanterweise ist das Ergebnis das Skalarprodukt der beiden entgegengesetzten Diagonalen eines Parallelogramms. Das ist aber irrelevant. Was ich sagen wollte, ist, dass diese vollständige Vereinfachung nicht viel bringt. Wie andere bereits erwähnt haben, reicht es aus, zu verschleiern oder zu verkomplizieren, was Sie tatsächlich zu berechnen versuchen. Sie möchten jedoch auf jeden Fall den ersten Schritt ausführen. Es lohnt sich immer, eine unnötige Quadratwurzel zu vermeiden. Nur die Quadrate der Entfernungen zu vergleichen, ist dasselbe, da die Entfernung selbst in der komplexen Ebene eindeutig positiv ist.
TASagent
16

Ja. Angenommen, Ihre distanceFunktion verwendet eine Quadratwurzel. Sie können dies vereinfachen, indem Sie die Quadratwurzel entfernen.

Beim Versuch, den größeren (oder kleineren) Abstand zu finden, gilt x^2 > y^2immer noch für x > y.

Weitere Versuche, die Gleichung mathematisch zu vereinfachen, sind jedoch wahrscheinlich sinnlos. Der Abstand zwischen vector1und vector2ist nicht der gleiche wie der Abstand zwischen vector1und vector3. Während die Gleichung mathematisch vereinfacht werden kann, wie Sams Antwort zeigt, ist die Form, in der sie gegenwärtig vorliegt, wahrscheinlich so einfach, wie Sie es aus Sicht der Prozessornutzung sehen werden.

MichaelHouse
quelle
Ich habe nicht genug Repräsentanten, aber ich würde, da es grundsätzlich falsch ist, glauben: "Kann ich Prozessorzeit sparen, indem ich diese Ungleichung vereinfache?" Die Antwort ist ja.
so verwirrt
Die Antwort lautet nur ja, wenn die Abstandsgleichung eine Quadratwurzel verwendet. Was ich erwähne.
MichaelHouse
Gültiger Punkt, ich würde meine Aussage zurückziehen. Es wird jedoch von 99% garantiert , dass der Benutzer euklidischen Abstand sqrt (sum (Maßabweichungen zum Quadrat)) bedeutet
im so verwirrt
@imsoconfused Fairerweise habe ich die Reihenfolge meiner Antwort geändert, um zuerst das wahrscheinlichste (99%) Szenario anzugeben.
MichaelHouse
2
Ja, ich habe die Erfahrung gemacht, dass eine DistanceSquared-Funktion sehr nützlich ist, wenn Sie mit solchen Dingen zu tun haben. Es ist genauso klar und vermeidet den teuren sqrt-Betrieb.
Loren Pechtel
0

Ein bisschen Mathe könnte helfen.

Was Sie versuchen zu tun, ist:

<v1, v2> < <v1, v3> =>
sqrt((y2-y1)^2+(x2-x1)^2) < sqrt((y3-y1)^2+(x3-x1)^2) =>
y2^2 - 2*y2y1 + y1^2 + x2^2 - 2*x2x1 + x1^2 < y3^2 - 2*y3y1 + y1^2 + x3^2 - 2*x3x1 + x1^2

Woraus Sie wiederholte Variablen entfernen und einige andere gruppieren können. Die Operation, die Sie überprüfen müssen, ist:

y3^2 - y2^2 - 2*y1(y3-y2) + x3^2 - x2^2 - 2*x1(x3-x2) > 0

Ich hoffe es hilft.

j4nSolo
quelle
-1

Die eigentliche Frage scheint zu sein, wie die Berechnung zur Bestimmung des nächsten Objekts reduziert werden kann.

Die Optimierung wird oft in Spielen durchgeführt, obwohl sie bei allen Optimierungen profilgesteuert sein sollte und die Dinge oft nicht vereinfacht .

Um unnötige Entfernungsberechnungen zu vermeiden, um das nächste Objekt oder alle Objekte innerhalb eines bestimmten Bereichs zu bestimmen, verwenden Sie einen räumlichen Index, z . B. einen Octree .

Dies zahlt sich nur bei einer großen Anzahl von Objekten aus. Bei nur drei Objekten ist es unwahrscheinlich, dass sie sich auszahlen, und vereinfacht den Code mit Sicherheit nicht .

Wille
quelle
4
Ich denke, die eigentliche Frage ist ziemlich einfach, und diese Antwort spricht das nicht an. Wenn Sie darüber spekulieren wollten, dass das OP tiefere, nicht genannte Fragen enthält, sollten Sie dies als Kommentar tun, wenn Sie die gestellte Frage nicht wirklich beantworten möchten.
Ich stimme dem nicht zu, weil das Aufrufen einer möglichen vorzeitigen Optimierung keine Antwort auf ein Problem ist, bei dem eine explizite Optimierung weder die Lesbarkeit noch die Code-Wartbarkeit beeinträchtigt , noch obskure Praktiken fördert. Wenn Sie tatsächlich einfachen und optimierten Code schreiben können, warum nicht? Es tut sicherlich nicht weh, es zu tun, selbst wenn Sie einen Plan auf höherer Ebene haben (kein Spieleentwickler wird jemals einige zusätzliche Mikrosekunden pro Frame verweigern, insbesondere auf Konsolen).
Teodron
@teodron: "Wenn Sie tatsächlich einfachen und optimierten Code schreiben können, warum nicht?" - Weil OP (und jetzt wir) eine nicht zu vernachlässigende Zeit damit verbracht hat, etwas zu optimieren, was ihm keinen Nutzen bringen könnte.
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft Ich bin damit einverstanden, dass es sich um eine geringfügige (daher unbedeutende Optimierung handelt, wenn für ein paar hundert Anrufe pro Frame verwendet, aber wenn der Größenfaktor auf Tausende ansteigt, ändern sich die Dinge sicherlich). Es steht uns allen jedoch frei, keine Zeit damit zu verschwenden, zu versuchen, etwas zu beantworten / optimieren, das wir für nicht realisierbar halten. Das OP fragte nach einer Sache, die Leute gingen davon aus, dass das OP keine Kenntnis von übergeordneten Strategien und Profilierungspraktiken hatte. Ich persönlich bevorzuge solche Bemerkungen in Kommentaren, nicht in Antworten. Tut mir leid, dass ich so wortreich
bin
-3

es hängt davon ab, wie hoch die Ausgabe der Distanz (v1, v2) ist

Wenn es sich um eine Dezimalzahl (Float oder Double) über einem Vektor handelt, ist es wahrscheinlich, dass das Entfernungsquadrat viel schneller ist

RoughPlace
quelle
5
Ich verstehe nicht, was es floatmit irgendetwas zu tun hat.
MichaelHouse
ich meinte einen float über einen anderen vektor, der nur nicht besonders gut erklärt wurde (und ich glaube, das
wusstest
5
Ich habe es nicht absichtlich falsch verstanden. Ich bin mir immer noch nicht sicher, was du meinst. Ich weiß nicht, warum eine Distanzfunktion einen Vektor zurückgeben würde.
MichaelHouse