線と線の交差

ユークリッド幾何学では、直線と直線の交点は、空集合、点、または別の直線になります。これらのケースを区別して交点を見つけることは、たとえば、コンピュータグラフィックス、動作計画、衝突検出などで役立ちます。

3次元ユークリッド幾何学では、2本の線が同一平面上にない場合、それらの線は交点を持たず^{[1] 、}斜線と呼ばれます。しかし、それらの線が同一平面上にある場合は、3つの可能性があります。2本が一致する（別個の線ではない）場合、それらの線には無数の共通点（つまり、どちらか一方の線上のすべての点）があります。2本が別個であるが同じ傾きを持つ場合、それらは平行であり、共通点がないと言われています。それ以外の場合、それらの線には1つの交点があります。

非ユークリッド幾何学の特徴は、2 本の直線が交差する可能性のある点の数と位置、および特定の直線と交差しない可能性のある線 (平行線) の数です。^{[詳細な説明が必要]}

2 本の直線が交差するための必要条件は、それらの直線が同じ平面上にあること、つまり斜線ではないことです。この条件を満たすことは、一方の直線上の 2 つの点ともう一方の直線上の 2 つの点を頂点とする四面体が、体積が0 であるという意味において退化していることと同等です。この条件の代数形式については、「斜線」§「歪度のテスト」を参照してください。

まず、 2次元空間における2本の直線L ₁とL ₂の交点を考える。直線L _{1 は}2つの異なる点( x ₁、y ₁ )と( x ₂、y ₂ )によって定義され、直線L ₂は2つの異なる点( x ₃、y ₃ )と( x ₄、y ₄ )によって定義される。^[2]

直線L ₁とL ₂の交点P は、行列式を使用して定義できます。

${\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}}}\,\!}$

行列式は次のように記述できます。

${\displaystyle {\begin{aligned}P_{x}&={\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})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}\\[4px]P_{y}&={\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})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}\end{aligned}}}$

2 本の線が平行または一致する場合、分母はゼロになります。

上記の交点は、点間の線分ではなく、点によって定義される無限に長い線分に対するものであり、2 つの線分のいずれにも含まれない交点を生成する可能性があります。線分に対する交点の位置を見つけるには、 1 次ベジェパラメータを使用して線L ₁と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}}}$

（ここでtとuは実数）。直線の交点は、tまたはuの次の値のいずれかで見つかります。ここで

${\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})}}}$

そして

${\displaystyle u=-{\frac {\begin{vmatrix}x_{1}-x_{2}&x_{1}-x_{3}\\y_{1}-y_{2}&y_{1}-y_{3}\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_{2})(y_{1}-y_{3})-(y_{1}-y_{2})(x_{1}-x_{3})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}},}$

と

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

0 ≤ t ≤ 1かつ0 ≤ u ≤ 1の場合には交点が存在します。交点は0 ≤ t ≤ 1の場合には最初の線分内にあり、 0 ≤ u ≤ 1の場合には 2 番目の線分内にあります。これらの不等式は除算を必要とせずにテストできるため、正確な点を計算する前に線分の交点の存在を迅速に判断できます。^[3]

2 本の非垂直線の交点の x座標とy座標は、次の置換と並べ替えを使用して簡単に見つけることができます。

2 本の直線にy = ax + cとy = bx + dという方程式があるとします。ここで、a と b は直線の傾き(勾配) 、 cとdは直線のy切片です。2 本の直線が交差する点 (交差する場合) では、両方のy座標が同じになるため、次の等式が成り立ちます。

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

この式を変形してxの値を抽出すると、

${\displaystyle ax-bx=d-c,}$

など、

${\displaystyle x={\frac {d-c}{a-b}}.}$

y座標を見つけるには、 2 つの直線方程式のいずれか、たとえば最初の方程式に xの値を代入するだけです。

${\displaystyle y=a{\frac {d-c}{a-b}}+c.}$

したがって、交点は

${\displaystyle P=\left({\frac {d-c}{a-b}},a{\frac {d-c}{a-b}}+c\right).}$

a = bの場合、2 本の線は平行であり、交差しません。ただし、 c = dの場合は、線は一致し、すべての点で交差します。

