Delaunay 三角剖分与 Voronoi 图

Rust + WebAssembly 用 Bowyer-Watson 算法增量构建三角网，并把图片变成低多边形艺术

🖱️ 点击 / 👆 轻点 加点，悬停查看三角形的外接圆：圆里永远没有其他点  |  「图片转低多边形」沿边缘多放点，再用三角形平均色重绘

📖 原理说明

把平面上的一堆点连成三角形有无数种方法，Delaunay 三角剖分是其中「最匀称」的一种：任何一个三角形的外接圆里都没有其他点。它会尽量避免细长的三角形，因此广泛用于地形建模、有限元网格和插值。它的对偶图是 Voronoi 图：把平面划分成若干区域，每个区域里的位置离某一个点最近。页面上鼠标悬停时显示的圆就是外接圆，你会发现圆里总是空的。

🧮算法原理

∀ 三角形 T，∀ 点 p ∉ T：|p − cT| ≥ rT空外接圆性质：c、r 是三角形的外接圆圆心和半径
Voronoi 边 = 相邻两个三角形外心的连线外心到三个顶点等距，所以正好在三块 Voronoi 区域的交界处
Bowyer-Watson 增量算法
每次加入一个点：找出所有外接圆包含这个点的三角形，把它们删掉，会留下一个多边形空洞（可以证明这些三角形连成一片），再把空洞的每条边与新点相连，形成新的三角形。每一步之后，空外接圆性质依然成立。
无穷远顶点
算法需要一个「包住所有点」的起点。常见做法是先放一个巨大的超级三角形，但它的顶点只是「很远」而不是真正无穷远，凸包边附近偶尔会漏掉很扁的三角形（测试里正好遇到过）。这里改用一个无穷远顶点：每条凸包边外侧挂一个「幽灵三角形」，它的外接圆严格等于这条边外侧的半平面，于是凸包边也能精确处理。所有点共线时还构不成三角形，就先暂存，等出现第一个不共线的点再开始。
Voronoi 图
共享一条边的两个三角形，把它们的外心连起来，就是一条 Voronoi 边；凸包边上只有一个三角形，就从外心向外画一条射线。
低多边形艺术
先用 Sobel 算子求出图片每个像素的边缘强度，按「均匀 + 边缘强度」的权重随机撒点，边缘处的点更密，再加上图片四周的点。剖分完后，每个三角形用它覆盖的所有像素的平均色填充。「边缘权重」越大，点越集中在轮廓上，形状越清楚。

🔄Rust 与 JavaScript 的分工

  1. JS点击时调用 dl_add(x, y)，随机撒点调用 dl_random(n)；悬停时用 dl_find 找到所在的三角形，dl_circumcircle 取它的外接圆。
  2. RustRust 维护三角网，每加一个点做一次 Bowyer-Watson 更新；dl_triangles()、dl_voronoi() 返回三角形和 Voronoi 线段。低多边形模式由 dl_lowpoly(像素, 宽, 高, 点数, 种子, 边缘权重) 一次完成撒点、剖分和上色，返回新图片。
  3. JSJS 用 Canvas 画出三角形、Voronoi 线段和外接圆。

⚡性能要点

  • 实测（Node 中运行同一个 WASM）：500 个点 3.7ms，2000 个点 26ms，5000 个点 144ms；Voronoi 图 1~2ms；把 800×560 的图片做成 1200 个点的低多边形约 50ms。
  • 这里寻找「外接圆包含新点的三角形」时直接检查所有三角形，所以总耗时是 O(n²)，点数加倍耗时约变成 4 倍。更快的实现会从上一个三角形出发沿着网格「走」到新点附近，只检查局部，整体接近 O(n log n)。
  • 测试检查了空外接圆性质、三角形方向、欧拉公式（三角形数 = 2n − 2 − 凸包点数，50 组随机点）、共圆的网格点和共线点。

源码crates/algorithms/delaunay/src/mesh.rswww/delaunay/index.js