用于查找一系列线段与其他线段之间的交叉点的简单,有效的算法？

Question

我已经看过其他用于查找多对多线段之间交叉点的算法,但是:

1. 快速的有点太复杂(二叉搜索树)
2. 我的情况略有不同(一对多,细分排列成序列)

我有许多"方式",每个都是一系列线段:[(x0,y0) - (x1,y1)],[(x1,y1) - (x2,y2)],...我想找到其中一种方式与其他方式之间的潜在交叉点.

有没有一种算法比我在测试方式中针对每个其他方式对每个段进行盲测？但是,我认为维护二叉搜索树对于应用程序来说太复杂了.如果我可以在不维护任何数据结构的情况下离开,那也会很好.

对于这个应用程序,如果返回一些错误否定,则可能会出现异常情况.(目标是为人类节省手动定位交叉点的工作量,因此可能会有一些失误.)语言是ActionScript.

Answer 1

我知道有两种方法可以在线段中找到交叉点.

第一种方法是使用Bentley-Ottmann算法找到所有交叉点.然后,您可以过滤掉您不想要的段对(来自同一组的段对).请注意,支持此算法的所有边缘情况可能非常困难,我不建议这样做.我也很难找到Bentley-Ottmann的现有实现,而且我只知道一个处理边缘情况的实现.

另一种方法是使用两个R-Tree(这是你的二叉搜索树吗？)来索引你的每个系列段.然后,您可以遍历一个系列的所有片段,并查找附近其他系列的片段集.通过这个有希望减少的一组段,您可以强制您的交叉点搜索.根据您的数据集,它可以与Bentley-Ottmann的性能紧密匹配,或者与蛮力方法完全相同.另一个缺点是,如果必须移动段,则必须更新索引.另一方面,我发现使用此算法处理边缘情况更容易,并且R-Tree实现应该更容易找到或实现自己.

我仍然建议你在尝试任何这些之前尝试蛮力方法.它不应该花太长时间,并且大多数代码仍然可以用于实现其他两个方法.您可能还会发现,它足够快,可以避免使用更复杂方法的不可避免的麻烦.

回答史蒂文的评论的小更新.

当我实现交叉点查找算法时,我不得不优化处理OSM数据的过程.我的大多数表演测试是使用伦敦市完成的,其中包含很多段和交叉点(不记得实际的数字,对不起).我的交点查找算法还必须处理每个边缘情况(退化段,重叠段,水平和垂直段以及在其端点上相交的段),并且能够处理不断变化的数据集.

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

我最初开始这是基于一个BO执行工作提出(寻找一个强大和高效实施直线段相交问题扫描线算法 在这里).可悲的是,要做到正确(奇怪的逻辑和数值稳定性问题)是非常棘手的,我最终不得不废弃它.回想起来,我应该尝试开源,但现在有点太晚了.

无论如何,我接着尝试了R-Tree方法,该方法运行得非常好并且设法将这个巨大的6小时减少到仅仅30分钟,其中大部分用于其他地方.尽管必须不断更新R-Tree中的段.

所以,如果您的数据集足够大或者您进行了足够的搜索,那么它是值得的.我仍然强烈建议首先尝试使用蛮力方法,如果速度不够快,请升级到R-Tree.