二维Delaunay三角网的任意点插入算法研究  

Study on the Algorithm for Two-Dimensional Random Point Insertion of Delaunay TIN

作　　者：张咏[1] 杨瑜华 董汉军[1] 

机构地区：[1]西安科技大学测绘科学与技术学院,陕西西安710054 [2]中冶成工上海五冶建设有限公司,上海201900

出　　处：《地理与地理信息科学》2009年第4期45-48,共4页Geography and Geo-Information Science

摘　　要：针对目前各种点插入算法的不足,提出一种二维Delaunay三角网任意点插入算法。首先基于凸壳区分点的位置,并利用三角形面积坐标、重心和点与有向线段关系三者构建的融和算法搜索插入点所在三角形,然后通过构建和优化新三角形完成点的插入,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。At present,there are many algorithms for the point insertion of Delaunay TIN, but their efficiency is low. There. are many factors that restrict the speed of point insertion. The most important reason is how to locate point in the triangle. According to the number of arithmetic steps in the algorithm, the operating efficiency can be measured quantitatively. Firstly, in this paper,the point location algorithm of the shortest path was analyzed by using of the advantages of existing algorithms. The point location was done using harmonious blend algorithm, which is designed according the relation of point and directed line segment, center of gravity and coordinate of triangle area. Then, using the point location algorithm, the point would be inserted into Delaunay TIN. Finally,the analysis and test showed that the application of point location algorithm greatly improved the effi- ciency of point insertion.

关 键 词：不规则三角网 点插入 点定位 凸壳 

分 类 号：P208[天文地球—地图制图学与地理信息工程]