schnelles geometrische Nähe Prädikat

Question

Ich habe 3 Punkte (A, B und X) und eine Entfernung (d). Ich muss, um eine Funktion zu machen, daß, wenn Punkt X Tests ist, näher ist als der Abstand d auf einen beliebigen Punkt auf dem Liniensegment AB.

Die Frage ist erstens ist meine Lösung richtig und dann mit einer besser (schneller) Lösung zu entwickeln.

Mein erster Durchgang ist wie folgt

AX = X-A
BX = X-B
AB = A-B

    // closer than d to A (done squared to avoid needing to compute the sqrt in mag)
If d^2 > AX.mag^2  return true

    // closer than d to B
If d^2 > BX.mag^2 return true

    // "beyond"  B
If (dot(BX,AB) < 0) return false

    // "beyond"  A
If (dot(AX,AB) > 0) return false

    // find component of BX perpendicular to AB
Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2 < d^2

Dieser Code wird mit der Absicht, das ausgeführt wird für einen großen Satz von P und einem großen Satz von A / B / d Drilling am Ende findet all P, dass ich zumindest eine A / B / d so passieren zu vermuten, dass es ist eine Art und Weise insgesamt die Kosten auf dieser Grundlage zu reduzieren, aber ich habe in dem noch nicht sehe.

(BTW:.. Ich bin mir bewusst, dass einige Neuordnungs, einige temporäre Werte und einige algebraische Identitäten könnten die Kosten für die oben abnehmen ich weggelassen sie nur für Klarheit)

---

