判断线段是否与多边形相交

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

然后计算点

Ax + By + C

和

a

的值

b

。如果

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()