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

问题描述

我在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)])

---

解决方案

我看到您回答了问题(似乎对使用交集很满意)，但也注意到shapely(以及底层的geos库)已经准备了几何，以便在某些谓词(CONTAINS、CONTAINS_PROGRECT、COVERS和INTERSETS)上进行更高效的批处理操作。 请参见Prepared geometry operations。

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

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