实现用于检测自相交多边形的蛮力算法
我最初实现了Hoey-Shamos算法，但是它对于将来的可维护性来说太复杂了（我对此没有发言权），并且报告不正确，因此我将使用经过优化的蛮力算法。
我的问题是：如何优化此代码以使其可用？
就目前而言，我的代码包含一个嵌套的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条记录（我有700,000条记录）仍需要8秒。这太长了，因此我需要优化这段代码。
与其他所有行进行比较之后，我尝试从列表中删除行，但是存在准确性问题（不知道为什么），并且速度的提高几乎没有引起注意。
这是我的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 <= 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的速度运行了所有700,000多个多边形。在可接受范围内！在运行此代码之前，肯定有一种方法可以查看多边形是否值得计算？我可以访问XMin，Xmax，YMin和YMax属性是否有帮助？
进行另一项测试，将多边形限制在1000条以下。花了一个多小时。
我删除了所有对多边形的限制，并且它已经运行了36个小时……仍然没有结果。
-生成线哈希集时，请使用另一个具有交集候选的哈希集/列表。如果有交叉的机会，我只会在此列表中添加行。但是，如何消除/增加可能性？如果只有三条线可能与其他线相交，我将4000条线与3条线而不是4000条线进行比较。仅此一项就可以带来巨大的不同。
-如果同一点出现两次，除了第一个和最后一个点，请省略运行嵌套的for循环。
编辑：
关于多边形的信息：总计700,000
有超过1,000个点的超过4000个多边形
有2个具有70,000或更多点的多边形
我认为有一点创意可以将时间缩短到十五分钟左右。
回答：
您当前的蛮力算法为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(..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 != null) && (pLo.XValue >=
pt.lo)循环，只要新点不为空（这意味着我们位于列表的末尾）并且新点的XValue大小仍大于或等于外循环当前点的低X值。第二个条件确保了内部循环仅查看与外部循环的端点的线重叠的线。
现在对我来说更清楚的是，我可以通过将endPoints List视为数组来解决整个fLink-bLink的笨拙问题：
- 用端点填充列表
- 按XValue对列表排序
- 使用索引迭代器（
i）而不是foreach枚举器按降序在列表中进行外循环 - （A）使用第二个迭代器（
j）在列表中进行内循环，从其开始通过i，直到结束pt.Lo。
我认为这会简单得多。如果需要，我可以发布这样的简化版本。
以上是 实现用于检测自相交多边形的蛮力算法 的全部内容， 来源链接： utcz.com/qa/422028.html
