给定一组点计算点覆盖区域的轮廓

Question

我想要查找点覆盖区域的轮廓多边形表示，因此可以说我有一个如下图所示的点列表：

我希望能够得到这些点与设定的距离从最外侧点覆盖preferebly边界的多边形坐标：

个多边形坐标检索应该代表的形状，看起来像下面的图片：

是有一个标准的算法已经在那里了这种计算的？

Answer 1

您描述的形状是一个alpha形状（在计算后添加了一个缓冲区），算法为described in this paper。

Hull在C语言中提供了一个实现（当与-aa一起使用），CGAL包含一个开源的实现alpha shapes C++。 CGAL文档描述了基本算法，该算法需要计算输入点的Delaunay三角剖分，然后使用定义的半径“切除”外部。