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三角网提取点云边缘的原理,并给出测试结果。