我最初实现了 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 条记录仍然需要 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 <= 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
有超过 4000 个具有 1000 个或更多点的多边形
有 2 个多边形具有 70,000 或更多点
我认为只要有一点创造力，就有可能把它缩短到十五分钟左右。