25
10/2015
判断二维平面上两线段是否相交
题目：如题，包含线段端点。重合也算相交。
解题思路：
假设两线段分别为AB、CD。则AB直线的方程为Fab（x,y） = (y-ya)(xa-xb) - (x-xa)(ya-yb)=0。我们注意到，若线段AB与线段CD相交，则必有
（1）直线AB与线段CD相交
（2）直线CD与线段AB相交
判断线段CD是否与直线AB相交，只需判断：点C和点D在直线AB的不同侧,即Fab(xc, yc)*Fab(xd, yd) <= 0。等于0表示点C或点D在AB直线上。于是，若线段AB与线段CD相交，则必有
（1）Fab(xc, yc)*Fab(xd, yd) <= 0
（2）Fcd(xa, ya)*Fcd(xb, yb) <= 0
代码如下：
struct Point{
double x;
double y;
Point(double _x, double _y) : x(_x), y(_y){};
};
//a在线段bc的哪一侧
double mult(Point a, Point b, Point c){
return (a.x - c.x)*(b.y - c.y) - (a.y - c.y)*(b.x - c.x);
}
bool solution(Point aa, Point bb, Point cc, Point dd){
if (mult(aa, cc, dd)*mult(bb, cc, dd) > 0)
{
return false;
}
if (mult(cc, aa, bb)*mult(dd, aa, bb) > 0)
{
return false;
}
return true;
}转载请注明：康瑞部落 » 判断二维平面上两线段是否相交
0 条评论