12.1 排列与计算几何

排列（Arrangement）与 Nef多面体都支持布尔集合运算，而排列的基础概念与多边形密切相关。本章深入探讨排列的数学基础、核心算法和高级应用。

排列（Arrangement）是计算几何中的核心数据结构，用于表示平面上几何对象（如线段、曲线）的细分结构。本章深入探讨排列的数学基础、核心算法（如Bentley-Ottmann扫描线算法）、布尔集合运算、闵可夫斯基和以及直骨架等高级主题。这些技术在计算机图形学、机器人运动规划、CAD/CAM系统和地理信息系统等领域有广泛应用。

12.1.1 Arrangement数据结构

DCEL（Doubly Connected Edge List）详解

DCEL是表示平面细分（planar subdivision）的标准数据结构。它将平面划分为顶点、边和面三个基本元素，并通过精心设计的指针结构维护它们之间的拓扑关系。

DCEL的核心组件：

顶点（Vertex）:
  - 坐标信息 (x, y)
  - 指向一条关联半边（incident halfedge）的指针

半边（Halfedge）:
  - 指向起点顶点的指针
  - 指向孪生半边（twin）的指针
  - 指向下一条半边（next）的指针
  - 指向上一条半边（previous）的指针
  - 指向关联面的指针

面（Face）:
  - 指向外部边界（outer CCB）的指针
  - 指向孔洞列表（holes）的指针
  - 指向孤立顶点的指针

DCEL拓扑结构示意图：

                    v2
                   /|\
                  / | \
                 /  |  \
                /   |   \
               /  f1|f2  \
              /     |     \
             /______|______\
            v0      v1      v3

