离散点集Delaunay三角网生成算法改进与软件开发

改进了三角形生长算法，在原算法的基础上，用均匀格网来划分离散点集，建立点集的栅格索引,快速生成初始三角形，再进行扩展；引进了封闭点的概念，在扩展过程中动态删除封闭点，加快了查找点的搜索过程；软件开发中采用VC的MPC类Carry和CList来管理数据，创建了CBuildtin和Craster两个类来生成三角网和栅格索引，提高了程序的可移植性。

Improvement of generatin algorithm of Delaunay triangulation network for the whole scatter points and software development

In this paper, we presented an improved algorithm for triangulation generation. Based on the original triangulation generation algorithm, we divide the whole scatter points into uniform grids and set up grid-index. In this way, we can quickly make the first triangle and then begin to expand the whole triangulation network. Second, we introduce the notion of close-point. During the process of expanding triangulation, the close-points are dynamically removed, which will accelerate the process of searching new points and generating new triangle. In addition, every triangle, except the first one, has actually only two sides that need to be expanded. We also apply this discovery to our algorithm. Futher, during the software development, we introduce Carray and Clist, the CLASS of MFC, to manage the data. Moreover, we create CLASS Cbuildtin that is used to generate the triangulation network and CLASS Craster that is used to generate the grid index, which can efficiently manage and deal with the data.