共查询到20条相似文献，搜索用时 93 毫秒
1.
路径规划问题是路网交通应用中的一个基础问题。A*算法是一个求解点到点最短路径问题的高效算法。但随着路网数据规模的增长,A*难以保证求解的实时性。利用并行计算进行加速是常用的算法性能提高手段,然而A*算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化。本文提出一种分段化搜索的改进A*算法（SA*）。该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解。分段搜索本身可以减少路径规划的搜索空间,借助多线程并行则可以进一步提高求解速度。实验结果表明,在真实路网数据上,利用16核的机器,SA*的性能可以达到A*算法的10-30倍。 相似文献
2.
基于弧段标记的交通网络时间最短路径算法 总被引：2，自引：0，他引：2
标号算法是经典的最短路径算法之一,在交通领域中具有广泛的应用。在交通领域中,时间最短路径比距离最短路径更有意义,而时间最短路径不仅与道路的时间权值有关,还与道路之间的转弯阻抗有关。在传统的交通路网抽象方式下,道路抽象为平面图中的弧段,道路间的交叉口抽象为节点。本文介绍了一种适用于传统交通路网模型的弧段标记时间最短路径算法,详细阐述了该算法的原理、数据基础与运行结构。通过分析和实例测试表明,该算法可以顾及城市路网在路口的交通限行与转弯延迟的影响,并且时间复杂度低,具有一定的实际应用价值。 相似文献
3.
城市环境下的车载LiDAR点云在道路边界提取时容易受到路边车辆、行人遮挡等影响，而造成伪边界点的生成和边界线的不连续。本文发现利用高程标准差约束能够有效的处理该类问题。本文首先进行数据预处理，包括点云分段及地面点滤波、基于相邻点间距离将地面点整合成扫描线存储；其次基于扫描线建立连续双窗口，采用扫描线双向移动窗口法，构造双窗口之间高差、夹角值、高程标准差3种约束条件获取候选路坎点，并根据道路边界的连续性采用密度聚类中的DBSCAN算法聚类去噪，生成较为连续且精确的路坎边界点；最后对边界断点区域计算累计曲率值和距离来判断该位置是否为路口，若边界线断点为路口不进行连接，反之，视为车辆或行人遮挡导致的断点，采用二次多项式曲线填补拟合，获得边界的数学参数模型。实验结果表明，在存在较多遮挡的城市环境下道路边界提取精度能够达到80%以上。 相似文献
4.
5.
地形建模是数字地形分析的重要基础工作。实时优化适应性网格算法（ROAM算法）是目前常用的地形建模方法。但ROAM算法应用于地形可视化实时渲染时要求原始数据为正方形,且渲染后常有裂缝产生,因而该法在地形建模实践中受到较大的限制。针对ROAM算法存在的上述不足,本文提出了基于内接正方形插值方法的改进ROAM算法。通过将多边形分割为一个内接正方形和多个边缘多边形,用多边形的一个顶点依次与其他顶点相连,使边缘多边形分割为多个三角形,并根据边缘三角形面积大小,确定是否对边缘多边形进行继续分割,由此解决数据源限定为正方形的问题,利用添加拆分点的方法消除地形渲染产生的裂缝。采用不规则地形的灰度图作为高程数据源进行地形模拟实验,结果表明：改进后的ROAM算法能够消除裂缝,且对数据源无约束性要求,降低了算法复杂度,提高了整体可视化性能,能够满足地形实时动态显示的要求。 相似文献
6.
Vatti算法是常用的矢量多边形裁剪算法之一,在其构建扫描束实现交点计算的过程中,二叉树的数据结构和递归计算方法导致其计算效率受矢量多边形边界顶点数量影响显著。本文针对Vatti算法执行过程中较为耗时的扫描束构建环节,提出了一种多边形边界顶点预排序的优化方法——VCS（Vertex Coordinate Pre-Sorting）方法,并基于该方法实现了对Vatti算法的GPU细粒度并行化。VCS方法使用双向链表对Vatti算法原有的二叉树数据结构进行了替换,以较小的额外存储空间取得了多边形边界顶点信息查找效率的明显提升。在GPU环境下采用双调排序算法对多边形边界顶点数组元素进行并行化排序并过滤出有效值,克服了原始算法使用二叉树存储导致效率低下的问题。实验结果表明,改进后的算法与原始算法相比,具有相同的计算精度;当多边形顶点数量为92万,CUDA每个线程块中的线程数量为32时,使用VCS优化方法,与采用CPU计算构建扫描束方法相比,GPU并行化方法获得了39.6倍的相对加速比,矢量多边形叠加分析算法效率总体上提升了4.9倍。 相似文献
7.
挖掘科学数据是当今数据库系统研究和应用领域内的一个热点问题。聚类是数据挖掘中的核心问题。K-中心算法的执行结果受到初始选择的中心点的影响，而且常常只能终止于局部最优，按照基于密度聚类算法的思想，聚类分析最终的中心点都是很“密的（dense）”点，结合这两种算法，如果初始选择的中心点就是“密的（dense）”点，并且这几个初始的中心点彼此相异度比较大，那就会减少算法执行的时间，并且提高聚类结果的准确度。 相似文献
8.
景区游览线路是游客游览不同景点的有效选择路径。在导航系统中通常结合各景点POI(Point of Interest)和景区路网的路径规划而生成,但是,针对具有一定范围与多出入口的景点(如建筑物类景点),单一的POI坐标描述机制规划产生的游览路径,往往与智能导游应用中实际可行的最优游览路径存在明显差异。本文分析了景点大小、多出入口等特征对景区游览路径规划的影响,提出了顶点和边的权重均可动态选择的景区双加权图模型,突破了单一POI描述机制的限制。同时,讨论了景区双加权图模型的化简、构建方法,并以Dijkstra算法和Prim算法为基础,给出了其最优路径规划求解算法。实验表明,本文模型及其最优路径规划算法所得结果更为优化与合理,具有较少的游览规划距离和更为紧凑的游览过程安排。 相似文献
9.
一种基于路网等级启发式策略的路径搜索算法 总被引：1，自引：1，他引：0
本文提出了一种基于路网等级启发式策略的路径搜索算法。通过引入考虑路网等级因素的代价评估函数,有目的地引导搜索过程考虑路网道路等级特征,限制路径搜索规模,在精度可控的前提下,大幅度提高时间最短路径算法的效率,并使得搜索路径结果更符合心理认知过程。其与经典的层次空间推理算法相比,本文提出的算法实现过程简单,效率和精度相似。理论分析和实验过程验证了本文所提出算法的有效性。 相似文献
10.
11.
合理规划中小学布局是优化教育资源配置、提高办学效益以及实现教育均衡发展的重要途径。本研究针对中国乡村建设的需要和中国多山的地理环境,考虑山地环境对乡村中小学选址的影响,构建多山环境下乡村中小学的区位模型,运用地理信息科学方法,以Visual Studio. Net 2010为开发平台,使用C#语言和ArcGIS Engine 10.0组件库,同时结合MATLAB编程,开发出基于交通网络的乡村中小学区位优化系统。最后将系统应用于贵州省某镇的小学布局优化中,分别在只考虑已有道路、假设道路可升级、假设道路可新建或升级3种情景下,通过改进的模拟退火算法,确定新建学校的最佳位置,以及新道路的修建和原有道路的升级情况,从而得到不同情景下各居民点学生的上学耗时。结果表明,交通网络对乡村中小学布局优化具有重要影响,改善交通网络条件能够有效提高学生的就学效率上学速度。 相似文献
12.
根据网格思想将道路网络进行分块并融合GPS所提供的定位数据,利用车辆行驶的位置、方向和实际道路网络的拓扑特性,提出一种快速实用的地图匹配算法。使GPS数据实时地与GIS地图数据匹配,有效地提高车辆导航的定位精度。 相似文献
13.
路网拓扑关系的生成是进行最优路径规划的基础。本文针对ISO GDF4.0模型对道路连通拓扑的定义,结合最优路径规划对道路网络连通拓扑的要求,提出一种使用R-tree空间索引和B-tree索引双重索引方式快速生成道路连通拓扑的算法。连通拓扑快速构建算法包括新道路生成和网络拓扑提取两部分,新道路生成过程中,首先,自上而下地打断道路形成直线段集并求交点,然后,自下而上地重构直线段集以生成新道路。在打断道路求交点过程中,对道路建立R-tree空间索引,显著提高了几何要素的查找速度。在网络拓扑提取过程中对序列化数据建立B-tree索引,使得其查找速度大大加快。通过对双重索引算法的时间复杂度分析与验证表明,本文提出的拓扑生成算法具有较高的执行效率。 相似文献
14.
人对所处客观世界的认识具有显著的空间层次特征,可指导出行路径规划过程。常用的层次空间推理的分层路径计算方法,虽顾及了路网的层次性特征,但道路规划等级与人对路网的层次性认知往往并不一致。而道路网络自身的拓扑结构可客观反映道路重要程度,以及出行者对道路的层次性认知经验。本文以拓扑结构指标表达道路的层次性特征,以此规划驾车出行路径,并通过与出租车行驶路径的匹配度及距离最短路径耗时比评价路径规划结果的合理性。研究结果表明,基于路网拓扑层次性表达的规划路径优于距离最短路径、动态时间最短路径、基于道路等级的静态时间最短路径及基于动态中介中心性分层的距离最短路径,与基于出租车经验建模的路径规划结果相当。但本文所提出的方法不需出租车经验建模所依赖的浮动车系统支持,更利于部署应用。 相似文献
15.
16.
一种基于SuperMap GIS的改进Dijkstra算法 总被引：1，自引：0，他引：1
为提高传统Dijkstra算法的搜索效率,满足车载导航中路径规划实时性的要求,本文利用SuperMapGIS平台的网络编辑功能,设计了一种基于SuperMap的改进Dijkstra算法。首先,结合道路网络的空间分布特性,在SuperMap中构建了道路网络;其次,设计算法,根据起止节点合理限制算法的搜索区域,并以经典Dijkstra为理论基础实现最短路径的求解;最后,结合需要设计了约束条件下的路径规划算法。在城市道路网络中的应用实例验证了算法的有效性。 相似文献
17.
18.
本文以区位-配给模型理论为指导,以路网疏散距离最短、场地服务容纳量最大为目标,构建最优避难疏散模型,以解决中小学避难场地选址问题。本文从保障学生避难疏散场地的安全性和适宜性角度出发,通过建立环境制约因素模型,对地形坡度、断裂带、河流湖泊、易燃易爆站点、高层建筑物倒塌范围和文物古迹保护范围6大因素进行空间叠加分析,计算了实际的避难需求和供给容量。为减少利用直线距离直接作为疏散道路产生的误差,本文通过对不受影响的路网信息进行网络分析,计算最短疏散道路,以获取实际的路网距离。本文将该方法应用于北京市西城区中小学避难场地选址的优化方案,有效地解决了中小学避难场地选址问题。 相似文献
19.
道路等级不仅反映在路网结构的静态骨架信息上,也蕴含在轨迹数据呈现的动态语义信息上。为解决(OpenStreetMap)OSM路网部分路段及路网生成产品等级缺失问题,本文提出一种顾及路网与轨迹多模特征的道路等级分类方法。首先通过轨迹数据的清洗、地图匹配和基于路名的路网合并实现轨迹点与命名道路的联结;然后以命名道路为分析单元,综合考虑路网及轨迹数据,在系统分析路网结构的道路几何特征、道路分布特征、道路拓扑特征及道路单双向信息基础上,进一步挖掘与融合轨迹数据蕴含的道路宽度、道路车流量、道路速度等静动态特征,形成关于道路等级的描述特征集,作为识别道路等级的基础与依据;最后以随机森林(RF)为基本分类器进行特征选择及模型训练实现道路等级识别。为验证本文方法,选取武汉市汉正街区域及二环区域,基于OSM路网数据及众源轨迹数据开展试验。该方法取得了较好的分类结果,小范围汉正街区域的验证集准确率为91.2%,大范围二环区域的验证集准确率达到80.8%。与单类特征相比,集成路网与轨迹特征极大提高了道路等级分类准确率;与原始路段形式进行道路等级分类相比,以路名重构道路形式进行道路等级分类效果更好。 相似文献
20.
利用车辆轨迹数据提取道路网络的几何特征与精度分析 总被引：2，自引：0，他引：2
电子地图数据是各种智能交通系统的基础数据,对方便人们交通出行、解决城市交通拥堵问题具有重要的意义。其中,道路网络数据又是电子地图的重要组成部分。传统的道路网络数据更新方法往往需要耗费大量人力物力,因此,从其他数据源中如遥感影像数据、LIDAR数据等提取道路网络的相关研究,已成为国内外的研究重点。车载定位设备的广泛应用使车辆轨迹数据的大量获取成为可能,轨迹数据是对车辆行驶路径的完整记录,同时也是道路网络几何特征的直接反映。当轨迹数据量足够大时,则可利用其构建路网,用于更新或修正现有地图上的路网空间信息。针对车辆轨迹数据的特点和道路网络的特性,本文提出一种细化的道路网络几何特征提取方法。车辆轨迹数据是矢量数据,将其转换为栅格数据后,就可采用图像细化的方法处理。图像细化可以在保持原图像拓扑结构不变的情况下,快速地提取出图像的中心像元,并且有效去除冗余信息。本文以上海陆家嘴的车辆轨迹数据为例进行了实验,结果表明,利用车辆轨迹数据构建路网不仅可行,而且简单、高效,取得了良好的效果。 相似文献