2D平面同色多边形聚合为所属区域的划分算法求解

适配需求的两类可行算法 #

你可以根据最终需要的输出形态选择对应方案： #

方案1：仅生成同色多边形的合并包围区域（对应示例2效果） #

该方案实现最简单，适合不需要划分无主空白区域的场景：

1. 按颜色分组：把所有输入的多边形先按颜色归类到不同的集合中
2. 同色多边形合并：对每个颜色的多边形集合，执行多边形联合（Union）操作，直接得到覆盖该颜色所有多边形的连续区域。如果同色多边形互不连通，最终结果会是一个多部件多边形（MultiPolygon），刚好能完整包含所有同色多边形
3. 可选优化：如果需要去掉多余的空白凹进，可以对联合结果做缓冲（Buffer）操作，先向内缩小再向外放大相同距离，平滑边界的同时不会改变对原有多边形的包含性

该方案在各类GIS工具、Shapely等几何处理库中都有现成API可以直接调用，Python实现的参考代码如下：

from shapely.ops import unary_union

# color_polygons为对应颜色的所有输入多边形列表
color_region = unary_union(color_polygons)
# 平滑边界的可选操作，数值根据实际精度需求调整
smooth_region = color_region.buffer(5).buffer(-5)

方案2：全平面区域划分（对应示例1效果） #

如果需要把整个平面划分成不同颜色的对应区域，和你联想到的Voronoi图思路一致，用多边形Voronoi图即可实现：

1. 预处理输入：先按颜色给所有多边形打标签
2. 生成多边形Voronoi图：和点Voronoi的逻辑类似，多边形Voronoi图会把平面划分成多个胞元，每个胞元内的所有点到对应输入多边形的距离小于到其他任何输入多边形的距离
3. 按颜色合并胞元：把所有属于同色多边形的Voronoi胞元做联合操作，得到的就是对应颜色的全平面划分区域
4. 边界修正：如果要求所有生成区域刚好和原有多边形边界重合，可以把生成的区域和对应颜色的原有多边形做联合，再和其他颜色的原有多边形做差，消除边界偏移

该方案的现成实现可以参考CGAL库的Polygon Voronoi Diagram模块，或者Python的vpyvoronoi扩展，完全可以覆盖你提到的共边、零散分布等边缘场景。

实际场景适配建议 #

针对你提到的行政区划分场景，优先选择方案1即可，只需要把对应归属的街区多边形合并，再根据需要做边界平滑，完全符合政务场景的使用需求。如果需要处理行政区之间的无主空白地带，再切换到方案2做全平面划分。

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