确定点是多边形还是通过

Question

我想弄清楚如何最好地做到这一点,如果我在2d平面上有一个矢量(由2个点组成的线),我如何确定它是否已通过多边形？

我知道我可以采取构成多边形的每一条线,看看是否有任何相交,但有更好的方法吗？

我已经阅读过这篇文章如何确定2D点是否在多边形内？这给了我一些想法,看看点是否在多边形内,但我需要看看它是否已经过了/相交了它.

我对技术细节并不感兴趣,我可能会在python中实现.

干杯

大卫

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

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

一如既往，维基百科是一个很好的起点： 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) 循环来关闭多边形！

祝你好运！