c# - 实现用于检测自相交多边形的蛮力算法

Question

我最初实现了hoey-shamos算法，但是对于将来的可维护性来说太复杂了（我在这方面没有发言权），而且它没有正确的报告，所以我将使用一个优化的蛮力算法。
我的问题是：如何优化这些代码以使其可用？
现在，我的代码包含一个嵌套for循环，重复同一个列表两次。
编辑：将行转换为哈希集并使用两个foreach循环…扫描10000次后减少了45秒还不够。

foreach (Line2D g in lines)
{                   
foreach (Line2D h in lines)
{
    if (g.intersectsLine(h))
    {
        return false;
    }
}                  

 } // end 'lines' for each loop

如果我强制“intersectsline（）”方法返回false（用于测试目的），扫描10000条记录（我有700000条记录）仍然需要8秒。这太长了，所以我需要优化这段代码。
我试着在与所有其他行进行比较后，从列表中删除行，但是有一个准确性问题（不知道为什么），速度的提高几乎不明显。
这是我的相交线方法。我发现了另一种方法 here，但看起来在所有方法调用和其他操作时会更慢。在我看来，计算斜率并不需要太多计算（如果我错了，请纠正我？）

public bool intersectsLine(Line2D comparedLine)
{

//tweakLine(comparedLine);
if (this.Equals(comparedLine) ||
    P2.Equals(comparedLine.P1) ||
    P1.Equals(comparedLine.P2))
{
    return false;
}

double firstLineSlopeX, firstLineSlopeY, secondLineSlopeX, secondLineSlopeY;

firstLineSlopeX = X2 - X1;
firstLineSlopeY = Y2 - Y1;

secondLineSlopeX = comparedLine.X2 - comparedLine.X1;
secondLineSlopeY = comparedLine.Y2 - comparedLine.Y1;

double s, t;
s = (-firstLineSlopeY * (X1 - comparedLine.X1) + firstLineSlopeX * (Y1 - comparedLine.Y1)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
t = (secondLineSlopeX * (Y1 - comparedLine.Y1) - secondLineSlopeY * (X1 - comparedLine.X1)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);

if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
{
    //console.WriteLine("s = {0}, t = {1}", s, t);
    //console.WriteLine("this: " + this);
    //console.WriteLine("other: " + comparedLine);
    return true;
}

return false; // No collision */

}

编辑：最大的瓶颈是大多边形！我排除了运行超过100行的多边形，它在5:10运行了700000多个多边形在可接受的范围内！在运行此代码之前，肯定有一种方法可以查看多边形是否值得计算？如果有帮助，我可以访问xmin、xmax、ymin和ymax属性？
运行另一个测试，将每个多边形限制在1000行以下花了一个多小时。
我去掉了所有多边形的限制，它已经运行了36个小时了…仍然没有结果。
我有几个想法：
-当我生成我的行哈希集时，要有另一个哈希集/列表，其中包含交叉点的候选项。如果有机会交叉，我只会在列表中添加行。但如何消除/增加可能性呢？如果只有三条线可能与其他线相交，我会比较4000条线和3条线，而不是4000条。单单这一点就可以产生巨大的影响。
-如果同一点出现两次（除了第一个和最后一个点），则忽略运行嵌套for循环。
编辑：
有关多边形的信息：
总计700000
有4000多个多边形，有1000多个点
有2个多边形，有70000个或更多点
我想只要有点创意就可以把时间缩短到15分钟左右。

Answer 1

当前的暴力算法是o（n^2）。对于你的两个70000行多边形来说，这几乎是100亿次运算的一部分，更不用说其他700000个多边形了显然，仅仅进行代码优化是不够的，所以您需要某种算法优化，它可以降低o（n^2），而不会过于复杂。
o（n^2）来自brute force算法中的嵌套循环，每个循环都以n为界，使其为o（n*n）。改善这一点的最简单方法是找到某种方法来减少内部循环，使其不受n的约束或依赖于endpointEntry。因此，我们需要找到一些方法来订购或重新订购内部行列表，以检查外部行，这样只需要扫描完整列表的一部分。
我采用的方法利用了这样一个事实：如果两条线段相交，那么它们的x值范围必须相互重叠。请注意，这并不意味着它们确实相交，但如果它们的X范围不重叠，那么它们就不能相交，因此不需要相互检查（Y值范围也是如此，但一次只能利用一个维度）。
这种方法的优点是，这些x范围可用于对直线的端点进行排序，这些端点可依次用作直线检查相交的起点和终点。
所以我们要做的就是定义一个自定义类（foreach(..in pts)），它表示直线两点的高x值或低x值。这些端点都放在同一个列表结构中，然后根据它们的x值进行排序。
然后我们实现了一个外部循环，在这个循环中，我们像在蛮力算法中那样扫描整个列表。然而，我们的内部循环却大不相同与其重新扫描整个列表中的行以检查相交，不如开始从外部循环行的高x值端点向下扫描排序的端点列表，并在通过该行的低x值端点以下时结束它。这样，我们只检查X值范围与外循环线重叠的线。
好的，这里有一节C类课程演示我的方法：

class CheckPolygon2
{
    // internal supporting classes
    class endpointEntry
    {
        public double XValue;
        public bool isHi;
        public Line2D line;
        public double hi;
        public double lo;
        public endpointEntry fLink;
        public endpointEntry bLink;
    }
    class endpointSorter : IComparer<endpointEntry>
    {
        public int Compare(endpointEntry c1, endpointEntry c2)
        {
            // sort values on XValue, descending
            if (c1.XValue > c2.XValue) { return -1; }
            else if (c1.XValue < c2.XValue) { return 1; }
            else // must be equal, make sure hi's sort before lo's
                if (c1.isHi && !c2.isHi) { return -1; }
                else if (!c1.isHi && c2.isHi) { return 1; }
                else { return 0; }
        }
    }

    public bool CheckForCrossing(List<Line2D> lines)
    {
        List<endpointEntry> pts = new List<endpointEntry>(2 * lines.Count);

        // Make endpoint objects from the lines so that we can sort all of the
        // lines endpoints.
        foreach (Line2D lin in lines)
        {
            // make the endpoint objects for this line
            endpointEntry hi, lo;
            if (lin.P1.X < lin.P2.X)
            {
                hi = new endpointEntry() { XValue = lin.P2.X, isHi = true, line = lin, hi = lin.P2.X, lo = lin.P1.X };
                lo = new endpointEntry() { XValue = lin.P1.X, isHi = false, line = lin, hi = lin.P1.X, lo = lin.P2.X };
            }
            else
            {
                hi = new endpointEntry() { XValue = lin.P1.X, isHi = true, line = lin, hi = lin.P1.X, lo = lin.P2.X };
                lo = new endpointEntry() { XValue = lin.P2.X, isHi = false, line = lin, hi = lin.P2.X, lo = lin.P1.X };
            }
            // add them to the sort-list
            pts.Add(hi);
            pts.Add(lo);
        }

        // sort the list
        pts.Sort(new endpointSorter());

        // sort the endpoint forward and backward links
        endpointEntry prev = null;
        foreach (endpointEntry pt in pts)
        {
            if (prev != null)
            {
                pt.bLink = prev;
                prev.fLink = pt;
            }
            prev = pt;
        }

        // NOW, we are ready to look for intersecting lines
        foreach (endpointEntry pt in pts)
        {
            // for every Hi endpoint ...
            if (pt.isHi)
            {
                // check every other line whose X-range is either wholly 
                // contained within our own, or that overlaps the high 
                // part of ours.  The other two cases of overlap (overlaps 
                // our low end, or wholly contains us) is covered by hi 
                // points above that scan down to check us.

                // scan down for each lo-endpoint below us checking each's 
                // line for intersection until we pass our own lo-X value
                for (endpointEntry pLo = pt.fLink; (pLo != null) && (pLo.XValue >= pt.lo); pLo = pLo.fLink)
                {
                    // is this a lo-endpoint?
                    if (!pLo.isHi)
                    {
                        // check its line for intersection
                        if (pt.line.intersectsLine(pLo.line))
                            return true;
                    }
                }
            }
        }

        return false;
    }
}

我不确定这个算法的真正执行复杂性是什么，但是我猜想对于大多数非病理多边形，它将接近O（n*qRT（n）），这应该足够快。
内环逻辑说明：
内部循环只是按照与外部循环相同的排序顺序扫描端点列表。但它将从外部循环当前在列表中的位置（某行的hiX点）开始扫描，并且只扫描到端点值低于该行的相应loX值为止。
这里需要技巧的是，这不能用枚举器（外部循环的 for）完成，因为无法枚举列表的子列表，也无法基于另一个枚举当前位置启动枚举。因此，我所做的是使用forward和backward links（flink和blink）属性创建一个双链接列表结构，该结构保留列表的排序顺序，但我可以在不枚举列表的情况下进行增量扫描：

for (endpointEntry pLo = pt.fLink; (pLo != null) && (pLo.XValue >= pt.lo); pLo = pLo.fLink)

将其分解，旧样式的循环说明符有三个部分：初始化、条件和增量递减。初始化表达式使用列表中当前点的前向链接初始化 endpointEntry pLo = pt.fLink;。即，列表中的下一个点，按降序排序。
然后执行内部循环的主体。然后应用增量减量 pLo，它只需使用内环的前向链路（ pLo = pLo.fLink）将内环的当前点（ pLo）设置为下一个较低点，从而推进内环。
最后，它在测试循环条件 pLo.fLink后循环，只要新点不为空（这意味着我们在列表的末尾），只要新点的 (pLo != null) && (pLo.XValue >= pt.lo)仍大于或等于外循环当前点的低x值。第二个条件确保内部循环只查看与外部循环端点的行重叠的行。
现在我更清楚的是，我也许可以把端点列表当作一个数组来处理整个fLink bLink笨拙：
用端点填充列表
按XValue对列表排序
按降序遍历列表的外部循环，使用索引迭代器（ XValue），而不是枚举器
（a）通过列表的内部循环，使用第二个迭代器（ i），从 foreach开始，到 j以下结束。
我觉得会简单得多。如果你愿意的话，我可以发布这样的简化版本。