C # Polyline является самопересекающимся

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

В этой статье описывается алгоритм строчной линии для нахождения пересечений в наборе отрезков. Ожидаемое время выполнения O (n + k), где n - количество сегментов, а k - количество пересечений.

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

Answer 2

Вот лучшая реализация вашей функции "Ориентация", позволяющая избежать проблем с ошибками округления.Возможно, это поможет в вашем случае.Возвращает 0, если p0 находится на прямой линии между p1 и p2.

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