二维Delaunay三角网的任意点删除算法研究  

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

作　　者：张咏[1,2] 刘长星[1] 董汉军[1] 赵奋军[3] 

机构地区：[1]西安科技大学测绘科学与技术学院,陕西西安710054 [2]中冶成工上海五冶建设有限公司,上海201900 [3]浙江省第七地质大队,浙江丽水323000

出　　处：《地理与地理信息科学》2008年第6期50-53,共4页Geography and Geo-Information Science

摘　　要：针对目前基于影响域多边形剖分的点删除算法缺陷,提出一种二维Delaunay三角网点删除算法。首先利用具有拓扑关系的三角网搜索影响多边形,并以三角形矢量面积为工具三角剖分影响域多边形,最后通过镶嵌优化后的剖分三角网完成点的删除,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。At present there are 4 kinds of algorithms of the point deletion of 2D Detaunay TIN in domestic and foreign studies. The＇point deletion algorithms based on the influence territory polygon triangulation is simply and easy to understand and realize. Although the algorithm efficiency is high, the influence polygon＇s search is imperfect, which only can process the influence territory for the simple polygon situation. In this paper, the influence polygon＇s search method was consummated through taking advantage of the topological relation of triangulation net. And then the triangle vector area tool was used for the triangulation of the random polygon. Lastly, the point deletion was completed by mosaically optimizing the triangular net to the original posi- tion. The efficiency analysis to the algorithm was carried on and proved that the efficiency is higher than other similar algorithms.

关 键 词：不规则三角网 多边形三角剖分 点删除 唯一性 

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