11.1 Voronoi图与Delaunay对偶

Voronoi图与 Delaunay三角剖分互为对偶，这种对偶关系是计算几何中最重要、最有用的性质之一。

11.1.1 Voronoi图：空间的势力范围划分

想象一下，在一片广袤的草原上分布着若干座水源（水井）。对于草原上的任意一点，牧民们自然会去最近的水源取水。如果我们把每座水源的”势力范围”——即距离该水源最近的所有点的集合——划分出来，就得到了Voronoi图。

Voronoi图（Voronoi Diagram）是计算几何中最基础、最重要的结构之一。给定平面上的一组站点（sites，可以是点、线段或其他几何对象），Voronoi图将平面划分为若干个区域，每个区域对应一个站点，区域内任意一点到对应站点的距离都不大于到其他任何站点的距离。

数学定义

设 $S = {s_{1}, s_{2}, ..., s_{n}}$ 是平面上的站点集合。站点 $s_{i}$ 的Voronoi单元（Voronoi Cell）定义为：

$V (s_{i}) = {p \in R^{2} : d (p, s_{i}) \leq d (p, s_{j}), \forall j \neq = i}$

其中 $d (p, s)$ 表示点 $p$ 到站点 $s$ 的距离（通常是欧几里得距离）。

整个Voronoi图就是所有Voronoi单元的并集：

$V D (S) = ⋃_{i = 1}^{n} V (s_{i})$

Voronoi单元的边界

两个相邻Voronoi单元的边界是平分线（bisector）的一部分。对于两个点站点 $p_{i}$ 和 $p_{j}$ ，它们的平分线是连接这两点的线段的垂直平分线：

$B (p_{i}, p_{j}) = {x \in R^{2} : d (x, p_{i}) = d (x, p_{j})}$

ASCII图示：两点Voronoi图

    站点A                    站点B
      *                        *
       \                      /
        \                    /
         \        |        /
          \       |       /
           \      |      /
            \     |     /
             \    |    /
              \   |   /
               \  |  /
                \ | /
                 \|/
    -------------*-------------  <-- 垂直平分线（Voronoi边）
                 /|\
                / | \
               /  |  \
              /   |   \
             /    |    \
            /     |     \
           /      |      \
          /       |       \
         /        |        \
        /                    \
       /                      \
      *                        *
    区域A                    区域B

Voronoi图的组成元素

一个完整的Voronoi图由以下元素构成：

Voronoi顶点（Voronoi Vertices）：三个或更多Voronoi单元的交点，到对应三个或更多站点的距离相等。
Voronoi边（Voronoi Edges）：两个Voronoi单元的公共边界，是平分线的一部分。
Voronoi面（Voronoi Faces）：每个站点对应的Voronoi单元内部区域。

ASCII图示：多点Voronoi图

                    站点1
                      *
                     /|\
                    / | \
                   /  |  \
                  /   |   \
                 /    |    \
                /     |     \
               /   V1 |      \
              /       |       \
    站点2 *--+--------+--* 站点3
            |\       /|
            | \  V2  / |
            |  \    /  |
            |   \  /   |
            |    \/    |
            |    /\    |
            |   /  \   |
            |  / V3 \  |
            | /      \ |
            |/        \|
    站点4 *-+----------+-* 站点5
              \        /
               \  V4  /
                \    /
                 \  /
                  \/
                  *
               站点6

    V1-V4: Voronoi单元（势力范围）
    线条: Voronoi边（平分线）
    交点: Voronoi顶点

无限Voronoi单元

位于点集凸包边界上的站点，其Voronoi单元是无界的（unbounded），即延伸到无穷远。这些单元至少有一条Voronoi边是射线而非线段。

                    凸包边界
    ------------------------------------------
         \          |          /
          \    V1  |    V2   /
           \       |       /
            \      |      /
             \     |     /
              \    |    /
               \   |   /
                \  |  /
    站点1 *------\-|-/------* 站点2
                  \|/
                   *
                站点3

    V1和V2: 无界Voronoi单元（延伸到凸包外）
    V3: 有界Voronoi单元（在凸包内部）

11.1.2 Delaunay与Voronoi的对偶关系

Voronoi图与Delaunay三角化之间存在着深刻而优美的对偶关系（duality）。这种对偶关系是计算几何中最重要、最有用的性质之一。

对偶图的概念

在图论中，一个平面图的对偶图是这样构造的：

原图的每个面对应对偶图的一个顶点
原图的每条边对应对偶图的一条边
原图的每个顶点对应对偶图的一个面

Voronoi-Delaunay对偶

Voronoi图与Delaunay三角化互为对偶：

Voronoi图	Delaunay三角化
Voronoi顶点	Delaunay三角形（面）
Voronoi边	Delaunay边
Voronoi面（单元）	Delaunay顶点（站点）

ASCII图示：对偶关系

    Voronoi图（实线）          Delaunay三角化（虚线）
    
         * 站点1                 * 站点1
        /|\                     /|\
       / | \                   / | \
      /  |  \                 /  |  \
     /   |   \               /   |   \
    /    |    \             /    |    \
   /  V1 |  V2 \           /  D1 |  D2 \
  /      |      \         /      |      \
 *-------*-------*       *-------*-------*
站点2   顶点    站点3   站点2   边    站点3
  \  V3  |  V4  /         \  D3  |  D4  /
   \     |     /           \     |     /
    \    |    /             \    |    /
     \   |   /               \   |   /
      \  |  /                 \  |  /
       \ | /                   \ | /
        \|/                     \|/
         * 站点4                 * 站点4

    V: Voronoi单元              D: Delaunay三角形
    *: Voronoi顶点（Delaunay    虚线: Delaunay边（Voronoi
       三角形外接圆圆心）          边的垂直平分线）

空圆性质（Empty Circle Property）

Delaunay三角化的核心性质——空圆性质，在Voronoi图中有着直观的几何解释：

一个三角形是Delaunay三角形，当且仅当其外接圆内部不包含任何站点。

在Voronoi图中，这个性质表现为：

每个Voronoi顶点是三个（或更多）站点的外接圆圆心
这个外接圆恰好通过这三个站点，且内部不包含其他站点

ASCII图示：空圆性质

              站点A
                *
               /|\
              / | \
             /  |  \
            /   |   \
           /    |    \
          /  空 | 圆  \
         /      |      \
        /       |       \
    站点B *-----O-----* 站点C
               |
               | Voronoi顶点
               | （外接圆圆心）
               |
               *
            站点D
            （在圆外）

    O是站点A、B、C的Voronoi顶点
    圆通过A、B、C三点，内部无其他站点
    因此三角形ABC是Delaunay三角形

对偶关系的应用

这种对偶关系具有重要的实际意义：

计算效率：可以先计算Delaunay三角化（通常更快），再通过对偶关系得到Voronoi图
数据结构复用：Voronoi图和Delaunay三角化可以共享底层数据结构
算法设计：许多Voronoi图相关的问题可以转化为Delaunay三角化上的问题

