实现用于检测自相交多边形的powershell算法
我最初实现了Hoey-Shamos算法，但是它太复杂了以至于未来的可维护性（我没有说明），并且没有正确报告，所以我将使用优化的powershell算法。
我的问题是：如何优化此代码才能使用？
就目前而言，我的代码包含一个嵌套的for循环，两次迭代相同的列表。
编辑：将线条转换为HashSet并使用两个foreach循环…扫描10,000个约45秒。 这还不够。
foreach (Line2D g in lines) { foreach (Line2D h in lines) { if (g.intersectsLine(h)) { return false; } } } // end 'lines' for each loop 如果我强制我的“intersectsLine（）”方法返回false（出于测试目的），扫描10,000条记录仍然需要8秒（我有700,000条记录）。 这太长了，所以我需要优化这段代码。
在尝试将其与所有其他行进行比较后，我尝试从列表中删除行，但是存在准确性问题（不知道为什么）并且速度增加几乎不可察觉。
这是我的intersectsLine方法。 我在这里找到了另一种方法，但看起来所有的方法调用和诸如此类的东西都会变慢。 计算斜率对我来说似乎并不像是需要太多的计算（如果我错了，请纠正我？）
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 = 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中运行了所有700,000多个多边形。 哪个在可接受的范围内！ 当然有一种方法可以在运行此代码之前查看多边形是否值得计算？ 如果有帮助，我可以访问XMin，Xmax，YMin和YMax属性吗？
进行另一项测试，将多边形限制在1000行以下。 花了一个多小时。
我删除了多边形的所有限制，它现在已经运行了36个小时……仍然没有结果。
我有几个想法：
– 当我生成我的行hashset时，让另一个hashset / List具有候选交集。 如果有交叉的机会，我只会在此列表中添加行。 但是，我如何消除/增加可能性？ 如果只有三条线可能与其他线相交，我会将4000线与3线而不是4000线进行比较。仅此一项就可以产生巨大的差异。
– 如果相同的点出现两次，除了第一个和最后一个点，省略运行嵌套的for循环。
编辑：
有关多边形的信息：总计700,000
有超过四千个多边形，有1,000或更多点
有2个多边形，有70,000或更多点
我认为有可能通过一点创造力将其降低到十五分钟左右。
您当前的Brute-Force算法是O（n ^ 2）。 对于你的两个70,000个线形多边形来说，这几乎是100亿次操作的因素，更不用说70万个其他多边形了。 显然，没有多少纯粹的代码优化就足够了，所以你需要一些可以降低O（n ^ 2）而不会过度复杂的算法优化。
O（n ^ 2）来自蛮力算法中的嵌套循环，每个循环由n限定，使其成为O（n * n）。 最简单的方法是找到一些方法来减少内部循环，使其不受n约束或依赖于n 。 因此，我们需要找到一种方法来订购或重新排序内部行列表以检查外部线，以便只需要扫描完整列表的一部分。
我采用的方法利用了这样一个事实：如果两个线段相交，那么它们的X值的范围必须相互重叠。 请注意，这并不意味着它们确实相交，但如果它们的X范围不重叠，则它们不能相交，因此不需要相互检查它们。 （Y值范围也是如此，但您一次只能利用一个维度）。
这种方法的优点是这些X范围可用于对线的端点进行排序，这些端点又可以用作起点和终点，以检查线的交叉点。
具体而言，我们所做的是定义一个自定义类（ endpointEntry ），它表示该行的两个点的高或低X值。 这些端点都放在相同的List结构中，然后根据它们的X值进行排序。
然后我们实现一个外循环，我们扫描整个列表就像在暴力算法中一样。 然而，我们的内环非常不同。 我们不是重新扫描整个列表以检查交叉点，而是从外环线的高X值端点开始扫描排序的端点列表，并在我们通过同一行的低X值端点下方时结束它。 这样，我们只检查X值范围与外环线重叠的线。
好的，这是ac #class演示我的方法：
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 { 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 lines) { List pts = new List (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 * SQRT（n）），这应该足够快。
内循环逻辑的说明：
Inner Loop只是以与外部循环相同的排序顺序扫描endPoints列表。 但是它将从外部循环当前位于列表中的外部循环（这是某行的hiX点）开始扫描，并且仅扫描直到endPoint值降低到同一行的相应loX值以下。
这里有些棘手的问题是，使用Enumerator（外部循环的foreach(..in pts)无法做到这一点，因为无法枚举列表的子列表，也无法根据另一个枚举当前位置启动枚举。 所以我所做的就是使用前向和后向链接（fLink和bLink）属性来创建一个双向链表结构，保留列表的排序顺序，但我可以在不枚举列表的情况下逐步扫描：
for (endpointEntry pLo = pt.fLink; (pLo != null) && (pLo.XValue >= pt.lo); pLo = pLo.fLink)
打破这种情况，旧式for循环说明符有三个部分：初始化，条件和递增 – 递减。 初始化表达式， endpointEntry pLo = pt.fLink; 使用列表中当前点的前向链接初始化pLo 。 也就是说，列表中的下一个点，按降序排序。
然后执行内循环的主体。 然后应用递增 – 递减pLo = pLo.fLink ， pLo使用它的前向链接（ pLo.fLink ）将内循环的当前点（ pLo ）设置为下一个较低点，从而推进循环。
最后，它在测试循环条件(pLo != null) && (pLo.XValue >= pt.lo)循环，只要新点不为空（这意味着我们在结束时）只要新点的XValue仍然大于或等于外环当前点的低X值，就可以了。 第二个条件确保内循环仅查看与外循环端点的线重叠的线。
现在更清楚的是，通过将endPoints List视为一个数组，我可能已经解决了整个fLink-bLink的笨拙：
- 使用endPoints填充列表
- 按XValue对列表进行排序
- 外循环通过列表降序，使用索引迭代器（
i），而不是foreach枚举器 - （A）内部循环遍历列表，使用第二个迭代器（
j），从i开始，到pt.Lo以下时pt.Lo。
我认为这会简单得多。 如果你愿意，我可以发布这样的简化版本。
有两件事需要检查：
- 闭合多边形由循环的点序列组成
- 如果这个序列中的相同点不止一次，那么它就是自相交的多边形。
- 请注意，第一个和最后一个点可以相同（在多边形表示上有所不同），在这种情况下，此点必须更加棕褐色两次。
- 检查多边形的所有非相邻线是否相交
- 不相邻的线路不分享任何一点
- 如果有交叉点则多边形是自相交的
对于不相交的多边形应该只有一半时间的简单优化：
int count = lines.Count(); for (int l1idx = 0; l1idx < count-1; l1idx++) for (int l2idx = l1idx+1; l2idx < count; l2idx++) { Line2D g = lines[l1idx]; Line2D h = lines[l2idx]; if (g.intersectsLine(h)) { return false; } }