C＃ポリラインは自己交差です

Question

ポリラインがいつでも自己交差するかどうかをチェックするタスクがあります。私のポリラインは長いので（約50点あります）、タイムアウトがありますので、このチェックは非常に速くなければなりません。ここで私が書いたものである。これらのメソッドの

public bool IsSelfCrossing() 
    { 
     if (size <= 5) 
      return false; 
     Point first = body.Points.ElementAt(size - 1); 
     Point second = body.Points.ElementAt(size - 2); 
     for (int i = 0; i < size - 3; i++) 
     { 
      if (Intersect(first, second, body.Points.ElementAt(i), 
       body.Points.ElementAt(i + 1))) 
      { 
       return true; 
      } 
     } 
     return false; 
    } 

    private double Orientation(Point p1, Point p2, Point p3) 
    { 
     double dx1 = p2.X - p1.X; 
     double dy1 = p2.Y - p1.Y; 
     double dx2 = p3.X - p1.X; 
     double dy2 = p3.Y - p1.Y; 
     return dx1 * dy2 - dy1 * dx2; 
    } 


    bool Intersect(Point p1, Point p2, Point p3, Point p4) 
    { 
     return 
       Orientation(p1, p3, p4) * Orientation(p2, p3, p4) < 0 && 
       Orientation(p3, p1, p2) * Orientation(p4, p1, p2) < 0; 
    } 

問題は、時にはそれが（メソッドはポリラインは自己交差点ですが、そうでないことを私に言っている）失敗したということです。 より良い解決策を教えてください。

Answer 1

丸め誤差の問題を避け、あなたの「オリエンテーション」機能のより高度な実装です。おそらくこれはあなたの場合に役立ちます。 p0がp1とp2の間の直線上にある場合は0を返します。

public static int Clockwise (Point p0, Point p1, Point p2) 
    { 
     const double epsilon = 1e-13; 

     double dx1 = p1.X - p0.X; 
     double dy1 = p1.Y - p0.Y; 
     double dx2 = p2.X - p0.X; 
     double dy2 = p2.Y - p0.Y; 
     double d = dx1 * dy2 - dy1 * dx2; 
     if(d > epsilon) return 1; 
     if(d < -epsilon) return -1; 
     if((dx1*dx2 < -epsilon) || (dy1*dy2 < -epsilon)) return -1; 
     if((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2)+epsilon) return 1; 
     return 0; 
    } 

そして、ここで私の「交差」機能である：

public static bool LineIntersects(Point p1,Point p2, Point q1,Point q2) 
    { 
     return (Clockwise(p1,p2,q1) * Clockwise(p1,p2,q2) <=0) && 
      (Clockwise(q1,q2,p1) * Clockwise(q1,q2,p2) <=0); 
    } 

Answer 2

本稿では、線分の集合の交点を見つけるための掃引線アルゴリズムについて説明します。 O（n + k）の実行時間が予想され、nはセグメントの数であり、kは交差点の数である。ここで

http://www.cs.tufts.edu/comp/163/notes05/seg_intersection_handout.pdf