ポイントがポリゴンのポリゴンの内側にあるかどうかを調べる最も速い方法は

Question

ポイントがポリゴンの内側にあるかどうかを調べる2つの主な方法があります。 1つは、最も推奨される答えであるhereを使用するレイトレーシング方法を使用しています。もう1つは、matplotlib path.contains_points（これは私にはわかりにくいようです）を使用しています。私は多くのポイントを連続してチェックしなければならないでしょう。これらの2つのいずれかが他のものよりも推奨されている場合、またはより良い第3の選択肢があるかどうかは誰にも分かりますか？

UPDATE：

私は2つの方法を確認し、matplotlibのは、はるかに高速になります。

与える

from time import time 
import numpy as np 
import matplotlib.path as mpltPath 

# regular polygon for testing 
lenpoly = 100 
polygon = [[np.sin(x)+0.5,np.cos(x)+0.5] for x in np.linspace(0,2*np.pi,lenpoly)[:-1]] 

# random points set of points to test 
N = 10000 
points = zip(np.random.random(N),np.random.random(N)) 


# Ray tracing 
def ray_tracing_method(x,y,poly): 

    n = len(poly) 
    inside = False 

    p1x,p1y = poly[0] 
    for i in range(n+1): 
     p2x,p2y = poly[i % n] 
     if y > min(p1y,p2y): 
      if y <= max(p1y,p2y): 
       if x <= max(p1x,p2x): 
        if p1y != p2y: 
         xints = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x 
        if p1x == p2x or x <= xints: 
         inside = not inside 
     p1x,p1y = p2x,p2y 

    return inside 

start_time = time() 
inside1 = [ray_tracing_method(point[0], point[1], polygon) for point in points] 
print "Ray Tracing Elapsed time: " + str(time()-start_time) 

# Matplotlib mplPath 
start_time = time() 
path = mpltPath.Path(polygon) 
inside2 = path.contains_points(points) 
print "Matplotlib contains_points Elapsed time: " + str(time()-start_time) 

、

Ray Tracing Elapsed time: 0.441395998001 
Matplotlib contains_points Elapsed time: 0.00994491577148 

同じ相対的な差は、三角形の代わりに100の側のポリゴンを用いたものを得ました。あなたは、私が唯一の二、path.contains_pointsを使用しました言及した方法の中から

from shapely.geometry import Point 
from shapely.geometry.polygon import Polygon 

point = Point(0.5, 0.5) 
polygon = Polygon([(0, 0), (0, 1), (1, 1), (1, 0)]) 
print(polygon.contains(point)) 

、：それはちょうどあなたがshapelyを考慮することができる問題

Answer 1

のこれらの種類に専念したパッケージを探しますので、私もすっきりチェックしますそれはうまく動作します。いずれにしても、テストに必要な精度に応じて、ポリゴン内のすべてのノードがTrue（偽でない場合はFalse）になるようにnumpyブールグリッドを作成することをお勧めします。あなたは多くのポイントのためのテストをするつもりされている場合、これは速いかもしれません（通知は、これはあなたが「ピクセル」の許容以内にテストを行っている依存していますが）：

from matplotlib import path 
import matplotlib.pyplot as plt 
import numpy as np 

first = -3 
size = (3-first)/100 
xv,yv = np.meshgrid(np.linspace(-3,3,100),np.linspace(-3,3,100)) 
p = path.Path([(0,0), (0, 1), (1, 1), (1, 0)]) # square with legs length 1 and bottom left corner at the origin 
flags = p.contains_points(np.hstack((xv.flatten()[:,np.newaxis],yv.flatten()[:,np.newaxis]))) 
grid = np.zeros((101,101),dtype='bool') 
grid[((xv.flatten()-first)/size).astype('int'),((yv.flatten()-first)/size).astype('int')] = flags 

xi,yi = np.random.randint(-300,300,100)/100,np.random.randint(-300,300,100)/100 
vflag = grid[((xi-first)/size).astype('int'),((yi-first)/size).astype('int')] 
plt.imshow(grid.T,origin='lower',interpolation='nearest',cmap='binary') 
plt.scatter(((xi-first)/size).astype('int'),((yi-first)/size).astype('int'),c=vflag,cmap='Greens',s=90) 
plt.show() 

、結果がこれです：

Answer 2

あなたのテストは良いですが、それだけでいくつかの特定の状況を測定します： 我々はポリゴン内でそれらをチェックする一つの多くの頂点を持つポリゴン、およびポイントの長い配列を持っています。

また、私はシンプルなリスト反復対matplotlibの-何とか-最適化された反復あなたはレイ法、 対ない matplotlibの-内部ポリゴン法を測定していると仮定しますが

のは、Nを作ろう独立した比較（ポイントとポリゴンのN個のペア）？

