欧氏障碍空间的最短路径问题解法

提出了利用地图代数栅格路径距离变换原理求解欧氏障碍空间最短路径问题的方法(MA-ESPO),实现了二维障碍空间最短路径的一个栅格解法,并且把障碍物、源、汇图形都扩大到任意形态图形。给出了基于地图代数的障碍空间下距离变换方法(MA-DTO),其简便地生成了整个障碍空间所有点的趋源距离,从而成为E2生成所定义障碍空间下各任意形态图形的Voronoi图的实际方法。     

《障碍空间最短路径的地图代数解法》出版

由武汉大学资源与环境科学学院胡鹏教授等著的《障碍空间最短路径的地图代数解法》近日由测绘出版社出版。欧氏障碍空间的最短路径(ESPO)问题是网络分析中的基础和核心之一,其中三维ESPO是NP难问题,至今无其他有效解,它的突破将具有重要意义和价值。本书阐述了新型矢-栅紧密结合型数据模型:"矢量为体,栅格为用;矢栅互换,利用长处",从而铺垫了解算复杂空间问题的"0"初始化计算途径;提出了地图代数的ESPO方法。理论上和实验上解决了著名的二     

基于MapX的道路拓扑和最短路径分析的讨论与实现

本文主要讨论利用M apX组件技术,结合可视化编程环境(V isual Basic)自动建立拓扑关系,并在此基础上采用D ijistra最短路径算法思想实现最短路径分析,为基于M apX的网络分析提供了一种解决办法。     

基于栅格GIS的最优路径分析及其应用

最优路径分析是在移动的起点和终点之间寻找最佳的移动线路,对于旅行中的最短路径确定、工程设计中连接两地之间的线状设施(如输电线路、输油气管线等)的最佳布局规划等具有重要意义.阐述基于栅格的最优路径分析的基本原理,提出基于栅格的最优路径分析的一般过程,并以某地天然气管线最佳铺设线路为例说明基于栅格的最优路径分析的具体应用.     

一种城市通行空间内混合路径分析模型研究

提出一种基于WebGIS的城市通行空间内混合路径分析服务的模型,集成矢量数据、栅格数据和位置兴趣点等不同类型数据,结合网络路径分析和栅格路径计算,能够面向用户提供城市通行空间下完整路径服务。应用JavaScriptWeb技术和百度地图开放平台,在Web环境下实现混合路径分析与服务功能,验证模型的可行性。结果表明,相比于电子地图应用,混合路径分析能完整覆盖城市空间下通行过程,为提升城市路径分析服务质量提供有效地解决方案。     

最短路径算法的改进及其实现方法

最短路径分析是 GIS最基本的网络分析功能。Dijkstra算法是目前公认的较好的最短路径算法。文中从节约存储空间 ,提高运算速度出发 ,在 Dijkstra算法基础上 ,对相关边算法进行改进 ,提出邻接结点算法 ,并给出算法的面向对象的实现方法     

利用组合技术的迪杰斯特拉算法改进探讨

最短路径分析是物流配送最基本的网络分析,等价于图论中的结点间求解最短路径的问题。本文在研究迪杰斯特拉算法基础上,基于组合技术对该算法进行改进。首先利用图的节点——弧段联合结构;其次搜索方法改为双向搜索;最后对扫描点按其所在边的权值进行排列。实验表明改进算法运行效率较高。     

最短路径问题的一种改进算法

最短路径分析是ＧＩＳ最基本的网络分析功能。迪杰斯特拉算法是目前公认的较好的最短路径算法。文中从节约存储空间、提高运算速度出发, 在该算法的基础上, 采用点弧联合结构表达图, 提出节点的最大邻接深度概念及相邻节点低值传递方法, 实现最短路径的自动判断与提取, 并给出算法的实现方法。     

越野通道最短路径分析的优化算法

在越野通道分析中,利用栅格的思想,将矢量地形数据栅格化,将影响通行的因素转化为相应栅格的属性,使用迷宫算法可以有效地进行最短路径分析。但迷宫算法具有一定的局限性,需要对其进行优化。利用以直代曲和样条模型的思想,即直线距离总比曲线距离短,最短路径是由一系列样条曲线组成,通过分析,在迷宫算法所得路径的基础上,提出了一种优化算法。实验结果表明,利用迷宫算法结合优化算法可以较好地解决越野通道分析中的最短路径问题。     

基于栅格数据的最优路径算法分析与设计

最优路径分析是GIS中基本空间分析之一,迄今为止,国内外出现不少关于最短路径/最优路径算法的研究,但其数据模型主要以矢量数据模型或网络模型为主,而建立在栅格数据模型上的最优路径算法的相关研究较少。基于栅格的最优路径算法是一些专业应用模型的基础,如道路通达度模型、城市引力模型、洪水演进过程模型等,其算法设计非常重要。本文在前人的研究基础上,提出一种用于计算栅格最优路径的算法,对其计算过程进行了详细的分析与描述,并根据实验结果总结了其优点和缺点。     

最短路径算法:分类体系与研究进展

最短路径算法是计算机科学与地理信息科学等领域的研究热点。本文首先讨论了平面图的搜索策略，然后从问题类型、网络类型和实现方法3方面对最短路径算法进行了系统的分类，从理论上比较了近年来所提出的各具有较高效率的串行最短路径算法的时间复杂度，并对国内外一些相关研究进行了综合评述，结合城市交通网络的实验结果，作者对几种应用最为广泛的串行最短路径算法的运行效率进行了分析和评价，最后对最短路径算法在实时化和并行化方面的发展进行了讨论。     

An optimum vehicular path algorithm for traffic network based on hierarchical spatial reasoning

