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

针对目前基于影响域多边形剖分的点删除算法缺陷,提出一种二维Delaunay三角网点删除算法。首先利用具有拓扑关系的三角网搜索影响多边形,并以三角形矢量面积为工具三角剖分影响域多边形,最后通过镶嵌优化后的剖分三角网完成点的删除,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。

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

At present there are 4 kinds of algorithms of the point deletion of 2D Delaunay 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 position.The efficiency analysis to the algorithm was carried on and proved that the efficiency is higher than other similar algorithms.