St_Hakky’s blog

Data Science / Human Resources / Web Applicationについて書きます

【Python】線分交差判定のプログラムを書いた

こんにちは。

仕事で「2つの線分が交差しているかどうか」を判定するプログラムを書いたのでその備忘録として書いておきます。

2つの線分が交差しているとは

2つの線分が交差しているとは、こちらのサイトによれば、

点A,Bを通る直線が線分CDと交差し、かつ
点C,Dを通る直線が線分ABと交差している

という風に解釈することができます。これにより、直線と線分の交差判定は、

直線を境界線として、線分を構成する2つの点が
直線に対して両側に存在するとき、直線と線分は交差する

によって判断することができる、と考えられます。2つの線分の交差判定は、この直線と線分の交差判定を用いて、片方の線分を直線とみなし、2回それを行うことで判断することができます。

直線と線分の交差判定

直線と線分の交差判定を2回行うことで2つの線分の交差判定ができることがわかりました。ここで、直線と線分の交差判定をどうやって行うかですが、これは簡単です。

直線に対して、2つの点がそれぞれ両側にあればいいので、直線の方程式を $y=ax-b$ とすると、2点( $(x1, y1), (x2, y2)$ ) において以下の式、

$$
y1-ax1-b>0 \\
y2-ax2-b<0
$$

または、

$$
y1-ax1-b<0 \\
y2-ax2-b>0
$$

が成り立てばいいとなります。つまり、2点を直線の方程式にいれた時に、2点間で符号が異なっていればいいとなります。

これをまとめると、以下のようになります。

$$
tc=(x1-x2)*(y3-y1)+(y1-y2)*(x1-x3) \\
td=(x1-x2)*(y4-y1)+(y1-y2)*(x1-x4) \\
\\
この式が、以下を満たとき、線分と直線は交差していると言える \\
\\
tc*td<0
$$

Pythonプログラム

特に難しくなくできます。

def intersect(p1, p2, p3, p4):
    tc1 = (p1[0] - p2[0]) * (p3[1] - p1[1]) + (p1[1] - p2[1]) * (p1[0] - p3[0])
    tc2 = (p1[0] - p2[0]) * (p4[1] - p1[1]) + (p1[1] - p2[1]) * (p1[0] - p4[0])
    td1 = (p3[0] - p4[0]) * (p1[1] - p3[1]) + (p3[1] - p4[1]) * (p3[0] - p1[0])
    td2 = (p3[0] - p4[0]) * (p2[1] - p3[1]) + (p3[1] - p4[1]) * (p3[0] - p2[0])
    return tc1*tc2<0 and td1*td2<0