| 一种基于Graham三角剖分生成Delaunay三角网的算法 |
| |
| 引用本文： | 宋晓宇,李东,王永会,王洪信. 一种基于Graham三角剖分生成Delaunay三角网的算法[J]. 沈阳建筑工程学院学报(自然科学版), 2007, 23(2): 328-331 |
| |
| 作者姓名： | 宋晓宇 李东 王永会 王洪信 |
| |
| 作者单位： | [1]沈阳建筑大学信息与控制工程学院,辽宁沈阳110168 [2]沈阳建筑大学图书馆,辽宁沈阳110168 |
| |
| 基金项目： | 科技部科技成果重点推广计划 |
| |
| 摘 要： | 目的提出一种基于Graham三角剖分生成Delaunay三角网的算法,加快Delaunay三角网的生成速度.方法首先按Graham扫描法对平面散乱点集进行排序,然后将排好序的点通过可见点的判断连接成Graham三角网,最后利用拓扑结构快速进行优化,使其成为Delaunay三角网.结果通过500至10000个点的测试,表明这种基于Graham三角剖分生成Delaunay三角网的生成速度快于传统基于凸包生成Delaunay三角网的生成速度.结论采用可见点表的数据结构以及利用点、边、三角形的有序性的特点构建Delaunay三角网,是提高建网速度的关键.
|
| 关 键 词： | Graham扫描法 Graham三角网 Delaunay三角网 可见点 |
| 文章编号： | 1671-2021(2007)02-0328-04 |
| 修稿时间： | 2006-10-14 |
An Algorithm of Constructing Delaunay Triangulation Based on Graham |
| |
| SONG Xiaoyu,LI Dong,WANG Yonghui,WANG Hongxin. An Algorithm of Constructing Delaunay Triangulation Based on Graham[J]. Journal of Shenyang Archit Civil Eng Univ: Nat Sci, 2007, 23(2): 328-331 |
| |
| Authors: | SONG Xiaoyu LI Dong WANG Yonghui WANG Hongxin |
| |
| Abstract: | In this paper,we present an algorithm of constructing Delaunay triangulation based on Graham's scan to accelerate the speed of constructing Delaunay triangulation.Firstly,the points must be arranged according to Graham's scan;secondly,the Graham triangulation is constructed with the arranged points by judging their visibility;and finally the triangulations are optimized into Delaunay triangulations using topological structure.By testing 500 to 10000 points,it shows that the constructing speed of this algorithm is faster than that of the traditional constructing triangulation algorithm.The conclusion shows that the key to accelerating the speed is to adopt the data structure of visible points and use the order characteristic of points,edges and triangles. |
| |
| Keywords: | Graham's scan Graham triangulation Delaunay triangulation visible point |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