Human beings' intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms.It is detailed in this paper how to utilize the hierarchical reasoning on the basis of greedy and directional strategy to establish a spatial heuristic,so as to improve running efficiency and suitability of shortest path algorithm for traffic network.The authors divide urban traffic network into three hierarchies and set forward a new node hierarchy division rule to avoid the unreliable solution of shortest path.It is argued that the shortest path,no matter distance shortest or time shortest,is usually not the favorite of drivers in practice.Some factors difficult to expect or quantify influence the drivers' choice greatly.It makes the drivers prefer choosing a less shortest,but more reliable or flexible path to travel on.The presented optimum path algorithm,in addition to the improvement of the running efficiency of shortest path algorithms up to several times,reduces the emergence of those factors,conforms to the intellection characteristic of human beings,and is more easily accepted by drivers.Moreover,it does not require the completeness of networks in the lowest hierarchy and the applicability and fault tolerance of the algorithm have improved.The experiment result shows the advantages of the presented algorithm.The authors argued that the algorithm has great potential application for navigation systems of large-scale traffic networks.     

An optimum vehicular path algorithm for traffic network based on hierarchical spatial reasoning

Human beings’ intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms. It is detailed in this paper how to utilize the hierarchical reasoning on the basis of greedy and directional strategy to establish a spatial heuristic, so as to improve running efficiency and suitability of shortest path algorithm for traffic network. The authors divide urban traffic network into three hierarchies and set forward a new node hierarchy division rule to avoid the unreliable solution of shortest path. It is argued that the shortest path, no matter distance shortest or time shortest, is usually not the favorite of drivers in practice. Some factors difficult to expect or quantify influence the drivers’ choice greatly. It makes the drivers prefer choosing a less shortest, but more reliable or flexible path to travel on. The presented optimum path algorithm, in addition to the improvement of the running efficiency of shortest path algorithms up to several times, reduces the emergence of those factors, conforms to the intellection characteristic of human beings, and is more easily accepted by drivers. Moreover, it does not require the completeness of networks in the lowest hierachy and the applicability and fault tolerance of the algorithm have improved. The experiment result shows the advantages of the presented algorithm. The authors argued that the algorithm has great potential application for navigation systems of large-scale traffic networks.     

顾及复杂路口交通规则的最短路径算法

基于真实道路的通行状况,分析了一些通常最短路径计算中难以处理的复杂交通路口状况,提出了相应的解决方案。     

Assessing Raster GIS Approximation for Euclidean Shortest Path Routing

Identifying a route that avoids obstacles in continuous space is important for infrastructure alignment, robotic travel, and virtual object path planning, among others, because movement through space is not restricted to a predefined road or other network. Vector and raster GIS (geographic information system) solution approaches have been developed to find good/efficient routes. On the vector side, recent solution approaches exploit spatial knowledge and utilize GIS functionality, offering significant computational advantages in finding an optimal solution to this path routing problem. Raster‐based shortest path techniques are widely applied in route planning for wayfinding, corridor alignment, robotics and video gaming to derive an obstacle avoiding path, but represent an approximation approach for solving this problem. This research compares vector and raster approaches for identifying obstacle‐avoiding shortest paths/routes. Empirical assessment is carried out for a number of planning applications, highlighting representational issues, computational requirements and resulting path efficiency.     

Finding least-cost paths across a continuous raster surface with discrete vector networks

The problem of finding the least-cost path from a source point to a destination point can be dealt with by routing across a continuous surface or routing along a discrete network. The solutions within these two contexts are linked to the use of a raster- or a vector-based least-cost path algorithm. This study presents a technique which integrates raster- and vector-based least-cost path algorithms for determining the least-cost path across a continuous raster surface with discrete vector networks. The technique incorporates ancillary vector data sets that are required to examine the travel cost at each link, connections between nodes, and the representation of intersecting links in the discrete vector network into raster-based least-cost path analysis. The integrated technique presented here is applicable to all-terrain vehicle navigation where a continuous raster surface and discrete vector networks need to be considered simultaneously in order to find least-cost paths. This paper describes the concept behind, and details of, the integrated technique. Applications of the technique with synthetic and real-world data sets are also presented. They provide proof that the technique is effective in finding least-cost paths across a continuous raster surface with discrete vector networks.     

交通运输最短路径分析系统的设计与实现

针对目前交通运输效力发挥不足的问题,研究道路网络模型构建和道路数据库设计,探讨分析交通运输最短路径分析流程,基于Dijkstra算法的基本原理,设计实现交通运输最短路径分析系统,从而优化运输资源配置,实现高质高效的交通运输。     

一种利用双侧凸包扩张模型的路径快速规划算法

针对障碍环境中路径规划存在的运算效率低、最短路径遗失问题,根据凸包边界在构建空间网络模型过程中具有快速高效的特点,结合路径与障碍物的相对位置关系,提出了一种基于双侧凸包扩张模型的路径快速规划算法.该算法在对凸包边界算法进行改进的基础上,提取左右侧关联障碍物的凸包边界作为网络模型,利用最短路径算法搜寻目标路径,并在Arc...     

在ArcGIS矢量图中搜寻最短路径的实现

最短路径问题是地理网络分析中的重要问题之一,具有重要的应用价值。搜索最短路径的方法很多,在研究了各种方法后,本文提出了在ArcGIS矢量图中搜索最短路径的新方法。首先,提取经过ArcGIS简单处理的矢量图的信息,然后,借助Floyd算法,用MATLAB建模来提取节点间的最短路径,最后根据模型运算的结果在矢量图中绘出最短路径。试验证明,该方法操作简单,效果良好。