嵌入式GIS中多尺度道路网路径规划方法的研究

针对大区域路径规划问题,论述了道路层次划分模型和多尺度道路网数据库的建立,提出了构建多级道路网拓扑结构的方法,利用层次空间推理和改进的启发式A*算法进行最优路径的选取。     

多层建筑空间的分层最优路径算法实现

由于多层建筑空间相对于室外环境存在按楼层分层的三维空间特性,在室内路径分析中需考虑楼层空间位置信息对最优路径规划的影响,而传统基于节点之间的网络连通拓扑模型的最优路径规划方法并没有空间概念,不能很好地应用于室内路径分析。为此,针对室内最优路径规划问题,基于多层建筑空间的层次特性,采用分层结构化的方法,提出结构化动态网络分析模式,实现了室内分层最优路径算法。该算法将各楼层路网和楼层连接均视为独立结构,根据停靠点的楼层分布情况,逐楼层动态构建跨越2个楼层的结构化网络模型并以该网络模型进行跨楼层的路径分析,从而得到多层建筑空间中遍历所有停靠点的最优路径。试验结果表明：相比传统最优路径算法,该算法在路径规划结果更加合理的情况下,时间效率有明显提高;另外,结构化动态网络分析模式可根据需求定义不同的楼层转换规则,更具灵活性。该算法可应用于城市大型公共建筑中,让室内路径分析与室外路径分析进行对接,使路径分析更科学、全面、合理。     

基于路网拓扑层次性表达的驾车路径规划方法

人对所处客观世界的认识具有显著的空间层次特征,可指导出行路径规划过程。常用的层次空间推理的分层路径计算方法,虽顾及了路网的层次性特征,但道路规划等级与人对路网的层次性认知往往并不一致。而道路网络自身的拓扑结构可客观反映道路重要程度,以及出行者对道路的层次性认知经验。本文以拓扑结构指标表达道路的层次性特征,以此规划驾车出行路径,并通过与出租车行驶路径的匹配度及距离最短路径耗时比评价路径规划结果的合理性。研究结果表明,基于路网拓扑层次性表达的规划路径优于距离最短路径、动态时间最短路径、基于道路等级的静态时间最短路径及基于动态中介中心性分层的距离最短路径,与基于出租车经验建模的路径规划结果相当。但本文所提出的方法不需出租车经验建模所依赖的浮动车系统支持,更利于部署应用。     

面向智能导游的双加权图模型及其路径规划

景区游览线路是游客游览不同景点的有效选择路径。在导航系统中通常结合各景点POI(Point of Interest)和景区路网的路径规划而生成,但是,针对具有一定范围与多出入口的景点(如建筑物类景点),单一的POI坐标描述机制规划产生的游览路径,往往与智能导游应用中实际可行的最优游览路径存在明显差异。本文分析了景点大小、多出入口等特征对景区游览路径规划的影响,提出了顶点和边的权重均可动态选择的景区双加权图模型,突破了单一POI描述机制的限制。同时,讨论了景区双加权图模型的化简、构建方法,并以Dijkstra算法和Prim算法为基础,给出了其最优路径规划求解算法。实验表明,本文模型及其最优路径规划算法所得结果更为优化与合理,具有较少的游览规划距离和更为紧凑的游览过程安排。     

基于室内路网的跨楼层路径规划技术的设计与实现

随着室内定位技术、BIM-GIS技术和室内地图研究的发展,室内位置服务需求日益旺盛。作为室内位置服务的关键技术之一,室内路径规划成为研究与应用热点。但是早先的路径规划技术往往基于单层网络拓扑模型而设计,由于模型缺少楼层之间的连通信息,而不能实现跨楼层导航算法分析;而后随着跨楼层导航算法的出现,跨楼层的路径规划、导航及定位得以实现,但这些跨楼层导航算法基于楼层连接通达规则,往往需要多次遍历楼层信息,运算效率低下。针对这一问题,本文利用电梯、扶梯、楼梯等楼层间连接信息,设计、实现了基于楼层连接表的室内多层路网分析模型,并采用逐层分析的方法和多次网络分析,实现室内跨楼层的带有多个途经点路径分析。整个技术框架包括跨楼层路网生成模块、位置点接收模块、网络分析模块、循环控制模块。算法方面,本研究采用双向遍历的A*最短路径分析算法,通过网络路径分析,最终将满足约束条件的规划路径显示在移动设备上,帮助用户实现跨楼层、多途经点的定位与路径导航。     

基于最优路径策略方法快速计算字符串编辑距离

