平面点集三角剖分算法的改进性研究

三角剖分

平面点集三角剖分算法的改进性研究

裴帅1, 王洋2

PEI Shuai1, WANG Yang2

1.山西大学 计算机与信息技术学院,山西省 太原市 030006 2,桂林理工大学 信息工程学院 广西省 桂林市 541006

1. College of Computer & Information Technology, Shanxi University, Taiyuan 030006, China 2. College of Information Engineering,Guilin, Guilin University of Technology Guangxi 541006 China E-mail: peishuai11428@

Planar point set triangulation dividing algorithm improvement research

Abstract: This paper introduces the triangulation of the basic knowledge and methods, and the use of VB development tools to achieve an improved triangulation algorithm. Discuss the various existing triangulation between faults, and all of the split were analyzed, finally the existing triangulation algorithm is given based on a hash point density method, makes the results more reasonable triangulation . Keywords: planar points, triangulation, density production method

摘要：本文介绍了三角剖分的基本知识和方法，并且使用VB开发工具实现了一种改进后的三角剖分算法。讨论了现有各种三角剖分之间的优缺点，并对各种剖分进行了系统分析，最终在现有剖分算法的基础上给出了一种散列点密度产生法，使得三角剖分的结果更加合理。 关键字：平面点，三角剖分,密度产生法

1平面点集三角剖分的定义

定义1.1给定平面内顶点集合{Vi}(i=1,2...,n),，用不相交的直线段连接Vi与

Vi,1＃i,j

n,i

j,使得n个点的凸壳内的每一个区域是一个三角形，这个过程称为三角

剖分，剖分后所形成的三角网格T也称为顶点集{Vi}的一个三角剖分。

在一般情况下，三角剖分对于顶点集合{Vi}的剖分结果并不是唯一的，按照以上定义进行剖分可能出现多种结果。当然，形态较优的三角剖分网格只是部分产生的结果，能够满足实际应用的需求。从实际经验中我们得到，如果三角形是等边的或者近似等边，这种形态的三角剖分则称为最小权三角剖分。无论是最近点意义下的Voronoi图，还是最远意义下的Voronoi图，都与点集的三角剖分有着密切的关系：最近意义下Voronoi图的对偶图就是点

三角剖分

集的一种三角剖分，因而由点集的三角剖分可以计算Voronoi图；最远点意义下Voronoi图的对偶图是点集凸壳（凸多边形）的一种三角剖分，由点集凸壳的某种三角剖分可以求得Voronoi图（只要该Voronoi图存在）。下面介绍集中平面点集三角剖分的几种算法。

2平面点集三角剖分算法及比较

2.1平面点集三角剖分的贪心算法

平面点集三角剖分算法的主要思想是对两点间的距离按照长短进行排序，生成长度不同线段，从小到大依次从这些线段中提取出三角剖分边，知道变数达到剖分要求。最终使剖分的边长度达到最小。

此算法虽然简单并且容易实现，但是其时间复杂度和空间复杂度都比较高，剖分的总体效率不高。

2.2渐次插入的三角剖分算法

渐次插入算法是对现有的Delaunay三角剖分插入新的点，当插入一个新点后，Delaunay三角网格将重新划分。初始三角网包含所有的数据点，可以未超三角形。算法如下：

步骤1定义包含所有数据点并作为初始Delaunay三角形的超三角形的顶点； 步骤2从数据中取出一点P加入到三角网中；

步骤3搜寻包含点P的三角形，将P与次三角形的三个顶点相连，形成三个三角形； 步骤4应用Lawson Lop从里到外更新所有生成的三角形； 步骤5重复步骤2至步骤4，直到所有点处理完毕； 步骤6删除所有包含一个或多个超三角形顶点的三角形。 2.3 Tsung-pao Fang和Les.pieg的Delaunay三角剖分算法

Tsung-pao Fang和Les.pieg的Delaunay三角剖分算法是一种较快的算法，这里简单说一下它的算法思想，就是使用一种单元格的网格构成形成三角形，然后搜寻边界和最近的点，通过凸壳旋转生成三角形。 2.4几种算法的比较

1.贪心算法的时间复杂性为O(n3)。

2.渐次插入三角网算法对约束情况下有一定的限制。

3.Tsung-pao Fang和Les.pieg的Delaunay三角剖分算法的时间复杂性为O(n)为线性的时间复杂度，同时生成的Delaunay三角形比较好，但该算法容易出现退化现象。

3一种新的平面点集三角剖分的算法

3.1算法的基本思想

本人在现在平面点集三角剖分算法基础上，研究出一个新的平面点集Delaunay三角剖

三角剖分

分算法。以上三角剖分算法都只是基于边和三角的形生成，而没有考虑平面中数据点集的生成对剖分的影响。

平面点集的生成会对整个抛分结果产生影响。如图3-1所示，由于A区域中的点过于集

图3-1 示例

中，而其它区域中的点比较分散使得抛分结果中出现了大量的病态三角形。这种病态三角形将会严重影响抛分算法。所以本人针对此缺点对抛分算法进行改进。算法的基本思想是：首先在平面点的提取方面，要尽量保证点集均匀的分布在所抛分的区域，然后在对平面点集进行抛分。

