%0 Journal Article
%T 一种快速生成平面Delaunay三角网的横向扩张法
%A 王燕平
%A 齐永安
%A 刘永和
%J 地球信息科学
%D 2008
%X 摘要： 目前已有多种基于平面上离散点集构造Delaunay三角网的算法,其中三角网扩张法、逐点插入法的平均时间复杂度为O(n2),分治算法和其他分块合并算法能使平均时间复杂度接近线性,但增加了算法的复杂性,从而使浮点计算误差错误发生的机率增大。本文作者提出了一种新算法:将用于构网的离散点集先按横坐标从小到大排序,在空间上表现为从左到右排列;然后先以点序列中的前三个点作为初始三角网,每次将剩余点集中最左边的点联入三角网,最终得到一个三角剖分,再用LOP法优化三角剖分。该算法的优势是具有快速的三角剖分过程,使整体的平均时间复杂度为O(n),并且构网效率高,算法简单。
%K Delaunay三角网
%K 快速算法
%K LOP优化
%K 不规则三角网
%K 时间复杂度
%U http://www.dqxxkx.cn/CN/abstract/abstract23290.shtml