d3-delaunay 源码解析外接圆圆心计算与无穷边界裁剪的秘密【免费下载链接】d3-delaunayCompute the Voronoi diagram of a set of two-dimensional points.项目地址: https://gitcode.com/gh_mirrors/d3/d3-delaunayd3-delaunay 是一个专为二维点集计算Voronoi 图泰森多边形的高性能开源库。想真正吃透它的算法精髓绕不开两个核心问题外接圆圆心是怎么算出来的无穷边界裁剪又是如何把延伸到无限远的单元塞回画布里的本文将带你逐行拆解src/voronoi.js源码揭开这两个秘密的完整面目。无论你是刚接触计算几何的新手还是想优化渲染性能的进阶开发者读完都能对 Voronoi 图算法建立扎实的理解。d3-delaunay 是什么从点集到 Voronoi 图的奇妙旅程 ️d3-delaunay 基于 Mapbox 的 Delaunator 快速三角剖分引擎先用扫描线算法把一堆散点连成Delaunay 三角剖分满足任意三角形的外接圆内不包含其他点的最优性质再通过对偶变换生成 Voronoi 图——Voronoi 图的每个顶点恰好是某个 Delaunay 三角形外接圆的圆心把相邻三角形的外接圆圆心连起来就是完整的 Voronoi 单元边界。整个库的骨架非常清晰只有四个源文件src/delaunay.js三角剖分主体封装 Delaunator提供render、find、neighbors等 APIsrc/voronoi.jsVoronoi 图核心外接圆圆心计算与无穷边界裁剪都在这里src/path.js轻量绘图上下文模拟 Canvas 2D 路径接口src/polygon.js多边形数据收集器输出坐标数组。而今天的主角就是 src/voronoi.js 中那 300 多行浓缩的精华。外接圆圆心计算Voronoi 图的几何基石 Voronoi 图与 Delaunay 三角剖分互为对偶因此算外接圆圆心是构建 Voronoi 图的第一个关键步骤。这段逻辑位于 src/voronoi.js 的_init()方法中每次初始化都遍历triangles数组每 3 个索引构成一个三角形用一套紧凑的向量公式批量产出所有圆心结果存入Float64Array类型的circumcenters数组为后续渲染和裁剪做准备。为什么 Voronoi 顶点恰好是外接圆圆心给定三角形三个顶点外接圆是唯一能同时经过这三个点的圆它的圆心到三个顶点的距离相等。而 Voronoi 单元的定义是到某个种子点最近的点集单元边界恰好是相邻种子点垂直平分线的交点——三点垂直平分线的交点正是它们的外接圆圆心。这一几何事实让三角剖分与外接圆圆心成了 Voronoi 图算法的免费午餐。外接圆圆心计算公式是如何推导的源码采用了一组基于叉积的高效公式。设三角形顶点为 p1(x1, y1)、p2(x2, y2)、p3(x3, y3)先构造两个向量dx x2 - x1, dy y2 - y1 // 向量 d p2 - p1 ex x3 - x1, ey y3 - y1 // 向量 e p3 - p1再计算叉积的两倍ab (dx * ey - dy * ex) * 2它等于以 d、e 为边的平行四边形面积。随后d 1 / ab bl dx² dy² // |d|² cl ex² ey² // |e|² x x1 (ey * bl - dy * cl) * d y y1 (dx * cl - ex * bl) * d这套公式的由来外接圆圆心 O 到三个顶点距离相等等价于两个线性方程O 到 p1、p2 等距O 到 p1、p3 等距用克莱姆法则解出 O 在以 d、e 为基底的坐标即可。最终结果化简为上面这组只用加减乘除的表达式——零分支、零平方根配合Float64Array紧凑存储就是它性能强劲的秘诀。退化三角形外接圆圆心在无穷远处的处理 当三个点近乎共线时叉积ab趋近于 0外接圆半径趋近于无穷大。源码用Math.abs(ab) 1e-9判定退化情形此时外接圆圆心被推到无穷远处方向必须垂直于三角形边且远离图的中心才能保证 Voronoi 单元朝外正确延伸if (bx undefined) { // 惰性计算凸包重心 bx, by仅遇到退化三角形时才触发 bx by 0; for (const i of hull) bx points[i * 2], by points[i * 2 1]; bx / hull.length, by / hull.length; } const a 1e9 * Math.sign((bx - x1) * ey - (by - y1) * ex); x (x1 x3) / 2 - a * ey; y (y1 y3) / 2 a * ex;关键在于Math.sign(...)的符号用凸包重心(bx, by)与顶点构成的向量做叉积判断哪一侧才是外侧从而把圆心推向远离重心的那一侧1e9这个巨大的系数让圆心足够远配合后面的射线投影机制就能稳定地裁剪出正确的无限单元边界。无穷边界裁剪让无界单元回到画布内 ✂️外接圆圆心算完后Voronoi 单元还没法直接画——位于凸包上的点的单元是无界的它们像射线一样伸向无穷远。必须把它们裁剪到用户给定的矩形边界[xmin, ymin, xmax, ymax]内默认 960×500这正是无穷边界裁剪的用武之地。哪些 Voronoi 单元是无界的只有凸包上的点才会产生无限单元。_init()后半段src/voronoi.js专门为凸包顶点计算外射线方向vectors[p0 2] vectors[p1] y0 - y1; vectors[p0 3] vectors[p1 1] x1 - x0;沿凸包边走一圈每条边(x0, y0) → (x1, y1)的法向量(y0 - y1, x1 - x0)就是单元向外延伸的方向。每个点占据vectors中 4 个槽位入射线 x/y 出射线 x/y内部点的槽位保持为 0。后续_clip()只需判断V[v] || V[v1]是否非零即可区分无限单元与有限单元有外射线 → 走_clipInfinite没有 → 走_clipFinite最后统一交给_simplify去掉共线冗余点。射线投影 _project让无穷远点精确落在边界框上 无限单元的起点是几乎在无穷远的外接圆圆心终点是凸包顶点沿法向射出的射线。_projectsrc/voronoi.js负责把这条射线与边界框求交找到最先碰到的边let t Infinity, c, x, y; if (vy 0) { // 射线朝上考虑顶边 if (y0 this.ymin) return null; if ((c (this.ymin - y0) / vy) t) y this.ymin, x x0 (t c) * vx; } else if (vy 0) { /* 底边同理 */ } if (vx 0) { /* 右边同理 */ } else if (vx 0) { /* 左边同理 */ } return [x, y];原理很朴素把射线写成参数式(x0 t·vx, y0 t·vy)对每条可能相交的边界边算出参数t取最小的 t就是最近交点。若起点已经在边界外则直接返回null表示整条射线都不需要画。_clipInfinitesrc/voronoi.js就是先把首尾两个无穷点投影到边界上形成一个初步闭合的多边形再走常规裁剪流程。多边形裁剪三件套_clipFinite / _clipSegment / _regioncode 投影完成后剩下的就是经典的多边形裁剪问题。d3-delaunay 实现了一套非常紧凑的组合拳_regioncodesrc/voronoi.jsCohen–Sutherland 区域编码用 4 位二进制表示点相对边界框的位置左0001、右0010、上0100、下1000一次判断即可知道点是否在框内_clipSegmentsrc/voronoi.js线段裁剪。两段编码都是 0 说明完全在框内c0 c1非零说明两点在框外同一侧直接丢弃否则按编码逐边求交点并迭代收缩_clipFinitesrc/voronoi.js对单元的多边形顶点做 Sutherland–Hodgman 式逐边扫描保留框内顶点、用_clipSegment补上跨越边界的交点最终输出完整的闭合多边形。这套组合还自带一个贴心细节如果裁剪后多边形为空代码会通过contains(i, 中心点)判断该单元是否完全包裹边界框中心若成立则直接返回整个矩形保证极端情况下也能渲染正确。边界行走 _edge补齐矩形角点 裁剪后的多边形可能还缺少边界框的角点。_edgecodesrc/voronoi.js判断相邻两点分别落在哪条边界边上若它们不在同一条边_edgesrc/voronoi.js就沿着边界框逆时针行走把中间的角点逐一插入多边形case 0b0100: e0 0b0110, x this.xmax, y this.ymin; break; // top → 右上角 case 0b0010: e0 0b1010, x this.xmax, y this.ymax; break; // right → 右下角插入前还会用contains(i, x, y)内部借助 src/delaunay.js 的_step跳跃式定位确认该角点确实属于这个单元避免画错邻居的地盘。最后_simplifysrc/voronoi.js把连续共线三点同 x 或同 y的冗余点删掉让输出的多边形既干净又省内存。完整调用链从点集到最终图形的源码导览 把上面的机制串起来一次典型的 Voronoi 渲染调用链是这样的Delaunay.from(points)建立三角剖分src/delaunay.jsdelaunay.voronoi(bounds)构造 Voronoi 实例_init()中批量计算全部外接圆圆心与凸包外射线调用renderCell(i)/render(context)时_clip(i)自动分发到_clipInfinite或_clipFinite完成无穷边界裁剪顶点坐标写入 src/polygon.js 的Polygon或直接绘制到 src/path.js 的路径上下文。对普通使用者来说delaunay.voronoi().cellPolygons()一行就能拿到所有裁剪好的泰森多边形而对想深度优化或移植算法的开发者来说src/voronoi.js 这份源码就是一份绝佳的计算几何速成教材。结语两个秘密一套优雅的设计 ✨回头看d3-delaunay 的秘密其实并不神秘外接圆圆心计算利用了 Voronoi 与 Delaunay 的对偶关系用一组无分支、无平方根的向量公式批量求解遇到共线退化三角形时巧用凸包重心和1e9大数把圆心推向无穷远处无穷边界裁剪则是一套教科书级算法的极致压缩——Cohen–Sutherland 区域编码、Sutherland–Hodgman 多边形裁剪、射线参数化投影、边界角点行走全部浓缩在百余行代码里配合Float64Array与位运算做到极致性能。理解了这两个核心你不仅能熟练使用 d3-delaunay还能把这份思路迁移到地理空间分析、点云处理、图像分割等任何需要 Voronoi 图的场景中。下次再看到那一片规整的泰森多边形不妨想想背后那位外接圆圆心与那把无限远裁剪剪刀——它们才是真正的幕后英雄。【免费下载链接】d3-delaunayCompute the Voronoi diagram of a set of two-dimensional points.项目地址: https://gitcode.com/gh_mirrors/d3/d3-delaunay创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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 是一个专为二维点集计算Voronoi 图泰森多边形的高性能开源库。想真正吃透它的算法精髓绕不开两个核心问题外接圆圆心是怎么算出来的无穷边界裁剪又是如何把延伸到无限远的单元塞回画布里的本文将带你逐行拆解src/voronoi.js源码揭开这两个秘密的完整面目。无论你是刚接触计算几何的新手还是想优化渲染性能的进阶开发者读完都能对 Voronoi 图算法建立扎实的理解。d3-delaunay 是什么从点集到 Voronoi 图的奇妙旅程 ️d3-delaunay 基于 Mapbox 的 Delaunator 快速三角剖分引擎先用扫描线算法把一堆散点连成Delaunay 三角剖分满足任意三角形的外接圆内不包含其他点的最优性质再通过对偶变换生成 Voronoi 图——Voronoi 图的每个顶点恰好是某个 Delaunay 三角形外接圆的圆心把相邻三角形的外接圆圆心连起来就是完整的 Voronoi 单元边界。整个库的骨架非常清晰只有四个源文件src/delaunay.js三角剖分主体封装 Delaunator提供render、find、neighbors等 APIsrc/voronoi.jsVoronoi 图核心外接圆圆心计算与无穷边界裁剪都在这里src/path.js轻量绘图上下文模拟 Canvas 2D 路径接口src/polygon.js多边形数据收集器输出坐标数组。而今天的主角就是 src/voronoi.js 中那 300 多行浓缩的精华。外接圆圆心计算Voronoi 图的几何基石 Voronoi 图与 Delaunay 三角剖分互为对偶因此算外接圆圆心是构建 Voronoi 图的第一个关键步骤。这段逻辑位于 src/voronoi.js 的_init()方法中每次初始化都遍历triangles数组每 3 个索引构成一个三角形用一套紧凑的向量公式批量产出所有圆心结果存入Float64Array类型的circumcenters数组为后续渲染和裁剪做准备。为什么 Voronoi 顶点恰好是外接圆圆心给定三角形三个顶点外接圆是唯一能同时经过这三个点的圆它的圆心到三个顶点的距离相等。而 Voronoi 单元的定义是到某个种子点最近的点集单元边界恰好是相邻种子点垂直平分线的交点——三点垂直平分线的交点正是它们的外接圆圆心。这一几何事实让三角剖分与外接圆圆心成了 Voronoi 图算法的免费午餐。外接圆圆心计算公式是如何推导的源码采用了一组基于叉积的高效公式。设三角形顶点为 p1(x1, y1)、p2(x2, y2)、p3(x3, y3)先构造两个向量dx x2 - x1, dy y2 - y1 // 向量 d p2 - p1 ex x3 - x1, ey y3 - y1 // 向量 e p3 - p1再计算叉积的两倍ab (dx * ey - dy * ex) * 2它等于以 d、e 为边的平行四边形面积。随后d 1 / ab bl dx² dy² // |d|² cl ex² ey² // |e|² x x1 (ey * bl - dy * cl) * d y y1 (dx * cl - ex * bl) * d这套公式的由来外接圆圆心 O 到三个顶点距离相等等价于两个线性方程O 到 p1、p2 等距O 到 p1、p3 等距用克莱姆法则解出 O 在以 d、e 为基底的坐标即可。最终结果化简为上面这组只用加减乘除的表达式——零分支、零平方根配合Float64Array紧凑存储就是它性能强劲的秘诀。退化三角形外接圆圆心在无穷远处的处理 当三个点近乎共线时叉积ab趋近于 0外接圆半径趋近于无穷大。源码用Math.abs(ab) 1e-9判定退化情形此时外接圆圆心被推到无穷远处方向必须垂直于三角形边且远离图的中心才能保证 Voronoi 单元朝外正确延伸if (bx undefined) { // 惰性计算凸包重心 bx, by仅遇到退化三角形时才触发 bx by 0; for (const i of hull) bx points[i * 2], by points[i * 2 1]; bx / hull.length, by / hull.length; } const a 1e9 * Math.sign((bx - x1) * ey - (by - y1) * ex); x (x1 x3) / 2 - a * ey; y (y1 y3) / 2 a * ex;关键在于Math.sign(...)的符号用凸包重心(bx, by)与顶点构成的向量做叉积判断哪一侧才是外侧从而把圆心推向远离重心的那一侧1e9这个巨大的系数让圆心足够远配合后面的射线投影机制就能稳定地裁剪出正确的无限单元边界。无穷边界裁剪让无界单元回到画布内 ✂️外接圆圆心算完后Voronoi 单元还没法直接画——位于凸包上的点的单元是无界的它们像射线一样伸向无穷远。必须把它们裁剪到用户给定的矩形边界[xmin, ymin, xmax, ymax]内默认 960×500这正是无穷边界裁剪的用武之地。哪些 Voronoi 单元是无界的只有凸包上的点才会产生无限单元。_init()后半段src/voronoi.js专门为凸包顶点计算外射线方向vectors[p0 2] vectors[p1] y0 - y1; vectors[p0 3] vectors[p1 1] x1 - x0;沿凸包边走一圈每条边(x0, y0) → (x1, y1)的法向量(y0 - y1, x1 - x0)就是单元向外延伸的方向。每个点占据vectors中 4 个槽位入射线 x/y 出射线 x/y内部点的槽位保持为 0。后续_clip()只需判断V[v] || V[v1]是否非零即可区分无限单元与有限单元有外射线 → 走_clipInfinite没有 → 走_clipFinite最后统一交给_simplify去掉共线冗余点。射线投影 _project让无穷远点精确落在边界框上 无限单元的起点是几乎在无穷远的外接圆圆心终点是凸包顶点沿法向射出的射线。_projectsrc/voronoi.js负责把这条射线与边界框求交找到最先碰到的边let t Infinity, c, x, y; if (vy 0) { // 射线朝上考虑顶边 if (y0 this.ymin) return null; if ((c (this.ymin - y0) / vy) t) y this.ymin, x x0 (t c) * vx; } else if (vy 0) { /* 底边同理 */ } if (vx 0) { /* 右边同理 */ } else if (vx 0) { /* 左边同理 */ } return [x, y];原理很朴素把射线写成参数式(x0 t·vx, y0 t·vy)对每条可能相交的边界边算出参数t取最小的 t就是最近交点。若起点已经在边界外则直接返回null表示整条射线都不需要画。_clipInfinitesrc/voronoi.js就是先把首尾两个无穷点投影到边界上形成一个初步闭合的多边形再走常规裁剪流程。多边形裁剪三件套_clipFinite / _clipSegment / _regioncode 投影完成后剩下的就是经典的多边形裁剪问题。d3-delaunay 实现了一套非常紧凑的组合拳_regioncodesrc/voronoi.jsCohen–Sutherland 区域编码用 4 位二进制表示点相对边界框的位置左0001、右0010、上0100、下1000一次判断即可知道点是否在框内_clipSegmentsrc/voronoi.js线段裁剪。两段编码都是 0 说明完全在框内c0 c1非零说明两点在框外同一侧直接丢弃否则按编码逐边求交点并迭代收缩_clipFinitesrc/voronoi.js对单元的多边形顶点做 Sutherland–Hodgman 式逐边扫描保留框内顶点、用_clipSegment补上跨越边界的交点最终输出完整的闭合多边形。这套组合还自带一个贴心细节如果裁剪后多边形为空代码会通过contains(i, 中心点)判断该单元是否完全包裹边界框中心若成立则直接返回整个矩形保证极端情况下也能渲染正确。边界行走 _edge补齐矩形角点 裁剪后的多边形可能还缺少边界框的角点。_edgecodesrc/voronoi.js判断相邻两点分别落在哪条边界边上若它们不在同一条边_edgesrc/voronoi.js就沿着边界框逆时针行走把中间的角点逐一插入多边形case 0b0100: e0 0b0110, x this.xmax, y this.ymin; break; // top → 右上角 case 0b0010: e0 0b1010, x this.xmax, y this.ymax; break; // right → 右下角插入前还会用contains(i, x, y)内部借助 src/delaunay.js 的_step跳跃式定位确认该角点确实属于这个单元避免画错邻居的地盘。最后_simplifysrc/voronoi.js把连续共线三点同 x 或同 y的冗余点删掉让输出的多边形既干净又省内存。完整调用链从点集到最终图形的源码导览 把上面的机制串起来一次典型的 Voronoi 渲染调用链是这样的Delaunay.from(points)建立三角剖分src/delaunay.jsdelaunay.voronoi(bounds)构造 Voronoi 实例_init()中批量计算全部外接圆圆心与凸包外射线调用renderCell(i)/render(context)时_clip(i)自动分发到_clipInfinite或_clipFinite完成无穷边界裁剪顶点坐标写入 src/polygon.js 的Polygon或直接绘制到 src/path.js 的路径上下文。对普通使用者来说delaunay.voronoi().cellPolygons()一行就能拿到所有裁剪好的泰森多边形而对想深度优化或移植算法的开发者来说src/voronoi.js 这份源码就是一份绝佳的计算几何速成教材。结语两个秘密一套优雅的设计 ✨回头看d3-delaunay 的秘密其实并不神秘外接圆圆心计算利用了 Voronoi 与 Delaunay 的对偶关系用一组无分支、无平方根的向量公式批量求解遇到共线退化三角形时巧用凸包重心和1e9大数把圆心推向无穷远处无穷边界裁剪则是一套教科书级算法的极致压缩——Cohen–Sutherland 区域编码、Sutherland–Hodgman 多边形裁剪、射线参数化投影、边界角点行走全部浓缩在百余行代码里配合Float64Array与位运算做到极致性能。理解了这两个核心你不仅能熟练使用 d3-delaunay还能把这份思路迁移到地理空间分析、点云处理、图像分割等任何需要 Voronoi 图的场景中。下次再看到那一片规整的泰森多边形不妨想想背后那位外接圆圆心与那把无限远裁剪剪刀——它们才是真正的幕后英雄。【免费下载链接】d3-delaunayCompute the Voronoi diagram of a set of two-dimensional points.项目地址: https://gitcode.com/gh_mirrors/d3/d3-delaunay创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考