不规则几何形状内最优布点算法咨询

适用算法推荐 #

针对在不规则几何形状内分配指定数量点（要求点间距离尽可能大、满足边缘最小距离）的需求，以下几种算法是行业内的常用解决方案：

1. 泊松圆盘采样（Poisson Disk Sampling） #

这是最适合此类场景的算法之一，核心特性：

• 保证所有点之间的距离不小于设定的最小阈值
• 点分布均匀，避免局部密集或稀疏
• 天然支持不规则区域约束，可通过向内缓冲区预处理实现边缘最小距离限制（先对原多边形做向内偏移，偏移量为要求的边缘最小距离，再在缓冲后的区域内生成点）
• 高效的实现（如Bridson算法）能快速生成符合要求的点集，即使是极不规则的形状也能适配

2. Lloyd松弛算法（Lloyd's Relaxation） #

如果已经有了初始点集（比如当前的网格采样结果），可以用这个算法迭代优化：

• 基于Voronoi图，每次迭代将每个点移动到其所属Voronoi单元格的重心
• 逐步让点分布更均匀，最大化点间的最小距离
• 可以和泊松采样结合，先用泊松采样生成初始点，再用Lloyd松弛进一步优化分布

3. 最大最小距离采样（Maximin Distance Sampling） #

该算法逻辑是每次选择离所有已有点最远的点，能严格保证点间距离最大化，但计算成本相对较高：

• 初始随机选一个点，之后每次迭代遍历候选区域，找到距离当前所有点最远的点加入集合
• 适合对“点间最大距离”要求极高的场景，但处理大规模点集时效率不如泊松采样

现有代码的问题分析 #

当前的网格+随机补点方案存在以下不足：

• 网格采样依赖外接矩形的均匀划分，无法适配不规则多边形的凹陷、狭长区域，容易出现边缘区域点缺失或分布不均
• 随机补点无法保证点间距离的最大化，会导致局部点密集，不符合需求
• 偏移调整的逻辑仅在网格基础上做简单偏移，未考虑多边形的几何约束

你的现有实现代码：

def _generate_systematic_sample_points(self, shp, plot_area):
    if self.sample_number < 1:
        max_number_of_points = math.ceil((self.sample_number * self.total_area) / plot_area)
    else:
        max_number_of_points = self.sample_number

    grid_number = math.ceil(math.sqrt(max_number_of_points))

    extent = shp.extent()
    x_min, y_min, x_max, y_max = extent.xMinimum(), extent.yMinimum(), extent.xMaximum(), extent.yMaximum()

    if not (np.isfinite(x_min) and np.isfinite(y_min) and np.isfinite(x_max) and np.isfinite(y_max)):
        QgsMessageLog.logMessage("Layer extent contains infinite or NaN values.", 'Your Plugin Name', Qgis.Critical)
        return None

    if x_min >= x_max or y_min >= y_max:
        QgsMessageLog.logMessage("Invalid range of x or y values.", 'Your Plugin Name', Qgis.Critical)
        return None

    side_length = math.sqrt(plot_area)
    x_spacing = (x_max - x_min) / grid_number
    y_spacing = (y_max - y_min) / grid_number

    valid_points = []
    offset = 0

    while len(valid_points) < max_number_of_points and offset < side_length:
        for i in range(grid_number):
            for j in range(grid_number):
                x = x_min + j * x_spacing + offset
                y = y_min + i * y_spacing + offset

                if x > x_max or y > y_max:
                    continue

                square_centroid = QgsPointXY(x + side_length / 2, y + side_length / 2)

                point = QgsGeometry.fromPointXY(square_centroid)
                if self._check_point_within_polygons(point, shp) and self._check_points_distance(point, plot_area,
                                                                                                 valid_points):
                    valid_points.append(point)
                    if len(valid_points) >= max_number_of_points:
                        break
            if len(valid_points) >= max_number_of_points:
                break
        offset += side_length / 2

    if len(valid_points) < max_number_of_points:
        remaining_points = max_number_of_points - len(valid_points)
        attempts = 0
        max_attempts = 3000
        while remaining_points > 0 and attempts < max_attempts:
            x = np.random.uniform(x_min, x_max)
            y = np.random.uniform(y_min, y_max)
            point = QgsGeometry.fromPointXY(QgsPointXY(x, y))
            if self._check_point_within_polygons(point, shp) and self._check_points_distance(point, plot_area,
                                                                                             valid_points):
                valid_points.append(point)
                remaining_points -= 1
            attempts += 1

    if len(valid_points) < max_number_of_points:
        QMessageBox.warning(self.dlg, "Warning!",
                            "Unable to generate plots with the established criteria. Only the possible plots were generated.")

    if valid_points:
        point_layer = self.create_point_layer(valid_points, shp.crs())
        return point_layer
    else:
        QgsMessageLog.logMessage("Could not generate plots with the established criteria.", 'Your Plugin Name',
                                 Qgis.Critical)
        return None

优化建议 #

1. 替换核心采样逻辑：用泊松圆盘采样替代网格+随机补点，先对原多边形做向内缓冲区处理（偏移量为边缘最小距离），再在缓冲区域内生成满足点间最小距离的点集
2. 补充优化步骤：如果生成的点数量不足或分布仍有瑕疵，可结合Lloyd松弛算法做迭代调整
3. 适配QGIS环境：可以利用QGIS的QgsGeometry.buffer()实现边缘距离约束，结合第三方库（如scipy或专用采样库）实现泊松采样逻辑，或自行实现Bridson算法的简化版本

内容的提问来源于stack exchange，提问作者Vinicius.rich