您当前的蛮力算法为O（n ^
2）。对于您的两个70,000线多边形，这几乎是100亿次运算的一部分，更不用说其他700,000个多边形了。显然，单凭代码优化就不够了，因此您需要某种算法优化，可以降低O（n
^ 2）而又不会过于复杂。
O（n ^ 2）来自蛮力算法中的嵌套循环，每个循环都以限制
n，使其为O（n *n）。改善此问题的最简单方法是找到减少内部循环的方法，以使该内部循环不受或依赖
n。因此，我们需要找到一种对内部行列表进行排序或重新排序以检查外部行的方法，以便仅扫描整个列表的一部分。
我采用的方法利用了以下事实：如果两个线段相交，则它们的X值范围必须彼此重叠。请注意，这并不意味着它们 确实 相交，但是如果它们的X范围不重叠，则它们
将无法 相交，因此无需相互检查。（Y值范围也是如此，但一次只能利用一个维度）。
这种方法的优势在于，可以使用这些X范围对直线的端点进行排序，这些端点又可以用作起点和终点，针对该起点和终点检查线以进行相交。
因此，具体地说，我们要做的是定义一个自定义类（
endpointEntry），该类代表直线两点的高X值或低X值。这些端点都放入相同的List结构中，然后根据它们的X值进行排序。
然后，我们实现一个外部循环，在该循环中，我们像蛮力算法一样扫描整个列表。但是，我们的内循环却大不相同。而不是重新扫描的线检查路口整个列表，我们宁可 开始
扫描下来从外环的线的高X值端点排序端点列表，并结束它，当我们通过这条线上的低X值端点之下。这样，我们仅检查X值范围与外循环线重叠的线。
好的，这是一个ac＃类，展示了我的方法：
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 * SQRT（n）），应该足够快。
内部循环逻辑的解释：
内循环只是按照与外循环相同的排序顺序扫描端点列表。但是它将从外循环当前在列表中的位置（这是某一行的hiX点） 开始
扫描外循环，并且只会扫描直到endPoint值下降到同一行的相应loX值以下。
这里的棘手之处在于，这无法使用枚举器（
foreach(..inpts)外部循环的）来完成，因为无法枚举列表的子列表，也无法基于另一个枚举的当前位置开始枚举。因此，我要做的是使用“向前和向后链接”（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 != null) && (pLo.XValue >=pt.lo)循环，只要新点不为空（这意味着我们位于列表的末尾）并且新点的
XValue大小仍大于或等于外循环当前点的低X值。第二个条件确保了内部循环仅查看与外部循环的端点的线重叠的线。
现在对我来说更清楚的是，我可以通过将endPoints List视为数组来解决整个flink-blink的笨拙问题：
- 用端点填充列表
- 按XValue对列表排序
- 使用索引迭代器（
i
）而不是foreach
枚举器按降序在列表中进行外循环 - （A）使用第二个迭代器（
j
）在列表中进行内循环，从其开始通过i
，直到结束pt.Lo
。
我认为这会简单得多。如果需要，我可以发布这样的简化版本。
