10.1 凸包算法 (Convex Hull Algorithms)

1. 理论基础

1.1 凸包的数学定义

定义 10.1 (凸集)：对于 d 维欧几里得空间中的点集 S，如果对于任意两点 p, q ∈ S，连接它们的线段完全包含在 S 中，则称 S 是凸集。

定义 10.2 (凸包)：给定 d 维空间中的点集 P，P 的凸包 (Convex Hull) 是包含 P 的最小凸集，记作 CH(P)。等价地，凸包可以表示为 P 中点的所有凸组合的集合：

$C H (P) = {\sum_{i = 1}^{n} λ_{i} p_{i} ∣ p_{i} \in P, λ_{i} \geq 0, \sum_{i = 1}^{n} λ_{i} = 1}$

性质：

凸包是唯一的
凸包的顶点都是原集合 P 中的点
在二维空间中，凸包是一个凸多边形
在三维空间中，凸包是一个凸多面体

1.2 不同维度的凸包

维度	几何对象	边界元素	复杂度
2D	凸多边形	边 (线段)	O(n log n)
3D	凸多面体	面 (三角形)	O(n log n)
dD	凸多胞体	(d-1)维单形	O(n^{⌊d/2⌋})

2. CGAL 凸包模块架构

2.1 模块组织

CGAL 的凸包功能分布在三个主要模块中：

Convex_hull_2/          # 二维凸包
  include/CGAL/
    convex_hull_2.h           # 主接口
    ch_graham_andrew.h        # Graham-Andrew 算法
    ch_akl_toussaint.h        # AKL-Toussaint 算法
    ch_bykat.h                # Bykat 算法 (QuickHull)
    ch_jarvis.h               # Jarvis 步进算法
    ch_melkman.h              # Melkman 算法 (简单多边形)
    ch_eddy.h                 # Eddy 算法
    convex_hull_traits_2.h    # 2D 几何特征
    Convex_hull_traits_adapter_2.h  # 适配器模式

Convex_hull_3/          # 三维凸包
  include/CGAL/
    Convex_hull_traits_3.h    # 3D 几何特征
    Convex_hull_face_base_2.h # 面基类
    Convex_hull_vertex_base_2.h # 顶点基类

Convex_hull_d/          # 高维凸包
  include/CGAL/
    Convex_hull_d.h           # d 维凸包类
    Convex_hull_d_traits_3.h  # 3D 特征适配器
    Convex_hull_d_to_polyhedron_3.h  # 转换器

2.2 算法选择策略

CGAL 根据迭代器类型自动选择最优算法：

// 来自 convex_hull_2.h
template <class InputIterator, class OutputIterator, class Traits>
inline OutputIterator CGAL_convex_hull_points_2(
    InputIterator first, InputIterator last,
    OutputIterator result, const Traits& ch_traits,
    std::input_iterator_tag)  // 输入迭代器 → Bykat (QuickHull)
{ return ch_bykat(first, last, result, ch_traits); }
 
template <class InputIterator, class OutputIterator, class Traits>
inline OutputIterator CGAL_convex_hull_points_2(
    InputIterator first, InputIterator last,
    OutputIterator result, const Traits& ch_traits,
    std::forward_iterator_tag)  // 前向迭代器 → AKL-Toussaint
{ return ch_akl_toussaint(first, last, result, ch_traits); }
 
template <class InputIterator, class OutputIterator, class Traits>
inline OutputIterator CGAL_convex_hull_points_2(
    InputIterator first, InputIterator last,
    OutputIterator result, const Traits& ch_traits,
    std::random_access_iterator_tag)  // 随机访问迭代器 → AKL-Toussaint
{ return ch_akl_toussaint(first, last, result, ch_traits); }

3. 二维凸包算法详解

3.1 AKL-Toussaint 算法

AKL-Toussaint 算法是一种输出敏感的凸包算法，通过快速排除内部点来提高效率。

算法思想：

