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

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

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

我读过这篇文章如何确定 2D 点是否在多边形内？ https://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test这给了我一些关于查看该点是否在多边形内的想法，但我需要查看它是否已经经过/相交。

如果你想要一个用于几何运算的Python库，请看看shapely https://github.com/Toblerity/Shapely。它使这变得简单someline.intersects(somepolygon).

这是一个交叉点、缓冲区和裁剪的快速示例（有一个很好的图......我正在使用descartes http://pypi.python.org/pypi/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