传统编辑距离算法采用动态规划方法用一个维度大小分别为源字符串长度和目标字符串长度的二维数组保存计算过程中求得编辑距离值。这种传统求解方式在时间效率和空间效率上开销较大,限制了编辑距离算法在长字符串中地应用。针对传统方法存在的问题,经深入研究编辑距离的求解过程,发现在某个关键区域内存在一条最优路径,通过确定最优路径所在关键区域可以快速地求解两字符串之间的编辑距离值。实验表明,方法在计算两字符串之间的编辑距离与传统方法相比可以降低问题的求解规模,提高算法的时间效率和空间效率。所描述的方法同样适用于图论中使用动态规划方法求解一般问题地应用,比如最优分配问题和背包问题等。     

基于地形数据的长距离越野路径快速规划方法研究

越野环境下机动车辆的快速路径规划在野外搜救、应急抢险及军事作战等领域均具有重要意义,在以上场景中,随着空间维数的增加,传统路径搜索算法计算复杂性急剧增长,可能无法在既定时间内求解可靠路径。为解决上述不足,本文结合越野路径规划不受路网通行限制以及两点之间直线最短的特点,提出以方向指向作为搜索策略的启发式算法,该算法搜索效率大幅提升,却难以保证求解质量。为进一步提高求解质量,提出了带有方向指向的Dijkstra分段算法,该算法在较低精度环境模型下通过Dijkstra算法找到最优路径,并将该路径进行分段,各分段以方向指向作为搜索策略进行路径搜索,从而在长距离越野路径规划中快速规划通行方案。为验证该算法的有效性,本文利用山西省某市的数字高程模型数据进行实验,引入了窗口移动法对地形进行先期的坡度计算和通行性分析,构建越野环境模型,调用路径搜索算法进行规划。实验结果表明,本文所提算法相比Dijkstra算法计算效率得到了大幅提升,且规划路径的长度接近于最优解。     

基于房产空间数据的楼宇空间疏散路径建模研究

紧急情况下人员快速、安全疏散是室内空间智能化导航和路径规划服务的研究热点.本文采用房产空间管理数据为数据源,以“路径”和“节点”为关键要素,设计了楼宇空间路径模型,用以表达楼宇内部的空间关系及拓扑结构.基于此模型进一步研究了用于紧急疏散的楼宇路径构建算法,论述了构建“单楼层”和“多楼层”路径过程中走廊(过道)路径提取、...     

基于改进RRT*算法的城市低空路径规划方法研究

随着无人机监测、巡查和测绘等低空技术得到广泛应用,低空长距离空中路径规划成为低空航空器应用面临的一个挑战。而传统快速扩展随机树（Rapidly-Exploring Random Trees/RRT）及其改进算法在大范围长距离低空三维空间下面临计算效率慢的问题,对此,本文提出一种带有R树空间索引的双向启发式RRT*算法,该算法在双向RRT*算法基础上为随机采样过程设置了启发函数,使得在面对狭小城市障碍物之间空隙时,能够避免局部最小值情况的出现。在此基础上为城市障碍物建立R树空间索引,减少了海量障碍物情况下碰撞检测的时间,提高了低空长距离空中路径规划效率。此外,为了得到更加符合无人机运动规律的路径,提高算法的实用性,在采样过程中设置转弯阈值控制转弯角度,并且对规划结果路径使用3次B-spline函数进行路径平滑。最后在武汉市三维城市场景中,利用武汉市建筑物数据进行了实验,实验证明相比已有算法,本文提出的带有R树空间索引的双向启发式RRT*算法相比较RRT算法和双向RRT*算法在500 m、 2000 m、 10 000 m不同距离下规划时间均降低了90%以上;采样次数相比RRT算法在不同距离下分别降低了51.6%、75%、86.7%,相比双向RRT*算法在不同距离下分别降低了20%、24.7%、57.3%;转弯次数相比RRT算法在不同距离下分别降低了77.3%、73.5%、78.3%,相比双向RRT*算法在不同距离下分别降低了37.5%、30.8%、16.8%;同时带有R树空间索引的双向启发式RRT*算法得到的结果路径长度相比其他2种算法也有缩短。该算法应用于低空长距离空中路径规划能够有效提高计算效率,降低规划时间,减少采样次数,缩短结果路径,减少转弯次数,丰富无人机的应用场景。     

基于中轴变换算法的室内外一体化导航路网自动生成方法

