假设在一般位置有n个线段。如何快速计算n个线段中的每一个线段,它与其他n-1相交的线段有多少?
我可以在O(N2)时间里天真地做这件事。在o((n+k)logn)时间内,我可以使用一个相当简单的扫描线算法(bentley ottmann)找到所有的交叉点,其中k是此类交叉点的数量,然后将我找到的交叉点聚合成一堆计数。
不过,我不需要找到十字路口,我只想知道有多少。我不知道如何将扫描线算法修改得更快,因为它需要为每个交叉点对树中的两个对象重新排序,而且我想不出任何其他技术不会遇到相同的问题。
我还想听听如何计算总共有多少个十字路口。
最佳答案
我很难相信在一般情况下你能比宾利奥特曼做得更好。如果你不在乎线段在哪里相交,你可以简化计算,但我不明白你如何在不找到线段的情况下计算交叉点。
本质上,宾利奥特曼是一种简化交叉口搜索空间的方法。还有其他方法,可能适用于特定的线段排列,但除非线段之间存在某种可预测的几何关系,否则您将无法比首先使用某种聪明的方法来找到候选交点,并结合对每个候选点的单独验证更好。
除非你的问题域有一些特定的特性,这可能会提供可利用的子结构,我认为你最好的速度打赌将是适应宾利奥特曼(或一些类似的扫描算法)并行执行。(将线段剪裁为标注栏很简单。当然,这是一个实际的而不是一个学术性的练习;并行算法可能最终会做更多的工作;它只是利用硬件在(恒定因子)更少的时间内完成工作。