基于Delaunay三角网的等值线绘制算法  

Algorithm of drawing isoline based on Delaunay triangle net

作　　者：蒋瑜[1] 杜斌[1] 卢军[1] 王鹏[1] 

机构地区：[1]成都信息工程学院软件工程学院,成都610225

出　　处：《计算机应用研究》2010年第1期101-103,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(60702075);成都信息工程学院院选自然科学基金资助项目(CSRF200702)

摘　　要：提出了一种快速构建Delaunay三角网算法(QGDTN)。在每次迭代中,该算法从点集P最左边的两点中,选取离凸边中点距离最近的一点与凸边构成Delaunay三角形,并加入三角网中,算法实现简单,且时间复杂度为O(n)。基于Delaunay三角网,根据三角形的各边上是否有等值点,用内插值法求出等值点坐标,跟踪、连接等值点生成等值线;最后,采用三次方Bezier曲线平滑等值线。实验证明,基于Delaunay三角网的等值线绘制算法是高效的,并且具有一定的实用价值。This paper proposed a new algorithm for quick generation Delaunay triangle net. In iterations, this algorithm selected a point from the leftmost two points in point set P, and the distance between this point and midpoint of convex edge was minimal. This point and convex edge constructed new Delaunay triangle, and added them to Delaunay triangle net. The naverage time complexity of the algorithm was O（n）. Based o Delaunay triangle net, computed the coordinate of equivalent points according to using interpolating method if there were equivalent points in each edge of triangles. Tracing and drawing equivalent points created isolines. At last, smoothed isolines based on cubic Bezier curve. Experiments results show the algorithm of drawing isoline based on Delaunay triangle net are high efficiency, and have some practical value.

关 键 词：等值线 DELAUNAY三角网 LOP优化 BEZIER曲线 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] P207[自动化与计算机技术—计算机科学与技术]