非常密集二维路段分布下bentleyotman与naives交叉口的性能比较

Question

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

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

为了了解维度，我首先使用了一个简单的实现，使用this和Numpy检查每对的交集。它的工作相对来说还可以，但是，可能是因为我没有注意到内存管理，所以它在大量的行中冻结。在

我已经花了几天的时间来修改我的非常混乱的代码来使用Bentley-Ottman行扫描算法，但是我意识到我需要从头开始重写它才能工作，主要是因为我一直在混合使用Numpy数组和显式索引的列表，而不是正确的数据结构。在

我的问题是，在这种非常密集、非常长的线段的特殊情况下，直线扫描算法是否一定比朴素的方法快，并且以多大的差距？在

Answer 1

经典的扫描线算法在O（n logn+k）时间内在O（n）空间中运行，其中n是分段数，k是交点数。显然k是在O（n^2）中。暴力方法（我想这可能是你的“天真”方法）需要O（n^2）时间和空间。在

如果你知道你有短线段稀疏分布在平面k可能很小，那么扫描线会更快。从空间方面看，这取决于你对输出做了什么。如果存储所有交点，则还需要O（n^2）空间和扫描线。在