确定一条线段是否与多边形相交。

Question

如果我在二维平面上有一个向量（由2个点组成的线），如何确定它是否穿过了一个多边形？

我知道可以取出构成多边形的每条线并查看是否有任何交点，但是否有更好的方法？

我已经阅读了这篇文章如何确定2D点是否在多边形内？，其中给了我一些关于判断点是否在多边形内的想法，但我需要知道它是否已经穿过/相交。

- David Bramer

---

你需要确定该直线是否与多边形的任何边相交或包含其顶点之一。根据你所做的工作，这通常可以通过提前为每个多边形计算一个边界圆来加速处理，并首先检查该直线是否与其相交以快速拒绝整个多边形。 - martineau

Answer 1

如果您需要进行几何运算的Python库，请看一下shapely。它使得这个过程像someline.intersects(somepolygon)一样简单。

以下是一个快速的示例，包括交集、缓冲和剪切（使用descartes将shapely多边形轻松转换为matplotlib补丁）。

import numpy as np
import matplotlib.pyplot as plt
import shapely.geometry
import descartes

circle = shapely.geometry.Point(5.0, 0.0).buffer(10.0)
clip_poly = shapely.geometry.Polygon([[-9.5, -2], [2, 2], [3, 4], [-1, 3]])
clipped_shape = circle.difference(clip_poly)

line = shapely.geometry.LineString([[-10, -5], [15, 5]])
line2 = shapely.geometry.LineString([[-10, -5], [-5, 0], [2, 3]])

print 'Blue line intersects clipped shape:', line.intersects(clipped_shape)
print 'Green line intersects clipped shape:', line2.intersects(clipped_shape)

fig = plt.figure()
ax = fig.add_subplot(111)

ax.plot(*np.array(line).T, color='blue', linewidth=3, solid_capstyle='round')
ax.plot(*np.array(line2).T, color='green', linewidth=3, solid_capstyle='round')
ax.add_patch(descartes.PolygonPatch(clipped_shape, fc='blue', alpha=0.5))
ax.axis('equal')

plt.show()

这将产生：

Blue line intersects clipped shape: True
Green line intersects clipped shape: False

- Joe Kington

---

这个适用于3D几何吗？（甚至N元几何？） - ThorSummoner

Answer 2

只有当一条线穿过多边形的边缘时才会相交（暂不考虑它通过一个顶点的情况）。因此，在您的情况下，您只需要测试多边形的所有边缘是否与您的线段相交。

很容易测试边缘是否与一条直线相交。只需用以下格式为您的直线构建一条直线方程：

Ax + By + C = 0

然后计算点 a 和 b 的值为 Ax + By + C。如果 a 和 b 的值的符号不同，则边缘 (a, b) 与该线相交。

现在需要解决的问题是如何处理线经过顶点（边缘的端点）的情况，但这很容易实现。

- AnT stands with Russia

Answer 3

如果你不太关心效率，可以简单地测试线段相交，给定两个参考点和多边形上所有相邻点对。一旦检测到交点，就知道你的线段与多边形相交了。

良好的起点是维基百科：http://en.wikipedia.org/wiki/Line-line_intersection 现在让我们通过一个例子来演示。

function line-polygon_intersection:
   Given points p0, p1 on plane P (your reference line)
   Given points q0..qn on plane P (the polygon)
   foreach ( qi, qi+1 ) pair of adjacent points:
      if line( p0, p1 ) intersects line( qi, qi+1 ):
          return true
   return false

别忘了用 (qn，q0) 循环来关闭多边形！

祝你好运！

- dusktreader

Answer 4

有没有快速的点在多边形算法？使用这种算法，您可以确定恰好一个点是否在内部，这也可能意味着相交。如果它们都在外面，则仍需要另一种方法之一。

- karmakaze