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