最近我在研究计算几何,正在尝试找到一种检查两条线段是否相交的方法。我认为可以使用逆时针方向(缩写为CCW)来确定。以下是我的代码:
struct point { double x, y };
double CCW(point a, point b, point c)
{ return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); }
int intersect(point a, point b, point c, point d)
{ return (CCW(a,b,c)*CCW(a,b,d)<0 && CCW(c,d,b)*CCW(c,d,a)<0); }
上述代码对我输入的测试用例有效,易读且非常易于实现。但是在网上搜索后,我发现了另一种解决线段交点问题的方式。此代码与我的代码类似,但它还有一些我实现中省略的if
语句。以下是代码:
struct line { point s, e; };
int middle(int a, int b, int c) {
int t;
if ( a > b ) {
t = a;
a = b;
b = t;
}
if ( a <= c && c <= b ) return 1;
return 0;
}
int intersect(line a, line b) {
if ( ( CCW(a.s, a.e, b.s) * CCW(a.s, a.e, b.e) < 0 ) &&
( CCW(b.s, b.e, a.s) * CCW(b.s, b.e, a.e) < 0 ) ) return 1;
if ( CCW(a.s, a.e, b.s) == 0 && middle(a.s.x, a.e.x, b.s.x) && middle(a.s.y, a.e.y, b.s.y) ) return 1;
if ( CCW(a.s, a.e, b.e) == 0 && middle(a.s.x, a.e.x, b.e.x) && middle(a.s.y, a.e.y, b.e.y) ) return 1;
if ( CCW(b.s, b.e, a.s) == 0 && middle(b.s.x, b.e.x, a.s.x) && middle(b.s.y, b.e.y, a.s.y) ) return 1;
if ( CCW(b.s, b.e, a.e) == 0 && middle(b.s.x, b.e.x, a.e.x) && middle(b.s.y, b.e.y, a.e.y) ) return 1;
return 0;
}
有人能解释一下这两种实现的区别,哪种更安全可靠吗?先谢谢了。