EDIT: Dies ist ein 2D-Problem (aber Lösung, die auf 3D verallgemeinert wäre cool

Edit: Bei der weiteren Reflexion, ich erwarte, dass die Trefferquote rund 50% betragen. Der X-Punkt kann in einer verschachtelten Hierarchie gebildet werden, so erwarte ich große Teilbäume als Allpass beschneiden zu können und all fail. Die A / B / d die Drillinge Begrenzung wird eher ein Trick sein.

Edit: d ist in der gleichen Größenordnung wie AB

.

---

edit: Artelius eine schöne Lösung gepostet. Ich bin mir nicht sicher, ob ich verstehe genau, was er immer an, als ich auf einer Tangente ausstieg, bevor ich es vollständig verstanden. Auf jeden Fall ein anderer Gedanke kam als Ergebnis etwas dagegen:

• Erste Artelius' Bit, Pre-cacluate eine Matrix, die AB aß den Ursprung und die Ausrichtung mit der X-Achse zentriert wird platzieren. (2 fügt hinzu: 4 Muls und 2 addiert)
• falten sie alle in den ersten Quadranten (2 abs)
• Maßstab in X & Y den zentralen Teil der Zone in ein Einheitsquadrat (2 MUL)
zu machen
• Test, wenn der Punkt in diesem Quadrat (2-Test) ist so beenden
• testen Sie die Endkappe (zurück zu den nicht skalierten Werte
  • in x übersetzt das Ende am Ursprung zu platzieren (1 zus)
  • Quadrat und fügen Sie (2 mul, 1 add)
  • Vergleichen bis d ^ 2 (1 cmp)

Ich bin ziemlich sicher, dass dies meine Lösung schlägt.

(wenn nichts besseres kommt sone Artelius erhält den "Preis":)

Answer 1

Wenn der Satz (A, B, D) in festen, kann man ein Paar von Matrizen für jede Berechnung des Koordinatensystem umzusetzen, so dass die Linie AB die X-Achse wird und der Mittelpunkt von AB ist der Ursprung.

I denkt dies eine einfache Art und Weise ist die Matrizen zu konstruieren:

trans = - ((A + B) / 2)        // translate midpoint of AB to origin

rot.col1 = AB / AB.mag         // unit vector in AB direction

                        0 -1    
rot.col2 = rot.col1 * (      ) // unit vector perp to AB
                        1  0 

rot = rot.inverse()            // but it needs to be done in reverse

Dann nehmen Sie nur jedes X und tun rot * (X + trans).

Die betreffende Region ist tatsächlich in symmetrisch sowohl die x- und y-Achsen, und schauen Sie den absoluten Wert des x-Koordinate nehmen, und des y-Koordinate.

Dann brauchen Sie nur zu überprüfen:

y < d && x < AB.mag/2            //"along" the line segment
|| (x - AB.mag/2)^2 + y^2 < d^2  // the "end cap".

Sie können einen anderen Trick; kann die Matrix um einen Faktor von AB.mag/2 (nicht vergessen, die Matrizen werden nur einmal berechnet pro (A, B), was bedeutet, dass es besser ist, dass sie zu finden ist langsamer, als die tatsächliche überprüfen selbst) verringern. Dies bedeutet, dass Ihr Scheck wird:

y < 2*d/AB.mag && x < 1
|| (x - 1)^2 + y^2 < (2*d/AB.mag)^2

zwei Instanzen von AB.mag / 2 mit der Konstante 1 ersetzt hat, könnte es einen Hauch schneller sein. Und natürlich können Sie vorauszuberechnen 2*d/AB.mag und (2*d/AB.mag)^2 auch.

Ob dies funktionieren wird schneller als andere Methoden ist abhängig von den Eingaben geben Sie es. Aber wenn die Länge von AB lange bis d verglichen wird, ich denke, es wird sich heraus wesentlich schneller als die Methode, die Sie geschrieben.

Answer 2

Hmmmmmmm .... Was ist die Trefferquote? Wie oft Punkt „X“ die Nähe Anforderungen?

Ich denke, Ihre bestehenden Algorithmus ist gut, und alle zusätzlichen Optimierungen von Abstimmung auf die realen Daten kommen. Wenn zum Beispiel des „X“ Punkt, um die Nähe Test 99% der Zeit trifft, dann denke ich, Ihre Optimierungsstrategie als wesentlich anders sein sollte, wenn es passiert nur den Test 1% der Zeit.

---

//en.wikipedia:

Übrigens, wenn Sie an den Punkt, wo man diesen Algorithmus mit Tausenden von Punkten laufen lassen, sollten Sie alle Punkte in einem K-dimensionalen Baum (oder KDTree ). Es macht die Berechnung der „nächsten Nachbarn“ viel einfacher.

Ihr Problem ist ein wenig komplexer als ein nächster Nachbar (weil Sie die Nähe zu a-Line-Segment sind die Überprüfung nicht nur die Nähe zu einem Punkt), aber ich denke immer noch, die KDTree wird handlich.

Answer 3

Wenn ich das richtig gelesen, dann ist dies fast die gleiche wie die klassischen ray / Kugel Schnitttest wie in 3D-Raytracing verwendet.

In diesem Fall haben Sie eine Kugel an der Stelle X des Radius d, und Sie versuchen, um herauszufinden, ob die Linie AB die Sphäre schneidet. Der einzige Unterschied mit Ray-Tracing ist, dass in diesem Fall, dass Sie eine bestimmte Linie AB haben, während in Raytracing den Strahl ist in der Regel wie origin + distance * direction verallgemeinert, und Sie kümmern sich nicht, wie weit die unendliche Linie AB+ es ist .

In Pseudo-Code aus meiner eigenen Raytracer (basierend auf dem Algorithmus in "Eine Einführung in der Ray-Tracing" gegeben (ed Glassner).

Vector v = X - A
Vector d = normalise(B - A)  // unit direction vector of AB
double b = dot(v, B - A)
double discrim = b^2 - dot(v, v) + d^2
if (discrim < 0)
     return false            // definitely no intersection

Wenn Sie bis hierher haben, dann gibt es einig Chance, dass Ihre Bedingung erfüllt ist. Sie müssen nur herausfinden, ob der Schnittpunkt (e) auf der Linie AB:

discrim = sqrt(discrim)
double t2 = b + discrim
if (t2 <= 0)
    return false             // intersection is before A

double t1 = b  - discrim

result = (t1 < length(AB) || (t2 < length(AB))

Answer 4

  

Dieser Code wird mit der Absicht, das ausgeführt wird für einen großen Satz von P und einem großen Satz von A / B / d Drilling am Ende findet all P, dass ich zumindest eine A / B / d so passieren zu vermuten, dass es ist eine Art und Weise insgesamt die Kosten auf dieser Grundlage zu reduzieren, aber ich habe in dem noch nicht sehe.

In dem Fall, wenn d ~ AB, für einen gegebenen Punkt X, können Sie zunächst prüfen, ob X zu einem der vielen Bereichen des Radius d und Mitte Ai oder Bi gehört. Schauen Sie sich das Bild:

     ......        .....
  ...........   ...........
 ...........................
.......A-------------B.......
 ...........................
  ...........   ...........
     .....         .....

Die ersten beiden Tests

If d^2 > AX.mag^2 return true
If d^2 > BX.mag^2 return true

sind die schnellsten sind, und d, wenn ~ AB sie sind auch diejenigen mit der höchsten Wahrscheinlichkeit erfolgreich zu sein (vorausgesetzt, dass der Test überhaupt gelingt). Gegeben X können Sie tun, um alle „Kugel-Tests“ zuerst, und dann alle die letzten diejenigen:

Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2 

Answer 5

Wenn die Anzahl der Sätze von A / B / d groß ist, und Sie sind auf jeden Fall in 2D, betrachten mit R-Bäume (oder deren Äquivalente oktogonalen), wobei jeder Eintrag in der R-Struktur ist die minimale Begrenzungsrahmen des A / B / d verdreifachen. Dies würde Sie eine Menge von den A / B / d Tripel testen beseitigen mit & konzentrieren Sie Ihre CPU-Leistung nur auf den wenigen, wo jeder Punkt X innerhalb der Begrenzungsrahmen des A / B / d triple ist. Dann machen Sie einen detaillierteren Test wie die, die Sie erwähnen.