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

d3-delaunay 源码解析德劳内三角剖分与扫描线算法的实现原理【免费下载链接】d3-delaunayCompute the Voronoi diagram of a set of two-dimensional points.项目地址: https://gitcode.com/gh_mirrors/d3/d3-delaunayd3-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 与 hullIndexneighbors() 生成器只需沿着半边环走一圈就能 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考