沃梦达 / 编程问答 / Python问题 / 正文

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

沃梦达教程 Python问题

2022-01-01 8

Fastest way to produce a grid of points that fall within a polygon or shape?(以最快的方式生成落在多边形或形状内的点网格？)

本文介绍了以最快的方式生成落在多边形或形状内的点网格？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我在Python中使用Shapely，并试图在最快的O(N)时间内在网格中生成落入形状内的等间距的点。形状可以是任何闭合多边形，而不仅仅是正方形或圆形。我目前的做法是：

查找最小/最大y&；x以生成矩形。
在给定间距参数(分辨率)的情况下构建点网格
逐个验证点是否落在形状内。

是否有更快的方法来完成此操作？

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