交差（幾何学）

幾何学において、交差点とは、2 つ以上のオブジェクト (直線、曲線、平面、面など) に共通する点、直線、または曲線のことです。ユークリッド幾何学における最も単純なケースは、 2 つの異なる直線間の交差点です。交差点は、1 つの点(頂点と呼ばれることもあります) であるか、存在しません (直線が平行である場合)。その他の幾何学的交差点の種類には、次のものがあります。

• 線と面の交差
• 線と球の交差
• 多面体と直線の交差
• 線分の交点
• 交差曲線

平面（高次元空間に埋め込まれた線状の幾何学的オブジェクト）の交差の判定は、線型代数の単純なタスク、つまり線型方程式の連立解法です。一般に、交差の判定は非線型方程式につながり、これはニュートン反復法などを使用して数値的に解くことができます。直線と円錐曲線（円、楕円、放物線など）または二次曲線（球、円柱、双曲面など）との交差の問題は、簡単に解ける二次方程式につながります。二次曲線同士の交差は、代数的に解ける四次方程式につながります。

2本の非平行線の交点を決定する

${\displaystyle a_{1}x+b_{1}y=c_{1},\ a_{2}x+b_{2}y=c_{2}}$

クラメールの規則または変数を代入することで、交点の座標が得られます 。 ${\displaystyle (x_{s},y_{s})}$

${\displaystyle x_{s}={\frac {c_{1}b_{2}-c_{2}b_{1}}{a_{1}b_{2}-a_{2}b_{1}}},\quad y_{s}={\frac {a_{1}c_{2}-a_{2}c_{1}}{a_{1}b_{2}-a_{2}b_{1}}}.\ }$

(線が平行な場合は、0 で割る必要があるため、これらの式は使用できません。) ${\displaystyle a_{1}b_{2}-a_{2}b_{1}=0}$

2 つの平行でない線分 については、対応する線の交点が線分内に含まれる必要がないため、必ずしも交点が存在するわけではありません (図を参照)。状況を確認するには、線のパラメトリック表現を使用します。 ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2})}$${\displaystyle (x_{3},y_{3}),(x_{4},y_{4})}$${\displaystyle (x_{0},y_{0})}$

${\displaystyle (x(s),y(s))=(x_{1}+s(x_{2}-x_{1}),y_{1}+s(y_{2}-y_{1})),}$

${\displaystyle (x(t),y(t))=(x_{3}+t(x_{4}-x_{3}),y_{3}+t(y_{4}-y_{3})).}$

対応するパラメータが条件を満たす場合、線分は対応する線の共通点でのみ交差します。パラメータは線形システムの解です。 ${\displaystyle (x_{0},y_{0})}$${\displaystyle s_{0},t_{0}}$${\displaystyle 0\leq s_{0},t_{0}\leq 1}$${\displaystyle s_{0},t_{0}}$

${\displaystyle s(x_{2}-x_{1})-t(x_{4}-x_{3})=x_{3}-x_{1},}$

${\displaystyle s(y_{2}-y_{1})-t(y_{4}-y_{3})=y_{3}-y_{1}\ .}$

これは、クラメールの規則 (上記参照) を使用してsとtについて解くことができます。条件が満たされる場合は、対応するパラメトリック表現にまたはを挿入し、交点 を取得します。 ${\displaystyle 0\leq s_{0},t_{0}\leq 1}$${\displaystyle s_{0}}$${\displaystyle t_{0}}$${\displaystyle (x_{0},y_{0})}$

例: 線分と線型システム の場合、${\displaystyle (1,1),(3,2)}$${\displaystyle (1,4),(2,-1)}$

${\displaystyle 2s-t=0}$

${\displaystyle s+5t=3}$

および。つまり、線は点で交差します。 ${\displaystyle s_{0}={\tfrac {3}{11}},t_{0}={\tfrac {6}{11}}}$${\displaystyle ({\tfrac {17}{11}},{\tfrac {14}{11}})}$