11.1.3 CGAL Voronoi图架构

CGAL的Voronoi_diagram_2包采用了一种独特的适配器模式（Adapter Pattern）设计，将Voronoi图作为Delaunay三角化的适配器来实现。

架构设计

    +-------------------------------------------+
    |         Voronoi_diagram_2<DG, AT, AP>      |
    |                                            |
    |  +--------------------------------------+  |
    |  |  Adaptation Traits (AT)              |  |
    |  |  - 定义Site_2类型                     |  |
    |  |  - 提供访问站点的方法                  |  |
    |  |  - 实现最近站点查询                    |  |
    |  +--------------------------------------+  |
    |                                            |
    |  +--------------------------------------+  |
    |  |  Adaptation Policy (AP)              |  |
    |  |  - 退化情况处理策略                    |  |
    |  |  - 边/面拒绝器                        |  |
    |  |  - 站点插入/删除策略                   |  |
    |  +--------------------------------------+  |
    |                                            |
    |  +--------------------------------------+  |
    |  |  Delaunay Graph (DG)                 |  |
    |  |  - Delaunay_triangulation_2          |  |
    |  |  - Segment_Delaunay_graph_2          |  |
    |  |  - Apollonius_graph_2                |  |
    |  +--------------------------------------+  |
    +-------------------------------------------+

核心组件

1. Delaunay Graph (DG)

这是底层的三角化结构，可以是：

Delaunay_triangulation_2：标准点集Delaunay三角化
Segment_Delaunay_graph_2：线段Delaunay图
Apollonius_graph_2：Apollonius图（加权点Voronoi）
Regular_triangulation_2：正则三角化

2. Adaptation Traits (AT)

适配器特征类定义了如何从Delaunay图获取Voronoi图所需的信息：

template<class DT2>
struct Delaunay_triangulation_adaptation_traits_2
{
  typedef typename DT2::Geom_traits::Point_2  Point_2;
  typedef Point_2                             Site_2;  // 站点类型
  
  // 提供访问站点的方法
  // 提供最近站点查询
  // 提供对偶点构造
};

3. Adaptation Policy (AP)

适配策略类处理退化情况，如共线点、重合点等：

template<class DT2>
struct Delaunay_triangulation_caching_degeneracy_removal_policy_2
{
  // 边拒绝器：决定哪些边应该被过滤
  // 面拒绝器：决定哪些面应该被过滤
  // 站点插入器：如何插入新站点
};

类型映射

Voronoi_diagram_2通过适配器将Delaunay图的类型映射为Voronoi图的类型：

Voronoi图类型	Delaunay图类型	说明
`Vertex`	`Face_handle`	Voronoi顶点是Delaunay面的对偶
`Face`	`Vertex_handle`	Voronoi面是Delaunay顶点的对偶
`Halfedge`	`Edge`	Voronoi边是Delaunay边的对偶

// Voronoi图类型定义示例
typedef CGAL::Exact_predicates_inexact_constructions_kernel  K;
typedef CGAL::Delaunay_triangulation_2<K>                    DT;
typedef CGAL::Delaunay_triangulation_adaptation_traits_2<DT> AT;
typedef CGAL::Delaunay_triangulation_caching_degeneracy_removal_policy_2<DT> AP;
typedef CGAL::Voronoi_diagram_2<DT, AT, AP>                  VD;
 
// 类型映射
VD::Vertex_handle    v;  // 对应 DT::Face_handle
VD::Face_handle      f;  // 对应 DT::Vertex_handle
VD::Halfedge_handle  e;  // 对应 DT::Edge

迭代器与循环器

Voronoi_diagram_2提供了丰富的迭代器和循环器用于遍历：

// 顶点迭代器（遍历所有Voronoi顶点）
for (VD::Vertex_iterator vit = vd.vertices_begin(); 
     vit != vd.vertices_end(); ++vit) {
  // vit->point() 返回Voronoi顶点的坐标
}
 
// 面迭代器（遍历所有Voronoi单元）
for (VD::Face_iterator fit = vd.faces_begin(); 
     fit != vd.faces_end(); ++fit) {
  // *fit 是一个Voronoi单元
}
 
// 半边迭代器（遍历所有Voronoi边）
for (VD::Halfedge_iterator hit = vd.halfedges_begin(); 
     hit != vd.halfedges_end(); ++hit) {
  // *hit 是一条Voronoi边
}
 
// 有界/无界面迭代器
for (VD::Bounded_faces_iterator bfit = vd.bounded_faces_begin();
     bfit != vd.bounded_faces_end(); ++bfit) {
  // 只遍历有界的Voronoi单元
}
 
for (VD::Unbounded_faces_iterator ufit = vd.unbounded_faces_begin();
     ufit != vd.unbounded_faces_end(); ++ufit) {
  // 只遍历无界的Voronoi单元
}

点定位（Point Location）

Voronoi_diagram_2支持高效的点定位查询：

// 定位查询点所在的Voronoi特征
VD::Point_2 query_point(x, y);
VD::Locate_result result = vd.locate(query_point);
 
// 使用std::variant访问结果
if (VD::Face_handle* f = std::get_if<VD::Face_handle>(&result)) {
  // 查询点在某个Voronoi面内部
  std::cout << "In face of site: " << (*f)->dual()->point() << std::endl;
} 
else if (VD::Halfedge_handle* e = std::get_if<VD::Halfedge_handle>(&result)) {
  // 查询点在Voronoi边上
  std::cout << "On edge" << std::endl;
}
else if (VD::Vertex_handle* v = std::get_if<VD::Vertex_handle>(&result)) {
  // 查询点在Voronoi顶点上
  std::cout << "At vertex: " << (*v)->point() << std::endl;
}

11.1.4 特殊类型的Voronoi图

CGAL支持多种类型的Voronoi图，每种对应不同的站点类型和距离度量。

点集Voronoi图（标准）

这是最常用的Voronoi图类型，站点是平面上的点。

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Voronoi_diagram_2.h>
#include <CGAL/Delaunay_triangulation_adaptation_traits_2.h>
#include <CGAL/Delaunay_triangulation_adaptation_policies_2.h>
#include <iostream>
#include <fstream>
#include <vector>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel                  K;
typedef CGAL::Delaunay_triangulation_2<K>                                    DT;
typedef CGAL::Delaunay_triangulation_adaptation_traits_2<DT>                 AT;
typedef CGAL::Delaunay_triangulation_caching_degeneracy_removal_policy_2<DT> AP;
typedef CGAL::Voronoi_diagram_2<DT, AT, AP>                                  VD;
 
typedef K::Point_2                    Point_2;
typedef AT::Site_2                    Site_2;
 
