Alpha shapes算法边缘点进行排序（C++）

1、背景介绍

        Alpha Shapes算法能够提取任意点云的边缘点，因此被广泛使用。直接将提取的边缘点进行相连，是混乱相交的多边形，无法真实刻画点云形状，如下图左图所示。这种无序结构，极大影响后续数据处理。而右图中有序结构点云，直接连接边缘点，可以精确刻画点云形状，这样有利于处于相关应用。

无序结构（混乱多边形）	有序结构（理想多边形）

2、边缘点排序介绍

       下面介绍一种基于深度优先遍历的边缘点排序方法。Alpha Shapes算法提取轮廓点的原理可以参考博客alpha shapes提取边界原理及详细步骤-CSDN博客，其识别的边缘点往往是点对，形成边缘边。因此，依据这一关系，可以对点云进行排序。本文根据前文介绍的深度优先遍历（DFS）算法，具体参考博客基于深度优先搜索（DFS）的闭合环检索-CSDN博客。搜索得到闭合多边形，从而对点云进行排序。

3、代码测试

      基于PCL、C++编写的对ALpha Shapes算法提取的边缘点进行排序，未调用三方API，源代码下载链接：https://download.csdn.net/download/qq_32867925/90893141

      该源代码包括一个cpp运行文件，以及6个测试数据。cpp文件直接在配置好的vs平台上运行即可。该源代码在vs2013+PCL1.8、vs2019+PCL 1.11上正常运行。

      直接将排序的边缘点相连，生成多边形。可以发现多边形可以精确刻画点云形状，孔洞内边缘点也进行了排序，证明程序的准确性。

整体图	局部放大图