線と線の交点

_まず、 2次元空間における2つの直線L1とL2の交点を考えます。直線L1は2つ_の異なる点( _x1 , _y1 )と₍ x2 , y2 )で定義_され、直線L2は_2つ^{の異なる点}( x3 , y3 ₎と( x4 , _y4 )で定義されます。_[ ⁶ ]

直線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つの線分のどちらにも含まれない交点を生成する可能性があります。線分に対する交点の位置を見つけるために、直線L1とL2_を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番目の線分内にあります。これらの不等式は除算を必要とせずにテストできるため、正確な交点を計算する前に、任意の線分交点の存在を迅速に判断できます。^{[ 7 ]}

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本の非垂直な直線の交点の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座標を求めるには、 xの値を2つの直線の方程式のいずれかに代入するだけでよい。例えば、最初の方程式に代入すると次のようになる。

${\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 では、すべての点は、順序付き 3 つ( x、y、w )として与えられる 3D 点の投影として定義できます。 3D から 2D 座標へのマッピングは( x ′、y ′) = ( ⁠ x / w ⁠、⁠ y / w ⁠ )です。 2D 点を( x、y、 1)と定義することで、同次座標に変換できます。

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

${\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本以上の直線が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 ]のランクも 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における2n個の方程式で表すことができる。

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

ここで、Aは2n × 3、bは2n ×1である。これまでと同様に、 Aがフル列ランクであり、拡大行列[ A | b ]がフル列ランクでない場合のみ、一意の交点が存在する。そして、存在する場合の一意の交点は次のように与えられる。

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

2次元の場合、まず、直線i を直線上の点p _iと、その直線に垂直な単位法線ベクトルn̂ _iで表します。つまり、x ₁とx ₂が直線 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から直線までの距離の二乗は次のようになります。

${\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は、線に沿った方向のゼロ固有値を除いてすべての固有値が 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は単位行列であり、したがって^{[ 9 ]}

${\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からいずれかの直線までの距離の二乗は、ピタゴラスの定理から与えられます。

${\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の擬似逆行列です。