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

本文描述了用于查找线段集中交点的扫线算法。它的预期运行时间为 O(n + k)，其中 n 是路段数，k 是交叉点数。

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

Answer 2

这是“方向”函数的更好实现，避免了舍入错误的问题。也许这对你的情况有帮助。如果 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);
    }