Abstract: This paper presents the research status of Delaunay triangulation algorithm and uses mesh generation to improve the speed of network construction. The paper makes the full use of topological relation between point and triangle, and reduces the times of the calculation of barycenter based on point-edge direction locating thesis to increase the efficiency of the location of triangle and accelerate the speed of network construction. The experimental results prove that the algorithm is of high efficiency and stability.

Key words: Triangular Irregular Network（TIN）, point insertion, triangle location

摘要： 讨论了离散点建立Delaunay三角网算法的研究现状，并采用网格划分提高构网速度。由于三角形定位的速度是影响构网速度的关键因素，改进了基于点线关系方向定位算法，充分利用点与三角形的拓扑关系，减少点线关系的方向定位算法中计算重心的次数，从而提高了三角形定位的效率和构网速度。通过测试证明了算法的高效型和稳定性。

关键词: 不规则三角网, 逐点插入法, 三角形定位