基于凸壳技术的Delaunay三角网生成算法

被引：17

作者：

陈学工 ^{[1
]}

陈树强 ^{[1
]}

王丽青 ^{[2
]}

机构：

[1] 中南大学信息科学与工程学院

[2] 中南大学信息物理工程学院

来源：

计算机工程与应用 | 2006年 / 06期

关键词：

Delaunay三角剖分; 凸壳; 计算几何;

D O I：

暂无

中图分类号：

TP391.41 [];

学科分类号：

080203 ;

摘要：

该文提出了一种针对散乱点集的快速构建Delaunay的算法。该算法首先对散乱点按有向角进行排序,以排序后的点顺序为基础,利用凸壳特性快速将散乱点联结成三角网,最后利用拓扑结构快速将其优化为Delaunay三角网。在联网过程中,充分利用有序点子集的凸壳特性,避免了所有的交点测试,从而保证了对散乱点集生成Delaunay三角网的效率。

引用

页码：27 / 29

页数：3

共 6 条

[1]

The Delaunay triangulation of a point set within an arbitrary2D domain. Min Weidong,Tang Zesheng. The Chinese Journal . 1995

[2]

Delaunay triangulations in TIN creation:an overview and a linear-time algorithm. Victor J D Tsai. International Journal of GIS . 1993

[3]

The Quick hull Algorithm for Convex Hulls. C Bradford Barber,David P Dobkin,Hannu Huhdanpaa. ACM Transactions on Mathematical Software . 1996

[4]

An Algorithm of Speedily Building TIN Based on Topological Structure and Convex Shell in GIS. Zhang Xiaocan,Huang Zhicai,Dai Qicheng et al. The Chinese Journal . 2002

[5]

Fast Delaunay Stratification. Petr Vaneecek,Ivana Kolingero. ACM . 2003

[6]

Improvements to randomized incremental delaunay insertion. I Kolingerova,B Zal. Computer Graphics . 2002

← 1 →