| 结合二叉树和Graham扫描技术的高效Delaunay三角网构建算法* |
| |
| 引用本文： | 李根,邹志文,鞠时光. 结合二叉树和Graham扫描技术的高效Delaunay三角网构建算法*[J]. 计算机应用研究, 2010, 27(3): 894-896. DOI: 10.3969/j.issn.1001-3695.2010.03.023 |
| |
| 作者姓名： | 李根 邹志文 鞠时光 |
| |
| 作者单位： | 江苏大学,计算机学院,江苏,镇江,212013 |
| |
| 基金项目： | 江苏省研究生科研创新计划资助项目(CX07B_125z);江苏省中小企业技术创新资金资助项目(BC2008140)；镇江市社会发展计划资助项目(SH2008028) |
| |
| 摘 要： | 为了提高不规则三角网的构建速度，提出了一种高效构建Delaunay三角网算法。首先对平面上的离散点集按一定的阈值进行分块，建立子块索引二叉树，然后利用Graham扫描技术对各子块构建Delaunay三角网，最后自底向上合并具有相同父节点的子块。通过具体实验与其他构网算法比较，该算法在构网速度上具有明显的优越性。
|
| 关 键 词： | 二叉树； Delaunay三角网； Graham扫描技术； 数据分块 |
Efficient algorithm of constructing Delaunay triangulation based on binary tree and Graham scanning technique |
| |
| LI Gen,ZOU Zhi-wen,JU Shi-guang. Efficient algorithm of constructing Delaunay triangulation based on binary tree and Graham scanning technique[J]. Application Research of Computers, 2010, 27(3): 894-896. DOI: 10.3969/j.issn.1001-3695.2010.03.023 |
| |
| Authors: | LI Gen ZOU Zhi-wen JU Shi-guang |
| |
| Affiliation: | (College of Computer, Jiangsu University, Zhenjiang Jiangsu 212013, China) |
| |
| Abstract: | In order to enhance the speed of constructing triangulated irregular network, this paper proposed an efficient algorithm of constructing Delaunay triangulation. Firstly, split the set of discrete points into several subsets with a threshold value and built an index binary tree during that process. Secondly it built Delaunay triangulation on these subsets by Graham scanning technique. Finally, merged the blocks with the same parent node from bottom to top. The result of the experiments shows that the algorithm, compared with other ways, has a distinct superiority in the speed of constructing irregular network. |
| |
| Keywords: | binary tree Delaunay triangulation Graham scanning technique dataset partition |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