# ... your code... 
lenpoly = 100 
polygon = [[np.sin(x)+0.5,np.cos(x)+0.5] for x in np.linspace(0,2*np.pi,lenpoly)[:-1]] 

M = 10000 
start_time = time() 
# Ray tracing 
for i in range(M): 
    x,y = np.random.random(), np.random.random() 
    inside1 = ray_tracing_method(x,y, polygon) 
print "Ray Tracing Elapsed time: " + str(time()-start_time) 

# Matplotlib mplPath 
start_time = time() 
for i in range(M): 
    x,y = np.random.random(), np.random.random() 
    inside2 = path.contains_points([[x,y]]) 
print "Matplotlib contains_points Elapsed time: " + str(time()-start_time) 

結果：

Ray Tracing Elapsed time: 0.548588991165 
Matplotlib contains_points Elapsed time: 0.103765010834 

matplotlibのはまだはるかに良いですが、ない100倍優れています。今それがある（

Ray Tracing Elapsed time: 0.0727779865265 
Matplotlib contains_points Elapsed time: 0.105288982391 

Answer 3

速度は何が必要ですし、余分な依存関係が問題とされていない場合、あなたは多分numbaは非常に便利： 今度は、はるかに単純な多角形を試してみましょう...

lenpoly = 5 
# ... same code 

結果どのプラットフォームでも簡単にインストールできます）。あなたが提案した古典的なray_tracingのアプローチは、numba @jitデコレータを使用し、多角形をnumpy配列にキャストすることで、numbaに簡単に移植できます。あなたの場合は

CPU times: user 18.7 ms, sys: 320 µs, total: 19.1 ms 
Wall time: 18.4 ms 

：コンパイル後に減少し、

%%time 
polygon=np.array(polygon) 
inside1 = [numba_ray_tracing_method(point[0], point[1], polygon) for 
point in points] 

CPU times: user 129 ms, sys: 4.08 ms, total: 133 ms 
Wall time: 132 ms 

：最初の実行が少し長く後続の呼び出しのいずれかよりもかかります

@jit(nopython=True) 
def ray_tracing(x,y,poly): 
    n = len(poly) 
    inside = False 
    p2x = 0.0 
    p2y = 0.0 
    xints = 0.0 
    p1x,p1y = poly[0] 
    for i in range(n+1): 
     p2x,p2y = poly[i % n] 
     if y > min(p1y,p2y): 
      if y <= max(p1y,p2y): 
       if x <= max(p1x,p2x): 
        if p1y != p2y: 
        xints = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x 
        if p1x == p2x or x <= xints: 
         inside = not inside 
     p1x,p1y = p2x,p2y 

    return inside 

：コードは次のようになります。関数の最初の呼び出しでスピードが必要な場合は、pyccを使用してモジュール内のコードをあらかじめコンパイルすることができます。 python src.pyとそれをビルドして実行

from numba import jit 
from numba.pycc import CC 
cc = CC('nbspatial') 


@cc.export('ray_tracing', 'b1(f8, f8, f8[:,:])') 
@jit(nopython=True) 
def ray_tracing(x,y,poly): 
    n = len(poly) 
    inside = False 
    p2x = 0.0 
    p2y = 0.0 
    xints = 0.0 
    p1x,p1y = poly[0] 
    for i in range(n+1): 
     p2x,p2y = poly[i % n] 
     if y > min(p1y,p2y): 
      if y <= max(p1y,p2y): 
       if x <= max(p1x,p2x): 
        if p1y != p2y: 
         xints = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x 
        if p1x == p2x or x <= xints: 
         inside = not inside 
     p1x,p1y = p2x,p2y 

    return inside 


if __name__ == "__main__": 
    cc.compile() 

：

私が使用しnumbaコードで

import nbspatial 

import numpy as np 
lenpoly = 100 
polygon = [[np.sin(x)+0.5,np.cos(x)+0.5] for x in 
np.linspace(0,2*np.pi,lenpoly)[:-1]] 

# random points set of points to test 
N = 10000 
# making a list instead of a generator to help debug 
points = zip(np.random.random(N),np.random.random(N)) 

polygon = np.array(polygon) 

%%time 
result = [nbspatial.ray_tracing(point[0], point[1], polygon) for point in points] 

CPU times: user 20.7 ms, sys: 64 µs, total: 20.8 ms 
Wall time: 19.9 ms 

：ようsrc.pyに機能を保存 「はB1（F8、F8、F8の[:, ：]） '

nopython=Trueでコンパイルするには、各varをfor loopの前に宣言する必要があります。事前に作成さSRCコードで

ライン：

@cc.export('ray_tracing', 'b1(f8, f8, f8[:,:])') 

は、関数名とそのI/OのVAR型、ブール出力を宣言するために使用されb1二フロートf8とフロートの二次元アレイ入力としてf8[:,:]。