voronoi图矢量算法.pdf

(basedonVector)Voronoi图构建算法GIS原理与算法Voronoi图„Voronoi图是计算几何中最重要的几何结构之一(紧次于凸壳),„它描述了对于一系实体集的邻近性问题。„邮局问题;„观测台问题;„学校(医院)问题;Voronoi图„Voronoi图的概念是由Dirichlet在1850年首先提出;„俄国数学家Voronoi于1907年在文章中做了进一步阐述,并提出高次方程化简;„气象学家Thiessen在1911年为了提高大面积气象预报结果,应用Voronoi图对观测站进行划分观测区域(多边形);„为了纪念这些科学家的成就,这种结构被称为Dirichlet剖分或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图,即:V(pi)={x:pi−x≤pj−x,∀j≠i}1、Definitions„基于half-planes概念:N个点的Voronio图是N-1个半平面的交,表示为:V(pi)=I1≤j≤n,j≠ih(pi,pj)Properties(1)„假设:集合S中,没有四点是共圆的。„Voronoi图是度数为三的正则图(图论),即:Voronoi图的每一个顶点恰好是图解的三条边的交点。„在S中,pi的每一个最邻近点确定一条Voronoi图多边形的一条边。„多边形V(i)是无界的当且仅当pi是集合S的凸壳的边界上的一个点。„对于S的Voronoi图的每一个顶点v,圆C(v)不包含S的其它的点(最大空圆)。Properties(2)„N个点上的一个Voronoi图至多有2N-5个顶点和3N-6条边。„对于欧拉公式:mv−me+mf=2对于V(p):(nv+1)−ne+n=2PropertiesofD(p)&V(p)PropertiesofD(p)&V(p)„EachVoronoiregionV(P)isconvex.„IfvisaVoronoivertexatthejunctionofV(p1),V(p2),andV(p3),thenvisthecenterofthecircleC(v)determinedbyp1,p2,andp3.„C(v)isthecircumcirclefortheDTcorrespondstov.„TheinteriorofC(v)containsnosites.„Ifpiisthenearestneighbortopj,then(pi,pj)isanedgeofD(p).„Ifthereissomecirclethroughpiandpjwhichcontainsnoothersites,then(pi,pj)isanedgeofD(p).Thereversealsoholds:.