检测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中的每个路段进行对照，并验证交叉点。不需要交点，我只想知道两个线段是否相交（真/假）。

实际上，foo中有几十亿行，bar中有几百行，所以我认为我将避免直接跳转到计算每对点的点积，而是执行先前的，更简单的检查来验证以下：

# two lines are potentially intersecting (and thus worth checking for a dot-product) if and only if:
((yFmin < yBmin) & (yFmax > yBmin) or (yFmin < yBmax) & (yFmax > yBmax))
  &
((xFmin < xBmin) & (xFmax > xBmin) or (xFmin < xBmax) & (xFmax > xBmax))

想法是，如果两个线段不一起满足此测试，则它们不可能相交。我正在尝试用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，该库可用于批量计算。