在一个多边形或形状内快速生成一个点网格的最快方法是什么？

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

- negfrequency

---

形状总是凸的吗？如果是，你可能只需要检查外部点。 - joostblack

该polygon.contains()函数能够接受numpy数组吗？如果可以，就可以使用numpy.meshgrid创建包含x和y坐标的两个矩阵，这比迭代更快。 - Filipe

np.meshgrid更快，但是shape.contains似乎不能处理numpy数组。你已经加速了我的软件。 - negfrequency

相关问题：获取位于Shapely多边形内部的所有点，提取给定外部坐标的多边形内部点。 - Georgy

shape 函数属于哪个库？ - Chau Loi

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

- mgc

Answer 2

我能想到的最好方法是这样做：

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

- Filipe

Answer 3

哦，当然可以。使用Shapely的交集方法。

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

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

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

- negfrequency

Answer 4

如果您想在一个shapely.geometry.Polygon中生成n个点，有一个简单的迭代函数可以做到。管理tol（容差）参数以加快点的生成速度。

import numpy as np
from shapely.geometry import Point, Polygon


def gen_n_point_in_polygon(self, n_point, polygon, tol = 0.1):
    """
    -----------
    Description
    -----------
    Generate n regular spaced points within a shapely Polygon geometry
    -----------
    Parameters
    -----------
    - n_point (int) : number of points required
    - polygon (shapely.geometry.polygon.Polygon) : Polygon geometry
    - tol (float) : spacing tolerance (Default is 0.1)
    -----------
    Returns
    -----------
    - points (list) : generated point geometries
    -----------
    Examples
    -----------
    >>> geom_pts = gen_n_point_in_polygon(200, polygon)
    >>> points_gs = gpd.GeoSeries(geom_pts)
    >>> points_gs.plot()
    """
    # Get the bounds of the polygon
    minx, miny, maxx, maxy = polygon.bounds    
    # ---- Initialize spacing and point counter
    spacing = polygon.area / n_point
    point_counter = 0
    # Start while loop to find the better spacing according to tolérance increment
    while point_counter <= n_point:
        # --- Generate grid point coordinates
        x = np.arange(np.floor(minx), int(np.ceil(maxx)), spacing)
        y = np.arange(np.floor(miny), int(np.ceil(maxy)), spacing)
        xx, yy = np.meshgrid(x,y)
        # ----
        pts = [Point(X,Y) for X,Y in zip(xx.ravel(),yy.ravel())]
        # ---- Keep only points in polygons
        points = [pt for pt in pts if pt.within(polygon)]
        # ---- Verify number of point generated
        point_counter = len(points)
        spacing -= tol
    # ---- Return
    return points

- Pierre Matran