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

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

我能想到的最好办法是：

X,Y = np.meshgrid(np.arange(latmin, latmax, resolution),
              np.arange(lonmin, lonmax, resolution))

#create a iterable with the (x,y) coordinates
points = zip(X.flatten(),Y.flatten())

valid_points.extend([i for i in points if polygon.contains(i)])

Answer 2

我看到您回答了您的问题（并且似乎对使用交集很满意），但也注意到shapely（以及底层的geos库）已经准备了几何体，以便对某些谓词（包含、正确地包含、覆盖和交集）进行更有效的批处理操作。 见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))

Answer 3

哦，为什么？是的。使用shapely的相交方法

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

# construct rectangle of points
x, y = np.round(np.meshgrid(np.arange(latmin, latmax, resolution), np.arange(lonmin, lonmax, resolution)),4)
points = MultiPoint(list(zip(x.flatten(),y.flatten())))

# validate each point falls inside shapes
valid_points.extend(list(points.intersection(polygon)))