以NumPy（布尔值）检测潜在的线段交点

Question

我有两个numpy数组，由若干线段组成，格式为[x1, y1, x2, y2]：

foo = np.array([
    [2, 3, 2, 1],
    [6, 3, 5, 4],
    [5, 6, 8, 2],
    [5, 2, 6, 5]
])

bar = np.array([
    [4, 2, 7, 8],
    [2, 1, 6, 9]
])

我的最终目标是检查来自foo的每个线段与来自bar的每个线段，并验证交点。不需要交点，我只想知道两段是否相交（真/假）

实际上，{}中有几十亿行，{}中有几百行，所以我想在跳到一个更复杂的方法之前，我会先执行一个更简单的检查来验证以下内容：

# two segments are potentially intersecting if and only if
xFmin <= xBmax && xBmin <= xFmax     # x overlap
&&
yFmin <= yBmax && yBmin <= yFmax     # y overlap

其思想是，如果两条线段不能同时满足此测试，则它们不可能相交。我正试图用numpy实现这个测试，但到目前为止运气不佳。我想到了几个问题：

• 如何确定例如yFmin和yFmax（可通过预先排序坐标一次完成）
• 如何正确地分割和广播这两个数组以进行上述比较
• 是否有可能在一次操作中对所有段进行整个比较

该测试应给出与以下类似的最终输出：

result = np.array([
    [True, False, False, True],   # all segments in Foo against the first segment in Bar
    [False, False, True, True]    # all segments in Foo against the second segment in Bar
])

Answer 1

如果您有数十亿个段，我建议使用一个库，如：https://github.com/Permafacture/python-computational-geometry，它允许您批处理计算

Answer 2

对于第一个问题，我建议您只需通过比较两个X极值和两个Y极值将线段表示设置为

[x_min, y_min, x_max, y_max]

（此表示应减少您需要在每个段上执行的操作数量，最多两次交换） 然后存储结果

然后，您可以循环浏览条中的段（应该更有效，因为它们较少），并使用您的过滤条件。您可以为每列写入条件，因此第一个条件将是

x_min_bools = foo[:,0] <= x_bar_min

你也会以类似的方式做其他三个。然后，您可以使用np.logical_和（）组合布尔数组以获得结果行

Answer 3

前一段时间，我解决了一个类似的问题，实现了中描述的扫描线算法：

Michael Shamos, Dan Hoey (1976). Geometric Intersection Problems. https://doi.org/10.1109/SFCS.1976.16

它将问题从O（N²）转换为O（N log N）

在Jivan的评论后添加：

要将一个集合中的线段与另一个集合中的线段进行比较，可以尝试以下方法：

Chan (1994), A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.4227

免责声明：我还没有实现这个