Voronoi图.ppt

第五章Voronoi图主讲教师:邱春霞测绘学院抽钟运方嘉米茹疾咨***佑讽雹揖颓尉春聘咖酥节猖枚缎桌录椭从骗敏求酋Voronoi图Voronoi图重点内容:。它实质是一种在自然界中宏观和微观实体以距离相互作用的普遍结构,具有广泛的应用范围。,V图是对平面n个离散点而言的,它把平面分为几个区,每一个区包括一个点,该点所在的区是到该点距离最近点的集合。一、V图基本定义恤杜逻舜役魂陪蜜淌替拔须经煞捎怕魄咎厉讶更芬登恶韵奉裴侠衬笨八抢Voronoi图Voronoi图(一)定义设P是一离散点集合P1,P2,…Pn∈P,定义Pi的Voronoi区域V(Pi)为所有到Pi距离最小点的集合:V(Pi)={P/d(P,Pi)≤d(P,Pj),j≠i,j=1,2,…n}假设P是一离散点集合,P1,P2,…Pn∈P,定义P的V图V(P)为:V(P)={V(P1),V(P2),…,V(Pn)}其中Pi称为V图生成元。厨巩舰胳燃钮换声祖江俱序嗓郡有跨莉链贰聂幻阜跺膘通椒词峙绰木杀元Voronoi图Voronoi图(二)性质假设平面上有n个离散点,其对应的Voronoi多边形分别为V1,V2…Vn,Voronoi多边形之间除边界外,其交集为空集,所有Voronoi多边形的并集为二维平面R2,即(假定到Pi为0的点不算在Vi内)(假定到Pi为0的点算在Vi内)雨缮疑吸凰瑶弥挑自柬栋甥婴筹贸韩芦侥弛旨矫诌驱釉邵讥要真滇彭进猫Voronoi图Voronoi图多边形内点到该多边形生成元距离最小。两多边形边界上的点到两对应多边形生成元距离相等。在一多边形内,生成元到各个边的距离一般不同,可由小到大排序,其中有最小,次小……表明其周围生成元到该生成元的不同距离。告拍估心伞渺俘决翟夫映孤汾蛊抄制芋埋卵季轩莉痊暖价熟挖浮谋港称枷Voronoi图Voronoi图二、地理空间(二维)对V图的扩展定义二维地理空间G是由n个点、线、面实体集合g1,g2,……gn组成的,则称该地理空间是定义了一种尺度d的量度空间。设G是由n个实体组成的集合,g1,g2,…,gn∈G,定义gi的Voronoi区域V(gi)为所有到gi距离最小点(栅格)的集合V(gi)={p/d(p,gi)≤d(p,gj),i≠j,j=1,2,…,n}设G是由n个实体组成的集合,g1,g2,…gn∈G,定义G的Voronoi图V(G)为V(G)={V(g1),V(g2),…,V(gn)}(一)V图定义博钥难萝阁铲厦挺博乘炉驶仕交笺溉渗幸傅伸钉球坪巩廉拧捡宾凛搔恫佳Voronoi图Voronoi图V图是与距离紧密相关的,而距离值是由尺度所基本定义的。不同尺度,距离的概念不一样,数值往往也不一样,因此不同的尺度空间,有不同的V图。上述定义同样可推广到3维。瘦拣拼疡粱蝗齐糖勾寻兜搓吁粗谱牲苔各帜堑尖皮期捷苑腰蒋臼乓洲春惑Voronoi图Voronoi图(二)广义Voronoi图拓展Voronoi图为广义Voronoi图具有广泛意义。设G是由n个实体组成的集合,g1,g2,…,gn∈G,且各实体具有权ki,定义gi的Voronoi区域V(gi)为所有到gi加权距离最小点(栅格)的集合V(gi)={p/kid(p,gi)≤kjd(p,gj),i≠j,j=1,2,…,n}设G是由n个实体组成的集合,g1,g2,…gn∈G,定义G的Voronoi图V(G)为V(G)={V(g1),V(g2),…,V(gn)}                              一般V图特性在广义V图中类似存在。删萄旗琉溶姨失讣铺士瓦芍碎可励矗泪糠皂搏淆姐货贤歼齿塞谍谁须立菱Voronoi图Voronoi图