空间邻近关系极其推理.ppt

,空间邻近关系及其推理 *,大纲,空间邻近关系的定义和分类 Delaunay三角网的性质及生成 Voronoi图的性质及生成 地理空间邻近关系的推理 基于Delaunay三角网的地理空间邻近关系推理 基于Voromoi图的空间邻近关系推理,空间邻近关系的定义,空间位置上：较近（定性距离） 拓扑关系上：相离（其间不存在任何空间对象） 本质上：空间距离关系,空间邻近关系的分类,直接邻近 空间目标Voronoi多边形存在，且有邻接边 侧向邻近 一空间目标为线状目标，其Voronoi多边形存在邻接边 最邻近 两空间目标距离在所有目标距离中最小 位置邻近 被考察空间中的点在空间多边形Voronoi多边形,Delaunay三角网的性质,同圆性：即每一个Delaunay三角形的外接圆不包括Delaunay三角网中的任何其他点。 最大最小角：在三角剖分中，所有Delaunay三角形的最小角之和最大。（最大程度接近等边三角形） 唯一性：对于一群点，Delaunay三角网是唯一的（若不存在四点共圆的情况）。,Delaunay三角网的生成（三角网生长法为例）讲解清楚,建立第一个三角形 选择最短边作为第一条边，得到第一边（Pt1Pt2），加入到边表 选择第三点Pt3， Pt3为顶点的角（角Pt1 Pt3 Pt2 ）最大的点作为第三点，新边加入边表 得到第一个三角形，将该三角形加入到三角表,Delaunay三角网的生成（三角网生长法为例）讲解清楚,扩展Tin 三角形边表出一个三角形（如ABC） 取该三角形可扩展边进行逐一扩展（如AB） 找与扩展边组成三角形的第三点(P) 第三点与扩展点C在扩展边异侧 使得角APB最大的点P作为第三点 生成新边（如FA，FB） 若新边在边表存在，则标记为不可扩展 若新边在边表不存在，则标记可扩展，且加入边表 生成新三角形(如AFB)，加入三角形表，并将扩展边（如AB）标记为不可扩展，再扩展另一条可扩展边（如AC）,A,B,C,D,E,F,Delaunay三角网的生成,1,2,5,7,3,8,9,4,6,10,11,11,12,13,Voronoi图的性质,Voronoi多边形之间除边界外，其交集为空集，所有Voronoi多边形的并集为二维平面R2 Voronoi图与Delaunay三角网对偶 Voronoi多边形边上的公共边上任一 点到两多边形生成元距离相等 在一多边形内，生成元到各个边的距离不同 多边形内点到该多边形生成元距离最小,Voronoi图的生成,对偶生成法 对偶生成法是指先生成Delaunay三角网，再根据Voronoi图与Delaunay三角网的对偶性质，做出其三角形三条边的中垂线,形成以每一三角形顶点为生成元的Voronoi多边形网 。,基于Delaunay三角网邻近关系推理,Delaunay三角网是根据空间目标的特征点进行的空间剖分。Delaunay每一个点都是联通的，Delaunay三角形的每一条边都隐含着两顶点间邻近关系。 以点状目标邻近关系推理为例（画图） 线状目标和面状目标间具有拓展性，导致邻近关系推理具有不确定性,基于Voronoi图邻近关系推理,Voronoi图用公共边表示生成元间邻近关系，Delaunay用两点间连边表示离散点之间的邻近关系 基于Voronoi图的空间邻近关系推理，是利用Voronoi多边形间的拓扑关系进行推理 Delaunay三角网反映的是生成该三角网的离散点之间的邻近关系 Voronoi图强调的是生成元的影响区域，更多的是用来进行邻近空间目标查询,基于Voronoi空间距离的聚类 银行业务点选址,我们可以发现空间目标对象Voronoi区域之间的Voronoi区域数目从一定程度上反映出其间的其他目标个数，这个数目体现出两空间对象的空间临近关系。 Voronoi距离：设任意两个空间目标Pi，Pj之间的的Voronoi区域最少个数k作为PiPj之间的Voronoi距离。,在本实验中，只考虑区域人口以及收入水平，我们选择楼栋作为生成点，以单楼栋的人口数和收入水平为权，生成加权Voronoi图，然后基于Voronoi距离对楼栋进行kmeans聚类。将得到的聚类中心作为银行业务点。,地理空间邻近关系的推理（应用）,区域