用于确定两个线段是否相交的C++程序

Question

最近我正在处理一些计算几何，并且试图找到一种检查两个线段是否相交的方法。我认为我可以使用逆时针方向（简称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); } 

上面的代码工作了我进入测试案例，它是相当可读的，很容易实现。但是在网上搜索之后，我找到了另一种解决细分交叉问题的方法。该代码与我的代码类似，但它还有一些我的实现忽略的语句。下面是代码：

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; 
} 

有人能解释一下这两个实现之间的差异，这是使用更安全？提前致谢。

Answer 1

您发现的功能还检查线段位于同一行内的情况。在这种情况下，它变成了查找两条线段是否重叠的单维问题。在这种情况下，您的代码将返回false。这是否是首选取决于应用程序。

例子：

point a={1,0}, b={3,0}, c={2,0}, d={4,0}; 

intersect(a,b,c,d); // your function will return false, 
        // but the one you found will return true 

您发现该功能还着眼于案件，其中一个线段的端点沿着另一条线段在于：

例子：

point a={1,0}, b={3,0}, c={2,0}, d={2,3}; 

intersect(a,b,c,d); // your function will return false, 
        // but the one you found will return true