CCG D03：计算几何：凸包、Voronoi 与 Delaunay

Base Knowledge, Mathematics, 计算共形几何, 02 扩展课程, 04 离散算法与网格, 01 Voronoi、Delaunay 与凸包 2026-10-12 2026-10-12 669 字
# 计算共形几何# 核心算法扩展

模块定位

核心问题：为什么凸包、幂图与 Delaunay 三角剖分贯穿 Ricci 流、最优输运和网格生成？

本页是“大而全”课程中的模块级教学提纲。每一个表格行都将独立成单概念短课；短课必须包含定义、推导、反例、计算例子和带答案自测，不能只给名词解释。

前置知识

  • F02 线性代数
  • F05 数值方法
  • 模块 05 三角网格

逐课目录

编号单概念课展开标准
D03-01方向测试与鲁棒谓词从直觉、定义、最小例子、定理条件到计算用途
D03-02二维凸包从直觉、定义、最小例子、定理条件到计算用途
D03-03增量算法从直觉、定义、最小例子、定理条件到计算用途
D03-04Voronoi 图从直觉、定义、最小例子、定理条件到计算用途
D03-05Delaunay 三角剖分从直觉、定义、最小例子、定理条件到计算用途
D03-06空圆性质从直觉、定义、最小例子、定理条件到计算用途
D03-07lifting 到抛物面从直觉、定义、最小例子、定理条件到计算用途
D03-08局部翻边从直觉、定义、最小例子、定理条件到计算用途
D03-09约束 Delaunay从直觉、定义、最小例子、定理条件到计算用途
D03-10power diagram从直觉、定义、最小例子、定理条件到计算用途
D03-11regular triangulation从直觉、定义、最小例子、定理条件到计算用途
D03-12高维凸包从直觉、定义、最小例子、定理条件到计算用途
D03-13内在 Delaunay从直觉、定义、最小例子、定理条件到计算用途
D03-14数值退化从直觉、定义、最小例子、定理条件到计算用途

理论主线

  • Voronoi-Delaunay 对偶
  • Delaunay 最大化最小角性质
  • lifting 与下凸包等价
  • Ptolemy 翻边与离散共形

计算与证明双线要求

学习本模块时，每个理论点都必须同时回答：

  1. 对象的严格定义是什么；
  2. 最小非平凡例子是什么；
  3. 定理使用了哪些假设；
  4. 去掉假设后有什么反例；
  5. 连续对象怎样离散存储；
  6. 离散算法怎样验证正确性和收敛性。

模块出口能力

  • 实现鲁棒二维 Delaunay
  • 构造 power diagram
  • 在曲面上维护 intrinsic Delaunay 网格

状态说明

本模块已经进入课程总图谱并完成逐课拆分。后续内容扩写按编号进行，不会再把整组理论压回一篇长文章。

许可协议：CC BY
作者：Davids
本文链接：https://hustjjd.github.io/ccg/atlas/delaunay-voronoi/
更新于：2026年10月12日