泰森多边形(Voronoi图)生成算法

泰森多边形(Vn图）生成算法作者谢卫国创立时间-1027审核人审核时间102文档状态草稿文档版本Ve .审批人审批时间最后修改人谢卫国最后修改时间0-7文档编号面向人员技术开发人员一、 文档目的本文描述了在gomdel模块中,生成泰森多边形所使用的算法。二、 概述GIS和地理分析中常常采用泰森多边形进行迅速插值，和分析地理实体的影响区域,是解决邻接度问题的又一常用工具。荷兰气候学家AHThessn提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的措施,即将所有相邻气象站连成三角形，作这些三角形各边的垂直平分线，于是每个气象站周边的若干垂直平分线便围成一种多边形。用这个多边形内所涉及的一种唯一气象站的降雨强度来表达这个多边形区域内的降雨强度，并称这个多边形为泰森多边形。如图1，其中虚线构成的多边形就是泰森多边形。泰森多边形每个顶点是每个三角形的外接圆圆心。泰森多边形也称为Vronoi图，或dihlet图。图1泰森多边形泰森多边形的特性是:l 每个泰森多边形内仅具有一种离散点数据l 泰森多边形内的点到相应离散点的距离近来l 位于泰森多边形边上的点到其两边的离散点的距离相等泰森多边形可用于定性分析、记录分析、邻近分析等。例如,可以用离散点的性质来描述泰森多边形区域的性质；可用离散点的数据来计算泰森多边形区域的数据;判断一种离散点与其他哪些离散点相邻时，可根据泰森多边形直接得出,且若泰森多边形是n边形，则就与n个离散点相邻；当某一数据点落入某一泰森多边形中时,它与相应的离散点最邻近,无需计算距离。在泰森多边形的构建中，一方面要将离散点构成三角网。这种三角网称为Delauay三角网。三、 Delauay三角形的构建Deuny三角网的构建也称为不规则三角网的构建,就是由离散数据点构建三角网，如图,即拟定哪三个数据点构成一种三角形,也称为自动联接三角网。即对于平面上n个离散点,其平面坐标为(i，yi）,1,2,，n，将其中相近的三点构成最佳三角形,使每个离散点都成为三角形的顶点。 图2 Delaunay三角网自动联接三角网的成果为所有三角形的三个顶点的标号,如:1,8；2,3;3，8,7;为了获得最佳三角形,在构三角网时，应尽量使三角形的三内角均成锐角，即符合Deaay三角形产生的准则：1、 任何一种elauna三角形的外接圆内不能涉及任何其他离散点。2、 相邻两个lnay三角形构成凸四边形,在互换凸四边形的对角线之后,六个内角的最小者不再增大。该性质即为最小角最大准则。图3凸包下面简介Tai(193)提出的在n维欧拉空间中构造Deny三角形的通用算法-凸包插值算法。(一）、凸包生成1、求出点集中满足min（x-)、min(x+y）、x(xy)、x（x+）的四个点,并按逆时针方向构成一种点的链表。这4个点是离散点中与涉及离散点的外接矩形的4个角点近来的点。这个点构成的多边形作为初始凸包。、对于每个凸包上的点I,设它的后续点为J,计算矢量线段IJ右侧的所有点到I的距离,求出距离最大的点K。3、将K插入I、之间,并将K赋给J。4、反复、3步,直到点集中没有在线段IJ右侧的点为止。、将J赋给I,J取其后续点，反复2、步。、当凸包中任意相邻两点连线的右侧不存在离散点时,结束点集凸包求取过程。完毕这一步后,形成了涉及所有离散点的多边形(凸包),如图3所示。(二）、环切边界法凸包三角剖分在凸包链表中每次寻找一种由相邻两条凸包边构成的三角形,在该三角形的内部和边界上都不涉及凸包上的任何其他点。将这个点去掉后得到新的凸包链表。反复这个过程,直到凸包链表中只剩三个离散点为止。将凸包链表中的最后三个离散点构成一种三角形,结束凸包三角剖分过程。图4 环切边界法凸包三角剖分完毕这一步后，将凸包中的点构成了若干Delaa三角形,如图4所示。（三）、离散点内插在对凸包进行三角剖分之后，不在凸包上的其他离散点，可采用逐点内插的措施进行剖分。基本过程为：、选择一种尚未构成三角形的离散点、在已经生成的三角形中，找出该离散点的三角形（离散点在该三角形在内部或者在该三角形的边上）3、如果离散点在三角形的内部，则将该三角形以及三角形的边删除,然后将三个顶点以及离散点分别连接,形成三个新的三角形。如果离散点在三角形的边上,记录点所在的边,根据拓扑关系，找出该边的左右相邻三角形T1,T,添加四条新边和四个新三角形NT,删除T,T2以及边E。对于新生成的三角形,需要挨个对其边进行空外接圆检测。具体做法为：对于新生成的三角形的边,找出该边相邻的两个三角形，判断该边一侧的对角的顶点与否位于此外一种三角形的外接圆的里面。如果是,则将边E删除，再将两个对角连接起来,形成两个新的三角形。对于新三角形的边,同样需要进行空外接圆检测,如此继续进行,直到所有新生成的三角形都通过空外接圆检测为止。4、反复1、3,直到所有非凸壳离散点都插入完为止。完毕这一步后，就完毕了Deaua三角网的构建,如图所示。图离散点内插四、 泰森多边形的建立环节建立泰森多边形算法的核心是对离散数据点合理地连成三角网，即构建eunay三角网。建立泰森多边形的环节为:1、离散点自动构建三角网,即构建Deluay三角网。对离散点和形成的三角形编号，记录每个三角形是由哪三个离散点构成的。、找出与每个离散点相邻的所有三角形的编号,并记录下来。这只要在已构建的三角网中找出具有一种相似顶点的所有三角形即可。图6 泰森多边形的建立3、对与每个离散点相邻的三角形按顺时针或逆时针方向排序,以便下一步连接生成泰森多边形。排序的措施可如图6所示。设离散点为o。找出以o为顶点的一种三角形,设为；取三角形除以外的另一顶点,设为a,则另一种顶点也可找出,即为;则下一种三角形必然是以f为边的，即为三角形F;三角形的另一顶点为e,则下一三角形是以为边的;如此反复进行，直到回到oa边。、计算每个三角形的外接圆圆心,并记录之。5、根据每个离散点的相邻三角形,连接这些相邻三角形的外接圆圆心，即得到泰森多边形。对于三角网边沿的泰森多边形,可作垂直平分线与图廓相交,与图廓一起构成泰森多边形。