指定边界内土地分配多边形生成算法技术问询

核心需求回顾 #

• 待分配区域：由GeoJSON多多边形定义
• 分配要求：每个账户对应指定面积（1-数千㎡），面积误差≤1%
• 形状要求：优先凸多边形，整体类Voronoi形态，边界区域可接受凹多边形
• 动态性：支持分配调整，调整后区域尽量保持稳定，可生成时序变化图
• 性能要求：支持数万级分配量，单条调整/生成响应<500ms，需为P时间可解

现有方案的问题分析 #

• Turf.js暴力随机法：形状合规性差（易出现不规则凹多边形）、无法保证无重叠、边界处理混乱，且逐次移除的方式效率极低，无法支撑数万级分配
• D3 Voronoi种子法：原生Voronoi仅基于种子点位置生成区域，无法直接匹配指定面积，手动调整种子点的复杂度极高，难以满足精度和效率要求

可行算法与实现思路 #

1. 带面积约束的加权Voronoi图（Weighted Voronoi Diagram，WVD） #

基于加权Voronoi图（也叫Power Diagram），每个种子点的权重与目标面积直接关联：

• 将每个账户的目标面积转换为种子点的权重（权重与面积正相关，具体映射关系可通过区域总面积与所有权重和的比例校准）
• 生成Power Diagram后，计算每个区域的实际面积，通过迭代微调种子点的权重或位置，将面积误差控制在1%以内
• 优势：天然具备类Voronoi的凸多边形形态，边界区域会自动适配原边界生成合理形状，且生成过程可批量处理，效率远高于暴力法

2. 网格化预分配+局部优化 #

如果对Voronoi形态的要求不是绝对严格，可采用此方法：

• 将待分配区域预划分为均匀网格（网格大小取最小分配面积的1/10~1/5，平衡精度和效率）
• 按照每个账户的目标面积，为其分配对应数量的网格，优先保证区域的连通性和凸性
• 对初始分配的网格集合进行边界平滑处理，生成符合要求的多边形，同时校准面积至误差范围内
• 动态调整时，仅在调整账户的相邻区域进行网格重分配，保证整体区域的稳定性，调整效率更高

3. 约束Delaunay三角剖分+区域合并 #

• 先对待分配区域进行约束Delaunay三角剖分，得到大量小三角形单元
• 根据每个账户的目标面积，将相邻的三角形单元合并，优先选择凸向的组合，形成符合面积要求的多边形
• 合并过程中通过贪心算法保证区域的凸性，边界区域可根据原边界调整合并逻辑
• 动态调整时，仅重新合并调整账户及其相邻区域的三角形单元，响应速度快

性能优化建议 #

• 采用WebAssembly（Wasm）实现核心算法逻辑，替代纯JavaScript，可将运算效率提升5~10倍，满足数万级分配和<500ms响应要求
• 动态调整时，采用局部更新策略，仅修改调整账户及其直接相邻的分配区域，避免全局重计算
• 预计算区域的总面积、边界特征等信息，减少重复计算

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