線分の交差判定

高校数学ではもちろん、大学の数学や物理でもよく言うところの「自明」であるのか、こういう用途に使えることを教えてはくれない。ここでは外積を使用することでふたつの線分がどの位置関係にあるのか判定できることを解説する。

2次元空間における外積はベクトル $\overrightarrow{A}=(a_x,a_y)$ と $\overrightarrow{B}=(b_x,b_y)$ があるときに、その外積は $\overrightarrow{A}\times \overrightarrow{B}=a_x\cdot b_y-a_y\cdot b_x$ で求められる。これをPythonで書けば次のようになる。

from typing import Self
 
class Vec2D:
    def __init__(self, x: float, y: float) -> None:
        self.x = x
        self.y = y
 
    def cross(self, other: Self) -> float:
        return self.x * other.y - self.y * other.x
 
class Point2D:
    def __init__(self, x: float, y: float) -> None:
        self.x = x
        self.y = y
 
    def __sub__(self, other: Self) -> Vec2D:
        return Vec2D(self.x - other.x, self.y - other.y)

また、ここで考える点は次のような位置関係にあるとする。

同じ傾きであれば外積は0

ここで $AB\times AB$ は0になる。逆ベクトルとの外積 $AB\times BA$ も0である。また、$AB$ の半分の長さの $A{B}^{\prime }$, $B^{\prime }=(5,5)$があったとしても、$AB\times A{B}^{\prime }$ の結果は同様に0になる。つまり、符号を無視して同じ傾きを持っていれば(平行であれば)、長さに関係なく外積は0になる。

a = Point2D(8, 7) - Point2D(2, 3)
b = Point2D(8, 7) - Point2D(2, 3)
print(a.cross(b))    # 0
 
a = Point2D(8, 7) - Point2D(2, 3)
b = Point2D(2, 3) - Point2D(8, 7)
print(a.cross(b))    # 0
 
a = Point2D(8, 7) - Point2D(2, 3)
b = Point2D(5, 5) - Point2D(2, 3)
print(a.cross(b))    # 0

始点が同じ場合の位置関係

次に $AB$ と $AC$ について考えてみる。$AB$ に対して反時計回りの方向にある $AC$ の外積は $AB\times AC>0$ となり、時計回りの方向にある $AB$ との外積は $AB\times AD<0$ となる。

a = Point2D(8, 7) - Point2D(2, 3)
b = Point2D(3, 9) - Point2D(2, 3)
print(a.cross(b))    # 32
 
a = Point2D(8, 7) - Point2D(2, 3)
b = Point2D(7, 4) - Point2D(2, 3)
print(a.cross(b))    # -14

線分ABとCDの交差判定

$AC$ と $AD$ の間に $AB$ があり、$CA$ と $CB$ の間に $CD$ があることを確認すればよい。これを計算すると次のようになる。

• $AC\times AB=-32,AD\times AB=14$ → $CD$ から見て交差する
• $CA\times CD=-17,CB\times CD=29$ → $AB$ から見て交差する
• 噛み砕くと…
  • $AC\times AB<0$ → $CD$ は $AB$ に対して反時計回り方向に交差するだけの十分な長さがある
  • $CA\times CD<0$ → $AB$ は $CD$ に対して反時計回り方向に交差するだけの十分な長さがある
  • $AD\times AB>0$ → $CD$ は $AB$ に対して時計回り方向に交差するだけの十分な長さがある
  • $CB\times CD>0$ → $AB$ は $CD$ に対して時計回り方向に交差するだけの十分な長さがある

さらに、$AC$ と $AD$, $CA$ と $CB$はそれぞれ入れ替えても同様なので、

$(AC\times AB)\cdot (AD\times AB)<0$ かつ $(CA\times CD)\cdot (CB\times CD)<0$

であれば線分 $AB$ と $CD$ は交差する。

多角形の凸包判定

任意の凹んでいない $n$ 角形 ($n\ge 3$) のことを凸包と言うが、反時計回りに一周するように頂点同士の外積を計算し、結果がすべて正であれば凸包となる。

ポリゴンの頂点を設定する際に、砂時計の形のようにねじれた形に配置することもできるが、その場合でも正しく判定できる。

多角形と点Pの内包判定

多角形の点のうち、最大の $x$ 座標を $x_{max}$ としたときに、線分 $P{P}^{\prime }=\{(min(p_x,x_{max}),p_y),(x_{max},p_y)\}$ がいずれかの辺とちょうど1回交差すれば多角形内に点Pが含まれている。線分Pと交差判定を行う辺が平行関係にあると外積は0になるので、辺上の点も内包扱いにする場合には追加の考慮が必要となる。