交差判定アルゴリズム

昔、Ｃマガにのってた線分交差判定ソース。

bool cross(Point p1, Point p2, Point q1, Point q2)
{
　　// 方程式の係数 Ax + By + C = 0
　　float A, B, C;

　　// 判定式
　　int d;
　
　　A = p2.y - p1.y;
　　B = p1.x - p2.x;
　　C = -( A * p1.x + B * p1.y);

　　d = (int)((A*q1.x + B*q1.y + C) * (A*q2.x + B*q2.y + C));
　
　　if(d > 0){
　　　　return false; // 非交差
　　}
　　else{
　　　　A = q2.y - q1.y;
　　　　B = q1.x - q2.x;
　　　　C = -( A * q1.x + B * q1.y);
　　　
　　　　d = (int)((A*p1.x + B*p1.y + C) * (A*p2.x + B*p2.y + C));
　　　
　　　　if(d > 0){
　　　　　　// 非交差
　　　　　　return false;
　　　　}
　　　　else{
　　　　　　// 交差
　　　　　　return true;
　　　　}
　　}
}