找到极值点（x 最小/最大，y 最小/最大）
构造初始四边形
排除四边形内部的点
对剩余点分别处理四个区域

复杂度：

最坏情况：O(n log n)
平均情况：O(n)（对于随机分布的点）

3.2 Graham-Andrew 算法 (单调链)

Graham-Andrew 算法是 Graham 扫描的变体，使用字典序排序。

算法步骤：

按 x 坐标排序（x 相同则按 y）
分别构造下凸壳和上凸壳
合并两个凸壳

// 核心扫描过程 (ch_graham_andrew_impl.h)
template <class BidirectionalIterator, class OutputIterator, class Traits>
OutputIterator ch_graham_andrew_scan(
    BidirectionalIterator first,
    BidirectionalIterator last,
    OutputIterator result,
    const Traits& ch_traits)
{
    typedef typename Traits::Left_turn_2 Left_turn_2;
    Left_turn_2 left_turn = ch_traits.left_turn_2_object();
    
    // 使用栈维护凸包顶点
    std::vector<Point> hull;
    for (auto it = first; it \!= last; ++it) {
        while (hull.size() >= 2 && 
               \!left_turn(hull[hull.size()-2], hull.back(), *it)) {
            hull.pop_back();  // 移除非左转的点
        }
        hull.push_back(*it);
    }
    // ...
}

3.3 QuickHull (Bykat) 算法

QuickHull 是一种分治算法，类似于快速排序。

算法步骤：

找到距离最远的两点（凸包直径）
将点集分为两个子集
对每个子集递归构造凸包
合并结果

// ch_bykat.h - 递归分割策略
template <class InputIterator, class OutputIterator, class Traits>
OutputIterator ch_bykat(
    InputIterator first, InputIterator last,
    OutputIterator result,
    const Traits& ch_traits)
{
    // 找到极值点
    auto [min_pt, max_pt] = find_extreme_points(first, last);
    
    // 分割点集
    auto [left_set, right_set] = partition_points(
        first, last, min_pt, max_pt, ch_traits);
    
    // 递归处理
    quick_hull_recursive(left_set, result, ch_traits);
    quick_hull_recursive(right_set, result, ch_traits);
    
    return result;
}

3.4 Jarvis 步进算法 (Gift Wrapping)

Jarvis 算法模拟包装礼物的过程，沿凸包边界逐步前进。

特点：

输出敏感：O(nh)，其中 h 是凸包顶点数
适合凸包顶点数较少的情况
简单直观

4. 三维凸包实现

4.1 核心类设计

// Convex_hull_traits_3.h
// 3D 凸包使用 Point_triple 作为平面表示
template <class R_>
class Point_triple {
protected:
    typedef typename R_::FT FT;
    typedef typename R_::Point_3 Point_3;
    Point_3 p_, q_, r_;  // 平面上不共线的三点
public:
    const Point_3& p() const { return p_; }
    const Point_3& q() const { return q_; }
    const Point_3& r() const { return r_; }
};
 
// Convex_hull_traits_3 类
template <class R_, class Polyhedron = Default, 
          class Has_filtered_predicates_tag = ...>
class Convex_hull_traits_3 {
public:
    typedef R_ R;
    typedef typename R::Point_3 Point_3;
    typedef Point_triple<R> Plane_3;  // 用三点表示平面
    
    // 关键谓词
    typedef typename R::Orientation_3 Orientation_3;
    typedef Point_triple_has_on_positive_side_3<R> Has_on_positive_side_3;
    typedef Point_triple_less_signed_distance_to_plane_3<R> 
            Less_signed_distance_to_plane_3;
    
    // 退化情况处理：投影到 2D
    typedef CGAL::Projection_traits_xy_3<R> Traits_xy_3;
    typedef CGAL::Projection_traits_yz_3<R> Traits_yz_3;
    typedef CGAL::Projection_traits_xz_3<R> Traits_xz_3;
};

4.2 增量式算法

三维凸包使用增量式构造算法：

