点がポリゴン内に存在するかどうかを確認する主な方法は2つあります。1つはレイトレーシング法を使用する方法です。ここ、これは最も推奨される回答ですが、もう 1 つは matplotlib を使用することですpath.contains_points(これは少しわかりにくいようです)。私は継続的に多くの点を確認する必要があります。これらの 2 つのうちのどちらかが他方よりも推奨されるか、またはさらに優れた 3 番目のオプションがあるかどうかを知っている人はいますか?
アップデート：
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もチェックします。これはこの種の問題に特化したパッケージのようです。
ベストアンサー1
検討してみてください形の良い:
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グリッドを作成することをお勧めします。多くのポイントに対してテストを行う場合は、これがより高速になる可能性があります（ただし、これは「ピクセル」の許容範囲内でテストを行っていることに依存します。):
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()
結果は次のようになります:
