d3-delaunay 源码解析：德劳内三角剖分与扫描线算法的实现原理

d3-delaunay 源码解析：德劳内三角剖分与扫描线算法的实现原理

【免费下载链接】d3-delaunayCompute the Voronoi diagram of a set of two-dimensional points.项目地址: https://gitcode.com/gh_mirrors/d3/d3-delaunay

d3-delaunay 是 D3 生态中最快的二维点集几何计算库之一，它借助扫描线算法完成德劳内三角剖分（Delaunay Triangulation），再基于三角剖分结果构建沃罗诺伊图（Voronoi 图）。本文将以源码解析的方式，带你逐层拆解 d3-delaunay 的实现原理：从扫描线算法的核心机制，到半边缘结构、凸包计算、外接圆圆心推导，再到无限单元的边界裁剪，彻底读懂这套经典的 JavaScript 计算几何代码。

什么是德劳内三角剖分？为什么它是沃罗诺伊图的基石

德劳内三角剖分，是把平面上的一组点连成三角形网格的一种特殊方式，它满足一条黄金法则：任何一个三角形的外接圆内部，都不包含其他输入点。这条看似简单的性质，让剖分结果具有两个迷人特征——最大化所有三角形的最小内角（避免出现"细长"病态三角形），以及生成唯一且稳定的网格结构。

更妙的是，沃罗诺伊图（也叫泰森多边形）与德劳内三角剖分是对偶关系：把每个三角形的外接圆圆心连接起来，就得到了沃罗诺伊图的边；反过来，每个 Voronoi 单元恰好包围一个输入点，单元内的任意位置到该点的距离都小于到其他点的距离。d3-delaunay 正是利用这层对偶性，先求三角剖分，再"免费"推导出 Voronoi 图。

扫描线算法：德劳内三角剖分的加速引擎

很多新手以为 d3-delaunay 自己实现了剖分算法，其实核心三角剖分由它封装的Delaunator库完成，d3-delaunay 负责在其之上补齐凸包、邻接索引与 Voronoi 图等能力。两者合起来，才是完整的扫描线算法实现：

// src/delaunay.js 第 1 行 import Delaunator from "delaunator";

扫描线算法的思想非常直观：想象一条竖直的线，从最左侧的点开始从左到右扫过整个平面。每当扫描线碰到一个新点时，就在已有的三角网格中定位它所在的三角形，将其拆分成三个新三角形，然后通过**边翻转（edge flip）**操作反复修复，直到重新满足德劳内性质。整个过程平均时间复杂度为 O(n log n)，配合 TypedArray 存储，能在几十毫秒内处理数万个点。

源码结构一览：四个模块各司其职

打开仓库根目录，src/下只有四个源文件，职责划分非常清晰：

• index.js：唯一入口，导出Delaunay和Voronoi两个类
• delaunay.js：三角剖分的封装层，负责凸包、半边缘索引、邻居查询与最近点查找
• voronoi.js：外接圆圆心计算、无限射线生成与边界裁剪
• path.js、polygon.js：把几何结果渲染成 SVG 路径的辅助工具

这种"三角剖分 + Voronoi 生成"的分层设计，让两个类可以独立使用：Delaunay只关心三角形，Voronoi只关心多边形。

三角剖分之后：半边缘结构、凸包与邻接关系的构建

Delaunay的构造函数在拿到 Delaunator 的剖分结果后，会调用 _init() 做关键的二次加工。其中最核心的数据结构是半边缘（halfedges）：三角剖分中每条边都会被两个三角形共享（边界边除外），halfedges 数组记录了每半边对应的"另一半"，这让遍历邻居变得极其高效。

// 用半边索引构建“每个点指向一条入射边”的映射 for (let e = 0, n = halfedges.length; e < n; ++e) { const p = triangles[e % 3 === 2 ? e - 2 : e + 1]; if (halfedges[e] === -1 || inedges[p] === -1) inedges[p] = e; }

同时 _init() 还处理了一个棘手场景——共线点：当所有点都在一条直线上时，正常剖分会失效，源码会对每个点施加一个微小的正弦扰动（points[i] += r * Math.sin(i + 0.5)），打破共线状态后再重新剖分。基于 inedges 与 hullIndex，neighbors() 生成器只需沿着半边环走一圈，就能 O(k) 地返回某个点的所有邻居点。

从三角形到沃罗诺伊图：外接圆圆心与射线方向

拿到三角剖分后，Voronoi 图的构建就顺理成章了。voronoi.js 的 _init() 先对每个三角形计算外接圆圆心——这里用到了标准的几何公式：

const d = 1 / ab; // ab 是两倍三角形面积 x = x1 + (ey * bl - dy * cl) * d; y = y1 + (dx * cl - ex * bl) * d;

面积趋近于 0 的退化三角形（凸包边界附近的"开三角形"）没有有限的外接圆圆心，源码会以凸包重心为参考点，让圆心沿垂直于半边方向的射线射向无穷远。每个凸包顶点对应的外向射线方向被存入vectors数组——这正是后续裁剪无限单元的"弹药"。

边界裁剪算法：让无限单元落回画布

Voronoi 图的边界单元理论上是无限延伸的，但屏幕和画布总是有限的。d3-delaunay 用一套精巧的裁剪管线解决这个问题：_cell收集某点周围一圈圆心构成的多边形，_clip根据该点是否位于凸包上，决定走_clipFinite（有限单元）还是_clipInfinite（无限单元）分支。

其中_regioncode用 4 位二进制码标记点相对于画布四条边的位置，配合类似 Cohen–Sutherland 的线段裁剪法，快速求出线段与矩形边界的交点；_project则把无限射线投影到画布边缘。最后_simplify会清理重复顶点，保证输出的多边形干净整洁。

性能与真实应用场景

得益于 TypedArray、半边结构与 O(n log n) 的扫描线算法，d3-delaunay 是 JavaScript 生态中性能顶尖的 Voronoi 实现。它的用途远超想象：数据可视化中的热力图与气泡图、游戏里的程序化地形生成与寻路、城市分区与信号覆盖分析，甚至艺术创作中的多边形风格化——把照片像素映射成 Voronoi 单元，就能得到低多边形艺术效果。

结语：一套值得反复品读的计算几何范本

d3-delaunay 的源码解析到这里就结束了。回顾全文：扫描线算法负责用 O(n log n) 完成德劳内三角剖分，半边缘结构支撑起高效的邻接遍历，外接圆圆心串联起三角剖分与沃罗诺伊图的对偶关系，而边界裁剪让无限几何落回有限画布。整套代码不到一千行，却浓缩了计算几何最优雅的几大经典思想——无论是做数据可视化、游戏开发，还是单纯想学习高性能几何算法的工程化写法，它都是极佳的范本。

【免费下载链接】d3-delaunayCompute the Voronoi diagram of a set of two-dimensional points.项目地址: https://gitcode.com/gh_mirrors/d3/d3-delaunay