２線分の交点

線分ＡＢ、ＣＤがあったときに、その交点を求めるには？
要素は２次元空間内に存在するものとします。

解説

線分ＡＢ上の任意の点Ｐは、媒介変数 r を用いて、以下のように表現できます。

P = A + r ( B - A )　（ r は[0～1]の値を取る）　・・・式①

同様に、ＣＤ上の任意の点Ｑも、媒介変数 s を用いて、以下のように表現できます。

Q = C + s ( D - C )　（ s は[0～1]の値を取る）　・・・式②

ＰとＱが同一点になる場合の r と s を求めれば、ＡＢとＣＤの交点は求まったことになります。

というわけで、P = Q を解きます。

　　P = Q
⇔　A + r ( B - A ) = C + s ( D - C )

Ｘ、Ｙに関する連立方程式にします。

⇔　Ax + r ( Bx - Ax ) = Cx + s ( Dx - Cx )
　　Ay + r ( By - Ay ) = Cy + s ( Dy - Cy )

これを解きますと、
r = { (Dy - Cy)(Cx - Ax) - (Dx - Cx)(Cy - Ay) }
　/ { (Bx - Ax)(Dy - Cy) - (By - Ay)(Dx - Cx) }　・・・式③
s = { (By - Ay)(Cx - Ax) - (Bx - Ax)(Cy - Ay) }
　/ { (Bx - Ax)(Dy - Cy) - (By - Ay)(Dx - Cx) }　・・・式④

演算回数を減らすために、一時変数を用います。

ACx = Cx - Ax
ACy = Cy - Ay
BUNBO = (Bx - Ax)(Dy - Cy) - (By - Ay)(Dx - Cx )

として、

r = { (Dy - Cy)ACx - (Dx - Cx)ACy } / BUNBO　・・・式⑤
s = { (By - Ay)ACx - (Bx - Ax)ACy } / BUNBO　・・・式⑥

・平行チェック

r、s を求めようとしたときに、r、s が求まらない場合があります。すなわち、BUNBOがゼロの場合です。このとき、２線分は平行であり、交差しません。

・重なりチェック

BUNBOがゼロで、さらに、式⑤、⑥の分子もゼロの場合には、２線分は重なりあっています。

・線分交差チェック

式①、②より、r、s が共に　0～1　の間の値として求まらなければ、２線分は交差していないとなります。
r、s 個別に言うと、

r < 0 ：点Ｐは、点Ａより手前

r > 1 ：点Ｐは、点Ｂより奥

s < 0 ：点Ｑは、点Ｃより手前

s > 1 ：点Ｑは、点Ｄより奥

となります。

bool CalcIntersectionPoint( const CNhPoint2d& pointA, const CNhPoint2d& pointB, const CNhPoint2d& pointC, const CNhPoint2d& pointD, CNhPoint2d& pointIntersection, double& dR, double& dS ) { double dBunbo = ( pointB.x - pointA.x ) * ( pointD.y - pointC.y ) - ( pointB.y - pointA.y ) * ( pointD.x - pointC.x ); if( 0 == dBunbo ) { // 平行 return false; } CNhVector2d vectorAC = pointC - pointA; dR = ( ( pointD.y - pointC.y ) * vectorAC.x - ( pointD.x - pointC.x ) * vectorAC.y ) / dBunbo; dS = ( ( pointB.y - pointA.y ) * vectorAC.x - ( pointB.x - pointA.x ) * vectorAC.y ) / dBunbo; pointIntersection = pointA + dR * ( pointB - pointA ); return true; }

考察

r、s の数値が0、1に非常に近い数値の場合には、演算誤差によって、
交差していないのに交差していると判定される場合や、
交差しているのに交差していないと判定される場合
がないとは言えません。
このような場合に配慮して、実用においては、交点計算に加えて、
・点と直線の距離計算を用いて、線分の端点がもう一方の線分上にあるかの判定を行う
もしくは、
・点と直線の半空間テストを用いて、線分の２端点がもう一方の線分をまたいでいるかかの判定を行う
必要があります。

ダウンロード

サンプルプロジェクト

参考

Graphics Gems Ⅲ：Faster Line Segment Intersection