6

最近、計算幾何学に少し取り組んでおり、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); }

上記のコードは、私が入力したテスト ケースで機能し、非常に読みやすく、実装が非常に簡単です。しかし、Web で検索した後、分節交差の問題を解決する別の方法を見つけました。コードは私のものと似ていますが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 つの実装の違いと、どちらを使用する方が安全かを誰かが説明できますか? 前もって感謝します。

4

1 に答える 1

3

あなたが見つけた関数は、線分が同じ線内にある場合もチェックしています。その場合、2 つの線分が重なるかどうかという 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

あなたが見つけた関数は、1 つの線分の終点が他の線分に沿っている場合も調べます。

例：

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
于 2013-03-09T13:13:50.823 に答える