int main()
{
  // 创建Voronoi图
  VD vd;
  
  // 插入站点
  std::vector<Point_2> points = {
    Point_2(0, 0),
    Point_2(100, 0),
    Point_2(100, 100),
    Point_2(0, 100),
    Point_2(50, 50)
  };
  
  for (const auto& p : points) {
    vd.insert(p);
  }
  
  // 验证有效性
  if (!vd.is_valid()) {
    std::cerr << "Voronoi diagram is invalid!" << std::endl;
    return 1;
  }
  
  // 输出统计信息
  std::cout << "Number of Voronoi vertices: " 
            << vd.number_of_vertices() << std::endl;
  std::cout << "Number of Voronoi faces: " 
            << vd.number_of_faces() << std::endl;
  std::cout << "Number of Voronoi halfedges: " 
            << vd.number_of_halfedges() << std::endl;
  
  // 遍历所有Voronoi顶点（对应Delaunay三角形的外心）
  std::cout << "\nVoronoi vertices (Delaunay circumcenters):" << std::endl;
  for (VD::Vertex_iterator vit = vd.vertices_begin(); 
       vit != vd.vertices_end(); ++vit) {
    std::cout << "  " << vit->point() << std::endl;
  }
  
  // 遍历所有Voronoi面（对应原始站点）
  std::cout << "\nVoronoi faces correspond to sites:" << std::endl;
  for (VD::Face_iterator fit = vd.faces_begin(); 
       fit != vd.faces_end(); ++fit) {
    // 通过dual访问对应的Delaunay顶点（即站点）
    std::cout << "  Site: " << fit->dual()->point() << std::endl;
  }
  
  return 0;
}

线段Voronoi图（Segment Delaunay Graph）

当站点是线段而非点时，Voronoi图的边不再是直线，而是由直线段和抛物线段组成的曲线。

几何特性：

点到线段的距离是点到线段上最近点的距离
两条线段的平分线可能是直线（平行线段）或抛物线（相交线段）

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Segment_Delaunay_graph_2.h>
#include <CGAL/Segment_Delaunay_graph_traits_2.h>
#include <iostream>
#include <fstream>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel  K;
typedef CGAL::Segment_Delaunay_graph_traits_2<K>             Gt;
typedef CGAL::Segment_Delaunay_graph_2<Gt>                   SDG2;
 
typedef Gt::Site_2             Site_2;
typedef K::Point_2             Point_2;
typedef K::Segment_2           Segment_2;
 
int main()
{
  SDG2 sdg;
  
  // 创建线段站点
  // 方法1：直接指定端点
  Site_2 s1 = Site_2::construct_site_2(Point_2(0, 0), Point_2(100, 0));
  Site_2 s2 = Site_2::construct_site_2(Point_2(50, 50), Point_2(50, -50));
  Site_2 s3 = Site_2::construct_site_2(Point_2(100, 100), Point_2(0, 100));
  
  // 方法2：从线段构造
  Segment_2 seg(Point_2(100, 0), Point_2(100, 100));
  Site_2 s4 = Site_2::construct_site_2(seg);
  
  // 插入站点
  sdg.insert(s1);
  sdg.insert(s2);
  sdg.insert(s3);
  sdg.insert(s4);
  
  // 验证
  if (!sdg.is_valid()) {
    std::cerr << "Segment Delaunay graph is invalid!" << std::endl;
    return 1;
  }
  
  std::cout << "Number of input sites: " << sdg.number_of_input_sites() << std::endl;
  std::cout << "Number of output sites: " << sdg.number_of_output_sites() << std::endl;
  
  // 遍历Voronoi边（对偶于Segment Delaunay图的边）
  int edge_count = 0;
  for (SDG2::Finite_edges_iterator eit = sdg.finite_edges_begin();
       eit != sdg.finite_edges_end(); ++eit, ++edge_count) {
    
    SDG2::Edge e = *eit;
    
    // 获取定义Voronoi边的四个站点
    // 每条Voronoi边由两个相邻的Delaunay边定义
    SDG2::Vertex_handle v[] = {
      e.first->vertex(sdg.ccw(e.second)),
      e.first->vertex(sdg.cw(e.second)),
      e.first->vertex(e.second),
      sdg.tds().mirror_vertex(e.first, e.second)
    };
    
    std::cout << "Edge " << edge_count << ":" << std::endl;
    for (int i = 0; i < 4; i++) {
      if (sdg.is_infinite(v[i])) {
        std::cout << "  [infinite]" << std::endl;
      } else {
        std::cout << "  " << v[i]->site() << std::endl;
      }
    }
  }
  
  return 0;
}

ASCII图示：线段Voronoi图

    线段A
    =====
      |        抛物线边界
      |      /
      |     /
      |    /
      |   /  区域A
      |  /
      | /
      |/__________
      /|          |
     / |          | 线段B
    /  |          |
   /   |__________|
  /
 / 区域B
/

    两条相交线段的Voronoi边界是抛物线
    两条平行线段的Voronoi边界是直线

圆形Voronoi图

圆形可以看作带权重的点（权重为半径平方），其Voronoi图是Apollonius图的特例。

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Apollonius_graph_2.h>
#include <CGAL/Apollonius_graph_filtered_traits_2.h>
#include <iostream>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel  K;
typedef CGAL::Apollonius_graph_filtered_traits_2<K>          Traits;
typedef CGAL::Apollonius_graph_2<Traits>                     Apollonius_graph;
 
typedef Traits::Site_2          Site_2;
typedef K::Point_2              Point_2;
 
int main()
{
  Apollonius_graph ag;
  
  // 插入圆形站点（带权重点）
  // Site_2(Point_2(x, y), weight)
  // 对于圆形，weight = radius^2
  
  Site_2 c1(Point_2(0, 0), 100);     // 圆心(0,0)，半径10
  Site_2 c2(Point_2(30, 0), 25);     // 圆心(30,0)，半径5
  Site_2 c3(Point_2(15, 25), 64);    // 圆心(15,25)，半径8
  Site_2 c4(Point_2(15, -20), 36);   // 圆心(15,-20)，半径6
  
  ag.insert(c1);
  ag.insert(c2);
  ag.insert(c3);
  ag.insert(c4);
  
  if (!ag.is_valid()) {
    std::cerr << "Apollonius graph is invalid!" << std::endl;
    return 1;
  }
  
  std::cout << "Number of visible sites: " 
            << ag.number_of_visible_sites() << std::endl;
  std::cout << "Number of hidden sites: " 
            << ag.number_of_hidden_sites() << std::endl;
  
  // 最近邻查询
  Point_2 query(15, 5);
  Apollonius_graph::Vertex_handle nearest = ag.nearest_neighbor(query);
  if (nearest != Apollonius_graph::Vertex_handle()) {
    std::cout << "Nearest site to query point: " 
              << nearest->site() << std::endl;
  }
  
  return 0;
}

11.1.5 Apollonius图：加权的势力范围

