javascript - 谁能解释 D3 中 delaunay 实现的 alpha 过滤？

Question

作为this显示，您可以使用它来过滤 delaunay 三 Angular 剖分并获得完美的限制。

谁能解释一下magik算法？

Answer 1

背景

经典之外并没有太多的魔力Delaunay triangulation算法，在 D3 中作为函数 d3.geom.delaunay() 实现。

在您链接到的示例中，alpha shapes被实现为修改后的 Delaunay 三 Angular 剖分，以这样一种方式，即至少有一个边大于 alpha 的任何三 Angular 形(在示例中它具有值 50)被从三 Angular 测量。

这就是为什么结果看起来像这样:(原始顶点、Delaunay 三 Angular 剖分和 Alpha 形状)

详情

d3.geom.delaunay() 返回三 Angular 形数组，所以这段代码:

mesh = d3.geom.delaunay(offset(vertices,600,0)).filter(function(t) {
    return dsq(t[0],t[1]) < asq && dsq(t[0],t[2]) < asq && dsq(t[1],t[2]) < asq;
});

加上 asq 是 alpha 的平方，而 dsq() 是计算平面中两点之间距离平方的函数，导致删除任何边至少大于 alpha 的三 Angular 形，这又会产生上图中的第三张图像。

希望这对您有所帮助。