核心概述：在平面点集上构造德劳内三角剖分（任一三角形外接圆内无其他输入点），基于抛物面提升到三维并取下半 3D 凸包的投影，时间 O(n^2)。
Description: Computes the Delaunay triangulation of a set of points. Each circumcircle contains none of the input points. If any three points are collinear or any four are on the same circle, behavior is undefined. Time: O(n^2) Status: stress-tested
展开阐述：
-
定义与背景
- 德劳内三角剖分（DT）：在不引入新点的情况下，将点集划分为三角形，使每个三角形的外接圆内部不包含其他点。其对偶图为036-几何-曼哈顿最小生成树并不直接等价，但与 Voronoi 图互为对偶。
- 典型场景：网格剖分、插值、地形建模、最近邻结构近似、027-几何-快速德劳内 对照实现与校验。
- 能力边界：实现假设不存在“三点共线”或“四点共圆”的退化输入，否则行为未定义（可能依赖外部扰动/打破平局策略）。
-
接口/数据结构（据实现）
- template<class P, class F> void delaunay(vector
& ps, F trifun)
- 其中 ps 为点集；trifun 是回调，对每个三角形顶点索引/点值调用 trifun(a,b,c)。
- template<class P, class F> void delaunay(vector
-
核心算法流程（抛物面提升 → 3D 凸包投影）
- 特判：当 sz(ps) == 3 时，根据三点的方向（顺/逆时针）直接回调输出一次。
- 抛物面提升：将二维点 (x, y) 映射到三维 (x, y, x²+y²)，使平面上的圆对应三维中的平面截面。
- 计算三维凸包：调用 017-几何-三维凸包（hull3d）。
- 选择下半壳面：对每个三角面 t，若法向量的 z 分量 < 0（面朝下），则该面在投影回平面后对应一个德劳内三角形。
- 顶点顺序：以 (t.a, t.c, t.b) 顺序回调，保证三角形在二维投影下为正向（ccw）。
-
复杂度与边界条件
- 复杂度：hull3d 的实现为 O(n^2)，整体因此为 O(n^2)。
- 退化输入：
- 三点共线：二维无法形成三角形；三维提升后也会出现退化面，代码未定义行为。
- 四点共圆：会导致多个有效三角剖分的并存（非唯一），实现未提供平局策略。
- 数值与稳健性：三维凸包涉及法向计算与面筛选，建议使用长整或高精度浮点以减小误差。
-
实现细节与常见坑
- 索引与顺序：从三维回到二维需保持一致的顶点顺序，否则得到 cw 多边形，影响后续应用。
- 回调设计：trifun 设计使得三角形消费灵活，可用于构图或直接计算面积/周长等。
- 去重与覆盖：三维凸包算法输出的面可能包含上半与下半，需要正确筛下半面（nz < 0）。
-
变体与扩展
- 快速德劳内：见 027-几何-快速德劳内 使用分治与 Quad-Edge，期望 O(n log n)。
- 鲁棒 DT：引入符号算术/精确谓词或随机扰动（jitter）处理共圆/共线退化。
- 约束德劳内（CDT）：在给定约束边下求 DT，一般需边优先嵌入与翻边维护。
-
正确性要点与不变式
- 抛物面提升确保“二维圆空性”对应“三维面朝向”筛选；下半壳的每个面投影回二维等价于满足空圆性质的三角形。
- 组合所有下半面投影即为德劳内三角剖分的边集的面分解。
-
对比与取舍
- 与 027-几何-快速德劳内 相比：实现更直观，依赖 3D 凸包，复杂度较高 O(n^2)，但代码短小、便于验证。
- 与增量法/翻边法相比：本法无需复杂的边数据结构，但对大规模点集效率略逊。