初始化：构造初始四面体
增量插入：逐个插入点，更新凸包
可见性判断：确定哪些面被新点”看到”
面片更新：移除可见面，添加新面

// 可见性判断核心逻辑
bool is_visible(const Plane_3& plane, const Point_3& point) {
    // 点在平面的正侧
    return orientation(plane.p(), plane.q(), plane.r(), point) == POSITIVE;
}
 
// 处理新插入的点
void insert_point(const Point_3& new_point) {
    std::vector<Face_handle> visible_faces;
    
    // 收集所有可见面
    for (auto face : hull_faces) {
        if (is_visible(face.plane(), new_point)) {
            visible_faces.push_back(face);
        }
    }
    
    // 找到可见区域的边界边
    auto boundary_edges = find_boundary_edges(visible_faces);
    
    // 移除可见面，添加新面
    for (auto face : visible_faces) remove_face(face);
    for (auto edge : boundary_edges) {
        add_face(edge, new_point);
    }
}

5. 高维凸包 (Convex_hull_d)

5.1 单纯复形表示

Convex_hull_d 使用单纯复形 (Simplicial Complex) 表示高维凸包：

// Convex_hull_d.h - 核心数据结构
template <class R_>
class Convex_hull_d : public Regular_complex_d<R_> {
    // 继承自 Regular_complex_d，维护单纯复形结构
    
    // 核心成员
    Point_list all_pnts_;           // 所有插入的点
    Vector_d quasi_center_;         // 原点单形的顶点之和
    Simplex_handle origin_simplex_; // 原点单形
    Facet_handle start_facet_;      // 起始面（用于遍历）
    Vertex_handle anti_origin_;     // 反原点（用于表示无限单形）
    
    // 统计信息
    std::size_t num_of_bounded_simplices;   // 有界单形数
    std::size_t num_of_unbounded_simplices; // 无界单形数
    std::size_t num_of_visibility_tests;    // 可见性测试次数
};

5.2 QuickHull 算法实现

高维 QuickHull 的核心是递归地处理面片：

// 初始化过程
template <class Forward_iterator>
void initialize(Forward_iterator first, Forward_iterator last) {
    // 1. 找到初始单形（d+1 个仿射无关点）
    // 2. 构建初始单形和其对偶的无限单形
    // 3. 将剩余点分配给各个面片
    // 4. 递归处理每个面片
}
 
// 面片处理
void process_facet(Facet_handle f, std::list<Point_d>& points) {
    if (points.empty()) return;
    
    // 找到距离面片最远的点
    Point_d furthest = find_furthest_point(f, points);
    
    // 收集所有可见面
    std::list<Facet_handle> visible_facets;
    visible_facets_search(f, furthest, visible_facets, ...);
    
    // 创建新的单形
    for (auto vf : visible_facets) {
        for (int k = 1; k <= dcur; ++k) {
            if (\!is_base_facet_visible(opposite_simplex(vf, k), furthest)) {
                // 创建新单形
                Simplex_handle T = new_simplex();
                // 设置顶点...
                compute_equation_of_base_facet(T);
            }
        }
    }
}

6. 使用示例

6.1 二维凸包基本用法

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
#include <vector>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
 
int main() {
    std::vector<Point_2> points = {
        Point_2(0, 0), Point_2(10, 0), 
        Point_2(10, 10), Point_2(6, 5), Point_2(4, 1)
    };
    
    std::vector<Point_2> hull;
    CGAL::convex_hull_2(points.begin(), points.end(), 
                        std::back_inserter(hull));
    
    std::cout << hull.size() << " points on the convex hull" << std::endl;
    // 输出: 3 points on the convex hull (0,0), (10,0), (10,10)
    
    return 0;
}

6.2 使用 Traits 适配器

#include <CGAL/Convex_hull_traits_adapter_2.h>
#include <CGAL/property_map.h>
 
// 自定义点类型
struct MyPoint {
    double x, y;
    int id;
};
 
