Berechnen der durchschnittlichen Entfernung von Punkt zu Liniensegment und Liniensegment zu Liniensegment

Question

Ich suche nach einem Algorithmus, um den durchschnittlichen Abstand zwischen einem Punkt und einem Liniensegment in 3D zu berechnen. Wenn also zwei Punkte A (x1, y1, z1) und B (x2, y2, z2), die das Liniensegment AB repräsentieren, und ein dritter Punkt C (x3, y3, z3) gegeben sind, ist der durchschnittliche Abstand zwischen jedem Punkt auf AB zu Punkt C?

Ich interessiere mich auch für die durchschnittliche Entfernung zwischen zwei Liniensegmenten. Was ist also der durchschnittliche Abstand von jedem Punkt auf AB zu dem nächsten Punkt auf CD, wenn AB und CD gegeben sind?

Ich hatte kein Glück mit den Web-Suchen, die ich ausprobiert habe, so dass alle Vorschläge geschätzt werden.

Danke.

Answer 1

Wenn Sie meinen, was ich denke du meinst mit „durchschnittlich“ (und „Abstand“, dh die L2-Norm von dreeves erwähnt), hier ist ein Verfahren, das ich denke, für die Suche nach dem durchschnittlichen Abstand zwischen einem Punkt arbeiten sollte und ein Liniensegment. Sie benötigen eine Funktion dot(A,B), die das Skalarprodukt zweier Vektoren verwendet.

// given vectors (points) A, B, C 
K1 = dot(A-C,A-C) 
K2 = 2*dot(B-A,A-C) 
K3 = dot(B-A,B-A) 
L1 = sqrt(K3*(K1+K2+K3)) 
L2 = sqrt(K3*K1) 
N = 4*K3*L1 + 2*K2*(L1-L2) + (K2*K2-4*K1*K3)*log((K2+2*L2)/(2*K3+K2+2*L1)) 
D = N/(8*K3^1.5) 

Angenommen ich alles richtig transkribiert haben, wird D dann der durchschnittliche Abstand.

Dies ist im Grunde nur Pseudocode zur Bewertung des Ergebnisses eines Integrals, das ich in Mathematica gemacht habe. Vielleicht gibt es dafür ein paar nette Abkürzungen, aber wenn, dann weiß ich es nicht. (Und wenn es keinen gibt, würde ich fragen, wie viel Sie wirklich brauchen, um diese Berechnung durchzuführen)

Wenn Sie die durchschnittliche Entfernung von dem nächsten Punkt auf einer Linie Segment CD zu allen Punkten auf AB finden möchten, in den meisten In den Fällen, in denen der nächstgelegene Punkt entweder C oder D ist, können Sie einfach beide überprüfen, um zu sehen, welcher näher ist (wahrscheinlich unter Verwendung einer Berechnung für den Mindestabstand, wie in anderen Antworten angegeben). Die einzige Ausnahme ist, wenn CD und AB parallel sind und Sie können eine Senkrechte von einem zum anderen laufen lassen, in diesem Fall müssten Sie Ihre Anforderungen genauer definieren.

Wenn Sie die durchschnittliche Entfernung zwischen allen Punkten auf CD und allen Punkten auf AB finden wollten, könnte es mit einem doppelten Integral gemacht werden, obwohl ich schaudere, wie kompliziert die resultierende Formel wäre.

Answer 2

Zunächst ist der Abstand zwischen zwei Punkten die Quadratwurzel aus der Summe der Quadrate der paarweisen Differenzen der Koordinaten. (Zum Beispiel ist der Abstand von (0,0,0) zu (1,1,1) sqrt (3), aber dies funktioniert für beliebige Punkte in einer beliebigen Anzahl von Dimensionen.) Dieser Abstand ist bekannt als l2-norm (Kleinbuchstaben L) oder Euklidische Norm. Write norm (A, B) für den Abstand zwischen den Punkten A und B.

Auf das interessante Problem der mittleren Abstände ... (Beachten Sie, dass der minimalen Abstand von einem Punkt auf eine Linie zu finden, oder zwischen Liniensegmente ist ein viel häufigeres Problem. Es gab eine Antwort hier mit guten Zeigern für dieses Problem, aber es scheint, dass es in der Zwischenzeit gelöscht wurde.)

Um die durchschnittliche Entfernung von einem Punkt C zu einem Liniensegment AB zu finden, betrachte den Abstand zu einem beliebigen Punkt zwischen A und B, nämlich (1-k) A + kB, wobei k von 0 bis 1 reicht. Das ist die Norm (C, (1-k) A + kB). Also ist die durchschnittliche Entfernung das Integral von k = 0 bis 1 der Norm (C, (1-k) A + kB).

