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

Question

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

我知道我可以采用构成多边形的每条线并查看是否有相交，但有更好的方法吗？

我读过这篇文章 如何确定 2D 点是否在多边形内？ 这给了我一些关于查看该点是否在多边形内的想法，但我需要查看它是否已经经过/相交。

Answer 1

如果您想要一个用于几何运算的 Python 库，请查看 shapely。它使得这就像someline.intersects(somepolygon)一样简单。

这是一个交叉点、缓冲区和裁剪的快速示例（有一个很好的图...我正在使用 descartes 轻松将形状多边形转换为 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

Answer 2

当且仅当线穿过多边形的一条边时，线才穿过多边形（暂时忽略穿过顶点时的情况）。因此，在您的情况下，您只需要根据您的线测试多边形的所有边，看看是否有交叉点。

测试边 (a, b) 是否与直线相交很容易。只需按照以下形式为直线建立直线方程

Ax + By + C = 0

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

剩下的就是找出一种方法来处理线经过顶点（边的端点）时的情况，但这很容易做到。

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) 循环来关闭多边形！

祝你好运！

Answer 4

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

Answer 5

此答案基于Joe Kington 对此问题的回答。
我修改了代码，使其可以与 Python 3 一起使用。还有一个问题是 shaply/numpy/matplotlib 的当前实现与代码不兼容。笛卡尔还有另一个问题。该版本不依赖于笛卡尔。我试图重现相同的外观。

# https://stackoverflow.com/questions/6050392/determine-if-a-line-segment-intersects-a-polygon
# modified for python 3, incl. fixes
import numpy as np
import matplotlib.pyplot as plt
import shapely.geometry

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.coords.xy), color='blue', linewidth=3, solid_capstyle='round')
ax.plot(*np.array(line2.coords.xy), color='green', linewidth=3, solid_capstyle='round')
plt.fill(*np.array(clipped_shape.boundary.coords.xy), facecolor=(0.49,0.49,1), edgecolor=(0.49,0.49,1), linewidth=3)
ax.axis('equal')

plt.show()