室内外一体化导航路网的快速生成与更新对面向行人的跨场景导航具有重要意义。当前研究主要关注单一场景下的导航路网构建,对于跨室内外场景的导航路网自动生成研究较少。本文基于对偶图思想与二维平面多边形中轴变换（Medial Axis Transform）算法,提出一种室内外一体化导航路网自动生成方法,并以某建筑CAD平面图及周边路网环境为基础数据进行了实例研究。结果表明：该方法能够根据原始数据的几何、拓扑、语义信息自动构建导航路网,并支持室内外跨场景的最短路径查询,在最短路径查询效率上较传统分场景寻路模型整体提升10.18%;相较单一场景下的导航路网,一体化导航路网可结合语义信息将室内及室外导航路网有机统一起来,解决跨场景寻求最优路径的问题,为最优路径规划的相关研究提供了新的思路。     

基于拓扑与形态特征的城市道路交通状态空间自相关分析

城市道路交通状态具有空间自相关特征。某一道路交通状态的变化会对其周边道路产生影响,故把握道路交通状态的空间自相关性是提高交通规划、交通预测水平的基础。然而,城市道路交通状态又具有空间异质性,即道路交通状态的影响扩散并非各向同性,其使得道路交通状态空间自相关性的度量更为复杂,因此仅从地理空间下道路之间的邻近关系出发进行分析有失偏颇。同时,城市道路具有拓扑结构特征和几何形态特征,二者对于交通状态自相关性的影响和制约,却未引起足够重视。本文从城市道路的拓扑结构特征和几何形态特征出发,提出了一种新的交通状态空间自相关路段识别规则,即基于交通状态变化的路段空间识别规则,通过拓扑社区发现方法刻画路段在空间上的聚集特征,同时,基于Stroke跟踪的几何形态概化来描述道路交通状态变化影响的空间异质性。结果表明,利用本文提出的识别规则产生的交通状态自相关路段集合,较仅考虑地理空间邻近或拓扑结构的识别规则更为合理,更好地揭示了城市道路交通状态的空间自相关特征。     

基于道路结构特征识别的城市交通状态空间自相关分析

 城市道路交通状态具有空间自相关特征。路段交通状态的变化会很快影响到邻近路段,导致一定空间范围内路段的交通状态发生改变。揭示城市交通状态的空间自相关特征,对交通规划、交通控制与诱导具有重要意义。然而,受到城市路网空间结构和道路拓扑特征的影响,城市道路交通状态的空间自相关并非各向同性,也并非均匀地向上下游扩散,而是有选择性地集中在部分邻近路段上。因此,仅考虑路段地理空间下的上下游邻近性,难以全面度量路段间交通状态的相互影响,识别出交通状态空间相关性强的道路集合。本文借鉴复杂网络分析方法,定量化分析了城市路网的模块化与层次性特征,利用城市路段在空间上的聚集特征和路段在网络中拓扑角色的差异,提出了一种新的交通状态自相关路段邻近性判别规则,即空间邻近且拓扑等价规则,以此规则实现交通状态空间相关路段聚类过程,更好地揭示城市路段之间的交通状态空间相关性。     

基于层次随机图的道路选取方法

 道路选取是道路网自动综合的关键问题之一,这方面已有多年研究,虽已取得很大进展,但尚不能自动完成一定比例尺下道路网的选取。本文提出一种基于层次随机图的道路选取方法,通过构建道路网的层次聚类结构以辅助道路选取。层次随机图是一种复杂网络模型,表现为一个二叉树,它不仅可以将复杂的道路网进行层次聚类,而且在可视化的同时提供了不同粒度的聚类信息。在构建道路网的层次随机图的基础上,本文采用累计权重数来衡量每条道路在整体层次结构中的重要性,并据此进行道路选择。我们将该方法应用到不同模式的实际道路网中进行道路选取试验,包括方格形、方格放射状、环形放射状、自由式路网等,以对应的谷歌地图作为参考进行道路选取符合数量、符合长度的定量评价和观察对比定性评价。试验表明本方法的选取结果与谷歌地图符合度很高。此外,与典型的基于路划长度和基于度中心度(degree centrality)的选取方法相比,本文方法更优。最后给出了本文方法优缺点的讨论和进一步研究的展望。     

基于动态中介中心性的城市道路网实时分层方法

 城市道路网中各路段的出行效率直接决定了公众实时出行过程中对道路的选择差异。本文提出一种动态道路网分层方法,通过引入城市道路实时交通状态信息,结合图论中的中介中心性评价方法,得到与时间相关的城市路网动态中介中心性层级结构。该方法考虑了不同时间段城市交通状态的差异,实现了城市路网层次的动态合理划分,在一定程度上缓解了由于数据空间范围限制引起的路网层级静态划分方法的局限性。本文所提出的方法可作为城市路网动态分层的有效方法,为多用户并发环境下的实时出行路径搜索提供更合理的数据基础,同时也可应用于更多的城市路网研究中。     

