| 基于分治策略的快速构建Delaunay三角网算法 |
| |
| 引用本文： | 宋晓宇,戚爰伟,王永会,魏志勇.基于分治策略的快速构建Delaunay三角网算法[J].沈阳建筑工程学院学报(自然科学版),2007,23(5):862-865. |
| |
| 作者姓名： | 宋晓宇 戚爰伟 王永会 魏志勇 |
| |
| 作者单位： | 沈阳建筑大学信息与控制工程学院 辽宁沈阳110168(宋晓宇，戚爰伟，王永会)，沈阳建筑大学学报编辑部 辽宁沈阳110168(魏志勇) |
| |
| 摘 要： | 目的降低构建Delaunay三角网的时间复杂度,提高构建Delaunay三角网的速度.方法首先递归分割点集,然后按照构网条件以分割线为轴线对其两侧的点进行构造三角网的操作,直至每个点都被包含进所构建的三角网,最后使其成为Delaunay三角网.结果通过1000~5000个点的测试,表明基于分治策略的快速构建Delaunay三角网的生成速度要快于传统基于分治策略生成Delaunay三角网的速度.结论该方法能够到边建网边优化,使程序一次成型,提高了建网速度,本算法的设计思想还可以推广到三维空间.
|
| 关 键 词： | 分治 Delaunay三角网 候选点 基边 |
| 文章编号： | 1671-2021（2007）05-0862-04 |
| 修稿时间： | 2007-03-10 |
A Fast Construction Algorithm of Delaunay Triangulation Based on Divide and Conquer |
| |
| SONG Xiaoyu,QI Yuanwei,WANG Yonghui,WEI Zhiyong.A Fast Construction Algorithm of Delaunay Triangulation Based on Divide and Conquer[J].Journal of Shenyang Archit Civil Eng Univ: Nat Sci,2007,23(5):862-865. |
| |
| Authors: | SONG Xiaoyu QI Yuanwei WANG Yonghui WEI Zhiyong |
| |
| Abstract: | Reduce the time complexity and enhance velocity of constructing the Delaunay TIN.First,divide up point set,and then construct the Delaunay TIN in axis of the division according to the TIN condition,we do this until every point is embodied into our constructed TIN,and we make it Delaunay TIN at last.It indicates that the velocity of such method which is based on divide and conquer is higher than the conventional one.This algorithm could establish and meanwhile optimize the Delaunay TIN,enabling the procedure formed before,enhancing its whole velocity.The design concept of this algorithm may also be promoted to the three-dimensional space. |
| |
| Keywords: | divide and conquer Delaunay triangulation candidate point basic edgc |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
