Linie-Linie-Schnittpunkt - Line–line intersection

In der euklidischen Geometrie kann der Schnittpunkt einer Linie und einer Linie die leere Menge , ein Punkt oder eine Linie sein. Das Unterscheiden dieser Fälle und das Auffinden des Schnittpunkts haben beispielsweise in der Computergrafik , der Bewegungsplanung und der Kollisionserkennung Verwendung .

In dreidimensionalen euklidischen Geometrie, wenn zwei Linien nicht in der gleichen Ebene sind sie genannt skew Linien und haben keinen Schnittpunkt. Wenn sie in derselben Ebene liegen, gibt es drei Möglichkeiten: Wenn sie zusammenfallen (keine verschiedenen Linien sind), haben sie unendlich viele Punkte gemeinsam (nämlich alle Punkte auf einem von ihnen); wenn sie verschieden sind, aber die gleiche Steigung haben, werden sie als parallel bezeichnet und haben keine gemeinsamen Punkte; andernfalls haben sie einen einzigen Schnittpunkt.

Die Unterscheidungsmerkmale der nichteuklidischen Geometrie sind die Anzahl und Lagen möglicher Schnittpunkte zwischen zwei Geraden und die Anzahl möglicher Geraden ohne Schnittpunkte (Parallellinien) mit einer gegebenen Geraden.

Formeln

Eine notwendige Bedingung für den Schnitt zweier Linien ist, dass sie sich in derselben Ebene befinden, d. h. keine schrägen Linien sind. Erfüllung dieser Bedingung ist äquivalent zu dem Tetraeders mit Scheitelpunkten an zwei der Punkte in einer Zeile und zwei der Punkte auf den anderen Leitung Wesen degenerierten im Sinne von Null Volumen . Für die algebraische Form dieser Bedingung siehe Schiefe Linien § Prüfung auf Schiefe .

Gegeben zwei Punkte auf jeder Linie

Zuerst betrachten wir den Schnittpunkt zweier Linien und im 2-dimensionalen Raum, wobei die Linie durch zwei verschiedene Punkte und definiert wird und die Linie durch zwei verschiedene Punkte und definiert wird . ${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle L_{1}}$${\displaystyle (x_{1},y_{1})}$${\displaystyle (x_{2},y_{2})}$${\displaystyle L_{2}}$${\displaystyle (x_{3},y_{3})}$${\displaystyle (x_{4},y_{4})}$

Der Schnittpunkt der Linie und kann mit Hilfe von Determinanten definiert werden . ${\displaystyle P}$${\displaystyle L_{1}}$${\displaystyle L_{2}}$

${\displaystyle P_{x}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix}}&{\ begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4}&y_{4} \end{vmatrix}}&{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\begin{vmatrix}x_ {1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{ vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix} }}\,\!\qquad P_{y}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix }}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4 }&y_{4}\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\ begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\ \{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}} \end{vmatrix}}}\,\!}$

Die Determinanten können ausgeschrieben werden als:

${\displaystyle {\begin{aligned}(P_{x},P_{y})={\Biggl (}&{\frac {(x_{1}y_{2}-y_{1}x_{2}) (x_{3}-x_{4})-(x_{1}-x_{2})(x_{3}y_{4}-y_{3}x_{4})}{D}},\\ &{\frac {(x_{1}y_{2}-y_{1}x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{ 3}y_{4}-y_{3}x_{4})}{D}}{\Biggr )}\end{ausgerichtet}}}$

wobei der Nenner ist:

${\displaystyle D=(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4}) }$

Wenn die beiden Geraden parallel oder zusammenfallen, ist der Nenner Null. Wenn die Linien fast parallel sind, kann eine Computerlösung auf numerische Probleme stoßen, die die oben beschriebene Lösung implementieren: Die Erkennung dieser Bedingung könnte einen ungefähren Test in einer praktischen Anwendung erfordern. Ein alternativer Ansatz könnte darin bestehen, die Liniensegmente so zu drehen, dass eines davon horizontal ist, wodurch die Lösung der gedrehten parametrischen Form der zweiten Linie leicht erhalten wird. Eine sorgfältige Diskussion der Sonderfälle ist erforderlich (Parallellinien/koinzidente Linien, überlappende/nicht überlappende Intervalle).

Gegeben zwei Punkte auf jedem Liniensegment