Apollonius图（Apollonius Diagram），也称为加权势能Voronoi图（Additively Weighted Voronoi Diagram），是标准Voronoi图的推广。在这种图中，每个站点是一个带权重的点（weighted point），可以直观地理解为一个具有”影响力半径”的中心点。

加权距离

对于带权重点 $s = (p, w)$ ，其中 $p$ 是位置， $w$ 是权重（通常 $w = r^{2}$ ， $r$ 是半径），点 $x$ 到 $s$ 的加权距离定义为：

$d_{w} (x, s) = ∥ x - p ∥^{2} - w$

或者使用Apollonius距离（带符号距离）：

$d_{A} (x, s) = ∥ x - p ∥ - w$

隐藏站点

Apollonius图的一个重要特性是站点隐藏（site hiding）：

如果一个站点A完全位于另一个站点B的”势力范围”内（即A的加权距离在B的边界内），则A被B隐藏，在Apollonius图中不可见。

ASCII图示：站点隐藏

    大圆（权重100）
         *********
      ***         ***
    **      小圆     **
   *    *  (权重25)    *
  *   *    *    *       *
 *  *   隐藏   *   *      *
 * *  站点    *     *     *
* *  (不可见) *       *    *
* *          *         *   *
* *         *           *  *
* *        *             * *
 * *      *               *
 *  *    *               *
  *  ****               *
   *                   *
    **               **
      ***         ***
         *********

    小圆完全在大圆内部，被大圆"隐藏"
    在Apollonius图中，小圆不产生Voronoi单元

Apollonius边

两个带权重点的Apollonius平分线是一个双曲线（如果权重不同）或直线（如果权重相同）。

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Apollonius_graph_2.h>
#include <CGAL/Apollonius_graph_filtered_traits_2.h>
#include <CGAL/MP_Float.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>
 
// 使用精确数类型进行几何计算
typedef CGAL::MP_Float                                          NT;
typedef CGAL::Simple_cartesian<NT>                              K;
typedef CGAL::Apollonius_graph_filtered_traits_2<K>             Traits;
typedef CGAL::Apollonius_graph_2<Traits>                        Apollonius_graph;
 
typedef Traits::Site_2    Site_2;
typedef K::Point_2        Point_2;
 
int main()
{
  // 批量插入站点（使用空间排序优化）
  std::vector<Site_2> sites;
  
  // 创建带权重点站点
  sites.push_back(Site_2(Point_2(0, 0), 100));      // 半径10
  sites.push_back(Site_2(Point_2(25, 0), 25));      // 半径5
  sites.push_back(Site_2(Point_2(12.5, 20), 64));   // 半径8
  sites.push_back(Site_2(Point_2(12.5, -15), 36));  // 半径6
  sites.push_back(Site_2(Point_2(50, 50), 144));    // 半径12
  
  Apollonius_graph ag;
  
  // 批量插入（自动按权重降序排序以优化性能）
  ag.insert(sites.begin(), sites.end());
  
  // 验证
  assert(ag.is_valid(true, 1));
  
  std::cout << "Total sites inserted: " << sites.size() << std::endl;
  std::cout << "Visible sites: " << ag.number_of_visible_sites() << std::endl;
  std::cout << "Hidden sites: " << ag.number_of_hidden_sites() << std::endl;
  
  // 遍历所有可见站点
  std::cout << "\nVisible sites:" << std::endl;
  for (Apollonius_graph::Visible_sites_iterator vit = ag.visible_sites_begin();
       vit != ag.visible_sites_end(); ++vit) {
    std::cout << "  Point: (" << vit->point().x() << ", " 
              << vit->point().y() << "), Weight: " << vit->weight() << std::endl;
  }
  
  // 最近邻查询示例
  std::cout << "\nNearest neighbor queries:" << std::endl;
  std::vector<Point_2> queries = {
    Point_2(10, 5),
    Point_2(30, 20),
    Point_2(-10, -10)
  };
  
  for (const auto& q : queries) {
    Apollonius_graph::Vertex_handle nearest = ag.nearest_neighbor(q);
    if (nearest != Apollonius_graph::Vertex_handle()) {
      std::cout << "Query (" << q.x() << ", " << q.y() << ") -> Nearest: ("
                << nearest->site().point().x() << ", "
                << nearest->site().point().y() << ")" << std::endl;
    }
  }
  
  return 0;
}

Apollonius图层次结构

对于大量站点，可以使用Apollonius_graph_hierarchy_2获得更好的查询性能：

#include <CGAL/Apollonius_graph_hierarchy_2.h>
 
typedef CGAL::Apollonius_graph_hierarchy_2<Traits>  Apollonius_hierarchy;
 
int main()
{
  Apollonius_hierarchy agh;
  
  // 插入大量站点
  for (int i = 0; i < 10000; ++i) {
    Point_2 p(rand() % 1000, rand() % 1000);
    NT weight(rand() % 100);
    agh.insert(Site_2(p, weight));
  }
  
  // 层次结构提供O(log n)的最近邻查询
  Point_2 query(500, 500);
  Apollonius_hierarchy::Vertex_handle nearest = agh.nearest_neighbor(query);
  
  return 0;
}

11.1.6 代码实现详解

本节提供完整的、可直接编译运行的代码示例。

完整示例1：基础Voronoi图操作

// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
// file: basic_voronoi.cpp
 
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Voronoi_diagram_2.h>
#include <CGAL/Delaunay_triangulation_adaptation_traits_2.h>
#include <CGAL/Delaunay_triangulation_adaptation_policies_2.h>
#include <CGAL/draw_voronoi_diagram_2.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>
 
// 类型定义
typedef CGAL::Exact_predicates_inexact_constructions_kernel                  K;
typedef CGAL::Delaunay_triangulation_2<K>                                    DT;
typedef CGAL::Delaunay_triangulation_adaptation_traits_2<DT>                 AT;
typedef CGAL::Delaunay_triangulation_caching_degeneracy_removal_policy_2<DT> AP;
typedef CGAL::Voronoi_diagram_2<DT, AT, AP>                                  VD;
 
typedef K::Point_2                    Point_2;
typedef AT::Site_2                    Site_2;
 
typedef VD::Locate_result             Locate_result;
typedef VD::Vertex_handle             Vertex_handle;
typedef VD::Face_handle               Face_handle;
typedef VD::Halfedge_handle           Halfedge_handle;
typedef VD::Ccb_halfedge_circulator   Ccb_halfedge_circulator;
 
// 打印半边端点
void print_endpoint(Halfedge_handle e, bool is_src) {
  std::cout << "\t";
  if (is_src) {
    if (e->has_source()) {
      std::cout << "Source: " << e->source()->point() << std::endl;
    } else {
      std::cout << "Source: point at infinity" << std::endl;
    }
  } else {
    if (e->has_target()) {
      std::cout << "Target: " << e->target()->point() << std::endl;
    } else {
      std::cout << "Target: point at infinity" << std::endl;
    }
  }
}
 
