確定點是否在多邊形或通過

Question

我想弄清楚如何在2D平面上有一個矢量（一條由2點組成的線）如何最好地做到這一點，我怎樣才能確定它是否已經通過通過多邊形？

我知道我可以把組成多邊形的每條線看看是否有相交，但有沒有更好的方法？

我讀過這篇文章How can I determine whether a 2D Point is within a Polygon?它給了我一些想法，看看點是否在一個多邊形內，但我需要看看它是否已經過去/相交它。

我對技術細節並不感興趣，我可能會在python中實現。

乾杯

大衛

Answer 1

如果你沒有太在意效率，你可以簡單地測試線的交點給你的兩個參考點和多邊形所有相鄰點對。一旦檢測到交叉點，就知道你的線與多邊形相交。

一個很好的出發點是，一如既往，維基百科：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 2

線條穿過多邊形當且僅當它穿過其中一條邊線時（忽略穿過頂點時的情況）。所以，在你的情況下，你只需要根據你的線測試你的多邊形的所有邊，看看是否有交集。

很容易測試邊緣(a, b)是否與直線相交。只需建立你的線上線方程如下形式

Ax + By + C = 0 

，然後計算點a和b值Ax + By + C。如果a和b的這些值的符號不同，則邊緣(a, b)與該線相交。

剩下的就是找出一種方法來處理線條穿過頂點（邊緣的端點）時的情況，但這很容易實現。

Answer 3

多邊形算法中沒有一個快速點嗎？使用一個，你可以確定是否有一個點在裏面，這也可能意味着相交。如果他們都在外面，還需要其他方法之一。

Answer 4

如果你想要一個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