Mathematica kann dieses Integral tun für einen bestimmten A, B und C.

Hier ist eine Mathematica Implementierung:

avgd[A_,B_,C_] := Integrate[Sqrt@Dot[(1-k)*A+k*B-C, (1-k)*A+k*B-C], {k, 0, 1}] 

Die Integra auch Norm[(1-k)*A+k*B-C] geschrieben werden können. Wie auch immer, Mathematica kann es für bestimmte Punkte tun, aber kann es nicht symbolisch integrieren, obwohl David es anscheinend irgendwie geschafft hat. Hier ist Davids Beispiel aus den Kommentaren:

> avgd[{0, 0, 0}, {4, 0, 0}, {4, 3, 0}] // N 

3.73594 

Für das Problem des durchschnittlichen Abstandes zwischen zwei Liniensegmenten, in der Theorie ich denke, das sollte funktionieren:

avgd[A_,B_,C_,D_] := Integrate[Norm[(1-k)A+k*B - (1-j)C - j*D], {k,0,1}, {j,0,1}] 

Aber Mathematica scheint, dass selbst zu ersticken für bestimmte Punkte, geschweige denn symbolisch.

Answer 3

Nun, wenn die Analyse fehlschlägt, für einen Computer erreichen und ein albernes Berechnungsmenge tun, bis Sie ein Gefühl für die Zahlen bekommen ...

ich auch eine Kopie von Mathematica zu haben. Um die Dinge einfach zu halten, da ein Dreieck in einer Ebene liegen muss, habe ich Folgendes im 2D-Raum bearbeitet. Um die Dinge besonders einfach zu halten, gebe ich einen Punkt bei {0,0} und ein Liniensegment von {1,0} bis {0,1} an. Die durchschnittliche Entfernung von Punkt zu Linie muss, wenn es sinnvoll ist, die durchschnittliche Länge aller Linien sein, die von {0.0} zu einer beliebigen Stelle auf dem Liniensegment gezogen werden können. Natürlich gibt es eine ganze Menge solcher Linien, so mit lasst uns beginnen, sagen wir, 10 Mathematica könnte dies als

Mean[Table[EuclideanDistance[{0, 0}, {1 - k, 0 + k}], {k, 0, 1, 10.0^-1}]]] 

die 0.830255 gibt berechnet werden. Der nächste Schritt ist offensichtlich, mache die Anzahl der Linien, die ich größer messe. In der Tat, lassen Sie uns eine Tabelle der Durchschnittswerte erstellen, da der Exponent von 10.0 kleiner wird (sie sind negativ!). In Mathematica:

Table[Mean[Table[EuclideanDistance[{0, 0}, {1 - k, 0 + k}], {k, 0, 1, 
10.0^-i}]], {i, 0, 6}] 

, die produziert:

{1, 0.830255, 0.813494, 0.811801, 0.811631, 0.811615, 0.811613} 

Nach diesem Ansatz I @ Daves Beispiel erneut gearbeitet (die dritte Dimension nicht vergessen):

Table[Mean[Table[EuclideanDistance[{0, 0}, {4, 0 + 3 k}], {k, 0, 1, 
10.0^-i}]], {i, 0, 6}] 

die gibt:

{9/2, 4.36354, 4.34991, 4.34854, 4.34841, 4.34839, 4.34839} 

Dies ist nicht ag ree mit was @dreeves sagt @ Daves Algorithmus berechnet.

EDIT: OK, also habe ich etwas mehr Zeit damit verschwendet. Für das einfache Beispiel I in erster Linie verwendet, das mit einem Punkt, an {0,0} ist und ein Liniensegment von {0,1} zu {1,0} erstreckt definiere ich eine Funktion in Mathematica (wie auch immer), wie folgt aus:

fun2[k_] := EuclideanDistance[{0, 0}, {0 + k, 1 - k}] 

Nun das ist integrierbar.Mathematica gibt:

In[13]:= Integrate[fun2[k], {k, 0, 1}] 

    Out[13]= 1/4 (2 + Sqrt[2] ArcSinh[1]) 

Oder, wenn Sie lieber Zahlen haben würden, dies:

In[14]:= NIntegrate[fun2[k], {k, 0, 1}] 
Out[14]= 0.811613 

das ist, was der rein numerische Ansatz, den ich früher nahm gibt.

Ich werde jetzt wieder an die Arbeit gehen, und es Ihnen allen überlassen, dies zu einem beliebigen Dreieck zu verallgemeinern, das durch einen Punkt und die Endpunkte eines Liniensegments definiert ist.