python - 检查一个线段是否与一组线段相交

Question

我有一条从点 A 到点 B 的线段 AB (2d)。对于海岸线(闭合多边形，3*10^3 个顶点)的表示，我有一个 NumPy 点数组 (2d)，这些点在同一点开始和结束.我想知道点 A 和 B 之间的连接是否与海岸线相交。

我的第一个方法是遍历封闭多边形的每个线段并检查它是否与 AB 相交。这是 the underlying method .

即使我使用 NumPy 数组或使用 cython 转换函数来执行此操作，它也不够快，因为我必须多次执行此操作不同的 A 和 B。

我想，这可能是一个概念性问题，我想知道是否有一种更聪明的方法来检查是否至少存在一个交集 (True/False)?

我也尝试使用 shapely。但这有点慢。

from shapely.geometry import LineString
import numpy as np

coastline = LineString(np.dstack(x_values,y_values))

def intersection(A,B,Coastline):

      AB = LineString([(A[0], A[1]), (B[0], B[1])])
      if AB.intersection(coastline).is_empty:
         return False
      return True

Answer 1

这是一个碰撞检测问题。

因此，在您的情况下，最好是将您的海岸线放在一个空间数据结构中，例如 bsp 树、四叉树、aabb 树等。

然后在你的线段和树结构之间进行交集。

例如，参见 CGAL AABB_tree: https://doc.cgal.org/latest/AABB_tree/index.html

该库适用于 3D，但同样的想法也适用于 2D。您可以非常快速地将几乎任何几何体嵌入到 aabbtree 和查询线交点中