VC环境下Delaunay三角剖分算法的设计及实现

沈璐 宋晓东 邓宇

(吉林建筑工程学院基础科学部，长春130118)

在计算机视觉领域中，把由两幅或多幅图像恢复空间景物的三维几何形状的问题称为三维重构.空间点的重构通常采用三角剖分的方法来重建点与点之间的关系.三角剖分是指将有限平面点集内的点，按一定的方式连接起来，成为互不交叉的三角形网.B.Delaunay于1934年由Voronoi图(简称V图)演化出的比V图更易于分析应用的Delaunay三角网.Delaunay三角网是最接近等角或等边的最优三角网.

Visual C++是Microsoft公司推出的一种的Win 32程序开发环境，它是面向对象的可视化集成编程系统.Visual C++开发的程序具有运行速度快、可移植能力强等特点，而且它还提供了丰富的位图操作函数，对图像处理提供了极大的方便［1-3］.本文在利用Visual C++的图像基本处理的基础上，结合MFC中的链表类等数据结构完成数据的Delaunay三角剖分.

1 Delaunay三角网的基本原理

Delaunay三角网的定义:它是一系列相连的但不重叠的三角形的集合，而且这些三角形的外接圆不包含这个区域内的其他任何点［4］.Delaunay三角网的外边界是一个凸多边形，它由连接Voronoi图中的凸集形成，通常称为凸壳.

Delaunay三角网络由于具有空外接圆和最小内角最大两个性质，被广泛应用于三维模型的重构中.“空外接圆”是指任何一个三角形的外接圆均不包含其他数据点［5］.“最小内角最大”即在所有可能的三角网中，Delaunay三角网中的三角形的最小内角最大.这两点保证了三角网最接近等角或等边的最优三角网，从而确保了准……