| 改进的自连接Delaunay三角网生成算法 |
| |
| 引用本文： | 凌海滨,吴兵.改进的自连接Delaunay三角网生成算法[J].计算机应用,1999,18(12):10-12. |
| |
| 作者姓名： | 凌海滨 吴兵 |
| |
| 作者单位： | 北京大学计算机科学技术研究所，北京 100871 |
| |
| 基金项目： | 国家“九五”重中之重科技攻关项目!（96B020312） |
| |
| 摘 要： | 本文提出了一个改进的自连接Ｄｅｌａｕｎａｙ三角网生成算法。在原算法的基础上引进了封闭点的概念，在三角网的生成过程中动态地剔除封闭点，从而大大加快了生成新三角形时对点的查找过程。其次，通过对边扩展过程的研究，发现对除了第一个三角形以外的其他三角形实际上只有两条可扩展的边，新算法对这一点也进行了改进。最后，给出了实验的结果数据。
|
| 关 键 词： | 自连接三角网 Delaunay三角剖分 封闭点 链表 |
| 修稿时间： | 1999年9月14日 |
AN IMPROVED ALGORITHM FOR AUTO-CONNECTED DELAUNAY TRIANGULATION |
| |
| Ling Haibin Wu Bing Institute of Computer Science and Technology,Peking University,Beijing.AN IMPROVED ALGORITHM FOR AUTO-CONNECTED DELAUNAY TRIANGULATION[J].journal of Computer Applications,1999,18(12):10-12. |
| |
| Authors: | Ling Haibin Wu Bing Institute of Computer Science and Technology Peking University Beijing |
| |
| Affiliation: | Ling Haibin Wu Bing Institute of Computer Science and Technology,Peking University,Beijing 100871 |
| |
| Abstract: | In this paper, we presented an improved algorithm for auto connected Delaunay triangulation. Based on the original algorithm, we proposed the notion of closed point. During the process of triangulation, the closed points are dynamically removed, therefore evidently accelerates the process of searching new point while generating new triangle. Second, according to the observation on edge expanding during the algorithm, we found out that every triangle, except the first one, has actually only two edges that need to be expanded. We also applied this discovery to our algorithm. Last, the experimental result is given. |
| |
| Keywords: | Auto connected triangulation Dealaunay triangulation Closed point List |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
