一种快速生成平面Delaunay三角网的横向扩张法

被引：16

作者：

刘永和 ^{[1
]}

王燕平 ^{[2
]}

齐永安 ^{[1
]}

机构：

[1] 河南理工大学

[2] 中国科学院大气物理所东亚区域气候-环境重点实验室全球变化东亚区域研究中心

来源：

地球信息科学 | 2008年 / 01期

关键词：

Delaunay三角网; 快速算法; LOP优化; 不规则三角网; 时间复杂度;

D O I：

暂无

中图分类号：

TP391.41 [];

学科分类号：

080203 ;

摘要：

目前已有多种基于平面上离散点集构造Delaunay三角网的算法,其中三角网扩张法、逐点插入法的平均时间复杂度为O(n2),分治算法和其他分块合并算法能使平均时间复杂度接近线性,但增加了算法的复杂性,从而使浮点计算误差错误发生的机率增大。本文作者提出了一种新算法:将用于构网的离散点集先按横坐标从小到大排序,在空间上表现为从左到右排列;然后先以点序列中的前三个点作为初始三角网,每次将剩余点集中最左边的点联入三角网,最终得到一个三角剖分,再用LOP法优化三角剖分。该算法的优势是具有快速的三角剖分过程,使整体的平均时间复杂度为O(n),并且构网效率高,算法简单。

引用

页码：20 / 25

页数：6

共 16 条

[1] 一种基于三角网扩张法的Delaunay三角网逐块归并算法 [J].