// 创建 property map
struct MyPointMap {
    typedef MyPoint key_type;
    typedef Point_2 value_type;
    typedef Point_2 reference;
    typedef boost::readable_property_map_tag category;
};
 
Point_2 get(MyPointMap, const MyPoint& p) {
    return Point_2(p.x, p.y);
}
 
int main() {
    std::vector<MyPoint> my_points = {...};
    
    // 使用适配器
    typedef CGAL::Convex_hull_traits_adapter_2<K, MyPointMap> Traits;
    Traits traits(MyPointMap());
    
    std::vector<MyPoint> hull;
    CGAL::convex_hull_2(my_points.begin(), my_points.end(), 
                        std::back_inserter(hull), traits);
    
    return 0;
}

6.3 三维凸包

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_3.h>
#include <CGAL/Polyhedron_3.h>
#include <list>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_3 Point_3;
typedef CGAL::Polyhedron_3<K> Polyhedron_3;
 
int main() {
    std::list<Point_3> points = {
        Point_3(0, 0, 0), Point_3(1, 0, 0), Point_3(0, 1, 0),
        Point_3(0, 0, 1), Point_3(0.5, 0.5, 0.5)
    };
    
    Polyhedron_3 poly;
    CGAL::convex_hull_3(points.begin(), points.end(), poly);
    
    std::cout << "Convex hull has " << poly.size_of_vertices() 
              << " vertices and " << poly.size_of_facets() << " facets"
              << std::endl;
    
    return 0;
}

6.4 高维凸包

#include <CGAL/Convex_hull_d.h>
#include <CGAL/Homogeneous_d.h>
 
typedef CGAL::Homogeneous_d<double> Kernel;
typedef CGAL::Convex_hull_d<Kernel> Convex_hull_d;
typedef Convex_hull_d::Point_d Point_d;
 
int main() {
    const int dim = 4;  // 4维空间
    Convex_hull_d ch(dim);
    
    // 插入点
    std::vector<double> coords(dim);
    for (int i = 0; i < 100; ++i) {
        for (int d = 0; d < dim; ++d) {
            coords[d] = rand() / (double)RAND_MAX;
        }
        ch.insert(Point_d(dim, coords.begin(), coords.end()));
    }
    
    std::cout << "Hull has " << ch.number_of_vertices() << " vertices"
              << std::endl;
    
    // 遍历凸包面片
    for (auto fit = ch.facets_begin(); fit \!= ch.facets_end(); ++fit) {
        // 处理每个面片
    }
    
    return 0;
}

7. 复杂度分析

7.1 时间复杂度

算法	维度	最坏情况	平均情况	输出敏感
Graham-Andrew	2D	O(n log n)	O(n log n)	否
AKL-Toussaint	2D	O(n log n)	O(n)	否
QuickHull	2D	O(n log n)	O(n log n)	是
Jarvis March	2D	O(nh)	O(nh)	是
增量式	3D	O(n log n)	O(n log n)	否
QuickHull	dD	O(n log n + n^{⌊d/2⌋})	-	是

7.2 空间复杂度

2D 凸包：O(n)，用于存储输入点和凸包顶点
3D 凸包：O(n)，使用 DCEL 数据结构
dD 凸包：O(n^{⌊d/2⌋})，最坏情况下凸包面片数

8. 关键文件位置

文件路径	说明
`/home/chunibyo/workspace/osc/cgal/Convex_hull_2/include/CGAL/convex_hull_2.h`	2D 凸包主接口
`/home/chunibyo/workspace/osc/cgal/Convex_hull_2/include/CGAL/ch_graham_andrew.h`	Graham-Andrew 算法
`/home/chunibyo/workspace/osc/cgal/Convex_hull_2/include/CGAL/ch_akl_toussaint.h`	AKL-Toussaint 算法
`/home/chunibyo/workspace/osc/cgal/Convex_hull_2/include/CGAL/ch_bykat.h`	QuickHull 算法
`/home/chunibyo/workspace/osc/cgal/Convex_hull_2/include/CGAL/Convex_hull_traits_adapter_2.h`	Traits 适配器
`/home/chunibyo/workspace/osc/cgal/Convex_hull_3/include/CGAL/Convex_hull_traits_3.h`	3D 凸包 Traits
`/home/chunibyo/workspace/osc/cgal/Convex_hull_d/include/CGAL/Convex_hull_d.h`	d 维凸包类