同次座標を使用すると、暗黙的に定義された 2 本の線の交点を簡単に特定できます。2D では、すべての点は 3D 点の投影として定義でき、順序付けられた 3 つの要素( x、y、w )として与えられます。3D 座標から 2D 座標へのマッピングは、( x ′、y ′) = ( ⁠x/わ⁠、⁠ええ/わ⁠ )。2D の点を( x , y , 1)と定義することで、同次座標に変換できます。

2次元空間で、a ₁ x + b ₁ y + c ₁ = 0およびa ₂ x + b ₂ y + c ₂ = 0と定義される2本の無限直線の交点を求めるとします。これらの2本の直線は、線座標でU ₁ = ( a ₁ , b ₁ , c ₁ )およびU ₂ = ( a ₂ , b ₂ , c ₂ )と 表すことができます。2本の直線の交点P ′は、次のように簡単に表されます^[4]

${\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})}$

c _p = 0の場合、線は交差しません。

2 本の直線の交差は、追加の直線を含むように一般化できます。n本の直線の交差問題の存在と表現は次のとおりです。

2次元では、2本以上の線が1点で交差することはまずありません。交差するかどうかを判定し、交差する場合は交点を見つけるために、i番目の方程式（i = 1, …, n）を次のように 書きます。

${\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}=b_{i},}$

これらの方程式を行列形式にまとめると、

${\displaystyle \mathbf {A} \mathbf {w} =\mathbf {b} ,}$

ここで、n × 2行列Aのi行目は[ a _{i 1} , a _{i 2} ]であり、wは2 × 1ベクトル[^x
_y]であり、列ベクトルbのi番目の要素はb _iである。 A が独立した列を持つ場合、その階数拡張行列[ A | b ]の階数も 2 である場合に限りnの交点が存在する。交点が存在する場合、交点は次のように与えられる。

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

ここで、A ^{g は}Aのムーア・ペンローズ一般逆行列です( A は列全体の階数を持つため、この形式になります)。あるいは、任意の 2 つの独立した方程式を同時に解くことで解を求めることもできます。ただし、 Aの階数が 1 の場合、拡張行列の階数が 2 であれば解は存在しませんが、階数が 1 であればすべての線が互いに一致します。

上記のアプローチは、3 次元に簡単に拡張できます。3 次元以上では、2 本の線が交差することはほぼありません。交差しない非平行線のペアは、斜め線と呼ばれます。ただし、交差が存在する場合は、次のように見つけることができます。

3次元では、線は2つの平面の交点として表され、それぞれの平面は次の式の式を持つ。

${\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}&a_{i3}\end{bmatrix}}{\begin{bmatrix}x\\y\\z\end{bmatrix}}=b_{i}.}$

したがって、 n本の線のセットは、3 次元座標ベクトルwの2 n 個の方程式で表すことができます。

${\displaystyle \mathbf {A} \mathbf {w} =\mathbf {b} }$

ここで、Aは2 n × 3、bは2 n × 1です。前と同様に、Aがフル列ランクを持ち、拡張行列[ A | b ]がフル列ランクを持たない場合にのみ、唯一の交点が存在し、存在する場合の唯一の交点は次のように与えられます。

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

2 次元以上の場合、通常、最小二乗法の意味で 2 つ以上の線に相互に最も近い点を見つけることができます。

2次元の場合、まず直線iを直線上の点p _iと、その直線に垂直な単位 法線ベクトル n̂ _iとして表します。つまり、x ₁とx _{2 が}直線1上の点である場合、p ₁ = x ₁とし、

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

これは、線に沿った単位ベクトルを直角に回転させたものです。

点xから直線( p , n̂ )までの距離は次のように表される 。

