核心概述：分治+四边结构构建平面点集的德劳内三角剖分，输出逆时针三角形序列，时间 O(n log n)。
Description: Fast Delaunay triangulation. Each circumcircle contains none of the input points. There must be no duplicate points. If all points are on a line, no triangles will be returned. Should work for doubles as well, though there may be precision issues in ‘circ’. Returns triangles in order {t[0][0], t[0][1], t[0][2], t[1][0], \dots}, all counter-clockwise. Time: O(n \log n) Status: stress-tested
展开阐述：
-
定义与背景
- 德劳内三角剖分（DT）：任一三角形外接圆内不含其他输入点的三角剖分，等价于最大化最小角，常用于网格质量保证与 Voronoi 对偶构造。
- 本实现为“快速德劳内”，采用分治合并并使用四边（Quad-Edge）结构维护拓扑，优于基于 3D 凸包的 O(n^2) 方案（见026-几何-德劳内三角剖分）。
-
接口/数据结构（据实现）
- vector
triangulate(vector
pts)，P=Point
- 输入要求：
- pts 需按坐标排序，且断言无重复点（unique 后等于 end）。
- 若 sz(pts) < 2，返回空；若全部共线，则不返回任何三角形。
- 输出约定：
- 以扁平数组返回，顺序为 {t0.a, t0.b, t0.c, t1.a, t1.b, t1.c, …}，每个三角形为 ccw 顺序。
- vector
-
核心算法流程（分治 + Quad-Edge）
- 分治递归 rec(S)：
- 基础情形（|S| ≤ 3）：直接构建最小三角形或线段；若三点共线，仅保留边。
- 划分：按 x 坐标将点集对半分为 L/R，分别递归计算 DT。
- 合并（寻找并维护公切线）：
- 找左右凸包的下公切线 base（以定向几何确保 ccw）。
- 以外接圆空性测试 circ 作为翻边判据：对于左右候选边，若某侧存在点在 base 形成的三角形外接圆内，则删除/旋转边，继续外扩。
- 使用 Quad-Edge 的 makeEdge / splice / connect 原语来插入与连接边，逐步“焊接”左右两侧三角网，直到不存在可改进边。
- 收集三角形：
- 遍历四边结构中每个面，按逆时针顺序输出三角形顶点，去除重复与非三角面。
- 函数 circ(p,a,b,c)：
- 判断点 p 是否在三角形 abc 的外接圆内；实现采用抛物面提升的有符号行列式，内部使用 __int128_t 防溢出。
- 分治递归 rec(S)：
-
复杂度与边界条件
- 复杂度：T(n)=2T(n/2)+O(n) ⇒ O(n log n)；常数因子来源于边操作与 in-circle 测试。
- 边界/退化：
- 重复点：不允许，须在预处理去重（assert）。
- 全部共线：不生成三角形（返回空），但内部边结构可维持线性链。
- 整型溢出：距离/行列式计算可溢出 64 位，已用 __int128_t 守护；若切换 double，circ 可能存在精度隐患。
- 稳健性：
- 极端近共圆/共线情况下，in-circle 判据对浮点敏感；如需更鲁棒可引入 long double 或精确谓词。
-
实现细节与常见坑
- Quad-Edge 不变量：每条边都有对偶与旋转映射；splice 维护环结构，connect 连接两面边界，务必保持半边环路一致性。
- 公切线选择：下公切线作为起点，有利于合并时沿着“可见边界”生长；若方向错置将导致 cw 输出或面翻转。
- 输出去重：仅收集内部 ccw 的三角面；确保不输出边界伪三角形或重复三元组。
- 排序与坐标：初始按 x（再 y）排序，递归划分保持均衡，避免退化到 O(n^2)。
-
变体与扩展
- 约束德劳内（CDT）：在分治框架上加入固定边（禁止翻边），需要更复杂的冲突解决策略。
- 动态插入：随机化增量插入 + 翻边维护，可支持在线场景。
- 双精度版本：P=Point
可用，但 circ 谓词要谨慎（阈值 eps）。
-
正确性要点与不变式
- 合并阶段仅在违反空圆性质时翻边，保证最终网满足德劳内条件。
- Quad-Edge 在任何时刻保持面边界循环闭合，避免悬挂边和自交。
- 输出三角均为 ccw，确保几何符号一致性。
-
对比与取舍
- 相比 026-几何-德劳内三角剖分（3D 凸包投影）：本法 O(n log n) 更快，代码更复杂；3D 法更直观但 O(n^2)。
- 相比 Bowyer–Watson 增量法：分治合并对并行/缓存友好，增量法实现更短小、插入顺序影响性能。