// 打印Voronoi单元信息
void print_face_info(Face_handle f) {
  std::cout << "Voronoi Face Information:" << std::endl;
  std::cout << "  Corresponding site: " << f->dual()->point() << std::endl;
  
  // 遍历该面的边界
  Ccb_halfedge_circulator ec_start = f->ccb();
  Ccb_halfedge_circulator ec = ec_start;
  int edge_count = 0;
  
  std::cout << "  Boundary edges:" << std::endl;
  do {
    std::cout << "    Edge " << edge_count++ << ": ";
    if (ec->has_source() && ec->has_target()) {
      std::cout << ec->source()->point() << " -> " << ec->target()->point();
    } else {
      std::cout << "[unbounded edge]";
    }
    std::cout << std::endl;
    ++ec;
  } while (ec != ec_start);
}
 
int main(int argc, char* argv[])
{
  VD vd;
  
  // 方式1：从文件读取站点
  if (argc > 1) {
    std::ifstream ifs(argv[1]);
    if (ifs) {
      Site_2 site;
      while (ifs >> site) {
        vd.insert(site);
      }
      ifs.close();
    }
  } else {
    // 方式2：使用预定义点集
    std::vector<Point_2> points = {
      Point_2(0, 0),
      Point_2(100, 0),
      Point_2(100, 100),
      Point_2(0, 100),
      Point_2(50, 50),
      Point_2(200, 50),
      Point_2(150, 150)
    };
    
    for (const auto& p : points) {
      vd.insert(p);
    }
  }
  
  // 验证Voronoi图的有效性
  if (!vd.is_valid()) {
    std::cerr << "Error: Voronoi diagram is invalid!" << std::endl;
    return 1;
  }
  
  std::cout << "=== Voronoi Diagram Statistics ===" << std::endl;
  std::cout << "Number of sites: " << vd.number_of_faces() << std::endl;
  std::cout << "Number of Voronoi vertices: " << vd.number_of_vertices() << std::endl;
  std::cout << "Number of Voronoi halfedges: " << vd.number_of_halfedges() << std::endl;
  std::cout << "Number of connected components: " << vd.number_of_connected_components() << std::endl;
  
  // 统计有界和无界面
  size_t bounded_count = 0;
  size_t unbounded_count = 0;
  for (VD::Face_iterator fit = vd.faces_begin(); fit != vd.faces_end(); ++fit) {
    if (fit->is_unbounded()) {
      ++unbounded_count;
    } else {
      ++bounded_count;
    }
  }
  std::cout << "Bounded faces: " << bounded_count << std::endl;
  std::cout << "Unbounded faces: " << unbounded_count << std::endl;
  
  // 打印所有Voronoi顶点（Delaunay外接圆圆心）
  std::cout << "\n=== Voronoi Vertices (Circumcenters) ===" << std::endl;
  int vertex_id = 0;
  for (VD::Vertex_iterator vit = vd.vertices_begin(); 
       vit != vd.vertices_end(); ++vit, ++vertex_id) {
    std::cout << "Vertex " << vertex_id << ": " << vit->point() << std::endl;
  }
  
  // 点定位查询
  std::cout << "\n=== Point Location Queries ===" << std::endl;
  std::vector<Point_2> queries = {
    Point_2(50, 50),    // 在Voronoi面内部
    Point_2(50, 0),     // 可能在Voronoi边上
    Point_2(50, 50)     // 重复测试
  };
  
  for (const auto& p : queries) {
    std::cout << "\nQuery point: (" << p.x() << ", " << p.y() << ")" << std::endl;
    
    Locate_result lr = vd.locate(p);
    
    if (Vertex_handle* v = std::get_if<Vertex_handle>(&lr)) {
      std::cout << "  Located on Voronoi VERTEX" << std::endl;
      std::cout << "  Vertex position: " << (*v)->point() << std::endl;
    } 
    else if (Halfedge_handle* e = std::get_if<Halfedge_handle>(&lr)) {
      std::cout << "  Located on Voronoi EDGE" << std::endl;
      print_endpoint(*e, true);
      print_endpoint(*e, false);
    } 
    else if (Face_handle* f = std::get_if<Face_handle>(&lr)) {
      std::cout << "  Located in Voronoi FACE" << std::endl;
      std::cout << "  Nearest site: " << (*f)->dual()->point() << std::endl;
    }
  }
  
  // 遍历特定面的边界
  std::cout << "\n=== First Voronoi Face Details ===" << std::endl;
  if (vd.faces_begin() != vd.faces_end()) {
    print_face_info(vd.faces_begin());
  }
  
  // 可选：可视化（需要CGAL_Qt5支持）
  // CGAL::draw(vd);
  
  return 0;
}

完整示例2：线段Voronoi图与最短路径

// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
// file: segment_voronoi_shortest_path.cpp
 
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Segment_Delaunay_graph_2.h>
#include <CGAL/Segment_Delaunay_graph_filtered_traits_2.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel  K;
typedef CGAL::Segment_Delaunay_graph_filtered_traits_2<K>    Gt;
typedef CGAL::Segment_Delaunay_graph_2<Gt>                   SDG2;
 
typedef Gt::Site_2             Site_2;
typedef K::Point_2             Point_2;
typedef K::Segment_2           Segment_2;
 
// 简化版最短路径计算（基于Voronoi图）
// 实际应用需要更复杂的图算法
struct ShortestPathNode {
  Point_2 point;
  double distance;
  int parent;
  
  bool operator>(const ShortestPathNode& other) const {
    return distance > other.distance;
  }
};
 
// 计算两点间欧几里得距离
double distance(const Point_2& p1, const Point_2& p2) {
  double dx = p1.x() - p2.x();
  double dy = p1.y() - p2.y();
  return std::sqrt(dx * dx + dy * dy);
}
 
