我最初实现了Hoey-Shamos算法，但是由于未来的可维护性太复杂（这不在我的控制范围内），而且它没有正确报告，因此我将使用优化过的暴力算法。
我的问题是：如何优化这段代码以使其可用？
目前，我的代码包含一个嵌套的for循环，对同一列表进行两次迭代。
编辑：将行转换为HashSet并使用两个foreach循环...扫描10,000个数据减少了约45秒。但还不够。
如果我强制我的“intersectsLine（）”方法返回false（用于测试目的），它仍然需要8秒扫描10,000条记录（我有700,000条记录）。这太长了，所以我需要优化这段代码。
我尝试在将List与所有其他行进行比较后从中删除行，但是存在精度问题（不知道为什么），而且速度提高几乎无法察觉。
这是我的intersectsLine方法。我找到了一种替代方法here，但看起来它会因为所有的方法调用等等而变得更慢。计算斜率似乎对我来说不需要太多计算（如果我错了，请纠正我？）
我认为通过一些创意，可以将这个时间缩短到十五分钟左右。
我的问题是：如何优化这段代码以使其可用？
目前，我的代码包含一个嵌套的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（用于测试目的），它仍然需要8秒扫描10,000条记录（我有700,000条记录）。这太长了，所以我需要优化这段代码。
我尝试在将List与所有其他行进行比较后从中删除行，但是存在精度问题（不知道为什么），而且速度提高几乎无法察觉。
这是我的intersectsLine方法。我找到了一种替代方法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内运行了所有70万个多边形。这已经在可接受的范围内了！肯定有一种方法可以在运行此代码之前查看一个多边形是否值得计算吗？如果有必要，我可以访问XMin、Xmax、YMin和YMax属性。
进行了另一项测试，将多边形限制在每个不到1000条线。用时一小时左右。
我删除了对多边形的所有限制，现在已经运行了36个小时...仍然没有结果。
我有几个想法：
- 当我生成我的线哈希集时，还有另一个哈希集/列表，其中包含交点候选项。只有在存在可能相交的情况下，我才会将线添加到此列表中。但是如何消除/添加可能性？如果只有三条线可能与其他线相交，那么我将比较4000条线和3条线，而不是4000条。这本身就可能会有很大的差异。
- 如果同一点出现两次，除了第一个和最后一个点，省略运行嵌套的for循环。
编辑：
关于多边形的信息： 总共有700,000个
有超过四千个多边形具有1,000个或更多点
有2个多边形具有70,000个或更多点
我认为通过一些创意，可以将这个时间缩短到十五分钟左右。