注:線分ではなく、点のペアによって決定される線を考慮すると、各条件は削除でき、メソッドは線の交点を生成します (上記を参照)。 ${\displaystyle 0\leq s_{0},t_{0}\leq 1}$

交差点については

• 線と円${\displaystyle ax+by=c}$ ${\displaystyle x^{2}+y^{2}=r^{2}}$

xまたはyの直線方程式を解き、それを円の方程式に代入すると、解は次のようになります（二次方程式の公式を使用） 。 ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2})}$

${\displaystyle x_{1/2}={\frac {ac\pm b{\sqrt {r^{2}(a^{2}+b^{2})-c^{2}}}}{a^{2}+b^{2}}}\ ,}$

${\displaystyle y_{1/2}={\frac {bc\mp a{\sqrt {r^{2}(a^{2}+b^{2})-c^{2}}}}{a^{2}+b^{2}}}\ ,}$

この条件が厳密な不等式で成り立つ場合、交点は 2 つあります。この場合、線は円の割線と呼ばれ、交点を結ぶ線分は円の 弦と呼ばれます。${\displaystyle r^{2}(a^{2}+b^{2})-c^{2}>0\ .}$

が成り立つ場合、交点は 1 つだけ存在し、直線は円に接します。弱い不等式が成り立たない場合、直線は円と交差しません。 ${\displaystyle r^{2}(a^{2}+b^{2})-c^{2}=0}$

円の中点が原点でない場合は、^[1]を参照してください。直線と放物線または双曲線の交点も同様に扱うことができます。

2つの円の交点の決定

• ${\displaystyle (x-x_{1})^{2}+(y-y_{1})^{2}=r_{1}^{2},\ \quad (x-x_{2})^{2}+(y-y_{2})^{2}=r_{2}^{2}}$

これは、直線と円が交差する前述のケースに簡略化できます。与えられた 2 つの方程式を引き算すると、直線方程式が得られます。

${\displaystyle 2(x_{2}-x_{1})x+2(y_{2}-y_{1})y=r_{1}^{2}-x_{1}^{2}-y_{1}^{2}-r_{2}^{2}+x_{2}^{2}+y_{2}^{2}.}$

この特別な線は、2 つの円の 根号線です。

特別な場合 ：${\displaystyle \;x_{1}=y_{1}=y_{2}=0}$
この場合、原点は最初の円の中心であり、2番目の中心はx軸上にあります（図を参照）。根線の方程式は次のように簡略化され、交点は次の ように表すことができます。${\displaystyle \;2x_{2}x=r_{1}^{2}-r_{2}^{2}+x_{2}^{2}\;}$${\displaystyle (x_{0},\pm y_{0})}$

${\displaystyle x_{0}={\frac {r_{1}^{2}-r_{2}^{2}+x_{2}^{2}}{2x_{2}}},\quad y_{0}={\sqrt {r_{1}^{2}-x_{0}^{2}}}\ .}$

円の場合、共通点はありません。円 の場合、共通点は 1 つあり、根線は共通接線です。 ${\displaystyle r_{1}^{2}<x_{0}^{2}}$
${\displaystyle r_{1}^{2}=x_{0}^{2}}$

上記のような一般的なケースは、シフトと回転によって特殊なケースに変換できます。

2 つの円盤(2 つの円の内部)の交差により、レンズと呼ばれる形状が形成されます。

楕円/双曲線/放物線と別の円錐曲線との交差の問題は、二次方程式の連立につながり、特殊な場合には 1 つの座標を消去することで簡単に解くことができます。円錐曲線の特殊な特性を利用して解を得ることができます。一般に、交点はニュートン反復法で方程式を解くことで決定できます。a) 両方の円錐曲線が暗黙的に (方程式によって) 与えられている場合は 2 次元ニュートン反復法、b) 一方が暗黙的に与えられ、もう一方がパラメトリックに与えられている場合は 1 次元ニュートン反復法が必要です。次のセクションを参照してください。

連続的に微分可能な（つまり、急激な曲がりがない） 2 つの曲線（2 次元空間）には、平面上の共通の点があり、この点に次の点がある場合、交差点があります（図を参照）。${\displaystyle \mathbb {R} ^{2}}$

