Effiziente Methode zum Finden der Entfernung zwischen zwei 3D-Punkten

Question

Ich schreibe einen Code in C++ und möchte den Abstand zwischen zwei Punkten berechnen. Frage 1:

I haben zwei Punkte P (x1, y1, z1) und Q (x2, y2, z2), wobei x, y und z Hin- und Herbewegungen/verdoppelt.

Ich möchte den Abstand zwischen diesen beiden Punkten finden. Eine Möglichkeit, es zu tun ist:

square_root (x_diff x_diff + y_diff y_diff + z_diff * z_diff)

Aber das ist wahrscheinlich nicht die effizienteste Art und Weise. (Zum Beispiel eine bessere Formel oder eine fertige Anwendung in math.h etc)

Frage 2:

Gibt es eine bessere Art und Weise, wenn ich möchte nur feststellen, ob P und Q in der Tat sind die gleichen Punkte?

Meine Eingaben sind x, y und z Koordinaten der beiden Punkte.

Vielen Dank

Answer 1

Benötigen Sie die tatsächliche Entfernung? Sie können die Entfernung im Quadrat verwenden, um festzustellen, ob sie gleich sind und für viele andere Zwecke. (spart bei der sqrt-Operation)

Answer 2

Nein, es gibt keinen besseren Weg.

Die Implementierung von square_root könnte optimiert werden.

Wenn Sie zwei Entfernungen vergleichen und wissen wollen, desto länger, aber egal, was die tatsächliche Entfernung ist, dann können Sie einfach den Quadratwurzelschritt komplett ingodieren und Ihre noch quadratischen Abstände manipulieren. Dies wäre zum Vergleichen von zwei Paaren von Punkten anwendbar, um zu bestimmen, ob sie zum Beispiel den gleichen Abstand voneinander haben.

Answer 3

Q2 Antwort: x1 = x2 und y1 = y2 und z1 = z2 wenn die Punkte gleich sind.

Unter Berücksichtigung, dass Sie Punkte als float/double speichern, müssen Sie möglicherweise den Vergleich mit etwas Epsilon durchführen.

Answer 4

Nein, es gibt keinen effizienteren Weg, das Dist zu berechnen. Jede Behandlung mit Sonderfällen p.x == q.x usw. wird im Durchschnitt langsamer sein.

Ja, der schnellste Weg zu sehen, ob p und q die gleichen Punkte sind, vergleicht nur x, y, z. Da sie float sind, sollten Sie nicht == überprüfen, sondern einen endlichen, kleinen Unterschied berücksichtigen, den Sie definieren.

Answer 5

Gibt es einen besseren Weg, wenn ich nur feststellen möchte, ob P und Q tatsächlich die gleichen Punkte sind?

Dann vergleichen Sie einfach die Koordinaten direkt!

bool areEqual(const Point& p1, const Point& p2) { 
    return fabs(p1.x - p2.x) < EPSILON && 
      fabs(p1.y - p2.y) < EPSILON && 
      fabs(p1.z - p2.z) < EPSILON; 
} 

Answer 6

Es gibt schnellere Wege, um eine ungefähre Entfernung aber nichts in den Standardbibliotheken gebaut zu bekommen. Werfen Sie einen Blick auf this article auf FlipCode, die die Methode für schnelle 2D-Entfernungen abdeckt.Es hat im Wesentlichen die sqrt-Funktion in eine zusammengesetzte lineare Funktion umgewandelt, die schnell berechnet werden kann, aber nicht 100% genau ist. Allerdings ist fpmath heutzutage auf modernen Maschinen ziemlich schnell, also optimieren Sie nicht zu früh, Sie könnten feststellen, dass Sie mit Ihrem einfachen Ansatz zurechtkommen.

Answer 7

Sie diesen Artikel interessant finden könnte:

http://www.codemaestro.com/reviews/9

Es beschreibt, wie die Quadratwurzel berechnet wurde in der Quake 3 Engine, dass es auf einigen CPU behauptet, ist lief 4 mal so schnell wie die sqrt() Funktion. Nicht sicher, ob es Ihnen in C++ heutzutage einen Leistungsschub geben wird - aber immer noch interessant lesen

Answer 8

Sie können versuchen, SSE-Erweiterungen zu verwenden. Zum Beispiel können Sie zwei Vektoren A init (x1, y1, z1) und B (x2, y2, z2):

_m128 A = _mm_set_ps(x1, y1, z1, 0.0f) 
_m128 B = _mm_set_ps(x2, y2, z2, 0.0f) 

Dann berechnen diff _mm_sub_ps mit:

__m128 Diff = _mm_sub_ps(A, B) 

Weiter berechnen sqr von diff:

__m128 Sqr = __mm_mul_ps(Diff, Diff) 

Und schließlich:

__m128 Sum = add_horizontal(Sqr) 
__m128 Res = _mm_sqrt_ss(Sum) 

R es [0] wird mit Ihrer Antwort gefüllt.

P.S. add_horizontal ist ein Ort zur Optimierung

Answer 9

Beachten Sie, dass bei Verwendung sqrt(dx*dx+dy*dy+dz*dz) die Summe der Quadrate überlaufen kann. hypot(dx, dy) berechnet eine Entfernung direkt ohne die Gefahr eines Überlaufs. Ich bin mir nicht sicher von der schnellsten 3D-Äquivalent, aber macht den Job und wird auch nicht überlaufen.

Answer 10

Soweit Frage 1 geht, ist die Leistungseinbuße die Berechnung der Quadratwurzel selbst. Die Formel für die Berechnung der Entfernung unter Verwendung der Quadratwurzel der paarweisen Koordinatenunterschiede ist, was es ist.

Ich würde dringend empfehlen, diese A-M-A-Z-I-N-G Quadratwurzel-Implementierung von John Carmack ID-Software zu lesen, die er in seinem Motor in Quake III verwendet. Es ist einfach MAGISCH.

Answer 11

Die GNU Scientific Library definiert gsl_hypot3, die genau die Entfernung berechnet, die Sie im ersten Teil Ihrer Frage wünschen. Eine Art Overkill, die das Ganze nur dafür zusammenstellt, angesichts von Darius 'Vorschlag, aber vielleicht gibt es da noch andere Sachen, die du haben willst.