tmy*_*ebu 8 language-agnostic algorithm geometry computational-geometry
假设我在一般位置有n个线段.对于我的每个n段,我如何快速计算它相交的其他n-1的数量？
我可以在O(n 2)时间内天真地做这件事.我可以在O((n + k)log n)时间内使用相当简单的扫描线算法(Bentley-Ottmann)找到所有交叉点,其中k是这样的交叉点的数量,然后将我发现的交叉点聚合成一堆计数.
不过,我不需要找到交叉路口; 我只是想知道有多少.我没有看到如何将扫描线算法修改得更快,因为它需要为每个交叉点重新排序树中的两个东西,我想不出任何其他没有遇到同样问题的技术.
我也有兴趣听听如何计算总交叉口数量.
在一般情况下,我很难相信你可以比Bentley Ottman做得更好.如果您不关心线段相交的位置,您可以稍微简化计算,但我不知道如何在不找到它们的情况下计算交叉.
本质上,Bentley Ottman是一种简化交叉点搜索空间的方法.还有其他方法,可能适用于线段的特定排列,但除非您的线段之间存在一些可预测的几何关系,否则您将无法比首先使用一些巧妙的方法找到候选交叉点并结合使用每个候选人的个人核实.
除非您的问题域具有一些可能提供可利用子结构的特定功能,否则我认为最好的选择是将Bentley Ottman(或类似的扫描算法)用于并行执行.(将线段剪切成条带很简单.找出一组最佳的条带也很有趣.)当然,这是一种实用而非学术的练习; 并行算法最终可能会完成更多的工作; 它只是利用硬件来完成(一个恒定的因素)更少的时间.