KACTL 算法笔记

045-几何-多边形并

8 min read

核心概述：对 n 个（不必凸）多边形计算几何并集的面积，输入顶点按逆时针给出，整体期望 O(N²) 处理所有边的覆盖贡献。

Description: Calculates the area of the union of polygons (not necessarily convex). The points within each polygon must be given in CCW order. Time: , where is the total number of points Status: stress-tested, Submitted on ECNA 2017 Problem A

展开阐述

  • 定义与背景
    • 问题：给定多组简单多边形 {P₁,…,P_k}（每个顶点序 ccw），求其并域的面积 |⋃P_i|。
    • 能力边界：支持凹多边形与跨多边形的边相交；每个输入多边形应为简单多边形（无自交），顶点逆时针以保证符号一致。
    • 典型场景：多障碍覆盖、平面分区并域统计、复杂几何布尔运算中的面积度量。
  • 接口/数据结构（据实现）
    • 函数签名：double polyUnion(vector<vector

      >& poly)，P = Point。

    • 语义：返回所有多边形的并集面积（double）。
    • 预期输入：每个多边形为顶点循环序列（不重复首点），方向 ccw。
  • 核心流程/要点（逐边参数化 + 区间覆盖）
    1. 边遍历：对每个多边形的每条边 A→B，建立其参数化表示 E(t)=A + (B−A)·t，t∈[0,1]。
    2. 收集事件点（交点与覆盖端点）：
      • 与其他所有边 C→D 求相交；若与 E 相交于 E(t*)，将 t* 作为候选事件插入。
      • 端点覆盖测试：用 sideOf/有向面积判断 E(t) 的微小两侧是“在其他多边形内部/外部”，将“进入/离开并域”的参数作为区间端点。
      • 共线重叠：当 E 与 C→D 共线且方向一致时，将重叠段的 t 区间端点加入；若反向但共线，同样按区间并处理（端点去重与排序靠统一的参数化）。
    3. 区间合并与可见长度：
      • 将所有 t 事件去重并排序，扫描相邻小段 [t_i, t_{i+1}] 的代表点 E( (t_i+t_{i+1})/2 ) 是否处于“未被其他多边形覆盖之外”的区域。
      • 把“可见”的片段长度 Δt_i 累加为当前边的可见比例 sum = Σ Δt_i。
    4. 边贡献累加：
      • 本边对面积的贡献是 A.cross(B) · sum；几何直觉为“鞋带公式项 × 在并域边界上实际保留下来的比例”。
      • 对所有边求和，最终总面积为 ret/2。
    5. 返回 ret/2，得到并域面积。
  • 复杂度与边界条件
    • 时间复杂度：对每条边与所有其他边比较，整体 O(N²)；其中交点与区间操作为线性对数或线性常数，但被 N² 主导。
    • 边界与退化：
      • 不相交多边形：互不影响，各自的边段全部可见，和为面积之和。
      • 完全包含：小多边形被大多边形覆盖，其边段可见比例为 0，仅保留外边界贡献。
      • 顶点接触/相切：交点参数 t* 可能重复；排序时需以 eps 去重，避免产生长度为 0 的伪区间。
      • 共线重叠边：需按参数区间合并；方向一致/相反都应正确累计覆盖，避免重复加面积。
      • 自交输入：实现假设简单多边形；若自交，其“内部”定义不唯一，结果未定义。
    • 数值与精度：
      • 使用 double 累计，统一 eps 判断“相交/共线/端点相等”；坐标量级过大时可考虑 long double。
      • 区间裁剪时对 t ∈ [0,1] 做上下夹，避免数值超界。
  • 变体/扩展
    • 仅多边形交/差面积：可采用相同“边参数化+区间可见性”思想，将“覆盖判定”从 Union 改为 Intersection 或 Difference 的判真表。
    • 凸多边形特化：两个凸多边形的并/交可用更快的合并或裁剪；但普遍多边形仍建议使用此 O(N²) 框架。
    • 输出并域轮廓：在记录区间的同时保留“可见段”的实际坐标，可重建并域边界折线用于可视化或后续计算。
    • 带洞与多环：输入多边形自身可包含洞时，需以“外环正、内环负”的环结构处理；若预先三角化，也可改为“可见三角片面积求和”。
  • 正确性要点与不变式
    • 鞋带一致性：总和形式 ret = Σ A.cross(B)·visible_fraction，等价于将边对总有向面积的贡献按“留在外部边界”的比例加权。
    • 覆盖判定局部化：仅需判断边上参数小区间的代表点是否属于“并域边界外侧”，从而避免全局拓扑构造。
    • 事件完备性：所有交点、进入/离开覆盖的端点都会体现在参数 t 事件序列中，保证不漏计可见段。
  • 与相邻技术的对比与取舍
    • 与扫描线平行坐标系（x 扫或 y 扫）对比：本法在边参数空间做一维覆盖，避免复杂的区段树/主动边维护，更贴合 KACTL 的“短小可复用”风格。
    • 与通用布尔库（如半边结构）对比：通用库能直接输出边界拓扑，但实现重量级；本法仅需面积时更简洁。
    • 与042-几何-多边形面积：并域面积本质是对“可见边”的鞋带累加；单个多边形的面积则不涉及覆盖筛除。
    • 与044-几何-多边形切割：切割是“多边形 ∩ 半平面”的特例；并域可视作对每条边按“被其他多边形覆盖”进行裁剪的全局版本。

关联节点

Graph View

Backlinks