摘要
Delaunay三角网在GIS/VR中用途广泛,分割—归并法和逐点插入法是目前普遍用于生成Delaunay三角网的两种算法。在研究基于这两种算法的合成算法后,对其进行了两点改进。一是简化凸壳的生成;二是三角形快速定位,通过确定向量之间的关系来解决点的定位问题,避免了复杂运算。实验结果证明,改进后的算法不仅继承原算法兼顾空间和时间的性能,且执行效率有明显提高。
Delaunay triangulation has wide application in Geographic Information System and Virtual Reality, and its two prevalent genera- tion algorithms are the divide and conquer algorithm and the incremental insertion algorithm. After having studied on the compound algorithm based on them, two improvements were made against it. One was to simplify the construction of the convex hull, the other was the fast location of the triangle, by ascertaining the relationship among vectors to resolve point＇ s locating, thus the complicated algorithm was avoided. Experi- mental results showed that the improved algorithm succeeded to the performance of the original algorithm in giving consideration to both time and space, and its executing efficiency was enhanced remarkably.
出处
《计算机应用与软件》
CSCD
2010年第8期138-140,共3页
Computer Applications and Software
基金
河南省科技厅重点科技攻关项目(0721022100)
