以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，它允许您批处理计算