1、背景介绍
Delaunay三角网是一种在平面上对一组点构造三角网格的方法，其中任何点都不在由其周围点形成的任何三角形的外接圆内部。这种方法确保了三角形尽可能接近等边三角形，从而避免了狭长的三角形。如下图所示，为利用平面上点集构建生成的 Delaunay三角网，包括若干个三角形，而每个三角形所处位置不同，比如有的位于三角网边缘处，有的位于内部。因此，根据这一特性，可以根据Delaunay三角网进行边缘检测，实现效果如右图所示，其将边缘点连接起来线段。
 |  |
2、Delaunay属性及边界点提取原理
python中专门构建Delaunay的第三方库，在scipy库中。生成的三角网，其包括2类属性：三角形顶点索引、近邻三角网索引。
2.1 三角形顶点索引
三角形顶点索引是记录组成三角形顶点，在原始点中的序列号。如下图所示，总共5个点，编号分别为0、1、2、3、4。Delaunay共生成4个三角。那么三角形索引，则是记录每个三角形中三个顶点，由这5个顶点中哪3个顶点组成。可知：
三角形 1：4 1 0
三角形2: 4 2 1
三角形3： 4 1 3
三角形4: 4 2 3
2.2 三角形邻域信息
三角形邻域信息，则是记录与该三角形相邻的信息。上述Delaunay三角网的三角形邻域信息如下。对于非零数字，表示与之相邻的三角形，其索引号；对于-1数字，则表明没有邻域三角形与之对应。
第一行[1, 3, -1]表示第一个三角形的邻域信息
- 第一个邻域三角形的索引是1
- 第二个邻域三角形的索引是3
- 第三个边没有邻域三角形（因为它位于整个Delaunay三角剖分的边界上），所以标记为-1
第二行[0, 2, 3]表示第二个三角形的邻域信息：
- 第一个邻域三角形的索引是0
- 第二个邻域三角形的索引是2
- 第三个邻域三角形的索引是3
Neighbors: [[1, 3, -1],[0, 2, 3],[1, 3, -1],[0, 1, 2]]3.3 基于Delaunay三角网提取边缘点原理
因此，根据上述介绍，可以采用如下步骤提取边缘点：对于每个三角形，对其每个邻域信息进行判断。若邻域信息中存在-1，则表明该三角网中存在边界边。将边界边提取出来，即可实现边缘点提取。
3、代码测试与结果分析
本程序基于python代码进行编写，在pycharm平台上进行运行，结合三方库scipy中Delaunay构建三角网。源代码下载链接：https://download.csdn.net/download/qq_32867925/89562829
3.1 简单图形测试
使用5个点构成的简单图形进行测试，测试结果如下图所示。5个点共生成4个三角形，提取的边界点连接，生成的多边形如右图，提取效果比较理想
 |  |
| Delaunay三角网 | 边界点连接成的边（红色） |
3.2 简单图形测试
随机生成100个平面点，生成的三角网如下。利用提取的边界点，生成的边界边效果还算比较理想。
 |  |
| Delaunay三角网 | 边界点连接成的边（红色） |
4、总结
介绍了利用Delaunay三角网提取点云边缘的原理，并给出测试结果。
