人生やり直しロードマップ

人生を詰みそうな人にネタとか何か伝えるブログ

スポンサーリンク

【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つで、

  1. 「直線lが線分Bと交差する」
  2. 「直線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);
}