复杂线-线对象的拓扑关系描述与计算方法

空间拓扑关系是GIS中空间查询和分析的基础。针对当前空间拓扑关系模型在表达较复杂对象间拓扑关系存在局限性的突出问题,以线对象为实例,根据点集拓扑理论,重新定义和区分线对象的复杂性;以9I模型为基础,提出一种适合二维复杂线对象的拓扑关系的线性序列描述模型,将复杂线-线的拓扑关系表示成基本拓扑关系的组合。分析不同情形下线之间拓扑关系不同的计算方法。为实现复杂线-线拓扑关系的计算,提高扫描线算法的效率,探讨包络矩形粗滤、线节点重合或共线的斜率坐标判断法等改进方法,提出判断线-线是否相交的矢量叉乘法,具有快速高效的特点。最后,通过实验系统导入线坐标串,进行图形绘制、拓扑关系计算并输出结果,从而验证该模型和算法的可行性。     

一种基于SuperMap GIS的改进Dijkstra算法

为提高传统Dijkstra算法的搜索效率,满足车载导航中路径规划实时性的要求,本文利用SuperMapGIS平台的网络编辑功能,设计了一种基于SuperMap的改进Dijkstra算法。首先,结合道路网络的空间分布特性,在SuperMap中构建了道路网络;其次,设计算法,根据起止节点合理限制算法的搜索区域,并以经典Dijkstra为理论基础实现最短路径的求解;最后,结合需要设计了约束条件下的路径规划算法。在城市道路网络中的应用实例验证了算法的有效性。     

Road lateral disconnection and crossing impacts in river landscape of Lancang River Valley in Yunnan Province, China

Roads are conspicuous components in a river landscape;however,their impacts on river landscape patterns and ecological processes have not been systematically studied at the watershed scale.In this paper,the Lancang River Valley in Yunnan Province,China was selected as a case to study road lateral disconnection and crossing impacts and identify river-road network interaction.This study was primarily focused on the road impacts on soil erosion intensity and patch density by using GIS analysis at different scales and explored their distribution with terrain factors.The results showed that river density revealed spatial autocorrelation although both of the roads and rivers were distributed unevenly in the valley.The lateral road(road curvature≥1.1)proportion correlated with soil erosion intensity(p 0.01)at the small sub-basin scale.Soil erosion intensity decreased with increasing lateral road buffer width.Light erosion generally accounted for a large proportion of the erosion in the lateral road buffer zones(1.0–4.0 km),while higher class lateral roads imposed greater impacts on soil erosion than lower class roads,which primarily had a moderate erosion level.In addition,the results of road-river intersection density indicated that road crossing impacts were significantly correlated with patch density at the small sub-basin scale.Topography factor(percent of slope25°in each sub-basin had a close relationship with the ratio of total length of road line with curvature value≥1.1 to the total number of intersections.The correlation(p 0.01)between road impacts and terrain factor revealed that topography affected the road impact distribution in the Lancang River Valley.     

顾及出租车OD点分布密度的空间Voronoi剖分算法及OD流可视化分析

为对城市各区域出租车OD轨迹流进行可视化分析,需对城市作空间剖分处理,以产生研究所需的子区域。传统的欧氏距离空间剖分方法,在空间上进行硬性切割不能有效地顾及城市人、物的时空流动模式,因此,本文提出了一种空间约束条件下,顾及出租车OD点分布密度的网络Voronoi剖分方法。首先,将道路网的边细分成线性单元,然后,设定空间约束以产生合适的发生元,让各发生元在路网上以线性单元为单位扩散步长,以不同的速度向周围联通道路进行扩散,最终将城市空间划分成一系列与出租车OD点分布密度相适应的空间子区域。利用OD流可视化理论与技术,基于划分的城市子区域分析出租车在这些区域的时空流动,并结合图论知识探究城市空间OD流拓扑图结构的变化,分析不同划分区域出租车流动模式。最后,通过北京地区一天的出租车轨迹数据,对本文提出的算法及分析方法进行了实验。     

基于拓扑结构分形维的道路选取方法

计算了复杂网络中单个节点的信息维数、体积维数和度体积维数,提出一种基于结构分形维的道路选取方法,考虑了道路网连通方式的多样性与差异性特征。实验结果表明,相比基于路划长度、中介中心性、邻近中心性、度中心性4种单指标道路选取模型,该方法能更好地保持路网整体结构、局部关键特征和拓扑连通性;并且与相应标准比例尺地图保持更高的一致性。