生成落在多边形或形状内的点网格的最快方法？

Question

我在 python 中使用 shapely 并尝试在网格中生成均匀间隔的点，这些点在最快的 O(n) 时间内落在形状内。形状可以是任何闭合多边形，而不仅仅是正方形或圆形。我目前的做法是：

1. 找到最小/最大 y 和 x 来构建一个矩形。
2. 给定间距参数（分辨率）构建点网格
3. 逐一验证这些点是否落在形状内。

有没有更快的方法来做到这一点？

# determine maximum edges
polygon = shape(geojson['features'][i]['geometry'])
latmin, lonmin, latmax, lonmax = polygon.bounds

# construct a rectangular mesh
points = []
for lat in np.arange(latmin, latmax, resolution):
    for lon in np.arange(lonmin, lonmax, resolution):
        points.append(Point((round(lat,4), round(lon,4))))

# validate if each point falls inside shape
valid_points.extend([i for i in points if polygon.contains(i)])

Answer 1

我看到您回答了您的问题（并且似乎对使用交集感到满意），但也注意到shapely（以及底层geos库）已经准备了几何图形，以便对某些谓词（包含、包含_正确、覆盖和相交）进行更有效的批量操作。请参阅准备的几何操作。

根据您问题中的代码改编，可以这样使用：

from shapely.prepared import prep

# determine maximum edges
polygon = shape(geojson['features'][i]['geometry'])
latmin, lonmin, latmax, lonmax = polygon.bounds

# create prepared polygon
prep_polygon = prep(polygon)

# construct a rectangular mesh
points = []
for lat in np.arange(latmin, latmax, resolution):
    for lon in np.arange(lonmin, lonmax, resolution):
        points.append(Point((round(lat,4), round(lon,4))))

# validate if each point falls inside shape using
# the prepared polygon
valid_points.extend(filter(prep_polygon.contains, points))