${\displaystyle d{\bigl (}\mathbf {x} ,(\mathbf {p} ,\mathbf {\hat {n}} ){\bigr )}={\bigl |}(\mathbf {x} -\mathbf {p} )\cdot \mathbf {\hat {n}} {\bigr |}=\left|(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\mathbf {\hat {n}} \right|=\left|\mathbf {\hat {n}} ^{\mathsf {T}}(\mathbf {x} -\mathbf {p} )\right|={\sqrt {(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\mathbf {\hat {n}} \mathbf {\hat {n}} ^{\mathsf {T}}(\mathbf {x} -\mathbf {p} )}}.}$

そして、点xから直線までの距離の2乗は

${\displaystyle d{\bigl (}\mathbf {x} ,(\mathbf {p} ,\mathbf {\hat {n}} ){\bigr )}^{2}=(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\left(\mathbf {\hat {n}} \mathbf {\hat {n}} ^{\mathsf {T}}\right)(\mathbf {x} -\mathbf {p} ).}$

多くの線までの距離の二乗の合計がコスト関数です。

${\displaystyle E(\mathbf {x} )=\sum _{i}(\mathbf {x} -\mathbf {p} _{i})^{\mathsf {T}}\left(\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)(\mathbf {x} -\mathbf {p} _{i}).}$

これは次のように並べ替えることができます。

${\displaystyle {\begin{aligned}E(\mathbf {x} )&=\sum _{i}\mathbf {x} ^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {x} -\mathbf {x} ^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}-\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {x} +\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\\&=\mathbf {x} ^{\mathsf {T}}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} -2\mathbf {x} ^{\mathsf {T}}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right)+\sum _{i}\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}.\end{aligned}}}$

最小値を見つけるには、 xについて微分し、その結果をゼロベクトルに設定します。

${\displaystyle {\frac {\partial E(\mathbf {x} )}{\partial \mathbf {x} }}={\boldsymbol {0}}=2\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} -2\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right)}$

それで

${\displaystyle \left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} =\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}}$

など

${\displaystyle \mathbf {x} =\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)^{-1}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right).}$

n̂ _{i は}2次元以上では明確に定義されていないが、 n̂ _i n̂ _i ^Tは単に対称行列であり、直線に沿った方向の固有値はゼロであり、その固有値は直線までの距離を与えるp _iと別の点の間の距離の半ノルムを与えることに注意することで、任意の次元数に一般化することができる。任意の次元数で、v̂ _{i が}i番目の直線に沿った単位ベクトルである場合、

${\displaystyle \mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}}$なる${\displaystyle \mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}}$

ここでIは単位行列であり、^[5]

${\displaystyle x=\left(\sum _{i}\mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}\right)^{-1}\left(\sum _{i}\left(\mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}\right)\mathbf {p} _{i}\right).}$

一連の直線の交点を見つけるには、それらの直線から最短距離にある点を計算します。各直線は、原点a _iと単位方向ベクトルn̂ _iによって定義されます。点pから直線の 1 つまでの距離の 2 乗は、ピタゴラスの法則から求められます。

${\displaystyle d_{i}^{2}=\left\|\mathbf {p} -\mathbf {a} _{i}\right\|^{2}-\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}=\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\left(\mathbf {p} -\mathbf {a} _{i}\right)-\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}}$

ここで( p − a _i ) ^T n̂ _{i は}直線i上のp − a _iの射影である。すべての直線に対する正方形までの距離の合計は

${\displaystyle \sum _{i}d_{i}^{2}=\sum _{i}\left({\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}}\left(\mathbf {p} -\mathbf {a} _{i}\right)-{\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}}\right)}$

この式を最小化するには、 pに関して微分します。

${\displaystyle \sum _{i}\left(2\left(\mathbf {p} -\mathbf {a} _{i}\right)-2\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)\mathbf {\hat {n}} _{i}\right)={\boldsymbol {0}}}$

${\displaystyle \sum _{i}\left(\mathbf {p} -\mathbf {a} _{i}\right)=\sum _{i}\left(\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\left(\mathbf {p} -\mathbf {a} _{i}\right)}$

その結果

${\displaystyle \left(\sum _{i}\left(\mathbf {I} -\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\right)\mathbf {p} =\sum _{i}\left(\mathbf {I} -\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {a} _{i}}$

ここで、I は単位行列です。これは行列Sp = Cであり、解はp = S ⁺ Cです。ここで、S ^+はSの擬似逆行列です。

球面幾何学では、任意の2つの大円は交差します。^[6]

双曲幾何学では、任意の直線と任意の点が与えられた場合、その点を通り、与えられた直線と交差しない直線は無数に存在する。^[6]

• 線分の交点
• 射影空間における直線の交差
• 2本の平行線間の距離
• 点から線までの距離
• 線と面の交差
• 平行線公理
• 三角測量（コンピュータービジョン）
• 交差（ユークリッド幾何学）§ 2つの線分

• 2 次元、3 次元、またはそれ以上の次元に適用可能な、最近接ポイントを持つ線分とセグメント間の距離。