Beachten Sie, dass der obige Schnittpunkt für die unendlich langen Linien gilt, die durch die Punkte definiert sind, und nicht für die Liniensegmente zwischen den Punkten, und kann einen Schnittpunkt erzeugen, der in keinem der beiden Liniensegmente enthalten ist. Um die Position des Schnittpunkts in Bezug auf die Liniensegmente zu finden, können wir Linien und Bézier- Parameter ersten Grades definieren : ${\displaystyle L_{1}}$${\displaystyle L_{2}}$

${\displaystyle L_{1}={\begin{bmatrix}x_{1}\\y_{1}\end{bmatrix}}+t{\begin{bmatrix}x_{2}-x_{1}\\y_ {2}-y_{1}\end{bmatrix}},\qquad L_{2}={\begin{bmatrix}x_{3}\\y_{3}\end{bmatrix}}+u{\begin{ bmatrix}x_{4}-x_{3}\\y_{4}-y_{3}\end{bmatrix}}}$

(wobei t und u reelle Zahlen sind). Der Schnittpunkt der Geraden wird mit einem der folgenden Werte von t oder u gefunden , wobei

${\displaystyle t={\frac {\begin{vmatrix}x_{1}-x_{3}&x_{3}-x_{4}\\y_{1}-y_{3}&y_{3}-y_{ 4}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{ 4}\end{vmatrix}}}={\frac {(x_{1}-x_{3})(y_{3}-y_{4})-(y_{1}-y_{3})(x_ {3}-x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3} -x_{4})}}}$

und

${\displaystyle u={\frac {\begin{vmatrix}x_{1}-x_{3}&x_{1}-x_{2}\\y_{1}-y_{3}&y_{1}-y_{ 2}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{ 4}\end{vmatrix}}}={\frac {(x_{1}-x_{3})(y_{1}-y_{2})-(y_{1}-y_{3})(x_ {1}-x_{2})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3} -x_{4})}},}$

mit:

${\displaystyle (P_{x},P_{y})=(x_{1}+t(x_{2}-x_{1}),\;y_{1}+t(y_{2}-y_{ 1}))\quad {\text{or}}\quad (P_{x},P_{y})=(x_{3}+u(x_{4}-x_{3}),\;y_{ 3}+u(y_{4}-y_{3}))}$

Es gibt einen Schnittpunkt, wenn 0.0 ≤  t  ≤ 1.0 und 0.0 ≤  u  ≤ 1.0. Der Schnittpunkt fällt in das erste Liniensegment, wenn 0,0  t  ≤ 1,0, und in das zweite Liniensegment, wenn 0,0  u  ≤ 1,0. Diese Ungleichungen können ohne Division getestet werden, was eine schnelle Bestimmung des Vorhandenseins eines Liniensegment-Schnittpunkts ermöglicht, bevor der genaue Punkt berechnet wird.

Gegeben zwei Geradengleichungen

Die Koordinaten und des Schnittpunkts zweier nicht-vertikaler Geraden können durch die folgenden Ersetzungen und Umordnungen leicht gefunden werden. ${\displaystyle x}$${\displaystyle y}$

Angenommen, zwei Geraden haben die Gleichungen und wo und sind die Steigungen (Gradienten) der Geraden und wo und sind die y- Schnittpunkte der Geraden. An dem Punkt, an dem sich die beiden Linien schneiden (falls dies der Fall ist ), sind beide Koordinaten gleich, daher die folgende Gleichheit: ${\displaystyle y=ax+c}$${\displaystyle y=bx+d}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle d}$${\displaystyle y}$

${\displaystyle ax+c=bx+d.}$

Wir können diesen Ausdruck neu anordnen, um den Wert von zu extrahieren , ${\displaystyle x}$

${\displaystyle ax-bx=dc,}$

und so,

${\displaystyle x={\frac {dc}{ab}}.}$

Um die y- Koordinate zu finden , müssen wir nur den Wert von x in eine der beiden Liniengleichungen einsetzen, zum Beispiel in die erste:

${\displaystyle y=a{\frac {dc}{ab}}+c.}$

Der Schnittpunkt ist also

${\displaystyle P\left({\frac{dc}{ab}},a{\frac{dc}{ab}}+c\right).}$

Beachten Sie, dass bei a = b die beiden Geraden parallel sind . Wenn auch c ≠ d ist , sind die Geraden verschieden und es gibt keinen Schnittpunkt, ansonsten sind die beiden Geraden identisch.

Homogene Koordinaten verwenden