int main(int argc, char* argv[])
{
  SDG2 sdg;
  
  // 定义障碍物（线段）
  std::vector<Segment_2> obstacles;
  
  if (argc > 1) {
    // 从文件读取
    std::ifstream ifs(argv[1]);
    if (ifs) {
      Site_2 site;
      while (ifs >> site) {
        sdg.insert(site);
      }
    }
  } else {
    // 创建示例障碍物环境
    // 水平墙
    obstacles.push_back(Segment_2(Point_2(20, 30), Point_2(80, 30)));
    obstacles.push_back(Segment_2(Point_2(20, 70), Point_2(80, 70)));
    
    // 垂直墙
    obstacles.push_back(Segment_2(Point_2(30, 20), Point_2(30, 80)));
    obstacles.push_back(Segment_2(Point_2(70, 20), Point_2(70, 80)));
    
    // 对角线障碍物
    obstacles.push_back(Segment_2(Point_2(0, 100), Point_2(100, 0)));
    
    // 插入到Segment Delaunay Graph
    for (const auto& seg : obstacles) {
      sdg.insert(Site_2::construct_site_2(seg));
    }
  }
  
  if (!sdg.is_valid()) {
    std::cerr << "Segment Delaunay graph is invalid!" << std::endl;
    return 1;
  }
  
  std::cout << "=== Segment Voronoi Diagram Statistics ===" << std::endl;
  std::cout << "Number of input sites: " << sdg.number_of_input_sites() << std::endl;
  std::cout << "Number of output sites: " << sdg.number_of_output_sites() << std::endl;
  
  // 分析Voronoi边
  std::cout << "\n=== Voronoi Edge Analysis ===" << std::endl;
  
  int finite_edge_count = 0;
  int infinite_edge_count = 0;
  
  // 遍历所有边（包括无限边）
  for (SDG2::All_edges_iterator eit = sdg.all_edges_begin();
       eit != sdg.all_edges_end(); ++eit) {
    if (sdg.is_infinite(*eit)) {
      ++infinite_edge_count;
    } else {
      ++finite_edge_count;
    }
  }
  
  std::cout << "Finite edges: " << finite_edge_count << std::endl;
  std::cout << "Infinite edges: " << infinite_edge_count << std::endl;
  
  // 遍历有限边并分析
  std::cout << "\n=== Finite Voronoi Edges ===" << std::endl;
  int edge_id = 0;
  for (SDG2::Finite_edges_iterator eit = sdg.finite_edges_begin();
       eit != sdg.finite_edges_end(); ++eit, ++edge_id) {
    
    SDG2::Edge e = *eit;
    
    // 获取定义这条Voronoi边的站点
    SDG2::Vertex_handle v[] = {
      e.first->vertex(sdg.ccw(e.second)),
      e.first->vertex(sdg.cw(e.second)),
      e.first->vertex(e.second),
      sdg.tds().mirror_vertex(e.first, e.second)
    };
    
    std::cout << "Edge " << edge_id << " defined by sites:" << std::endl;
    for (int i = 0; i < 4; ++i) {
      if (!sdg.is_infinite(v[i])) {
        Site_2 site = v[i]->site();
        if (site.is_point()) {
          std::cout << "  [" << i << "] Point: (" 
                    << site.point().x() << ", " << site.point().y() << ")" << std::endl;
        } else if (site.is_segment()) {
          std::cout << "  [" << i << "] Segment: ("
                    << site.segment().source().x() << ", " << site.segment().source().y()
                    << ") -> ("
                    << site.segment().target().x() << ", " << site.segment().target().y()
                    << ")" << std::endl;
        }
      }
    }
  }
  
  // 最近邻查询示例
  std::cout << "\n=== Nearest Neighbor Queries ===" << std::endl;
  std::vector<Point_2> queries = {
    Point_2(50, 50),
    Point_2(10, 10),
    Point_2(90, 90)
  };
  
  for (const auto& q : queries) {
    SDG2::Vertex_handle nearest = sdg.nearest_neighbor(q);
    if (nearest != SDG2::Vertex_handle()) {
      Site_2 site = nearest->site();
      std::cout << "Query (" << q.x() << ", " << q.y() << ") -> ";
      if (site.is_point()) {
        std::cout << "Nearest point: (" << site.point().x() 
                  << ", " << site.point().y() << ")" << std::endl;
      } else if (site.is_segment()) {
        std::cout << "Nearest segment" << std::endl;
      }
    }
  }
  
  return 0;
}

完整示例3：Apollonius图与设施选址

// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
// file: apollonius_facility_location.cpp
 
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Apollonius_graph_2.h>
#include <CGAL/Apollonius_graph_filtered_traits_2.h>
#include <CGAL/Apollonius_graph_hierarchy_2.h>
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel  K;
typedef CGAL::Apollonius_graph_filtered_traits_2<K>          Traits;
typedef CGAL::Apollonius_graph_2<Traits>                     Apollonius_graph;
typedef CGAL::Apollonius_graph_hierarchy_2<Traits>           Apollonius_hierarchy;
 
typedef Traits::Site_2    Site_2;
typedef K::Point_2        Point_2;
typedef K::FT             FT;
 
// 设施选址问题：给定一组带权重的设施位置，找到服务范围最优的布局
struct Facility {
  Point_2 location;
  double weight;  // 服务能力（权重越大，服务范围越大）
  int id;
};
 
// 生成随机设施
std::vector<Facility> generate_random_facilities(int n, unsigned seed) {
  std::mt19937 gen(seed);
  std::uniform_real_distribution<> pos_dist(0, 1000);
  std::uniform_real_distribution<> weight_dist(100, 1000);
  
  std::vector<Facility> facilities;
  for (int i = 0; i < n; ++i) {
    facilities.push_back({
      Point_2(pos_dist(gen), pos_dist(gen)),
      weight_dist(gen),
      i
    });
  }
  return facilities;
}
 
// 计算Apollonius距离
double apollonius_distance(const Point_2& p, const Site_2& site) {
  double dx = p.x() - site.point().x();
  double dy = p.y() - site.point().y();
  double euclidean = std::sqrt(dx * dx + dy * dy);
  double radius = std::sqrt(site.weight());
  return euclidean - radius;
}
 
