如何提取两个非重叠多边形之间的间隙为新多边形？

1. 先明确间隙的核心定义 #

布尔裁剪（difference、exclusiveOr）在多边形无相交时确实无效——A - C结果还是A，对称差结果是A+C，都不是你要的间隙。首先要明确：你要的间隙是包含两个多边形的最小闭合区域减去A、C本身，还是两个多边形之间的连通通道区域？两种场景对应不同解法：

2. 通用基础方案（凸包差集法） #

如果间隙是“包裹A、C的最小区域减去两者”，可以这么做：

• 计算两个多边形的联合凸包：凸包是能包裹所有顶点的最小凸多边形，自己实现可以用Andrew算法或Graham扫描，用第三方库（如Boost.Geometry、CGAL）直接调用接口更高效。
• 执行差集操作：用联合凸包作为“母多边形”，依次减去A和C，得到的结果就是凸包内部、A/C外部的间隙区域。

3. 连通间隙的精确识别（平面分区法） #

如果间隙是两个多边形之间的连通通道（比如A、C都在一个更大的封闭区域内，间隙是它们之间的狭窄空间）：

• 确定外部边界：比如画布的矩形边界，或者包含A、C的封闭区域多边形。
• 平面分区：将外部边界、A、C作为输入，用平面扫描算法把整个区域分割成多个连通面。第三方库（如CGAL的Polygon Partitioning模块）能直接完成这一步。
• 筛选间隙区域：遍历所有分区后的区域，判断是否满足「不在A/C内部，且边界同时接触A和C」，符合条件的就是目标间隙。

4. 第三方库快捷实现示例（Boost.Geometry） #

不想自己写算法的话，用成熟几何库能快速落地：

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/multi_polygon.hpp>

namespace bg = boost::geometry;
typedef bg::model::polygon<bg::model::d2::point_xy<double>> Polygon;
typedef bg::model::multi_polygon<Polygon> MultiPolygon;

int main() {
    Polygon A, C;
    // 初始化A、C的顶点（需确保多边形闭合、无自相交）

    MultiPolygon ac_mp;
    ac_mp.push_back(A);
    ac_mp.push_back(C);

    // 计算A和C的联合凸包
    Polygon convex_hull;
    bg::convex_hull(ac_mp, convex_hull);

    // 凸包减去A和C，得到间隙
    MultiPolygon gap;
    bg::difference(convex_hull, ac_mp, gap);

    // 处理gap结果
    return 0;
}

5. 关键注意事项 #

• 确保所有多边形是**闭合、简单（无自相交）**的，否则几何库操作会报错。
• 处理浮点数精度问题：用epsilon阈值比较顶点坐标，避免因精度误差导致的判断错误。
• 如果间隙是多个不连通区域，需逐个判断是否符合你的间隙定义。

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