線と線の交差点

Common point(s) shared by two lines in Euclidean geometry

交差する2本の線

ユークリッド幾何学において、直線と直線の交点は、空集合、一点、あるいは直線（一致する場合）のいずれかとなります。これらの場合を区別し、交点を求めることは、例えばコンピュータグラフィックス、動作計画、衝突検出などに応用できます。

ユークリッド空間において、2本の直線が同一平面上にない場合、それらの直線には交点がなく^{[1] 、}斜直線と呼ばれます。しかし、それらの直線が同一平面上にある場合、3つの可能性が存在します。2本の直線が一致する（同じ直線である）場合、それらの直線には無限個ある点がすべて共通しています。2本の直線は異なっているが同じ方向を向いている場合、それらは平行であるとされ、共通点はありません。そうでない場合、それらの直線には1つの交点があり、例えば、単集合として表されます。 ${\displaystyle \{A\}}$

非ユークリッド幾何学は、球面など、1 本の直線が他のどの直線とも平行ではない空間や、1 つの点を通る複数の直線がすべて別の直線と平行になる空間を記述します。^{[さらなる説明が必要]}

数式

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

各線上に2点ずつある場合

_まず、 2次元空間における2本の直線L1とL2の交点を考える_。直線L1_{は2つの異なる点}( x1、y1 )と( _{x2 、y2} )で定義され、直線L2は2_つの異なる点( x3、y3 ₎と( x4、_y4 )で定義される。[ ^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 つの線が平行または一致する場合、分母は 0 になります。

各線分上の2点が与えられる

上記の交点は、点間の線分ではなく、点によって定義される無限長の直線の交点であり、2つの線分のいずれにも含まれない交点を生成する可能性があります。線分に対する交点の位置を求めるために、直線L ₁とL ₂を1次ベジェ曲線パラメータで定義します。

${\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軸と を共有し、と簡約する場合、 ${\displaystyle x_{2}=x_{1}+1}$ ${\displaystyle t}$ ${\displaystyle u}$ $${\displaystyle t=u={\frac {y_{1}-y_{3}}{y_{1}-y_{2}-y_{3}+y_{4}}},}$$ $${\displaystyle (P_{x},P_{y})={\bigl (}x_{1}+t,\;y_{1}+t(y_{2}-y_{1}){\bigr )}\quad {\text{or}}\quad (P_{x},P_{y})={\bigl (}x_{1}+t,\;y_{3}+t(y_{4}-y_{3}){\bigr )}.}$$

2つの直線方程式が与えられた場合

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 つの線は一致し、すべての点で交差します。

同次座標の使用

同次座標を用いることで、暗黙的に定義された2本の直線の交点を非常に簡単に決定することができます。2次元では、すべての点は3次元点の投影として定義でき、これは順序付けられた3つの組( x , y , w )として与えられます。3次元座標から2次元座標へのマッピングは、( x ′, y ′) = ( ⁠×/わ⁠、⁠y/わ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行以上

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が独立な列を持つ場合、その階数2 である。そして拡張行列[ A | b ]の階数場合にのみ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次元にも容易に拡張できます。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の2n方程式で表すことができます。

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

斜線に最も近い点

PQ、2つの斜線ABとCDの間の最短距離はABとCDの両方に垂直です

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

2次元では

2次元の場合、まず直線iを、直線上の点p _iとその直線に垂直な単位 法線ベクトル n̂ _iで表します。つまり、直線1上の点x ₁とx _{2であれば、} 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).}$

2次元以上

n̂ _{i は}2次元以上では明確に定義されないが、n̂ i n̂ i T は単に対称行列であり、直線に沿う方向の固有値が0で、その方向の固有値が1であることに注意すれば、任意の次元に一般化できる。この固有値は、_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から直線のいずれかまでの距離の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つの線分

参考文献

1. Cook, Jeremy (2023年11月21日). 「幾何学における共面線｜定義、図、例」 . 2024年11月1日閲覧。
2. Weisstein, Eric W.「Line-Line Intersection」. MathWorld . 2008年1月10日閲覧。
3. アントニオ・フランクリン (1992). 「第IV章6: 線分の交差の高速化」. カーク・デイビッド (編). 『グラフィックス・ジェムズIII 』 . アカデミック・プレス, pp.  199– 202. ISBN 0-12-059756-X。
4. Birchfield, Stanley (1998-04-23). 「同次座標」. robotics.stanford.edu . 2000年9月29日時点のオリジナルよりアーカイブ。 2015年8月18日閲覧。
5. Traa, Johannes (2013). 「Least-Squares Intersection of Lines」（PDF） . cal.cs.illinois.edu . オリジナル（PDF）から2017年9月12日にアーカイブ。 2018年8月30日閲覧。
6. 「双曲空間の探究」（PDF） . math.berkeley.edu . 2022年6月3日閲覧。

外部リンク

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Line–line_intersection&oldid=1323331140"