給定一組點計算點覆蓋區域的輪廓

Question

我想要查找點覆蓋區域的輪廓多邊形表示，因此可以說我有一個如下圖所示的點列表：

我希望能夠得到這些點與設定的距離從最外側點覆蓋preferebly邊界的多邊形座標：

個多邊形座標檢索應該代表的形狀，看起來像下面的圖片：

是有一個標準的算法已經在那裏了這種計算的？

Answer 1

您描述的形狀是一個alpha形狀（在計算後添加了一個緩衝區），算法爲described in this paper。

Hull在C語言中提供了一個實現（當與-aa一起使用），CGAL包含一個開源的實現alpha shapes C++。 CGAL文檔描述了基本算法，該算法需要計算輸入點的Delaunay三角剖分，然後使用定義的半徑「切除」外部。