[解決済み] Python である点がポリゴンの中にあるかどうかをチェックする最も速い方法は何ですか？

質問

ある点がポリゴンの内部に属しているかどうかを調べるには、主に2つの方法があります。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 = np.random.rand(N,2)


# 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辺の多角形の代わりに三角形を使っても、同じ相対的な差が得られました。shapelyはこの手の問題に特化したパッケージのようなので、こちらも確認してみます。

どのように解決するのか？

あなたは 形よく :

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

紹介された方法のうち、私は2番目しか使ったことがありません。 path.contains_points を使いましたが、うまくいきました。いずれにせよ、テストに必要な精度によっては、ポリゴン内のすべてのノードをTrue（そうでない場合はFalse）にするnumpyのboolグリッドを作成することをお勧めします。もしあなたが多くの点に対してテストを作ろうとしているなら、この方が速いかもしれません ( しかし、これはあなたが許容誤差quot;pixel"内でテストを作っていることに注意してください。 ):

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

のように、結果はこうなります。