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