python - Bentley-Ottman 与纯叉积交集的性能非常密集的 2D 段分布

Question

我要解决的问题是找到跨越给定矩形的线段之间的所有交点。线是随机生成的，直到给定数量，顺序为 1E3-1E4，并且所有端点都可以在矩形上找到。它基本上是在一个圆圈中生成随机和弦的矩形情况。在低密度系统 looks like this .

我主要感兴趣的输出是从直线和交叉点生成的图形，最好是我可以从 .csv 文件提供给 matplotlib 的形式。

为了了解尺寸，我首先进行了简单的实现，使用 this 检查每对是否相交与 NumPy 。它工作得相对不错，但是，可能是因为我没有注意内存管理，它在大量行时卡住。

现在我已经尝试了几天来调整我极其困惑的代码以使用 Bentley-Ottman 线扫描算法，但我意识到我需要从头开始重写它才能工作，主要是因为我一直在将列表与 Numpy 数组和显式索引混合使用，而不是使用适当的数据结构。

我的问题是，在这种非常密集、非常长的线段的特殊情况下，线扫描算法是否一定比原始方法更快，差距有多大？

Answer 1

经典扫描线算法在 O(n) 空间内运行 O(n log n + k) 时间，其中 n 是段数，k 是交叉点数。显然 k 在 O(n^2) 中。蛮力方法(我想这可能是您的“天真”方法)需要 O(n^2) 时间和空间。

如果您知道在平面 k 中稀疏分布的短线段可能很小，那么扫描线会更快。从空间方面来看，这取决于您对输出的处理方式。如果存储所有交点，则扫掠线也需要 O(n^2) 空间。