给定一组在平面上的点的,α-形状的概念,对于给定的正数α,通过找到Delaunay三角剖分并删除对于其中至少一个边缘的长度超过了阿尔法任何三角形定义.这是使用d3的示例:
http://bl.ocks.org/gka/1552725
问题是,当有数千个点时,简单地绘制所有内部三角形对于交互式可视化来说太慢了,所以我想找到边界多边形.这不是那么简单,因为从这个例子可以看出,有时可能会有两个这样的多边形.
作为简化,假设已经执行了一些聚类,因此保证每个三角测量的唯一边界多边形.找到这个边界多边形的最佳方法是什么？特别是,边缘必须一致地排序,它必须支持"洞"的可能性(想想圆环或圆环形状 - 这在GeoJSON中是可表达的).