9. 注意事项

数值稳定性：建议使用 Exact_predicates_inexact_constructions_kernel (Epick)
退化情况：处理共线点、共面点时需要特别注意
输出格式：凸包顶点按逆时针顺序输出（2D）
内存管理：高维凸包可能消耗大量内存

Chunibyo

Explorer

10.1 凸包算法 (Convex Hull Algorithms)

10.1 凸包算法 (Convex Hull Algorithms)

1. 理论基础

1.1 凸包的数学定义

1.2 不同维度的凸包

2. CGAL 凸包模块架构

2.1 模块组织

2.2 算法选择策略

3. 二维凸包算法详解

3.1 AKL-Toussaint 算法

3.2 Graham-Andrew 算法 (单调链)

3.3 QuickHull (Bykat) 算法

3.4 Jarvis 步进算法 (Gift Wrapping)

4. 三维凸包实现

4.1 核心类设计

4.2 增量式算法

5. 高维凸包 (Convex_hull_d)

5.1 单纯复形表示

5.2 QuickHull 算法实现

6. 使用示例

6.1 二维凸包基本用法

6.2 使用 Traits 适配器

6.3 三维凸包

6.4 高维凸包

7. 复杂度分析

7.1 时间复杂度

7.2 空间复杂度

8. 关键文件位置

9. 注意事项

Graph View

Table of Contents

Backlinks

Chunibyo

Explorer

10.1 凸包算法 (Convex Hull Algorithms)

10.1 凸包算法 (Convex Hull Algorithms) §

1. 理论基础 §

1.1 凸包的数学定义 §

1.2 不同维度的凸包 §

2. CGAL 凸包模块架构 §

2.1 模块组织 §

2.2 算法选择策略 §

3. 二维凸包算法详解 §

3.1 AKL-Toussaint 算法 §

3.2 Graham-Andrew 算法 (单调链) §

3.3 QuickHull (Bykat) 算法 §

3.4 Jarvis 步进算法 (Gift Wrapping) §

4. 三维凸包实现 §

4.1 核心类设计 §

4.2 增量式算法 §

5. 高维凸包 (Convex_hull_d) §

5.1 单纯复形表示 §

5.2 QuickHull 算法实现 §

6. 使用示例 §

6.1 二维凸包基本用法 §

6.2 使用 Traits 适配器 §

6.3 三维凸包 §

6.4 高维凸包 §

7. 复杂度分析 §

7.1 时间复杂度 §

7.2 空间复杂度 §

8. 关键文件位置 §

9. 注意事项 §

Graph View

Table of Contents

Backlinks

10.1 凸包算法 (Convex Hull Algorithms)

1. 理论基础

1.1 凸包的数学定义

1.2 不同维度的凸包

2. CGAL 凸包模块架构

2.1 模块组织

2.2 算法选择策略

3. 二维凸包算法详解

3.1 AKL-Toussaint 算法

3.2 Graham-Andrew 算法 (单调链)

3.3 QuickHull (Bykat) 算法

3.4 Jarvis 步进算法 (Gift Wrapping)

4. 三维凸包实现

4.1 核心类设计

4.2 增量式算法

5. 高维凸包 (Convex_hull_d)

5.1 单纯复形表示

5.2 QuickHull 算法实现

6. 使用示例

6.1 二维凸包基本用法

6.2 使用 Traits 适配器

6.3 三维凸包

6.4 高维凸包

7. 复杂度分析

7.1 时间复杂度

7.2 空间复杂度

8. 关键文件位置

9. 注意事项