平面散乱点集的Delaunay三角剖分算法

Algorithm about Delaunay triangulations for 2D scattered datasets

描述了一种平面散乱点集的Delaunay三角剖分算法.首先对散乱点集预处理,保证每次插入的点落在已处理点集形成的临时边界环外;然后逐点插入预处理后的点,使临时边界环不断向外围扩展,直至点集处理完毕,形成散乱点集的三角网格;最后运用Delaunay优化准则优化.该算法由于充分利用了Visual C++语言中MFC类的数据资源,使得编程容易实现.最后举例验证了该算法的优越性.

A Delaunay triangulation algorithm is presented for large sets of 2D scattered data-points.Firstly a preprocessing of the scattered datasets guarantees the inserted new point to be located outside the transient boundary loop which is formed by the points processed previously.Secondly the preprocessed point is inserted one by one to make the transient boundary loop enlarged continuously,and then a fundamental triangular grid is formed after all the data-points are processed.Lastly,the Delaunay optimal criter...