Durch die Verwendung homogener Koordinaten kann der Schnittpunkt zweier implizit definierter Geraden recht einfach bestimmt werden. In 2D kann jeder Punkt als Projektion eines 3D-Punktes definiert werden, der als geordnetes Tripel angegeben wird . Die Abbildung von 3D- auf 2D-Koordinaten ist . Wir können 2D-Punkte in homogene Koordinaten umwandeln, indem wir sie als definieren . ${\displaystyle (x,y,w)}$${\displaystyle (x',y')=(x/w,y/w)}$${\displaystyle (x,y,1)}$

Angenommen, wir wollen den Schnittpunkt zweier unendlicher Geraden im 2-dimensionalen Raum finden, die als und definiert sind . Wir können diese beiden Linien in Linienkoordinaten darstellen als und , ${\displaystyle a_{1}x+b_{1}y+c_{1}=0}$${\displaystyle a_{2}x+b_{2}y+c_{2}=0}$${\displaystyle U_{1}=(a_{1},b_{1},c_{1})}$${\displaystyle U_{2}=(a_{2},b_{2},c_{2})}$

Der Schnittpunkt zweier Geraden ist dann einfach gegeben durch ${\displaystyle P'}$

${\displaystyle P'=(a_{p},b_{p},c_{p})=U_{1}\times U_{2}=(b_{1}c_{2}-b_{2}c_{ 1},a_{2}c_{1}-a_{1}c_{2},a_{1}b_{2}-a_{2}b_{1})}$

Wenn sich die Linien nicht schneiden. ${\displaystyle c_{p}=0}$

Mehr als zwei Zeilen

Der Schnittpunkt zweier Linien kann verallgemeinert werden, um zusätzliche Linien einzubeziehen. Existenz und Ausdruck für das n- Linien-Schnittpunktproblem sind wie folgt.

In zwei Dimensionen

In zwei Dimensionen schneiden sich mehr als zwei Linien mit ziemlicher Sicherheit nicht an einem einzigen Punkt. Um festzustellen, ob dies der Fall ist, und falls ja, um den Schnittpunkt zu finden, schreiben Sie die i- te Gleichung ( i = 1, …, n ) als und stapeln Sie diese Gleichungen in Matrixform als ${\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}\end{bmatrix}}{\begin{bmatrix}x&y\end{bmatrix}}^{\mathsf {T}}=b_{i}, }$

${\displaystyle Aw=b,}$

wobei die i -te Zeile des n × 2 - Matrix A ist , w der 2 × 1 - Vektor ist ( x, y ) ^T , und das i -te Element des Spaltenvektors b ist b _i . Wenn A unabhängige Spalten hat, ist sein Rang 2. Dann und nur dann, wenn der Rang der erweiterten Matrix [ A | b ] ebenfalls 2 ist, existiert eine Lösung der Matrixgleichung und damit ein Schnittpunkt der n Geraden. Der Schnittpunkt, falls vorhanden, ist gegeben durch ${\displaystyle (a_{i1},a_{i2})}$

${\displaystyle w=A^{g}b=\left(A^{\mathsf {T}}A\right)^{-1}A^{\mathsf {T}}b,}$

wo ist die verallgemeinerte Moore-Penrose-Inverse von (die die gezeigte Form hat, weil A vollen Spaltenrang hat). Alternativ kann die Lösung durch gemeinsames Lösen von zwei beliebigen unabhängigen Gleichungen gefunden werden. Aber wenn der Rang von A nur 1 ist, dann gibt es keine Lösung, wenn der Rang der erweiterten Matrix 2 ist, aber wenn sein Rang 1 ist, fallen alle Linien zusammen. ${\displaystyle A^{g}}$${\displaystyle A}$

In drei Dimensionen

Der obige Ansatz kann ohne weiteres auf drei Dimensionen erweitert werden. In drei oder mehr Dimensionen schneiden sich sogar zwei Linien mit ziemlicher Sicherheit nicht; Paare von nicht parallelen Linien, die sich nicht schneiden, werden als Schräglinien bezeichnet . Wenn jedoch eine Schnittmenge existiert, kann sie wie folgt gefunden werden.

In drei Dimensionen wird eine Gerade durch den Schnittpunkt zweier Ebenen dargestellt, von denen jede eine Gleichung der Form hat Somit kann eine Menge von n Geraden durch 2 n Gleichungen im 3-dimensionalen Koordinatenvektor w = ( x , y , z ) ^T : ${\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}&a_{i3}\end{bmatrix}}{\begin{bmatrix}x&y&z\end{bmatrix}}^{\mathsf {T}}=b_ {ich}.}$

