【C言語】2つの線分の交差判定
任意の2点同士の2線分の交差の判定「C言語編」
C言語での線分交差判定が無いので作りました。
2本の線分をA,Bとする。
その端点をp1 (p1x,p1y),p2 (p2x,p2y)とp3 (p3x,p3y),p4 (p4x,p4y)とする。
またp1、p2を通る直線をl、p3、p4を通る直線をmとする。l,mはA,Bそれぞれの延長である。
A,Bが交差するための条件は2つで、
- 「直線lが線分Bと交差する」
- 「直線mと線分Aと交差する」
の双方を満たせばよい。
1では直線lの方程式にp3 (p3x,p3y),p4 (p4x,p4y)をそれぞれ代入し,代入した値同士の積が負であれば交差している。
2では同様に直線mの方程式にp1 (p1x,p1y),p2 (p2x,p2y)をそれぞれ代入し,代入した値同士の積が負であれば交差している。4点がこれらを共に満たしているとき、線分A,Bは交差しています。
原理などは参考サイト様:Algorithm
をC言語で書いたものがこちら。
//2本の線分の端点を(p1x,p1y)(p2x,p2y)と(p3x,p3y)(p4x,p4y)とする。 int Intersection(int p1x,int p2x,int p3x,int p4x, int p1y,int p2y,int p3y,int p4y){ if (((p1x - p2x) * (p3y - p1y) + (p1y - p2y) * (p1x - p3x)) * ((p1x - p2x) * (p4y - p1y) + (p1y - p2y) * (p1x - p4x)) < 0){ if (((p3x - p4x) * (p1y - p3y) + (p3y - p4y) * (p3x - p1x)) * ((p3x - p4x) * (p2y - p3y) + (p3y - p4y) * (p3x - p2x)) < 0){ //交差したら1を返す。 return(1); } } //交差していなかったら0を返す。 else return(0); }