int main()
{
  // 生成随机设施
  int num_facilities = 100;
  auto facilities = generate_random_facilities(num_facilities, 42);
  
  std::cout << "=== Facility Location Problem ===" << std::endl;
  std::cout << "Number of facilities: " << num_facilities << std::endl;
  
  // 方法1：使用普通Apollonius图
  {
    Apollonius_graph ag;
    
    auto start = std::chrono::high_resolution_clock::now();
    
    // 插入所有设施
    for (const auto& f : facilities) {
      ag.insert(Site_2(f.location, f.weight));
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    std::cout << "\n--- Apollonius Graph ---" << std::endl;
    std::cout << "Construction time: " << duration.count() << " ms" << std::endl;
    std::cout << "Visible sites: " << ag.number_of_visible_sites() << std::endl;
    std::cout << "Hidden sites: " << ag.number_of_hidden_sites() << std::endl;
    
    // 查询测试
    std::vector<Point_2> query_points = {
      Point_2(500, 500),
      Point_2(100, 100),
      Point_2(900, 900)
    };
    
    std::cout << "\nNearest facility queries:" << std::endl;
    for (const auto& q : query_points) {
      auto query_start = std::chrono::high_resolution_clock::now();
      auto nearest = ag.nearest_neighbor(q);
      auto query_end = std::chrono::high_resolution_clock::now();
      auto query_time = std::chrono::duration_cast<std::chrono::microseconds>(
        query_end - query_start);
      
      if (nearest != Apollonius_graph::Vertex_handle()) {
        std::cout << "  Query (" << q.x() << ", " << q.y() << "): "
                  << "Nearest facility at (" << nearest->site().point().x()
                  << ", " << nearest->site().point().y() << "), "
                  << "query time: " << query_time.count() << " us" << std::endl;
      }
    }
  }
  
  // 方法2：使用层次结构（更快查询）
  {
    Apollonius_hierarchy agh;
    
    auto start = std::chrono::high_resolution_clock::now();
    
    for (const auto& f : facilities) {
      agh.insert(Site_2(f.location, f.weight));
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    std::cout << "\n--- Apollonius Graph Hierarchy ---" << std::endl;
    std::cout << "Construction time: " << duration.count() << " ms" << std::endl;
    
    // 查询测试（应该更快）
    std::vector<Point_2> query_points = {
      Point_2(500, 500),
      Point_2(100, 100),
      Point_2(900, 900)
    };
    
    std::cout << "\nNearest facility queries (hierarchy):" << std::endl;
    for (const auto& q : query_points) {
      auto query_start = std::chrono::high_resolution_clock::now();
      auto nearest = agh.nearest_neighbor(q);
      auto query_end = std::chrono::high_resolution_clock::now();
      auto query_time = std::chrono::duration_cast<std::chrono::microseconds>(
        query_end - query_start);
      
      if (nearest != Apollonius_hierarchy::Vertex_handle()) {
        std::cout << "  Query (" << q.x() << ", " << q.y() << "): "
                  << "Nearest facility at (" << nearest->site().point().x()
                  << ", " << nearest->site().point().y() << "), "
                  << "query time: " << query_time.count() << " us" << std::endl;
      }
    }
  }
  
  // 分析服务覆盖
  std::cout << "\n=== Service Coverage Analysis ===" << std::endl;
  Apollonius_graph ag;
  for (const auto& f : facilities) {
    ag.insert(Site_2(f.location, f.weight));
  }
  
  // 统计可见设施
  std::cout << "Visible facilities (provide service): " 
            << ag.number_of_visible_sites() << std::endl;
  std::cout << "Hidden facilities (covered by others): " 
            << ag.number_of_hidden_sites() << std::endl;
  
  // 计算覆盖率（简化模型）
  double coverage_ratio = static_cast<double>(ag.number_of_visible_sites()) 
                          / num_facilities;
  std::cout << "Coverage ratio: " << coverage_ratio * 100 << "%" << std::endl;
  
  return 0;
}

11.1.7 应用场景与案例

Voronoi图在计算机科学和工程领域有着广泛的应用。

1. 设施选址问题（Facility Location）

问题描述：给定一组候选位置和客户需求分布，选择最优的设施位置以最小化服务成本。

Voronoi图应用：

每个设施的服务区域即为其Voronoi单元
通过分析Voronoi单元的大小和形状，评估服务均衡性
Apollonius图可处理设施服务能力不同的情况

    客户分布            Voronoi服务区域          优化后布局
    
     *  *  *               |\                      |\
    * * * * *          ----| \----             ----| \----
     *  *  *             / |  \                  / |  \
    -------*---         /  |   \                /  |   \
       F1   *          / V1| V2 \              / V1| V2 \
    * * F2 * *        /    |    \            /    |    \
     *  *  *         /-----F1----F2--       /-----F1----F2--
    * * * * *            V3|V4               优化 |  优化
       F3                F3                  V3  F3  V4
       
    F: 设施位置          原始服务区域          均衡化服务区域

2. 最近邻搜索（Nearest Neighbor Search）

问题描述：在大量数据点中快速找到查询点的最近邻。

Voronoi图应用：

点定位查询直接给出最近邻站点
使用层次结构（如Apollonius_graph_hierarchy_2）可实现O(log n)查询
适用于k-NN搜索、范围查询等变体

// 最近邻搜索示例
VD vd;
// ... 插入站点 ...
 
Point_2 query(x, y);
VD::Locate_result result = vd.locate(query);
 
if (VD::Face_handle* f = std::get_if<VD::Face_handle>(&result)) {
  // 查询点所在的Voronoi面对应的站点就是最近邻
  Point_2 nearest_site = (*f)->dual()->point();
  double distance = std::sqrt(CGAL::squared_distance(query, nearest_site));
}

3. 自然邻域插值（Natural Neighbor Interpolation）

问题描述：根据离散采样点的值，估计任意位置的值。

Voronoi图应用：

自然邻域插值使用Voronoi单元的面积作为权重
当插入查询点时，其”窃取”的Voronoi区域面积比例即为各邻居的权重
产生平滑、局部、无参数的插值结果

    采样点与Voronoi图          插入查询点Q
    
         P1                      P1
          *                       *
         /|\                     /|\
        / | \                   / | \
       /  |  \                 /  |  \
      / V1|V2 \               / V1|V2 \
   P2*----+----*P3         P2*----+----*P3
      \ V3|V4 /               \  |Q|  /
       \  |  /                 \ | | /
        \ | /                   \| |/
          *P4                     *P4
    
    权重w_i = area(V_i(Q)) / area(V(Q))
    插值值 = sum(w_i * value(P_i))

4. 纹理合成（Texture Synthesis）

问题描述：从小样本纹理生成大面积无缝纹理。

Voronoi图应用：

使用Voronoi图进行空间划分
在每个Voronoi单元内放置纹理补丁
在边界处进行融合处理

5. 机器人路径规划

问题描述：在存在障碍物的环境中规划机器人运动路径。

Voronoi图应用：

障碍物作为线段站点构建Segment Voronoi图
Voronoi边代表与障碍物等距的路径
最大化与障碍物的安全距离

    障碍物环境              Voronoi路径
    
    ========               ========
    |      |               |\    /|
    |  障  |               | \  / |
    |  碍  |      ->       |  \/  |
    |  物  |               |  /\  |
    |      |               | /  \ |
    ========               |/    \|
                           ========
                           
    粗线: 障碍物           细线: 安全路径（Voronoi边）

6. 网格生成

问题描述：生成高质量计算网格用于有限元分析。

Voronoi图应用：

Centroidal Voronoi Tessellation (CVT) 用于优化网格点分布
对偶的Delaunay三角化作为网格
最大化最小角，改善网格质量

11.1.8 性能考量与优化

时间复杂度

操作	标准Voronoi	层次结构	说明
构造（n个站点）	O(n log n)	O(n log n)	随机插入
单点插入	O(log n) avg	O(log n)	均摊时间
点定位查询	O(log n)	O(log n)	期望时间
最近邻查询	O(log n)	O(log n)	期望时间
遍历所有边	O(n)	O(n)	线性时间

空间优化

批量插入：使用批量插入而非逐点插入，可利用空间排序优化

// 推荐：批量插入
std::vector<Site_2> sites;
// ... 填充sites ...
vd.insert(sites.begin(), sites.end());

层次结构：对于大量查询操作，使用层次结构（如Apollonius_graph_hierarchy_2）
缓存策略：使用caching_degeneracy_removal_policy缓存退化测试结果

数值稳定性

核选择：
- Exact_predicates_inexact_constructions_kernel：推荐，平衡速度和精度
- Exact_predicates_exact_constructions_kernel：需要精确构造时使用
退化处理：
- 共线点、重合点等退化情况由Adaptation Policy处理
- 使用degeneracy_removal_policy自动过滤退化边

内存使用

Voronoi_diagram_2作为适配器，内存开销主要来自底层的Delaunay图：

每个站点：约100-200字节
每条边：约50-100字节
每个顶点：约50-100字节

对于百万级站点，建议：

使用64位系统
考虑分块处理大数据集
使用流式算法（如果可用）

11.1.9 本章小结

本章深入探讨了Voronoi图及其在CGAL中的实现：

理论基础：Voronoi图将空间划分为各站点的”势力范围”，与Delaunay三角化互为对偶。
CGAL架构：采用适配器模式，Voronoi_diagram_2作为Delaunay图的适配器，支持多种站点类型。
类型支持：
- 点集Voronoi：标准欧几里得Voronoi图
- 线段Voronoi：边界由直线和抛物线组成
- Apollonius图：支持加权站点，处理隐藏站点
核心操作：
- 点定位：O(log n)查询点所在单元
- 最近邻：直接通过对偶关系获得
- 遍历：支持多种迭代器和循环器
应用场景：设施选址、最近邻搜索、自然邻域插值、路径规划、网格生成等。

11.1.10 练习

练习1：基础Voronoi图构造

编写程序读取一组二维点，构造其Voronoi图，并输出：

Voronoi顶点坐标
每个Voronoi单元的顶点数
有界和无界单元的数量

提示：使用VD::Face_iterator遍历所有面，使用Face::is_unbounded()判断是否有界。

练习2：最近邻分类器

实现一个k-NN（k最近邻）分类器：

使用训练数据点构造Voronoi图
对于每个查询点，找到其k个最近邻
根据邻居的类别标签投票决定查询点类别

提示：从查询点所在Voronoi面开始，按距离顺序遍历相邻单元。

练习3：线段障碍物路径规划

给定平面上的线段障碍物，实现：

构造Segment Voronoi图
找到从起点到终点的安全路径（沿Voronoi边）
可视化路径和Voronoi图

提示：使用Segment_Delaunay_graph_2，将Voronoi边作为图的边进行最短路径搜索。

练习4：设施选址优化

给定一组候选设施位置和服务需求分布：

使用Apollonius图建模不同容量的设施
实现模拟退火或遗传算法优化设施布局
目标：最小化最大服务距离，最大化覆盖范围

提示：利用Apollonius_graph_hierarchy_2加速大量最近邻查询。

练习5：自然邻域插值

实现自然邻域插值算法：

构造采样点的Voronoi图
对于查询点，计算插入后各邻居的权重（面积比例）
使用权重进行加权平均插值

提示：需要计算Voronoi单元面积，可使用Ccb_halfedge_circulator遍历单元边界。

延伸阅读：

CGAL Voronoi_diagram_2文档：https://doc.cgal.org/latest/Voronoi_diagram_2/
de Berg et al., “Computational Geometry: Algorithms and Applications”
Aurenhammer, “Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure”

Chunibyo

Explorer

11.1 Voronoi图与Delaunay对偶

11.1 Voronoi图与Delaunay对偶 §

11.1.1 Voronoi图：空间的势力范围划分 §

数学定义 §

Voronoi单元的边界 §

Voronoi图的组成元素 §

无限Voronoi单元 §

11.1.2 Delaunay与Voronoi的对偶关系 §

对偶图的概念 §

Voronoi-Delaunay对偶 §

空圆性质（Empty Circle Property） §

对偶关系的应用 §

11.1.3 CGAL Voronoi图架构 §

架构设计 §

核心组件 §

1. Delaunay Graph (DG) §

2. Adaptation Traits (AT) §

3. Adaptation Policy (AP) §

类型映射 §

迭代器与循环器 §

点定位（Point Location） §

11.1.4 特殊类型的Voronoi图 §

点集Voronoi图（标准） §

线段Voronoi图（Segment Delaunay Graph） §

圆形Voronoi图 §

11.1.5 Apollonius图：加权的势力范围 §

加权距离 §

隐藏站点 §

Apollonius边 §

Apollonius图层次结构 §

11.1.6 代码实现详解 §

完整示例1：基础Voronoi图操作 §

完整示例2：线段Voronoi图与最短路径 §

完整示例3：Apollonius图与设施选址 §

11.1.7 应用场景与案例 §

1. 设施选址问题（Facility Location） §

2. 最近邻搜索（Nearest Neighbor Search） §

3. 自然邻域插值（Natural Neighbor Interpolation） §

4. 纹理合成（Texture Synthesis） §

5. 机器人路径规划 §

6. 网格生成 §

11.1.8 性能考量与优化 §

时间复杂度 §

空间优化 §

数值稳定性 §

内存使用 §

11.1.9 本章小结 §

11.1.10 练习 §

练习1：基础Voronoi图构造 §

练习2：最近邻分类器 §

练习3：线段障碍物路径规划 §

练习4：设施选址优化 §

练习5：自然邻域插值 §

Graph View

Table of Contents

Backlinks

11.1 Voronoi图与Delaunay对偶

11.1.1 Voronoi图：空间的势力范围划分

数学定义

Voronoi单元的边界

Voronoi图的组成元素

无限Voronoi单元

11.1.2 Delaunay与Voronoi的对偶关系

对偶图的概念

Voronoi-Delaunay对偶

空圆性质（Empty Circle Property）

对偶关系的应用

11.1.3 CGAL Voronoi图架构

架构设计

核心组件

1. Delaunay Graph (DG)

2. Adaptation Traits (AT)

3. Adaptation Policy (AP)

类型映射

迭代器与循环器

点定位（Point Location）

11.1.4 特殊类型的Voronoi图

点集Voronoi图（标准）

线段Voronoi图（Segment Delaunay Graph）

圆形Voronoi图

11.1.5 Apollonius图：加权的势力范围

加权距离

隐藏站点

Apollonius边

Apollonius图层次结构

11.1.6 代码实现详解

完整示例1：基础Voronoi图操作

完整示例2：线段Voronoi图与最短路径

完整示例3：Apollonius图与设施选址

11.1.7 应用场景与案例

1. 设施选址问题（Facility Location）

2. 最近邻搜索（Nearest Neighbor Search）

3. 自然邻域插值（Natural Neighbor Interpolation）

4. 纹理合成（Texture Synthesis）

5. 机器人路径规划

6. 网格生成

11.1.8 性能考量与优化

时间复杂度

空间优化

数值稳定性

内存使用

11.1.9 本章小结

11.1.10 练习

练习1：基础Voronoi图构造

练习2：最近邻分类器

练习3：线段障碍物路径规划

练习4：设施选址优化

练习5：自然邻域插值