a) 異なる接線（横断交差、横断後の交差）、または

b) 接線が共通で、互いに交差している（接点に接した後）。

両方の曲線に点Sとそこの接線が共通しているが、曲線同士が交差していない場合は、曲線は点Sで接していることになります。

接触する交差点はめったに現れず、扱いが難しいため、以下の考察ではこのケースは省略します。以下のいずれの場合も、必要な微分条件はすべて前提としています。交差点の決定は常に、ニュートン反復法で解くことができる 1 つまたは 2 つの非線形方程式につながります。出現するケースのリストは次のとおりです。

• 両方の曲線が明示的に与えられている場合: 、それらを等しくすると次の式が得られます。${\displaystyle y=f_{1}(x),\ y=f_{2}(x)}$

${\displaystyle f_{1}(x)=f_{2}(x)\ .}$

• 両方の曲線がパラメトリックに与えられている場合:${\displaystyle C_{1}:(x_{1}(t),y_{1}(t)),\ C_{2}:(x_{2}(s),y_{2}(s)).}$

これらを等しくすると、2 つの変数を持つ 2 つの方程式が得られます。

${\displaystyle x_{1}(t)=x_{2}(s),\ y_{1}(t)=y_{2}(s)\ .}$

• 一方の曲線がパラメトリックに与えられ、もう一方が暗黙的に与えられている場合:${\displaystyle C_{1}:(x_{1}(t),y_{1}(t)),\ C_{2}:f(x,y)=0.}$

これは明示的なケース以外では最も単純なケースです。 のパラメトリック表現を曲線の方程式に挿入すると、次の方程式が得られます。 ${\displaystyle C_{1}}$${\displaystyle f(x,y)=0}$${\displaystyle C_{2}}$

${\displaystyle f(x_{1}(t),y_{2}(t))=0\ .}$

• 両方の曲線が暗黙的に与えられている場合:${\displaystyle C_{1}:f_{1}(x,y)=0,\ C_{2}:f_{2}(x,y)=0.}$

ここで、交点はシステムの解である。

${\displaystyle f_{1}(x,y)=0,\ f_{2}(x,y)=0\ .}$

ニュートン反復法には、両方の曲線を視覚化することで得られる便利な開始値が必要です。パラメータまたは明示的に与えられた曲線は、任意のパラメータtまたはxに対して対応する点を計算するのが容易であるため、簡単に視覚化できます。暗黙的に与えられた曲線の場合、このタスクはそれほど簡単ではありません。この場合、開始値と反復の助けを借りて曲線点を決定する必要があります。を参照してください。^[2]

例:

1:円で囲みます（図を参照）。 ${\displaystyle C_{1}:(t,t^{3})}$${\displaystyle C_{2}:(x-1)^{2}+(y-1)^{2}-10=0}$