${\displaystyle Aw=b}$

wobei nun A 2 n × 3 und b 2 n × 1 ist. Wie zuvor gibt es genau dann einen eindeutigen Schnittpunkt, wenn A vollen Spaltenrang hat und die erweiterte Matrix [ A | b ] nicht, und der eindeutige Durchschnitt, falls er existiert, ist gegeben durch

${\displaystyle w=\left(A^{\mathsf {T}}A\right)^{-1}A^{\mathsf {T}}b.}$

Nächste Punkte, um Linien zu verzerren

In zwei oder mehr Dimensionen können wir normalerweise einen Punkt finden, der zwei oder mehr Linien im Sinne der kleinsten Quadrate am nächsten liegt .

In zwei Dimensionen

In dem zweidimensionalen Fall wird zuerst darstellen Linie i als ein Punkt, an der Linie und eine Einheitsnormalvektor , senkrecht zu dieser Linie. Das heißt, wenn und Punkte auf Linie 1 sind, dann sei und sei ${\displaystyle p_{i}}$ ${\displaystyle {\hat {n}}_{i}}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle p_{1}=x_{1}}$

${\displaystyle {\hat {n}}_{1}:={\begin{bmatrix}0&-1\\1&0\end{bmatrix}}{\frac {x_{2}-x_{1}}{\ |x_{2}-x_{1}\|}}}$

Dies ist der um 90 Grad gedrehte Einheitsvektor entlang der Linie.

Beachten Sie, dass der Abstand von einem Punkt x zur Linie gegeben ist durch ${\displaystyle (p,{\hat{n}})}$

${\displaystyle d(x,(p,n))=|(xp)\cdot {\hat{n}}|=\left|(xp)^{\top }{\hat{n}}\right| =\left|{\hat{n}}^{\top}(xp)\right|={\sqrt {(xp)^{\top }{\hat{n}}{\hat{n}}^ {\top}(xp)}}.}$

Der quadrierte Abstand von einem Punkt x zu einer Geraden ist also

${\displaystyle d(x,(p,n))^{2}=(xp)^{\top}\left({\hat{n}}{\hat{n}}^{\top}\right )(xp).}$

Die Summe der quadrierten Distanzen zu vielen Linien ist die Kostenfunktion :

${\displaystyle E(x)=\sum _{i}(x-p_{i})^{\top }\left({\hat {n}}_{i}{\hat {n}}_{ i}^{\top}\right)(x-p_{i}).}$

Dies kann neu angeordnet werden:

${\displaystyle {\begin{aligned}E(x)&=\sum _{i}x^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^ {\top}xx^{\top }{\hat{n}}_{i}{\hat{n}}_{i}^{\top}p_{i}-p_{i}^{\top }{\hat{n}}_{i}{\hat{n}}_{i}^{\top}x+p_{i}^{\top }{\hat{n}}_{i} {\hat{n}}_{i}^{\top}p_{i}\\&=x^{\top}\left(\sum _{i}{\hat {n}}_{i} {\hat{n}}_{i}^{\top}\right)x-2x^{\top}\left(\sum _{i}{\hat{n}}_{i}{\hat {n}}_{i}^{\top}p_{i}\right)+\sum_{i}p_{i}^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}.\end{ausgerichtet}}}$

Um das Minimum zu finden, differenzieren wir nach x und setzen das Ergebnis gleich dem Nullvektor:

${\displaystyle {\frac {\partial E(x)}{\partial x}}=0=2\left(\sum_{i}{\hat{n}}_{i}{\hat{n} }_{i}^{\top}\right)x-2\left(\sum_{i}{\hat{n}}_{i}{\hat{n}}_{i}^{\ oben }p_{i}\right)}$

so

${\displaystyle \left(\sum_{i}{\hat{n}}_{i}{\hat{n}}_{i}^{\top}\right)x=\sum_{i} {\hat{n}}_{i}{\hat{n}}_{i}^{\top}p_{i}}$

und so

${\displaystyle x=\left(\sum_{i}{\hat{n}}_{i}{\hat{n}}_{i}^{\top}\right)^{-1}\ left(\sum_{i}{\hat{n}}_{i}{\hat{n}}_{i}^{\top}p_{i}\right).}$

In mehr als zwei Dimensionen

