资源描述：
《Voronoi图矢量算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、GIS原理与算法第七章Voronoi图构建算法（basedonVector）2011.6Voronoi图¢Voronoi图是计算几何中最重要的几何结构之一（紧次于凸壳），¢它描述了对于一系实体集的邻近性问题。¢邮局问题；¢观测台问题；¢学校（医院）问题；Voronoi图¢Voronoi图的概念是由Dirichlet在1850年首先提出；¢俄国数学家Voronoi于1907年在文章中做了进一步阐述，并提出高次方程化简；¢气象学家Thiessen在1911年为了提高大面积气象预报结果，应用Voronoi图对观测站进行划分观测区域（多边形）；¢为了纪念这些科学家的成就，这种结构被称为Dir
2、ichlet剖分或Voronoi图或Thiessen多边形。主要内容¢Definitions&Properties(定义和性质)¢VectorAlgorithm(矢量算法)¢Order-kVD(多阶VD)¢LineandareaVD(线和面的VD)¢MinkowskimetricVD(M度量VD)¢OtherVoronoidiagram(其他VD)¢Applications(应用)1、Definitions&Properties¢非形式化定义：做靠近基点集合中每一个基点区域的组合。¢基于距离概念：平面中N个点的集合S，对于S中每个点pi，平面中更接近的点pi的轨迹即为Voronoi图
3、，即：V(p)={x:p−x≤p−x,∀j≠i}iij1、Definitions¢基于half-planes概念：N个点的Voronio图是N-1个半平面的交,表示为：V(p)=Ih(p,p)i1≤j≤n,j≠iijProperties（1）¢假设：集合S中，没有四点是共圆的。¢Voronoi图是度数为三的正则图（图论），即：Voronoi图的每一个顶点恰好是图解的三条边的交点。¢在S中，pi的每一个最邻近点确定一条Voronoi图多边形的一条边。¢多边形V（i）是无界的当且仅当pi是集合S的凸壳的边界上的一个点。¢对于S的Voronoi图的每一个顶点v，圆C（v）不包含S的其它的点
4、（最大空圆）。Properties（2）¢N个点上的一个Voronoi图至多有2N-5个顶点和3N-6条边。¢对于欧拉公式：m−m+m=2vef对于V（p）：(n+1)−n+n=2vePropertiesofD(p)&V(p)PropertiesofD(p)&V(p)¢EachVoronoiregionV(P)isconvex.¢IfvisaVoronoivertexatthejunctionofV(p1),V(p2),andV(p3),thenvisthecenterofthecircleC(v)determinedbyp1,p2,andp3.¢C(v)isthecircumcir
5、clefortheDTcorrespondstov.¢TheinteriorofC(v)containsnosites.¢Ifpiisthenearestneighbortopj,then(pi,pj)isanedgeofD(p).¢Ifthereissomecirclethroughpiandpjwhichcontainsnoothersites,then(pi,pj)isanedgeofD(p).Thereversealsoholds:foreveryDelaunayedge.Thereissomeemptycircle.2、VectorAlgorithm•自Shamos和Hoe
6、y[1975]把Voronoi图作为一种有效的数据结构引入计算机领域，并成为计算几何领域的主要研究热点之一。•许多学者对：•平面点集Voronoi图的算法[Shamos&Hoey,1975;Hwang,1979;Lee,1980,………]•平面特殊复杂实体的Voronoi算法，如线段[Kirkpatrick,1979]、线状或非交圆片状[Lee,1981]、任意圆片状[Sharir,1985]、平面凸壳[Leven&Sharir,1987]和曲线[Yap,1987]等做了深入的研究，并建立了许多有效的算法，2、VectorAlgorithm°以上算法都是以离散点集算法为基础。经典点集
7、的算法归纳起来有四种[Aurenhammer1991]：°增量法(Incrementalmethod)°分治法(Divide-and-conquermethod)°间接法(In-directedmethod)°扫描法(Planesweepmethod)2.1增量法(IncrementalMethod)1.基本原理：增量法增量法2.边界问题°三点设置：增量法3.时间复杂度°比较距离：°每点需要O（l）°O(1+2+….+(n-1))=O(n)2增量法增量法4
