三角剖分

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

裴帅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图的对偶图就是点