一种Delaunay三角剖分快速实现算法

摘要

提出了一种针对平面散乱点集的快速构建并实现Delaunay三角剖分的算法。该算法首先对平面散乱点在XOY平面上按x轴正向进行排序，并对三角形外接圆的圆心及半径进行了预先计算，以排序后的点顺序为基础，利用逐点插入法快速将散乱点联结成三角网。在程序设计实现方面，给出了一种类的结构及相应一些函数，充分利用VC的STL所提供一些功能来提高程序的运行效率以及程序的可读性，使整个程序结构简捷清晰，实现证明算法运行高效稳健。