寻求无重叠多Polygon偏移算法及重叠区域合理分配方案

核心需求 #

给定一组互不相交、不自相交的多边形，生成满足以下要求的向外偏移区域：

• 偏移区域不得与原多边形自身区域重叠
• 多个多边形的偏移区域出现重叠时，按类似示例图的“就近归属”策略分配重叠部分

实现步骤 #

1. 生成单个多边形的初始偏移区域 #

先对每个多边形执行向外偏移（缓冲）操作，用已有的单多边形偏移算法即可。完成偏移后，必须将原多边形区域从偏移结果中剔除，确保偏移区域和原多边形无重叠。

2. 重叠区域的分配处理 #

针对多个偏移区域的重叠部分，采用「距离优先归属」策略（和示例图逻辑匹配）：

• 基于所有原多边形生成Voronoi图，Voronoi图的边界就是不同多边形的“势力范围”分界线，越靠近某个原多边形的区域，归属该多边形
• 将每个初始偏移区域与对应的Voronoi区域做交集运算，最终得到的区域就是该多边形的最终偏移结果——重叠部分会被Voronoi边界分割，自动归属到距离最近的原多边形对应的偏移区域

实用工具库 #

• Python环境：使用shapely库，它支持多边形缓冲（buffer()）、差集（difference()）、交集（intersection()）等核心运算，搭配scipy的Voronoi生成工具就能快速实现上述逻辑
• C++环境：使用CGAL库，该库提供成熟的多边形偏移、布尔运算及Voronoi图生成模块，适合高性能场景

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