《浅析平面Voronoi图构造及应用.ppt》由会员分享，可在线阅读，更多相关《浅析平面Voronoi图构造及应用.ppt（27页珍藏版）》请在三一文库上搜索。
1、浅析平面Voronoi图的构造及应用,新疆乌鲁木齐市第一中学 王栋,引言：,在计算几何这一领域中，Voronoi图是仅次于凸壳的一个重要的几何结构。这是由于Voronoi图在求解点集或其他几何对象与距离有关的问题时起重要作用。 常见的问题包括谁离谁最近，谁离谁最远，等等。,现在，让我们大家首先来了解一下Voronoi图的定义！,Voronoi图的定义,设P1,P2是平面上的两个点，L是的它们的中垂线，L将平面分成两部分半平面L1和半平面L2，在L1内的点P具有特性|PP1|PP2|，即位于Ll内的点比平面中其他点更接近点P1 ，我们记半平面H(P1, P2)= L1 ，同理半平面H(P2, P
2、1)= L2 。,直线L,P1,P2,平面L1,平面L2,P,Voronoi图的定义,对于平面上n个点的点集S,定义V(Pi)=H(Pi,Pj)，即V(Pi)表示比其他点更接近Pi的点的轨迹是n-1个半平面的交集，它是一个不多于n-1条边的凸多边形区域，称为关联于Pi的Voronoi多边形或关联于Pi的Voronoi多边形域。,pi,n=6时的一种V(pi),位于多边形V(pi)内的任意一个点P满足|PPi|j),p,Pj,Voronoi图的定义,对于S中的每个点都可以 作一个Voronoi多边形，这样n个Voronoi多边形组成的图称为Voronoi图，记为Vor(S)。,n=6时的Vor(
3、S),Voronoi图的构造,传统的构造方法,分治法构造Delaunay三角剖分法,编写麻烦,难于理解,编写容易,易于理解,O(N log N),Voronoi图的构造,用分治法构造角最优三角剖分，首先要对点集依照X坐标排序。如果点集内点的个数小于等于三，那么可以直接构造，否则将点集拆分成为两个含点数目近似的点集进行构造，最后合并这两个点集。,如何合并呢？,点集内含点个数为2的情况,点集内含点个数为3的情况,合并两个子点集的角最优三角剖分,首先，求解两个点集的凸包的最下方的正切线,并连接两端点。,接下来，如图所示，A1A4为两个凸包的正切线，求出它们的中垂线L14。,然后找到L14与A1(或A
4、4)相关联的边中，中垂线与L14有交点的边，如果有多个边，那么选择交点Y坐标最小的点所关联边。,如图所示，选择的边为A1A2，那么连接A2A4，并且删除与A2A4相交的边。设A2A4为新产生的正切线。,A1,A2,A3,A5,A6,A4,直线L14,相交的边,新确定的正切线,A1,A2,A3,A5,A6,A4,Voronoi图的构造,重复上述步骤，我们就能合并两个点集的角最优三角剖分。 这样，依照该方案，我们就能构造出来点集S的角最优三角剖分了。 这个三角剖分的直线对偶图就是点集S的Voronoi图。,Voronoi图的构造,T(N)=2T(N/2)+O(N),求解含有n个点的点集的角最优三角
5、剖分,求解含有n/2个点的点集的角最优三角剖分,合并两个点集的角最优三角剖分,O(NlogN),Voronoi图的在信息学中的应用,例3.Fat Man,例1.Run Away,例2.Voronoi图与平面MST问题,Voronoi图的在信息学中的应用,例1.Run Away 平面上有一个矩形，在矩形内有一些点，请你求得矩形内另一个点，该点离与它最近的已知点最远（点的个数=1000）。,B,A,C,D,Voronoi图的在信息学中的应用,思路一：大家可能很容易想到用枚举法,情况一：过三点的圆的圆心,情况二：两点中垂线与矩形的边的交点,B,A,所求点,C,B,A,C,所求点,D,D,Vorono
6、i图的在信息学中的应用,根据刚才分析的两种情况，我们可以构造两种方案。第一种方案针对所求点为过三个点的圆的圆心的状态，我们枚举三个点，求出它们组成的三角形的外心和半径，然后枚举其它的点，看它们是不是在这个圆中。第二种方案是枚举两个点的中垂线，求出中垂线与矩形的交点，然后根据这三个点来计算最远位置，进行判断。,它的时间复杂度：O(n4),太高了,Voronoi图的在信息学中的应用,思路二：Voronoi图,首先介绍一个Voronoi图的性质：设v是Vor(S)的顶点，则圆C(v)内不含S的其他点。根据这个性质我们很容易想到用Voronoi图来解决问题，方法如下：,步1.计算点集S的Voronoi
7、图Vor(S)。,步2.计算点集S的凸壳CH(S)。设得到的圆最大半径Rmax =0。,步3.枚举每个Voronoi点v,如果v在矩形内部，计算v为圆心的圆的半径并且修改Rmax 。,步4.枚举枚个CH(S)中的边e，求出e的中垂线与矩形的交点v，计算v到边e两端点的距离，并且修改Rmax。,时间复杂度 O(n log n),Voronoi图与平面MST问题,例2.平面MST问题 给定平面上的点集S，求出连接S中所有点的最小长度的树，并且要求最小生成树的结点恰好是S中的点。,Voronoi图与平面MST问题,传统的求最小生成树的方法是贪心法，要是纯粹使用贪心法求平面最小生成树，我们所作的程序时
8、间复杂度至少为：O(n2),有没有更快的方法呢？,当然有!用Voronoi图。,Voronoi图与平面MST问题,我们都知道Voronoi图的对偶图是点集的角最优三角剖分，我们把这个三角剖分中的边组成的集合叫做DT(S). 那么，我们可以得出这样一个定理：,最小生成树MST是角最优三角剖分DT(S)的一个子集,关于定理的证明,也就是说，具有直径ab的圆周上或圆内必有S中的点，假设c在该圆周上或者圆内，那么|ac|ab|，并且|bc|ab|。那么，我们删除ab，把树T分成Ta和Tb两部分，不妨假设cTa，那么我们添加边cb，可以合并成新的树，并且的总长度小于T，因此包含ab的树长度不可能是最小的
9、。所以必然MSTDT(S),证明： 假设存在一条边abDT(S)，则由三角剖分的定理可以知道过a,b有一个空圆。因此如果ab不属于DT(S)，那么过a,b的圆不可能是空的。,a,b,c,Ta,Tb,Voronoi图与平面MST问题,根据这个条件，我们可以得到一个新的方案，构造角最优三角剖分，然后计算最小生成树，总的时间复杂度是O(n log n)。,可能大家会问这样一个问题：,我想告诉大家！Voronoi图不仅能快速解决距离问题,除了距离问题,Voronoi图还有什么用呢?,Voronoi图还可以扩宽我们的解题思路,Voronoi图拓宽解题思路,例3.Fat Man 在超市走廊上两边都是墙，中
10、间有一些障碍物，这些障碍物都是一些很小的半径可以忽略的点，你是一个胖子，可以将你的抽象成一个圆柱。现在你要从走廊的一头走到另一头。请问你最大的直径是多少？（走廊长L,宽W）,问题分析：,刚开始拿到题目可能会手足无措，如果只是知道平面上的一些点，我们很难确定从走廊一头到另一头的路线，也很难运用枚举等方法来解决问题。但是，当你学了Voronoi图，情况就不一样了！,Voronoi图拓宽解题思路,首先我们建立Voronoi图，显然一个人如果想穿过这些障碍物，那么走Voronoi边才是最佳的，因为如果不走Voronoi边，必然会使你的圆心进入一个Voronoi多边形内，这将使人更靠近一个障碍物，因而会
11、减少人的半径。所以最佳路线必定由一些Voronoi边组成。,原来障碍点,Voronoi图拓宽解题思路,接下来，由于人还可以从走廊边与障碍物之间通过，那么对于每一个障碍点(x,y)我们可以在走廊壁上增加障碍点(x,0),(x,W),一共增加2n个障碍点。另外在走廊开始和尽头增加四个障碍点（-W,0），（-W,W），（L+W,0），（L+W,W）这四个点与其它点之间距离不小与W，这样就不影响结果。然后对于这3n+4个点求Voronoi图。,最后我们对于整个图进行变相的求最短路即可。,新增点,原来障碍点,总结,距离问题,减少冗余计算,特殊几何问题,带来新思路,运用Voronoi图,运用Voronoi图,O(n4),O(n log n),O(n2),O(n log n),没思路,有思路,从无到有,化繁为简,扩展思路,总结II,巧用算法,勇于实践,谢谢大家！,