関数の ニュートン反復法${\displaystyle t_{n+1}:=t_{n}-{\frac {f(t_{n})}{f'(t_{n})}}}$

${\displaystyle f(t)=(t-1)^{2}+(t^{3}-1)^{2}-10}$実行する必要があります。開始値として、-1 と 1.5 を選択できます。

交点は次のとおりです: (-1.1073, -1.3578), (1.6011, 4.1046)

2:${\displaystyle C_{1}:f_{1}(x,y)=x^{4}+y^{4}-1=0,}$

${\displaystyle C_{2}:f_{2}(x,y)=(x-0.5)^{2}+(y-0.5)^{2}-1=0}$（図を参照）。

ニュートン反復法

${\displaystyle {x_{n+1} \choose y_{n+1}}={x_{n}+\delta _{x} \choose y_{n}+\delta _{y}}}$実行する必要があるが、線形システムの解は${\displaystyle {\delta _{x} \choose \delta _{y}}}$

${\displaystyle {\begin{pmatrix}{\frac {\partial f_{1}}{\partial x}}&{\frac {\partial f_{1}}{\partial y}}\\{\frac {\partial f_{2}}{\partial x}}&{\frac {\partial f_{2}}{\partial y}}\end{pmatrix}}{\delta _{x} \choose \delta _{y}}={-f_{1} \choose -f_{2}}}$点において、開始値として(−0.5, 1)と(1, −0.5)を選択できます。${\displaystyle (x_{n},y_{n})}$

線形システムはクラメールの規則によって解くことができます。

交点は（−0.3686, 0.9953）と（0.9953, −0.3686）です。

2 つの多角形の交点を決定したい場合は、多角形の任意の線分のペアの交点をチェックすることができます (上記参照)。線分の多い多角形の場合、この方法はかなり時間がかかります。実際には、ウィンドウ テストを使用して交差アルゴリズムを高速化します。この場合、多角形を小さなサブ多角形に分割し、任意のサブ多角形の最小のウィンドウ (座標軸に平行な辺を持つ長方形) を決定します。時間のかかる 2 つの線分の交点の決定を開始する前に、任意のウィンドウのペアに共通点があるかどうかをテストします。^{[3]を参照してください。}

3 次元空間では、曲線と面の間に交差点 (共通点) が存在します。次のセクションでは、横断交差のみを考慮します。

3 次元の一般的な位置における線と平面の交点は点です。

一般的に、空間内の線はパラメトリックに表現され 、平面は方程式で表現されます。方程式にパラメータ表現を挿入すると、線形方程式が得られます。 ${\displaystyle (x(t),y(t),z(t))}$${\displaystyle ax+by+cz=d}$

${\displaystyle ax(t)+by(t)+cz(t)=d\ ,}$

交差点のパラメータ。 ${\displaystyle t_{0}}$${\displaystyle (x(t_{0}),y(t_{0}),z(t_{0}))}$

線形方程式に解がない場合、その線は平面上にあるか、平面に平行になります。

線が 2 つの交差する平面によって定義され、3 番目の平面によって交差する必要がある場合、3 つの平面の共通交点を評価する必要があります。 ${\displaystyle \varepsilon _{i}:\ {\vec {n}}_{i}\cdot {\vec {x}}=d_{i},\ i=1,2}$${\displaystyle \varepsilon _{3}:\ {\vec {n}}_{3}\cdot {\vec {x}}=d_{3}}$

線形独立法線ベクトルを持つ3つの平面の交点は ${\displaystyle \varepsilon _{i}:\ {\vec {n}}_{i}\cdot {\vec {x}}=d_{i},\ i=1,2,3}$${\displaystyle {\vec {n}}_{1},{\vec {n}}_{2},{\vec {n}}_{3}}$

${\displaystyle {\vec {p}}_{0}={\frac {d_{1}({\vec {n}}_{2}\times {\vec {n}}_{3})+d_{2}({\vec {n}}_{3}\times {\vec {n}}_{1})+d_{3}({\vec {n}}_{1}\times {\vec {n}}_{2})}{{\vec {n}}_{1}\cdot ({\vec {n}}_{2}\times {\vec {n}}_{3})}}\ .}$

証明するには、スカラー三重積の規則を使用して確立する必要があります。スカラー三重積が 0 に等しい場合、平面には三重交差がないか、直線 (または、3 つの平面がすべて同じ場合は平面) になります。 ${\displaystyle {\vec {n}}_{i}\cdot {\vec {p}}_{0}=d_{i},\ i=1,2,3,}$

平面の場合と同様に、以下のケースは非線形システムとなり、1次元または3次元のニュートン反復法を使用して解くことができます。^[4]

• パラメトリック曲線と${\displaystyle C:(x(t),y(t),z(t))}$

パラメトリックサーフェス${\displaystyle S:(x(u,v),y(u,v),z(u,v))\ ,}$

• パラメトリック曲線と${\displaystyle C:(x(t),y(t),z(t))}$

暗黙の表面${\displaystyle S:f(x,y,z)=0\ .}$

例：

パラメトリック曲線 と${\displaystyle C:(t,t^{2},t^{3})}$

暗黙の表面（図参照）。${\displaystyle S:x^{4}+y^{4}+z^{4}-1=0}$

交点は、(−0.8587, 0.7374, −0.6332)、(0.8587, 0.7374, 0.6332)です。

線と球の交差は単純な特殊なケースです。

線と平面の場合と同様に、一般的な位置における曲線と面の交差は個別の点から構成されますが、曲線は面内に部分的または全体的に含まれる場合があります。

2 つの交差する面は交差曲線を生じます。最も単純なケースは、2 つの平行でない平面の交差線です。

球と平面の交点が空または単一の点ではない場合、それは円です。これは次のように表すことができます。

S を中心Oの球、Sと交差する平面Pとします。Pに垂直で、 EでPと交わるOE を描きます。AとBを交差点上の任意の 2 つの異なる点とします。すると、AOEとBOE は、共通の辺OE を持ち、斜辺AOとBO が等しい直角三角形になります。したがって、残りの辺AEとBEは等しいです。これは、交差点のすべての点が平面P上の点Eから同じ距離にあることを証明しています。言い換えると、交差点のすべての点は、中心Eを持つ円C上にあります。^{[5]これは、} PとSの交差点がCに含まれることを証明しています。OE は円の軸であることに注意してください。

ここで、円Cの点Dについて考えます。C はP内にあるため、D も P内にあります。一方、三角形AOEとDOE は、共通の辺OEを持ち、辺EAとED が等しい直角三角形です。したがって、斜辺AOとDO は等しく、Sの半径に等しいため、D はS内にあります。これは、C がPとSの交点に含まれることを証明しています。

当然の帰結として、球面上には3つの与えられた点を通る円が1つだけ存在する。^[6]

この証明は、円上の点はすべてその極の1つから共通の角度距離にあることを示すために拡張することができます。^[7]

楕円を生成できる円錐曲線も比較してください。

2つの球の交差が円であることを示すには、（一般性を失うことなく）1つの球（半径）が原点を中心としていると仮定します。この球上の点は ${\displaystyle R}$

${\displaystyle x^{2}+y^{2}+z^{2}=R^{2}.}$

また、一般性を失うことなく、半径 の2番目の球面が原点からの 距離にある正のx軸上の点を中心としていると仮定する。その点は${\displaystyle r}$${\displaystyle a}$

${\displaystyle (x-a)^{2}+y^{2}+z^{2}=r^{2}.}$

球面の交点は、両方の方程式を満たす点の集合です。方程式を引き算すると、

${\displaystyle {\begin{aligned}(x-a)^{2}-x^{2}&=r^{2}-R^{2}\\a^{2}-2ax&=r^{2}-R^{2}\\x&={\frac {a^{2}+R^{2}-r^{2}}{2a}}.\end{aligned}}}$

特異なケース では、球は同心です。2 つの可能性があります。 の場合、球は一致し、交差は球全体になります。 の場合、球は分離しており、交差は空です。aがゼロ以外の場合、交差はこの x 座標を持つ垂直面にあり、両方の球と交差するか、両方の球に接するか、両方の球の外部にある可能性があります。結果は、球面と平面の交差に関する前の証明から得られます。 ${\displaystyle a=0}$${\displaystyle R=r}$${\displaystyle R\not =r}$

• 線と面の交差
• 線と球の交差
• 直線と円筒の交差
• 解析幾何学#交差
• 計算幾何学
• 直線の方程式
• 交差（集合論）
• 交差理論

• Hobbs, CA (1921). 立体幾何学. GH Kent. pp. 397 ff.

• Haines, Eric (2021 年 6 月 6 日)。「交差点 (レイ トレーシング リソース ページ)」。リアルタイム レンダリング。2023年12 月 14 日閲覧。さまざまな一般的なオブジェクトの交差点ルーチンのグリッド。書籍や Web 上のリソースを参照します。
• ニコラス・M・パトリカラキス、前川隆志、「コンピュータ支援設計・製造のための形状調査」、Springer、2002年、ISBN 3540424547、9783540424543、pp. 408。[1] 
• Sykes, M.; Comstock, CE (1922). 立体幾何学. Rand McNally. pp. 81 ff.