简单，一些有效的算法，寻找一个系列的线段和其他的交点？

Question

我看过其他算法，用于寻找多到多个线段之间的交叉点，但是：

1. 快速搜索有点太复杂了(二进制搜索树)
2. 我的情况略有不同(一对多，并且分段排列成序列)。

我有许多“方法”，每一个都是一系列的线段：(x0，y0)-(x1，y1)，(x1，y1)-(x2，y2)，.我想找出其中一种方式和所有其他方法之间的潜在交叉点。

是否有一种算法比盲目地测试我的测试方式中的每一段相对于其他方法的每一段要好呢？但是，我认为维护二进制搜索树对于应用程序来说太复杂了。如果我可以在不维护任何数据结构的情况下逃脱，那也会很好。

对于这个应用程序，如果返回一些错误的底片，对于不寻常的情况，可能是可以的。(其目标是为人类节省人工定位交叉口的工作，因此有几次失误可能是可以的。)语言是ActionScript。

Answer 1

我知道有两种方法可以找到直线段中的交叉点。

第一种方法是使用宾利-奥特曼算法查找所有的交叉口。然后，您可以筛选出不想要的段对(来自同一组的段对)。请注意，支持该算法的所有边缘情况可能非常困难，我不推荐它。此外，我很难找到现有的Bentley-渥太华和我只知道一个处理边缘案件的人的实现。

另一种方法是使用两个R-树 (这是您的二进制搜索树吗？)索引您的一系列片段中的每一个。然后，您可以迭代一个系列的所有段，并查找邻近的另一个系列的段集。有了这个希望减少的段集，您就可以强行强制您的交叉搜索。取决于您的数据集，它既可以与本特利-奥特曼的性能紧密匹配，也可以执行完全类似于蛮力的方法。另一个缺点是，如果您必须移动您的段，您必须更新您的索引。另一方面，我发现使用该算法处理边缘情况更容易，而R-Tree实现应该更容易找到或实现自己。

我仍然建议你在尝试其中任何一种之前，先尝试一下蛮力方法。它不应该花太长时间，而且大多数代码对于实现另外两种方法仍然是有用的。您可能还会发现，它的速度足够快，以避免不可避免的头痛与更复杂的方法。

小更新，回答史蒂文的评论。

当我实现求交算法时，我必须优化处理OSM数据的过程。我的大多数性能测试都是在伦敦金融城进行的，伦敦金融城包含了很多片段和交叉口(对不起，不记得实际的数字)。我的求交算法还必须处理每一种边缘情况(简并段、重叠段、水平和垂直段以及端点相交的段)，并能够处理不断变化的数据集。

我正在优化的过程可以在不断修改它所处理的数据集的同时，调用数十万次的求交算法。除了交叉搜索之外，它还做了很多其他的事情。使用天真的方法，这需要大约6个小时的时间来执行。

我最初开始研究一个基于本论文的B实现(寻找一种健壮而高效的扫描直线算法的实现，用于直线段交点问题这里)。可悲的是，很难纠正(奇怪的逻辑和数值稳定性问题)，最后我不得不放弃它。回顾过去，我本应该尝试开源的，但现在为时已晚了。

无论如何，我尝试了R-Tree方法，它非常有效，并设法将这个巨大的6小时缩短到了30分钟，而大部分时间都花在了其他地方。这是尽管必须不断更新R-树中的段。

所以是的，如果你的数据集足够大，或者你做了足够多的搜索，这是值得的。我仍然强烈建议先尝试蛮力的方法，如果速度不够快，升级到R树。