2つの線分が交差しているかどうかを判断するためのC++プロシージャ

Question

最近、計算幾何学で少し作業しています.2つの線分が交差しているかどうかを調べる方法を探しています。私はそれを決めるために反時計回りの方向（略して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; 
} 

誰かが2つの実装の違いは何かを説明することができますか？どちらが安全ですか？前もって感謝します。

Answer 1

見つかった関数は、線分が同じ行内にある場合もチェックしています。その場合、2つの線分が重なり合っているかどうかを見つける1次元の問題になります。この場合、コードはfalseを返します。これが好ましいかどうかは、アプリケーションによって異なります。

例：

例：

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 

あなたが見つけ

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 

機能も1つのラインセグメントの終点は、他の線分に沿っている例を見て