浅析平面Voronoi图构造及应用.ppt
《浅析平面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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 浅析 平面 Voronoi 构造 应用
链接地址:https://www.31doc.com/p-2597413.html