半边关系:
  e0: v0 -> v1 (twin: e0', face: f1)
  e1: v1 -> v2 (twin: e1', face: f1)
  e2: v2 -> v0 (twin: e2', face: f1)
  e0': v1 -> v0 (twin: e0, face: f2)
  e1': v2 -> v1 (twin: e1, face: f2)
  e2': v0 -> v2 (twin: e2, face: f2)

DCEL的数学性质：

对于任何有效的平面细分，DCEL满足欧拉公式：

$V - E + F = 1 + C$

其中 $V$ 是顶点数， $E$ 是边数， $F$ 是面数（包括无界面）， $C$ 是连通分量数。

对于连通的平面细分（ $C = 1$ ）：

$V - E + F = 2$

顶点、边、面的拓扑关系

顶点的分类：

孤立顶点（Isolated Vertex）：不与任何边关联，位于某个面的内部
边界顶点（Boundary Vertex）：位于面的边界上，度（degree）至少为1
内部顶点（Interior Vertex）：完全位于某个面的内部

顶点的度（Degree）：

顶点的度等于与其关联的半边数量。对于简单多边形，所有顶点的度为2；对于排列，顶点的度可以是任意偶数（因为每条边贡献两个半边）。

// 获取顶点的度
template<typename Arrangement>
size_t vertex_degree(typename Arrangement::Vertex_const_handle v) {
    return v->degree();
}

面的边界表示：

每个面通过**连通分量边界（Connected Component of Boundary, CCB）**来描述其边界：

外部边界（Outer CCB）：面的外边界，逆时针方向
孔洞（Holes）：面内部的孔洞边界，顺时针方向
孤立顶点：位于面内部的孤立点

面F的结构:
+---------------------------+
|  外部边界 (逆时针)         |
|  +---------------------+  |
|  |  孔洞1 (顺时针)     |  |
|  |  +---+              |  |
|  |  |   |              |  |
|  |  +---+              |  |
|  |                     |  |
|  |  孔洞2 (顺时针)     |  |
|  |     +--+            |  |
|  |     |  |            |  |
|  |     +--+            |  |
|  +---------------------+  |
|                           |
|  * 孤立顶点               |
+---------------------------+

组合嵌入的概念

**组合嵌入（Combinatorial Embedding）**是指平面图的拓扑结构，不考虑具体的几何形状，只关注顶点、边和面的连接关系。

关键概念：

旋转系统（Rotation System）：对于每个顶点，定义与其关联的边的循环顺序
面迹（Face Walk）：沿边的特定遍历顺序定义面
拓扑等价：两个嵌入如果具有相同的旋转系统，则称为拓扑等价

排列的组合嵌入：

给定一组曲线，其排列的组合嵌入由以下信息完全确定：

所有交点（顶点）
每个顶点处曲线的循环顺序
每条曲线段（边）连接的两个顶点

示例：两条相交线段

    A-------B
      \   /
       \ /
        X      <-- 交点
       / \
      /   \
    C-------D

组合嵌入信息:
- 顶点: A, B, C, D, X
- 顶点X处的循环顺序: (XA, XC, XB, XD) 或 (XA, XD, XB, XC)
- 边: (A,X), (X,B), (C,X), (X,D)
- 面: 4个有界面 + 1个无界面

12.1.2 Bentley-Ottmann扫描线算法

算法原理

Bentley-Ottmann算法是计算线段排列（即求所有线段交点）的经典算法，时间复杂度为 $O ((n + k) lo g n)$ ，其中 $n$ 是线段数， $k$ 是交点数。

核心思想：

使用一条垂直扫描线从左向右扫过平面，维护扫描线与线段集合的交点顺序。当扫描线遇到特定事件（站点事件或交点事件）时，更新数据结构并检测新的交点。

扫描线过程可视化：

时间 t0:                    时间 t1:
    |                           |
    |    s1                     |    s1
    |   /                       |   / \
    |  /                        |  /   \
    | /   s2                    | /  X  s2  <-- 发现交点
    |/    |                     |/  /   |
    +------------>               +--/----->
                                  /
                                 s3

事件队列处理顺序:
1. 线段s1左端点 (站点事件)
2. 线段s2左端点 (站点事件)
3. 线段s3左端点 (站点事件)
4. s1与s2交点 (交点事件)
5. 线段s3右端点 (站点事件)
6. 线段s1右端点 (站点事件)
7. 线段s2右端点 (站点事件)

事件处理

事件类型：

站点事件（Site Event）：扫描线遇到线段的左端点或右端点
交点事件（Intersection Event）：扫描线遇到两个线段的交点

站点事件处理（左端点）：

算法: 处理左端点事件
输入: 线段s，扫描线状态T，事件队列Q

1. 将s插入扫描线状态T，保持y坐标顺序
2. 令s_above = T中s上方的线段
3. 令s_below = T中s下方的线段
4. 如果s与s_above相交，将交点加入Q
5. 如果s与s_below相交，将交点加入Q

站点事件处理（右端点）：

算法: 处理右端点事件
输入: 线段s，扫描线状态T，事件队列Q

1. 令s_above = T中s上方的线段
2. 令s_below = T中s下方的线段
3. 从T中删除s
4. 如果s_above与s_below相交，将交点加入Q

交点事件处理：

算法: 处理交点事件
输入: 交点p，涉及线段s1和s2，扫描线状态T，事件队列Q

1. 在T中交换s1和s2的位置
2. 令s_new_above = T中s1上方的线段
3. 令s_new_below = T中s2下方的线段
4. 如果s1与s_new_above相交，将交点加入Q
5. 如果s2与s_new_below相交，将交点加入Q
6. 输出交点p

扫描线状态维护：

扫描线状态使用平衡二叉搜索树（如std::set）维护，按线段与扫描线交点的y坐标排序。关键操作：

// 扫描线状态的比较器
struct SweepLineCompare {
    double sweep_x;  // 当前扫描线x坐标
    
    bool operator()(const Segment* s1, const Segment* s2) const {
        double y1 = s1->y_at_x(sweep_x);
        double y2 = s2->y_at_x(sweep_x);
        return y1 < y2;
    }
};

CGAL实现细节

CGAL的Arrangement_2类使用改进的Bentley-Ottmann算法构建排列。以下是核心实现示例：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Arr_non_caching_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <vector>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Arr_non_caching_segment_traits_2<Kernel> Traits;
typedef Traits::Point_2 Point;
typedef Traits::X_monotone_curve_2 Segment;
typedef CGAL::Arrangement_2<Traits> Arrangement;
 
// 批量插入线段构建排列
void construct_arrangement(std::vector<Segment>& segments) {
    Arrangement arr;
    
    // 使用扫描线算法批量插入
    CGAL::insert(arr, segments.begin(), segments.end());
    
    std::cout << "排列统计:" << std::endl;
    std::cout << "  顶点数: " << arr.number_of_vertices() << std::endl;
    std::cout << "  边数: " << arr.number_of_edges() << std::endl;
    std::cout << "  面数: " << arr.number_of_faces() << std::endl;
}

复杂度分析：

操作	时间复杂度	空间复杂度
构建排列	$O ((n + k) lo g n)$	$O (n + k)$
单条曲线插入	$O ((n + k) lo g n)$	$O (n + k)$
点定位	$O (lo g n)$ 到 $O (n)$	$O (n)$
遍历所有顶点	$O (n + k)$	$O (1)$

其中 $n$ 是曲线数， $k$ 是交点数。

12.1.3 布尔集合运算

2D布尔运算

布尔集合运算对两个或多个多边形执行集合操作：并（Union）、交（Intersection）、差（Difference）和对称差（Symmetric Difference）。

布尔运算定义：

给定两个多边形 $P$ 和 $Q$ ：

并（Join/Union）： $P \cup Q = {x ∣ x \in P 或 x \in Q}$
交（Intersection）： $P \cap Q = {x ∣ x \in P 且 x \in Q}$
差（Difference）： $P ∖ Q = {x ∣ x \in P 且 x \in / Q}$
对称差： $P △ Q = (P ∖ Q) \cup (Q ∖ P)$

布尔运算可视化：

输入多边形:                    并运算结果:
+-------+                      +-------+
| P     |                      |       |
|   +---+---+                  |       +---+
|   | Q |   |      -->         |           |
+---+---+   |                  +-----------+
        |   |
        +---+

交运算结果:                    差运算结果:
    +---+                          +-------+
    |   |                          | P     |
    |   |                          |   +---+
    +---+                          +---+

对称差结果:
+-------+
|       |
|   +---+---+
+---+       |
    |       |
    +-------+

CGAL布尔运算实现：

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <list>
 
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef CGAL::Polygon_2<Kernel> Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes_2;
 
// 执行布尔并运算
bool compute_union(const Polygon_2& P, const Polygon_2& Q, 
                   Polygon_with_holes_2& result) {
    return CGAL::join(P, Q, result);
}
 
// 执行布尔交运算
void compute_intersection(const Polygon_2& P, const Polygon_2& Q,
                          std::list<Polygon_with_holes_2>& result) {
    CGAL::intersection(P, Q, std::back_inserter(result));
}
 
// 执行布尔差运算
void compute_difference(const Polygon_2& P, const Polygon_2& Q,
                        std::list<Polygon_with_holes_2>& result) {
    CGAL::difference(P, Q, std::back_inserter(result));
}
 
// 执行对称差运算
void compute_symmetric_difference(const Polygon_2& P, const Polygon_2& Q,
                                  std::list<Polygon_with_holes_2>& result) {
    CGAL::symmetric_difference(P, Q, std::back_inserter(result));
}

完整示例：

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <list>
 
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef CGAL::Polygon_2<Kernel> Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes_2;
 
typedef std::list<Polygon_with_holes_2> Pwh_list_2;
 
int main() {
    // 构造第一个多边形
    Polygon_2 P;
    P.push_back(Point_2(0, 0));
    P.push_back(Point_2(5, 0));
    P.push_back(Point_2(3.5, 1.5));
    P.push_back(Point_2(2.5, 0.5));
    P.push_back(Point_2(1.5, 1.5));
    
    // 构造第二个多边形
    Polygon_2 Q;
    Q.push_back(Point_2(0, 2));
    Q.push_back(Point_2(1.5, 0.5));
    Q.push_back(Point_2(2.5, 1.5));
    Q.push_back(Point_2(3.5, 0.5));
    Q.push_back(Point_2(5, 2));
    
    // 计算并集
    Polygon_with_holes_2 unionR;
    if (CGAL::join(P, Q, unionR)) {
        std::cout << "并集计算成功" << std::endl;
    }
    
    // 计算交集
    Pwh_list_2 intR;
    CGAL::intersection(P, Q, std::back_inserter(intR));
    
    return 0;
}

Nef多面体回顾

Nef多面体是表示多边形/多面体集合的通用数据结构，支持任意布尔运算。Nef多面体可以表示：

开集和闭集
非流形几何
有孔洞的多边形

Nef多面体的层次结构：

Nef多面体
├── 选择函数（Selective Function）
│   └── 为每个面、边、顶点标记内外状态
├── 球面映射（Spherical Map）
│   └── 将局部邻域映射到单位球面
└── 拓扑结构
    ├── 顶点（Vertex）
    ├── 边（Edge）
    ├── 面（Face）
    └── 体积（Volume，3D）

Nef多面体的局部视图：

点p处的局部邻域:

        外部区域
           |
     ------+-------
          |p
    ------+-------
           |
        内部区域

球面映射: 将p的邻域投影到单位球面

           ^
           | 外部半球 (标记为外部)
    -------+-------
           |
           | 内部半球 (标记为内部)

正则化与非正则化运算

**正则化（Regularization）**是布尔运算的重要概念。集合 $S$ 的正则化定义为：

$S^{*} = closure (interior (S))$

即先取内部再取闭包。正则化消除”悬挂边”、“孤立点”等低维特征。

正则化与非正则化比较：

输入: 两个共享边的多边形

+-------+
|   A   |
|       |
+---+---+  <-- 共享边
    |   |
    | B |
    +---+

非正则化并集:              正则化并集:
+-------+                  +-------+
|       |                  |       |
|       |                  |       |
+---+---+                  +       +
    |   |                  |       |
    |   |                  |       |
    +---+                  +-------+
(保留共享边作为内部边)      (消除内部边)

CGAL的布尔运算默认产生正则化结果。使用Gps_segment_traits_2可以控制正则化行为。

12.1.4 闵可夫斯基和

数学定义

两个集合 $P$ 和 $Q$ 的闵可夫斯基和定义为：

$P \oplus Q = {p + q ∣ p \in P, q \in Q}$

在几何上，这相当于将 $Q$ 的中心放在 $P$ 的每个点上，然后取并集。

闵可夫斯基和的可视化：

多边形P:              多边形Q:              P ⊕ Q:
    *                    +-------+            +-----------+
   / \                   |       |           /             \
  /   \                  |   *   |          /   +-------+   \
 *-----*                 +-------+         *---*       *---*
                                              \       /
                                               \     /
                                                *---*

闵可夫斯基和的性质：

交换律： $P \oplus Q = Q \oplus P$
结合律： $(P \oplus Q) \oplus R = P \oplus (Q \oplus R)$
平移不变性： $(P + t) \oplus Q = (P \oplus Q) + t$
凸包性质： $conv (P \oplus Q) = conv (P) \oplus conv (Q)$

卷积方法

**卷积（Convolution）**是计算闵可夫斯基和的核心技术。对于两个多边形，其卷积定义为：

$P \otimes Q = {p + q ∣ p \in \partial P, q \in \partial Q, 法向量相同}$

卷积的构建过程：

步骤1: 计算边向量
P的边: e1, e2, ..., en
Q的边: f1, f2, ..., fm

步骤2: 按角度排序
将所有边向量按极角排序

步骤3: 构建卷积多边形
按排序后的顺序连接边向量

示例:
P = 三角形 (边方向: 0°, 120°, 240°)
Q = 正方形 (边方向: 0°, 90°, 180°, 270°)

排序后的方向: 0°, 0°, 90°, 120°, 180°, 180°, 240°, 270°

卷积结果: 八边形

简化卷积（Reduced Convolution）：

CGAL使用简化卷积方法，只考虑可能出现在闵可夫斯基和边界上的边对，显著提高计算效率。

#include <CGAL/minkowski_sum_2.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
 
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef CGAL::Polygon_2<Kernel> Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes_2;
 
// 使用简化卷积计算闵可夫斯基和
Polygon_with_holes_2 compute_minkowski_sum(
    const Polygon_2& P, 
    const Polygon_2& Q) {
    return CGAL::minkowski_sum_by_reduced_convolution_2(P, Q);
}
 
// 使用完整卷积计算闵可夫斯基和
Polygon_with_holes_2 compute_minkowski_sum_full(
    const Polygon_2& P, 
    const Polygon_2& Q) {
    return CGAL::minkowski_sum_by_full_convolution_2(P, Q);
}

完整示例：

#include <CGAL/minkowski_sum_2.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <iostream>
 
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef CGAL::Polygon_2<Kernel> Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes_2;
 
int main() {
    // 构造三角形
    Polygon_2 P;
    P.push_back(Point_2(-1, -1));
    P.push_back(Point_2(1, -1));
    P.push_back(Point_2(0, 1));
    
    // 构造正方形
    Polygon_2 Q;
    Q.push_back(Point_2(3, -1));
    Q.push_back(Point_2(5, -1));
    Q.push_back(Point_2(5, 1));
    Q.push_back(Point_2(3, 1));
    
    // 计算闵可夫斯基和
    Polygon_with_holes_2 sum = CGAL::minkowski_sum_2(P, Q);
    
    std::cout << "闵可夫斯基和的外边界顶点数: " 
              << sum.outer_boundary().size() << std::endl;
    
    return 0;
}

在机器人运动规划中的应用

闵可夫斯基和在机器人运动规划中有核心应用，特别是在**构型空间（Configuration Space, C-space）**方法中。

障碍物扩展原理：

给定机器人 $R$ 和障碍物 $O$ ，机器人在 $O$ 附近不能到达的区域可以通过闵可夫斯基和计算：

$O^{'} = O \oplus (- R)$

其中 $- R$ 是机器人关于原点的反射。

C-space障碍物构建：

原始场景:                C-space表示:
    
    障碍物O                扩展障碍物O'
    +----+                    +--------+
    |    |                    |        |
    +----+                    |   +--+ |
                              |   |  | |
    机器人R                   |   +--+ |
      *                       |        |
     / \                      +--------+
    *---*

机器人可以到达的位置 = 工作空间 \ O'

路径规划算法框架：

// 构建C-space障碍物
std::vector<Polygon_2> build_cspace_obstacles(
    const Polygon_2& robot,
    const std::vector<Polygon_2>& obstacles) {
    
    std::vector<Polygon_2> cspace_obstacles;
    
    // 反射机器人
    Polygon_2 reflected_robot = reflect_polygon(robot);
    
    // 计算每个障碍物的扩展
    for (const auto& obstacle : obstacles) {
        Polygon_with_holes_2 expanded = 
            CGAL::minkowski_sum_2(obstacle, reflected_robot);
        cspace_obstacles.push_back(expanded.outer_boundary());
    }
    
    return cspace_obstacles;
}

12.1.5 直骨架与屋顶算法

直骨架定义

多边形 $P$ 的**直骨架（Straight Skeleton）**是通过连续收缩多边形边界形成的骨架结构。与Voronoi图不同，直骨架完全由直线段组成。

直骨架的构建过程：

时间 t=0:              时间 t=1:              时间 t=2:
+----------------+     +------------+         +--------+
|                |     |            |         |        |
|                |     |   +----+   |         |   /\   |
|                | --> |   |    |   |   -->   |  /  \  |
|                |     |   +----+   |         | /    \ |
|                |     |            |         |/      \|
+----------------+     +------------+         +--------+

直骨架: 追踪顶点运动轨迹形成的树状结构

直骨架的数学定义：

直骨架是收缩过程中多边形顶点的角平分线轨迹的并集。每个顶点沿其内角平分线方向以速度 $1/ sin (θ /2)$ 移动，其中 $θ$ 是内角。

直骨架的组成：

弧（Arc）：顶点运动轨迹
节点（Node）：
- 原始顶点（收缩开始）
- 边事件（一条边收缩为点）
- 分裂事件（多边形分裂）
面（Face）：每个原始边对应一个面

屋顶算法

屋顶算法将直骨架解释为三维屋顶结构。想象多边形边界以45度角向上”生长”，直骨架对应屋顶的”屋脊线”。

屋顶结构可视化：

俯视图:                    3D屋顶视图:
                           
+--------+                 \       /
|        |                  \     /
|        |      -->          \   /
|        |                    \ /
+--------+                     V
                              / \
                             /   \

屋顶面的性质：

每个原始边对应一个屋顶面
屋顶面与水平面成45度角
屋顶面的交线对应直骨架的弧
屋顶的高度对应收缩时间

多边形偏移

**多边形偏移（Offset）**是直骨架的直接应用，用于创建多边形的等距内缩或外扩版本。

内偏移（Inset）：

原始多边形:           偏移距离d:            偏移结果:
+--------------+     +--------------+     +--------+
|              |     |  +--------+  |     |        |
|              |     |  |        |  |     |        |
|              | --> |  |        |  | --> |        |
|              |     |  |        |  |     |        |
|              |     |  +--------+  |     |        |
+--------------+     +--------------+     +--------+

外偏移（Offset/ outset）：

原始多边形:           外偏移结果:
    +--+                 +-------+
    |  |                /         \
    +--+      -->      |    +--+   |
                      |    |  |   |
                       \    +--+  /
                        +-------+

CGAL直骨架实现：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/create_straight_skeleton_2.h>
#include <CGAL/create_offset_polygons_2.h>
#include <memory>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef CGAL::Straight_skeleton_2<K> Ss;
typedef std::shared_ptr<Ss> SsPtr;
 
// 创建直骨架
SsPtr create_skeleton(const Polygon_2& poly) {
    return CGAL::create_interior_straight_skeleton_2(
        poly.vertices_begin(), poly.vertices_end());
}
 
// 创建偏移多边形
std::vector<std::shared_ptr<Polygon_2>> create_offset(
    const Polygon_2& poly, double offset_distance) {
    
    SsPtr skeleton = create_skeleton(poly);
    
    return CGAL::create_offset_polygons_2(
        offset_distance, *skeleton);
}

完整示例：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/create_straight_skeleton_2.h>
#include <CGAL/draw_straight_skeleton_2.h>
#include <cassert>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef CGAL::Straight_skeleton_2<K> Ss;
typedef std::shared_ptr<Ss> SsPtr;
 
int main() {
    // 构造星形多边形
    Polygon_2 poly;
    poly.push_back(Point(-1, -1));
    poly.push_back(Point(0, -12));
    poly.push_back(Point(1, -1));
    poly.push_back(Point(12, 0));
    poly.push_back(Point(1, 1));
    poly.push_back(Point(0, 12));
    poly.push_back(Point(-1, 1));
    poly.push_back(Point(-12, 0));
    
    assert(poly.is_counterclockwise_oriented());
    
    // 创建内部直骨架
    SsPtr iss = CGAL::create_interior_straight_skeleton_2(
        poly.vertices_begin(), poly.vertices_end());
    
    // 打印直骨架信息
    CGAL::Straight_skeletons_2::IO::print_straight_skeleton(*iss);
    
    // 可视化
    CGAL::draw(*iss);
    
    // 创建外部直骨架（需要指定最大偏移距离）
    double max_offset = 5;
    SsPtr oss = CGAL::create_exterior_straight_skeleton_2(
        max_offset, poly);
    
    CGAL::draw(*oss);
    
    return 0;
}

偏移多边形创建：

#include <CGAL/create_offset_polygons_2.h>
#include <vector>
 
// 创建内偏移多边形
typedef std::shared_ptr<Polygon_2> PolygonPtr;
typedef std::vector<PolygonPtr> PolygonPtrVector;
 
PolygonPtrVector create_inset_polygons(
    const Ss& skeleton, double offset) {
    return CGAL::create_offset_polygons_2(offset, skeleton);
}
 
// 创建外偏移多边形
PolygonPtrVector create_outset_polygons(
    const Polygon_2& poly, double offset) {
    return CGAL::create_exterior_skeleton_and_offset_polygons_2(
        offset, poly);
}

12.1.6 代码实现详解

完整排列操作示例

// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
/*!
 * 排列操作综合示例
 * 演示DCEL遍历、点定位和面遍历
 */
 
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Arr_non_caching_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_walk_along_line_point_location.h>
#include <iostream>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Arr_non_caching_segment_traits_2<Kernel> Traits;
typedef Traits::Point_2 Point;
typedef Traits::X_monotone_curve_2 Segment;
typedef CGAL::Arrangement_2<Traits> Arrangement;
typedef CGAL::Arr_walk_along_line_point_location<Arrangement> Point_location;
 
// 遍历排列的所有面
void traverse_faces(const Arrangement& arr) {
    std::cout << "=== 面遍历 ===" << std::endl;
    
    for (auto fit = arr.faces_begin(); fit != arr.faces_end(); ++fit) {
        if (fit->is_unbounded()) {
            std::cout << "无界面:" << std::endl;
        } else {
            std::cout << "有界面:" << std::endl;
        }
        
        // 遍历面的外部边界
        if (!fit->is_unbounded()) {
            std::cout << "  外部边界: ";
            auto circ = fit->outer_ccb();
            auto curr = circ;
            do {
                std::cout << "(" << curr->source()->point() << ") ";
            } while (++curr != circ);
            std::cout << std::endl;
        }
        
        // 遍历面的孔洞
        int hole_count = 0;
        for (auto hit = fit->holes_begin(); hit != fit->holes_end(); ++hit) {
            std::cout << "  孔洞 " << ++hole_count << ": ";
            auto circ = *hit;
            auto curr = circ;
            do {
                std::cout << "(" << curr->source()->point() << ") ";
            } while (++curr != circ);
            std::cout << std::endl;
        }
    }
}
 
// 遍历顶点的邻接关系
void traverse_vertex_neighbors(const Arrangement& arr) {
    std::cout << "\n=== 顶点邻接关系 ===" << std::endl;
    
    for (auto vit = arr.vertices_begin(); vit != arr.vertices_end(); ++vit) {
        std::cout << "顶点 (" << vit->point() << "): ";
        
        if (vit->is_isolated()) {
            std::cout << "孤立顶点" << std::endl;
            continue;
        }
        
        std::cout << "度=" << vit->degree() << ", 邻接: ";
        
        // 使用循环器遍历邻接半边
        auto first = vit->incident_halfedges();
        auto curr = first;
        do {
            std::cout << "(" << curr->source()->point() << ") ";
        } while (++curr != first);
        std::cout << std::endl;
    }
}
 
// 点定位查询
void point_location_query(Point_location& pl, const Point& query_point) {
    std::cout << "\n=== 点定位查询 ===" << std::endl;
    std::cout << "查询点: (" << query_point << ")" << std::endl;
    
    auto obj = pl.locate(query_point);
    
    // 判断查询结果类型
    if (auto* v = boost::get<Arrangement::Vertex_const_handle>(&obj)) {
        std::cout << "结果: 位于顶点上 (" << (*v)->point() << ")" << std::endl;
    } else if (auto* e = boost::get<Arrangement::Halfedge_const_handle>(&obj)) {
        std::cout << "结果: 位于边上 [" << (*e)->curve() << "]" << std::endl;
    } else if (auto* f = boost::get<Arrangement::Face_const_handle>(&obj)) {
        if ((*f)->is_unbounded()) {
            std::cout << "结果: 位于无界面内" << std::endl;
        } else {
            std::cout << "结果: 位于有界面内" << std::endl;
        }
    }
}
 
int main() {
    // 构造排列
    Arrangement arr;
    
    // 插入线段形成两个相交的正方形
    Segment s1(Point(0, 0), Point(4, 0));
    Segment s2(Point(4, 0), Point(4, 4));
    Segment s3(Point(4, 4), Point(0, 4));
    Segment s4(Point(0, 4), Point(0, 0));
    Segment s5(Point(2, -1), Point(2, 5));
    Segment s6(Point(-1, 2), Point(5, 2));
    
    CGAL::insert(arr, s1);
    CGAL::insert(arr, s2);
    CGAL::insert(arr, s3);
    CGAL::insert(arr, s4);
    CGAL::insert(arr, s5);
    CGAL::insert(arr, s6);
    
    // 输出排列统计
    std::cout << "排列统计:" << std::endl;
    std::cout << "  顶点数: " << arr.number_of_vertices() << std::endl;
    std::cout << "  边数: " << arr.number_of_edges() << std::endl;
    std::cout << "  面数: " << arr.number_of_faces() << std::endl;
    
    // 验证欧拉公式: V - E + F = 2 (对于连通平面细分)
    int V = arr.number_of_vertices();
    int E = arr.number_of_edges();
    int F = arr.number_of_faces();
    std::cout << "  欧拉公式验证: " << V << " - " << E << " + " << F 
              << " = " << (V - E + F) << std::endl;
    
    // 遍历面
    traverse_faces(arr);
    
    // 遍历顶点邻接关系
    traverse_vertex_neighbors(arr);
    
    // 点定位
    Point_location pl(arr);
    point_location_query(pl, Point(2, 2));  // 面内部
    point_location_query(pl, Point(2, 0));  // 边上
    point_location_query(pl, Point(0, 0));  // 顶点上
    
    return 0;
}

布尔运算综合示例

// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
/*!
 * 布尔运算综合示例
 * 演示并、交、差、对称差运算
 */
 
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <list>
#include <iostream>
 
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef CGAL::Polygon_2<Kernel> Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes_2;
typedef std::list<Polygon_with_holes_2> Pwh_list_2;
 
// 打印多边形信息
void print_polygon(const Polygon_2& P) {
    std::cout << "多边形顶点数: " << P.size() << std::endl;
    std::cout << "顶点: ";
    for (auto vit = P.vertices_begin(); vit != P.vertices_end(); ++vit) {
        std::cout << "(" << *vit << ") ";
    }
    std::cout << std::endl;
}
 
void print_polygon_with_holes(const Polygon_with_holes_2& pwh) {
    std::cout << "外边界顶点数: " << pwh.outer_boundary().size() << std::endl;
    std::cout << "孔洞数: " << pwh.number_of_holes() << std::endl;
}
 
// 布尔运算演示
void boolean_operations_demo() {
    // 构造多边形P（L形）
    Polygon_2 P;
    P.push_back(Point_2(0, 0));
    P.push_back(Point_2(4, 0));
    P.push_back(Point_2(4, 2));
    P.push_back(Point_2(2, 2));
    P.push_back(Point_2(2, 4));
    P.push_back(Point_2(0, 4));
    
    // 构造多边形Q（矩形）
    Polygon_2 Q;
    Q.push_back(Point_2(1, 1));
    Q.push_back(Point_2(5, 1));
    Q.push_back(Point_2(5, 3));
    Q.push_back(Point_2(1, 3));
    
    std::cout << "=== 输入多边形 ===" << std::endl;
    std::cout << "多边形P:" << std::endl;
    print_polygon(P);
    std::cout << "多边形Q:" << std::endl;
    print_polygon(Q);
    
    // 1. 并运算
    std::cout << "\n=== 并运算 (P ∪ Q) ===" << std::endl;
    Polygon_with_holes_2 union_result;
    if (CGAL::join(P, Q, union_result)) {
        std::cout << "并集结果:" << std::endl;
        print_polygon_with_holes(union_result);
    } else {
        std::cout << "P和Q不相交" << std::endl;
    }
    
    // 2. 交运算
    std::cout << "\n=== 交运算 (P ∩ Q) ===" << std::endl;
    Pwh_list_2 intersection_result;
    CGAL::intersection(P, Q, std::back_inserter(intersection_result));
    std::cout << "交集组件数: " << intersection_result.size() << std::endl;
    int i = 1;
    for (const auto& pwh : intersection_result) {
        std::cout << "  组件 " << i++ << ": ";
        print_polygon_with_holes(pwh);
    }
    
    // 3. 差运算
    std::cout << "\n=== 差运算 (P \\ Q) ===" << std::endl;
    Pwh_list_2 difference_result;
    CGAL::difference(P, Q, std::back_inserter(difference_result));
    std::cout << "差集组件数: " << difference_result.size() << std::endl;
    
    // 4. 对称差
    std::cout << "\n=== 对称差 (P △ Q) ===" << std::endl;
    Pwh_list_2 sym_diff_result;
    CGAL::symmetric_difference(P, Q, std::back_inserter(sym_diff_result));
    std::cout << "对称差组件数: " << sym_diff_result.size() << std::endl;
    
    // 5. 相交测试
    std::cout << "\n=== 相交测试 ===" << std::endl;
    bool intersect = CGAL::do_intersect(P, Q);
    std::cout << "P和Q是否相交: " << (intersect ? "是" : "否") << std::endl;
    
    // 6. 方向测试
    std::cout << "\n=== 方向测试 ===" << std::endl;
    CGAL::Oriented_side side = CGAL::oriented_side(P, Point_2(1, 1));
    std::cout << "点(1,1)相对于P的位置: ";
    switch (side) {
        case CGAL::ON_ORIENTED_BOUNDARY: std::cout << "边界上"; break;
        case CGAL::ON_POSITIVE_SIDE: std::cout << "内部"; break;
        case CGAL::ON_NEGATIVE_SIDE: std::cout << "外部"; break;
    }
    std::cout << std::endl;
}
 
int main() {
    boolean_operations_demo();
    return 0;
}

闵可夫斯基和与路径规划示例

// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
/*!
 * 闵可夫斯基和在机器人运动规划中的应用
 */
 
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/minkowski_sum_2.h>
#include <CGAL/Polygon_2.h>
#include <vector>
#include <iostream>
 
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Vector_2 Vector_2;
typedef CGAL::Polygon_2<Kernel> Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes_2;
 
// 反射多边形（关于原点）
Polygon_2 reflect_polygon(const Polygon_2& P) {
    Polygon_2 reflected;
    for (auto vit = P.vertices_begin(); vit != P.vertices_end(); ++vit) {
        reflected.push_back(Point_2(-vit->x(), -vit->y()));
    }
    return reflected;
}
 
// 平移多边形
Polygon_2 translate_polygon(const Polygon_2& P, const Vector_2& v) {
    Polygon_2 translated;
    for (auto vit = P.vertices_begin(); vit != P.vertices_end(); ++vit) {
        translated.push_back(*vit + v);
    }
    return translated;
}
 
// 构建C-space障碍物
std::vector<Polygon_2> build_cspace_obstacles(
    const Polygon_2& robot,
    const std::vector<Polygon_2>& obstacles) {
    
    std::vector<Polygon_2> cspace_obstacles;
    Polygon_2 reflected_robot = reflect_polygon(robot);
    
    std::cout << "构建C-space障碍物..." << std::endl;
    std::cout << "机器人顶点数: " << robot.size() << std::endl;
    std::cout << "障碍物数量: " << obstacles.size() << std::endl;
    
    for (size_t i = 0; i < obstacles.size(); ++i) {
        // 计算闵可夫斯基和: obstacle ⊕ (-robot)
        Polygon_with_holes_2 expanded = 
            CGAL::minkowski_sum_2(obstacles[i], reflected_robot);
        
        cspace_obstacles.push_back(expanded.outer_boundary());
        std::cout << "  障碍物 " << i+1 << " 扩展后顶点数: " 
                  << expanded.outer_boundary().size() << std::endl;
    }
    
    return cspace_obstacles;
}
 
// 简单的碰撞检测（点在多边形内测试）
bool is_collision(const Point_2& point, const std::vector<Polygon_2>& obstacles) {
    for (const auto& obs : obstacles) {
        if (obs.has_on_bounded_side(point) || obs.has_on_boundary(point)) {
            return true;
        }
    }
    return false;
}
 
int main() {
    // 定义三角形机器人
    Polygon_2 robot;
    robot.push_back(Point_2(0, 0.5));
    robot.push_back(Point_2(-0.5, -0.5));
    robot.push_back(Point_2(0.5, -0.5));
    
    // 定义障碍物
    std::vector<Polygon_2> obstacles;
    
    // 障碍物1: 正方形
    Polygon_2 obs1;
    obs1.push_back(Point_2(2, 2));
    obs1.push_back(Point_2(4, 2));
    obs1.push_back(Point_2(4, 4));
    obs1.push_back(Point_2(2, 4));
    obstacles.push_back(obs1);
    
    // 障碍物2: 三角形
    Polygon_2 obs2;
    obs2.push_back(Point_2(6, 1));
    obs2.push_back(Point_2(8, 2));
    obs2.push_back(Point_2(7, 4));
    obstacles.push_back(obs2);
    
    // 构建C-space障碍物
    std::vector<Polygon_2> cspace_obs = build_cspace_obstacles(robot, obstacles);
    
    // 测试路径规划
    Point_2 start(0, 0);
    Point_2 goal(10, 5);
    
    std::cout << "\n路径规划测试:" << std::endl;
    std::cout << "起点 (" << start << ") 碰撞检测: " 
              << (is_collision(start, cspace_obs) ? "碰撞" : "自由") << std::endl;
    std::cout << "终点 (" << goal << ") 碰撞检测: " 
              << (is_collision(goal, cspace_obs) ? "碰撞" : "自由") << std::endl;
    
    // 测试路径上的点
    std::cout << "\n路径采样测试:" << std::endl;
    for (int i = 0; i <= 10; ++i) {
        double t = i / 10.0;
        Point_2 p(start.x() + t * (goal.x() - start.x()),
                  start.y() + t * (goal.y() - start.y()));
        bool collision = is_collision(p, cspace_obs);
        std::cout << "  点 (" << p << "): " 
                  << (collision ? "碰撞" : "自由") << std::endl;
    }
    
    return 0;
}

12.1.7 应用场景

计算机辅助设计（CAD）

布尔运算在CAD中的应用：

实体建模流程:

基本体素          布尔运算           复杂模型
+-------+        +-------+         +-------+
|       |   ∪    |  +--+ |         | +--+  |
|   +   |   -->  |  |  | |   -->   | |  |  |
|       |        |  +--+ |         | +--+  |
+-------+        +-------+         +-------+

特征操作:
- 拉伸 (Extrusion)
- 旋转 (Revolution)
- 扫掠 (Sweep)
- 放样 (Loft)

地理信息系统（GIS）

空间分析操作：

地图叠加分析:

土地利用图层:      土壤类型图层:      叠加结果:
+---+---+---+      +---+---+---+      +---+---+---+
| A | A | B |      | 1 | 2 | 2 |      |A1 |A2 |B2 |
+---+---+---+  ∩   +---+---+---+  =   +---+---+---+
| A | C | C |      | 1 | 1 | 3 |      |A1 |C1 |C3 |
+---+---+---+      +---+---+---+      +---+---+---+

A: 农业用地  B: 林地  C: 城市
1: 肥沃土壤  2: 沙质土壤  3: 粘土

机器人运动规划

构型空间方法：

工作空间:                      C-space:
    
    障碍物                      扩展障碍物
    +----+                      +--------+
    |    |                      |        |
    +----+                      |   +--+ |
                                |   |  | |
    机器人                      |   +--+ |
      *                         |        |
     / \                        +--------+
    *---*
    
路径规划 = 在C-space中寻找从起点到终点的无障碍路径

计算机图形学

多边形裁剪与CSG建模：

CSG树结构:

       ∪
      / \
     ∩   圆柱
    / \
   立方体  球

表示: (立方体 ∩ 球) ∪ 圆柱

12.1.8 本章小结

本章深入探讨了排列与布尔运算的核心概念和算法：

核心数据结构：

DCEL（双向连接边表）：平面细分的标准表示，通过顶点、半边和面维护拓扑关系
组合嵌入：描述平面图的拓扑结构，与几何形状无关
欧拉公式： $V - E + F = 2$ 是验证平面细分有效性的重要工具

核心算法：

Bentley-Ottmann扫描线算法： $O ((n + k) lo g n)$ 时间复杂度计算线段交点
事件驱动处理：站点事件和交点事件的正确处理是算法正确性的关键
简化卷积：高效计算闵可夫斯基和的核心技术

布尔运算：

支持并、交、差、对称差等标准集合运算
Nef多面体提供通用的集合表示
正则化运算消除低维特征，产生符合物理直觉的结果

高级应用：

闵可夫斯基和：机器人运动规划中C-space障碍物的构建
直骨架：多边形偏移、屋顶设计、形状分析

数值稳健性：

在使用这些算法时，数值稳健性是重要考虑因素：

精确几何计算：CGAL的Exact_predicates_exact_constructions_kernel提供精确计算，避免浮点误差
退化情况处理：共线点、重合边等退化情况需要特殊处理
计算复杂度：理解算法的时间复杂度，选择合适的算法变体

复杂度总结表：

算法/操作	时间复杂度	空间复杂度
Bentley-Ottmann	$O ((n + k) lo g n)$	$O (n + k)$
布尔运算	$O ((n + m) lo g (n + m))$	$O (n + m)$
闵可夫斯基和（简化卷积）	$O (nm lo g (nm))$	$O (nm)$
直骨架构建	$O (n r lo g n)$	$O (n)$
点定位（最坏情况）	$O (n)$	$O (n)$
点定位（期望）	$O (lo g n)$	$O (n)$

其中 $n, m$ 是输入规模， $k$ 是交点数， $r$ 是直骨架节点数。

12.1.9 练习

理论练习

练习12.1：DCEL验证给定一个DCEL表示的平面细分，编写算法验证其满足欧拉公式。考虑如何处理多个连通分量的情况？

练习12.2：扫描线算法分析分析Bentley-Ottmann算法中事件队列的最大长度。证明其空间复杂度为 $O (n + k)$ 。

练习12.3：闵可夫斯基和性质证明闵可夫斯基和的以下性质：

交换律： $P \oplus Q = Q \oplus P$
平移不变性： $(P + t) \oplus Q = (P \oplus Q) + t$
凸包性质： $conv (P \oplus Q) = conv (P) \oplus conv (Q)$

练习12.4：直骨架与Voronoi图比较直骨架和Voronoi图的异同。在什么情况下两者会重合？

编程练习

练习12.5：排列遍历实现一个函数，遍历排列的所有有界面，并计算每个面的面积。使用CGAL的Arrangement_2类。

练习12.6：布尔运算序列实现一个函数，接受多边形列表和布尔运算序列（如”A ∪ B ∩ C \ D”），计算最终结果。考虑运算符优先级。

练习12.7：机器人路径规划扩展12.1.6节的示例，实现A*算法在C-space中搜索从起点到终点的最短路径。

练习12.8：多边形偏移实现一个函数，给定多边形和偏移距离序列，生成一系列向内偏移的多边形，直到多边形消失。

应用练习

练习12.9：地图叠加给定两个多边形图层（如行政区划和土地利用），实现空间叠加分析，计算每个叠加区域的属性组合。

练习12.10：屋顶设计给定建筑物 footprint（多边形），使用直骨架生成不同风格的屋顶设计（如四坡顶、人字顶等）。

参考文献：

de Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. (2008). Computational Geometry: Algorithms and Applications (3rd ed.). Springer.
CGAL Project. (2024). CGAL User and Reference Manual (6.0.1 ed.). https://doc.cgal.org/
Bentley, J. L., & Ottmann, T. A. (1979). Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, 28(9), 643-647.
Aichholzer, O., Aurenhammer, F., Alberts, D., & Gärtner, B. (1995). A novel type of skeleton for polygons. Journal of Universal Computer Science, 1(12), 752-761.
Fogel, E., Halperin, D., Wein, R., & Zukerman, B. (2012). 2D Arrangements. In CGAL User and Reference Manual.

Chunibyo

Explorer

12.1 排列与计算几何

12.1 排列与计算几何 §

12.1.1 Arrangement数据结构 §

DCEL（Doubly Connected Edge List）详解 §

顶点、边、面的拓扑关系 §

组合嵌入的概念 §

12.1.2 Bentley-Ottmann扫描线算法 §

算法原理 §

事件处理 §

CGAL实现细节 §

12.1.3 布尔集合运算 §

2D布尔运算 §

Nef多面体回顾 §

正则化与非正则化运算 §

12.1.4 闵可夫斯基和 §

数学定义 §

卷积方法 §

在机器人运动规划中的应用 §

12.1.5 直骨架与屋顶算法 §

直骨架定义 §

屋顶算法 §

多边形偏移 §

12.1.6 代码实现详解 §

完整排列操作示例 §

布尔运算综合示例 §

闵可夫斯基和与路径规划示例 §

12.1.7 应用场景 §

计算机辅助设计（CAD） §

地理信息系统（GIS） §

机器人运动规划 §

计算机图形学 §

12.1.8 本章小结 §

12.1.9 练习 §

理论练习 §

编程练习 §

应用练习 §

Graph View

Table of Contents

Backlinks

12.1 排列与计算几何

12.1.1 Arrangement数据结构

DCEL（Doubly Connected Edge List）详解

顶点、边、面的拓扑关系

组合嵌入的概念

12.1.2 Bentley-Ottmann扫描线算法

算法原理

事件处理

CGAL实现细节

12.1.3 布尔集合运算

2D布尔运算

Nef多面体回顾

正则化与非正则化运算

12.1.4 闵可夫斯基和

数学定义

卷积方法

在机器人运动规划中的应用

12.1.5 直骨架与屋顶算法

直骨架定义

屋顶算法

多边形偏移

12.1.6 代码实现详解

完整排列操作示例

布尔运算综合示例

闵可夫斯基和与路径规划示例

12.1.7 应用场景

计算机辅助设计（CAD）

地理信息系统（GIS）

机器人运动规划

计算机图形学

12.1.8 本章小结

12.1.9 练习

理论练习

编程练习

应用练习