本人在均匀点生成过程中采取密度生成法。如图3-2所示，我们将抛分区域面积除以抛分点个数得到区域A，在插入点时我们将随机生成一个坐标点D，判断以点D为中心以A区域为范围内是否有点存在，如果有点存在那么在D坐标中插入点，如图3-2中D1 点坐标所示在区域A1中没有其它点，所以在D1 点可以插入数据点。如果不存在将重新寻找其它区域插入数据点，如图3-2中要插入D2点在A1区域已经存在D3点那么此区域就不能在插入新点。这种方法可以使数据点均匀的分布在整个区域。

图3-2 示例

3.2算法的具体描述

输入：平面面积S，数据点个数n。 输出：平面中n个点的三角剖分列表L。 具体步骤如下：

步骤1使用平面面积S除以数据点个数n等于单位点最少所需面积Smin。 步骤 2 随机在平面范围内选取一个坐标d(x,y)。

步骤 3 判断以d(x,y)点为中心点，判断在Smin为正方形面积范围内是否存在点。如

三角剖分

果存在执行步骤2，否则继续执行下一步。

步骤 4 将坐标d(x,y)插入D(d1,d2...dk),k<=n（数据点集合）。 步骤 5 执行步骤2直到n个点全部插入D(d1,d2...dk),k<=n

步骤 6 从D(d1,d2...dn)中取出三个不在同一直线上的点d1,d2,d3为待扩展的三角形的顶点，d1d2为待扩展边。

步骤 7 查看d1d2边的使用次数flag=2，返回，如果flag<2，继续。

步骤 8 在点列表D中查找满足条件的点d4，依次从列表中取出点di(i=1,2...n)；执行步骤3时会出现以下几种情况：

1)判断di(i=1,2...n)点是否为三角形的端点，如果是，转步骤3，否则继续。 2)判断di(x,y),i=1,2...n点与d3点是否分别位于线段d1(x1,y1)d2(x2,y2)两侧。这个判断是取决于两个三阶行列式

xx1x2

yy1y2

1

x3

y3y1y2

111

1 与 x11

x2

的值是否同号。如果是同号,表示d与d3位于d1d2的同一侧，转步骤3，否则继续。

3)查看p点的边是否有p1,p2点，如果有其中之一的边使用次数flag=2，转步骤3，如果flag＜2，继续。

步骤9计算d1d与dd2的夹角以及d1d'与d'd2的夹角的角度值，d'为上一次找到的点，如果新生成的角度比上一次找到的点所成的角度小，则在列表D中更新这个值并且记录d点。记录到d点就继续，否则返回步骤3。

步骤10 d点为找到的点，将以d1,d2,d4为顶点的三角形加入到三角形列表L中。 步骤11 分别更新d1,d2,d4的边表，删除所有边使用次数flag=2的点。返回步骤3，直至查找完n个点后输出结果，终止。

4算法实现与分析

本人使用VB语言对改进前算法和改进后算法进行实现。实现结果如图4-1和图4-2所示。

三角剖分

图4-1改进前算法抛分图

图4-2改进后算法抛分图

图4-1是对平面上随机生成的30个数据点进行的抛分，图4-2是对生成点算法改进后的抛分结果。我们从两图比较中可以得到改进后算法抛分结果中减少了病态三角形的数量。

我们又对两种方法进行了不同散力点进行抛分，得到抛分结果中病态三角形数量如图4-3所示。

图4-3改进后算法稳定性测试

三角剖分

在使用不同散列点个数进行测试，我们可以清晰的看到改进后算法的病态三角形有了很大的减少，并且在不同散列点个数的测试下性能比较稳定。

根据以上实验，我们可以得到改进算法减少了病态三角形的生成并且性能稳定。该算法在实际中不仅适用于各种复杂的计算区域，而且能非常方便的实现局部加密。它适用于计算机图形学的很多领域，该算法简单、实用、具有很强的通用性，可以满足很多实际工程的需要。

参考文献:

[1] 薛禹群,谢春红.地下水数值模拟[M].版本.北京:科学出版社,2007:383-401. [2] 孙讷正.地下水流数学模型和数值方法[M].版本.北京:地质出版社,1981:242-252. [3] 玄光男,程润伟.遗传算法与工程设计[M]. 北京:科学出版社, 2000. [4] 张文修,梁怡.遗传算法的数学基础[M].西安: 西安交通大学出版社,2000. [5] 吴秋玲,江金龙.一种定向交叉的单纯形遗传算法[J].九江学院学报,2007,3:8-11 [6] 张智星,孙春在.神经-模糊和软计算[M].西安: 西安交通大学出版社,2000:131—135

[7] 李令莱,王凌,郑大钟.基于Simplex-annealing 混合方法的模型参数估计[J].清华大学学报,

2002,42(9):1207-1208.

[8] Jesús Carrera, Andrés Alcolea. Inverse problem in hydrogeology [J]. Hydrogeology Journal, 2005,

13(1):206-222.

[9] Mahinthakumar G. Hybrid genetic algorithm local search methods for solving groundwater source

identification inverse problems [J]. Journal of Water Resources Planning and Management, 2005, 131(1):45-57.

作者简介：裴帅，女，1984年12月25日出生，硕士，研究方向为地下水数值模拟。 王洋，男，1983年4月15日出生，硕士，研究方向为网格的剖分

基金项目：山西省回国留学人员科研项目(Research Project Supported by Shanxi Scholarship Council of China No.200811)

联系方式：电话：13403436836；地址：山西大学计算机与信息技术学院；邮编：030006 Email：peishuai11428@

本文来源：https://www.bwwdw.com/article/stx4.html