C++中分割Boost Polygon为子区域并获取各区域随机点的方法

基础场景复现 #

你给出的Boost Polygon创建示例代码如下：

Polygon2D create_polygon(Point2D const& p1, Point2D const& p2, Point2D const& p3, Point2D const& p4) {
    return {{p1, p2, p3, p4, p1}};
}

int main() {
    auto const& polygon = create_polygon({0., 0.}, {0., 4.}, {7., 4.}, {7., 0.});
    return 0;
}

上述是规则矩形的简化示例，实际场景中多边形多为不规则形态，切分后的子区域不需要强制为正方形。

Boost 库相关能力说明 #

Boost 没有提供开箱即用的任意多边形等面积切分专用工具：

• Boost.Polygon 自带的Voronoi模块核心用于生成点/线段集的泰森多边形，输出单元面积完全受输入种子点分布控制，无法直接保证子区域面积均等，确实不符合你的需求。
• 你可以组合Boost.Geometry的基础接口自行实现切分逻辑，全程不会修改原始多边形结构：
  • 调用boost::geometry::area计算原始多边形总面积，结合你需要的子区域大小确定切分阈值
  • 借助扫描线切割、多边形求交接口实现逐段切分
  • 切分完成后用boost::geometry::within做包含判定，支撑后续子区域随机点采样逻辑。

通用成熟实现算法 #

不依赖Boost的情况下，以下三种算法都能满足你提出的无需固定子区域数量、子区域面积尽量均等的要求，都是工业界落地验证过的方案：

• 梯形分解重组法
  首先通过水平/垂直扫描线对多边形做梯形分解，将所有分解得到的梯形按空间顺序累加面积，每累加值达到单个子区域的目标面积就执行一次切分，最后将同属一个子区域的相邻小梯形合并为完整子多边形。该方案实现难度低，对所有简单多边形（含凹多边形）兼容，面积误差可控制在1%以内，仅需要传入目标子区域面积阈值即可自动适配不同尺寸、形态的多边形，不需要提前固定切分数量。
• 重心Voronoi优化法（CVT）
  普通Voronoi切分面积不均的问题根源是初始种子点随机分布，你可以配合Lloyd迭代优化种子点位置：每次迭代计算当前所有Voronoi单元的重心，将种子点移动到对应重心位置，重复3-10次后生成的Voronoi单元面积就会非常均匀。该方案生成的子区域形状更规整自然，适合对区域视觉效果有要求的场景，缺点是实现复杂度高于梯形分解，迭代过程有一定计算开销。
• 递归二分法
  针对当前待切分多边形，选择合适的切割方向将其切为面积相等的两部分，再对生成的两个子多边形重复执行二分操作，直到所有子区域面积达到预设阈值。该方案逻辑最简单、代码量最少，切分得到的子区域面积可以做到严格均等，缺点是切割方向选择不当容易生成狭长子块。

采样优化提示 #

完成子区域切分后，不建议直接在子多边形的外接矩形内生成随机点再做包含判定，狭长多边形场景下采样效率会极低。更高效的方案是先对每个子多边形做三角剖分，采样时先按三角形面积加权选中目标三角形，再在三角形内部生成均匀随机点，采样效率会有数量级提升。如果你的最终目标只是在整个多边形内生成均匀分布的随机点，甚至不需要提前做多边形切分，直接用三角剖分加权采样或者网格拒绝采样即可实现，逻辑更简洁。

内容的提问来源于stack exchange，提问作者Konat Undoshy