检测 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 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

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

迈克尔·沙莫斯，丹·霍伊(1976(。几何相交问题。 https://doi.org/10.1109/SFCS.1976.16

它将问题从 O(N²( 转换为 O(N log N(。

在Jivan的评论之后添加：

对于一个集合中的段与另一个集合中的段的比较，您可以尝试此方法：

Chan (1994(，一种用于报告红/蓝段交叉点的简单梯形扫描算法。 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.4227

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

Answer 2

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

Answer 3

对于第一个问题，我建议只遍历所有段，并通过比较两个 X 极值和两个 Y 极值来对条目进行排序，将段表示设置为类似

[x_min, y_min, x_max, y_max]

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

然后，您可以遍历 bar 中的段(应该更有效，因为它们的数量更少(并使用您的过滤条件。您可以编写每列的条件，因此第一个将是

x_min_bools = foo[:,0] <= x_bar_min

你以类似的方式做其他三个。然后，您可以使用 np.logical_and(( 组合布尔数组来获取结果行。