KACTL 算法笔记

044-几何-多边形切割

7 min read

核心概述：用有向直线 s→e 对多边形进行一次半平面裁剪，保留直线左侧（含/不含边界按实现约定），线性时间返回裁剪后的多边形顶点序列。

Returns a vector with the vertices of a polygon with everything to the left of the line going from s to e cut away. Usage: vector

p = …; p = polygonCut(p, P(0,0), P(1,0)); Status: tested but not extensively

展开阐述

  • 定义与背景
    • 半平面与方向：有向直线由两点 (s, e) 定义，定义“左侧”为满足 cross(e−s, x−s) ≤ 0（或 ≥0，取决于实现的左正/右正约定）的点集。本实现语义为“保留左侧”，与049-几何-点在直线哪侧的符号保持一致尤为重要。
    • 任务：给定简单多边形 poly（顶点按顺序给出，默认 ccw），返回与半平面的交多边形。常用于半平面交、视域/可行域裁剪、布尔运算的基础步骤。
    • 能力边界：输入多边形可为凸或非凸；输出为（可能退化的）简单多边形或空集。
  • 接口/数据结构（据实现）
    • 函数签名：vector

      polygonCut(const vector

      & poly, P s, P e)，P = Point。

    • 输入约定：
      • poly：多边形顶点按顺序（通常 ccw）；若为 cw，裁剪后仍得到正确几何，但“左侧”的几何直觉需以实现的符号为准。
      • s,e：定义裁剪直线；要求 s ≠ e。
    • 返回值：裁剪后的多边形顶点序列（闭合由顶点循环隐含，不重复首点）。
  • 核心流程/要点（逐边分类 + 相交点拼接）
    1. 扫描边：对 poly 的每条有向边 (prev, cur)，计算 a = s.cross(e, cur)、b = s.cross(e, prev)。
    2. 交点判定：当 a 与 b 异号（含一端为 0 的情形按实现约定归入异号/同号之一）时，边与直线相交。使用线性插值求交点：
      • t = a / (a − b)（注意分母零判），交点 q = cur + (prev − cur) * t。
    3. 顶点去留：
      • 若 cur 在“左侧”（例如以 a < 0 作为左侧判定；若采用 a ≥ 0，需全局一致），将 cur 追加到结果。
      • 若发生交点，则将交点 q 追加（顺序与参数化一致，避免自交）。
    4. 闭合处理：遍历完所有边即得到裁剪后的顶点序列，无需额外去重；若首末点数值接近可按 eps 合并。
  • 复杂度与边界条件
    • 时间复杂度：O(n)。
    • 退化与边界：
      • 整体在右侧：返回空多边形。
      • 整体在左侧：返回原多边形（仅可能出现与直线共线边的“轻微冗余顶点”）。
      • 共线边：当 a 或 b ≈ 0 时属于边界；通常按“包含边界”的约定保留共线且位于左侧的段。若需严格裁掉边界，可对 |a|,|b| 与 eps 比较调整包含性。
      • 顶点恰落直线：交点与顶点重合，应避免重复插入（可在插入前做与上一个点的距离 eps 合并）。
      • 空/线性退化：裁剪后可能变成线段/点甚至空集；根据下游需要可在结果长度 < 3 时特殊标记。
    • 数值与精度：
      • 浮点：统一 eps 控制“在左侧/在直线上”的阈值；t 的分母 (a−b) 近零时需分支处理（视作无交或整段共线）。
      • 整数：若切换到整数模板且需要交点坐标，将产生分数；建议使用 double/long double 承载交点坐标。
  • 变体/扩展
    • 多次裁剪（半平面交）：对一组半平面重复调用 polygonCut 并级联结果，得到任意凸多边形的交（经典半平面交的多边形版）。
    • 边界包含策略：可提供 strict 参数控制是否将共线段计入结果；例如 strict=false 表示包含边界。
    • 扇形/圆形裁剪：可通过分段近似或与020-几何-圆与直线相交、021-几何-圆与多边形相交组合实现曲线边界的裁剪。
  • 正确性要点与不变式
    • 单调拼接：按边遍历顺序插入交点与保留点，保证结果顶点顺序正确且无自交。
    • 方向一致性：统一采用同一“左侧”定义；交点插入位置以参数化 t 的顺序保证边段顺序不翻转。
    • 保持凸性：若输入凸多边形，任意一次半平面裁剪后仍为凸多边形（或退化为线/点/空），便于后续算法使用。
  • 与相邻技术的对比与取舍
    • 与扫描线布尔（多边形并/交/差）：polygonCut 是“多边形 ∩ 半平面”的特例，实现短小、稳健；通用布尔需更复杂的数据结构（见045-几何-多边形并）。
    • 与033-几何-直线与凸包交：后者做查询（返回交的边索引/类型），本节点执行构造性裁剪。
    • 与029-几何-点在多边形内：点包含常作为布尔/裁剪的子过程；本节点则面向区域构造。

关联节点

Graph View

Backlinks