Obwohl dies in mehr als zwei Dimensionen nicht genau definiert ist, kann dies auf eine beliebige Anzahl von Dimensionen verallgemeinert werden, indem man feststellt, dass dies einfach die (symmetrische) Matrix mit allen Eigenwerten Eins ist, mit Ausnahme eines Null-Eigenwerts in der Richtung entlang der Linie, die eine Seminorm auf liefert der Abstand zwischen einem anderen Punkt, der den Abstand zur Linie angibt. Wenn in einer beliebigen Anzahl von Dimensionen ein Einheitsvektor entlang der i- ten Linie ist, dann ${\displaystyle {\hat {n}}_{i}}$${\displaystyle {\hat{n}}_{i}{\hat{n}}_{i}^{\top }}$${\displaystyle p_{i}}$${\displaystyle {\hat {v}}_{i}}$

${\displaystyle {\hat{n}}_{i}{\hat{n}}_{i}^{\top }}$ wird ${\displaystyle I-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }}$

wobei I die Identitätsmatrix ist, und so

${\displaystyle x=\left(\sum_{i}I-{\hat{v}}_{i}{\hat{v}}_{i}^{\top}\right)^{-1 }\left(\sum_{i}\left(I-{\hat{v}}_{i}{\hat{v}}_{i}^{\top}\right)p_{i}\ rechts).}$

Allgemeine Herleitung

Um den Schnittpunkt einer Reihe von Linien zu finden, berechnen wir den Punkt mit minimalem Abstand zu ihnen. Jede Linie wird durch einen Ursprung und einen Einheitsrichtungsvektor definiert, . Das Quadrat der Entfernung von einem Punkt zu einer der Geraden wird von Pythagoras gegeben: ${\displaystyle a_{i}}$${\displaystyle n_{i}}$${\displaystyle p}$

${\displaystyle d_{i}^{2}=\left\|p-a_{i}\right\|^{2}-\left[\left(p-a_{i}\right)^{\mathsf {T}}*n_{i}\right]^{2}=\left(p-a_{i}\right)^{\mathsf {T}}*\left(p-a_{i}\right) -\left[\left(p-a_{i}\right)^{\mathsf{T}}*n_{i}\right]^{2}}$

Wobei: ist die Projektion von auf der Linie . Die Summe der Abstände zum Quadrat zu allen Linien ist: ${\displaystyle {\left(p-a_{i}\right)}^{\mathsf {T}}*n_{i}}$${\displaystyle \left(p-{{a}_{i}}\right)}$${\displaystyle i}$

${\displaystyle \sum_{i}d_{i}^{2}=\sum_{i}\left[{\left(p-a_{i}\right)^{\mathsf {T}}}* \left(p-a_{i}\right)-{\left[\left(p-a_{i}\right)^{\mathsf {T}}*n_{i}\right]^{2}} \rechts]}$

Um diesen Ausdruck zu minimieren, differenzieren wir ihn nach . ${\displaystyle p}$

${\displaystyle \sum_{i}\left[2*\left(p-a_{i}\right)-2*\right[{{\left(p-a_{i}\right)}^{\ mathsf {T}}}*n_{i}]*n_{i}]=0}$

${\displaystyle \sum_{i}\left(p-a_{i}\right)=\sum_{i}\left[n_{i}*n_{i}^{\mathsf {T}}\right ]*\left(p-a_{i}\right)}$

Es ergibt:

${\displaystyle \left[\sum_{i}\left[I-{n_{i}}*{n_{i}}^{\mathsf {T}}\right]\right]*p=\sum_ {i}\left[I-{n_{i}}*{n_{i}}^{\mathsf {T}}\right]*{a_{i}}}$

Wo ist die Identitätsmatrix. Dies ist eine Matrix mit Lösung , wobei die Pseudo-Inverse von ist . ${\displaystyle I}$${\displaystyle S*p=C}$${\displaystyle p={S^{+}}*C}$${\displaystyle {S}^{+}}$${\displaystyle S}$

Siehe auch

• Schnittpunkt des Liniensegments
• Linienschnittpunkt im projektiven Raum
• Abstand zwischen zwei parallelen Linien
• Entfernung von einem Punkt zu einer Linie
• Linie-Ebene-Schnittpunkt
• Paralleles Postulat
• Triangulation (Computer Vision)
• Schnittpunkt (Euklidische Geometrie) § Zwei Liniensegmente

Verweise

Externe Links

• Abstand zwischen Linien und Segmenten mit ihrem engsten Annäherungspunkt , anwendbar auf zwei, drei oder mehr Dimensionen.