共查询到20条相似文献，搜索用时 500 毫秒
1.
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. 相似文献
2.
The problem of finding the K shortest paths (KSPs) between a pair of nodes in a road network is an important network optimization problem with broad applications. Yen's algorithm is a classical algorithm for exactly solving the KSP problem. However, it requires numerous shortest path searches, which can be computationally intensive for real large networks. This study proposes a fast algorithm by introducing a generalized spur path reuse technique. Using this technique, shortest paths calculated during the KSP finding process are stored. Accordingly, many shortest path searches can be avoided by reusing these stored paths. The results of computational experiments on several large‐scale road networks show that the introduced generalized spur path reuse technique can avoid more than 98% of shortest path searches in the KSP finding process. The proposed algorithm speeds up Yen's algorithm by up to 98.7 times in experimental networks. 相似文献
3.
为充分利用已有化简成果及其蕴含的化简知识,本文集成几种机器学习算法提出图形、图像融合利用的智能化简方法,实现顶点取舍决策的学习和优化。首先,分别利用全连接神经网络和卷积神经网络设计、构建基于图形的顶点取舍模型和基于图像的顶点取舍模型,通过样本训练各模型拟合从图形特征到顶点取舍和从栅格图像到顶点取舍的映射;然后,基于线性加权、朴素贝叶斯、支持向量机、人工神经网络构建多种融合决策模型,实现基于图形和基于图像的顶点取舍的融合利用;最后,通过试验用例对所有模型进行测试。试验结果表明：基于图形和基于图像的顶点取舍模型在一定程度上学习、掌握了化简算子,融合利用后还能进一步提高化简准确性、实现优势互补。 相似文献
4.
成本表面模型是在连续空间中进行路径优化的基础。目前,在连续空间中进行路径优化多是基于单分辨率成本表面模型的。但在使用该模型解决诸如输电、调水、公路和铁路、输油输气等路径优化问题时,存在一些缺点,例如数据冗余、计算成本高、易受地物“边缘效应”影响等。针对这些问题,本文提出了一种面向路径优化的GIS变分辨率栅格成本表面模型,并详细阐述了这种数据模型的设计思想和建模方法。实验结果证明,该模型能有效的对地物密集度和地形复杂度进行建模,解决单分辨率模型遇到的问题。将该模型与传统的单分辨率成本表面模型的计算结果进行对比分析,表明本文建立的模型在多种环境下均能选出合理的路径,且计算效率得到明显提高。 相似文献
5.
将栅格地形根据不同的邻域结构形成稀疏栅格网络和稠密栅格网络,分析了稀疏网络中最优路径问题的建模和基于Dijkstra算法的求解方法,以及稠密网络中最优路径问题的建模和基于模拟退火算法的求解方法。比较了这两种方法求解结果的准确性和效率的差异,发现基于稀疏网络的Dijkstra算法更适合于栅格地形的最优路径问题的求解。 相似文献
6.
Harri Antikainen 《Transactions in GIS》2013,17(1):96-108
The conventional raster‐based least‐cost path technique, in which the connectivity graph is constructed by treating each raster cell as a node and linking each node to its adjacent neighbors, has been widely used to determine optimum paths in space. Unfortunately, paths calculated with this method are subject to distortions that stem from the imposed node‐link structure. Due to the distortions, the calculated paths may be longer than the true optimum paths in continuous space, and because of this, they may also look highly unrealistic when displayed on a map. This study examines how the quality of the raster‐based paths can be improved by using larger connectivity patterns on the one hand, and placing nodes on the sides of the cells of a raster instead of at their centers, on the other. In addition, the utility of the quadtree structure is examined. The different methods are evaluated against three different datasets using the cost distance of the calculated paths and processing times as evaluation criteria. The results indicate that raster‐based paths can be improved by using the evaluated techniques, although the degree of improvement is also dependent on the properties of the underlying cost raster. 相似文献
7.
Cédric H David David J Gochis David R Maidment Wei Yu David N Yates Zong-Liang Yang 《Transactions in GIS》2009,13(4):363-377
The National Elevation, Hydrography and Land Cover datasets of the United States have been synthesized into a geospatial dataset called NHDPlus which is referenced to a spheroidal Earth, provides geospatial data layers for topography on 30 m rasters, and has vector coverages for catchments and river reaches. In this article, we examine the integration of NHDPlus with the Noah-distributed model. In order to retain compatibility with atmospheric models, Noah-distributed utilizes surface domain fields referenced to a spherical rather than spheroidal Earth in its computation of vertical land surface/atmosphere water and energy budgets (at coarse resolution) as well as horizontal cell-to-cell water routing across the land surface and through the shallow subsurface (at fine resolution). Two data-centric issues affecting the linkage between Noah-distributed and NHDPlus are examined: (1) the shape of the Earth; and (2) the linking of gridded landscape with a vector representation of the stream and river network. At mid-latitudes the errors due to projections between spherical and spheroidal representations of the Earth are significant. A catchment-based "pour point" technique is developed to link the raster and vector data to provide lateral inflow from the landscape to a one-dimensional river model. We conclude that, when Noah-distributed is run uncoupled to an atmospheric model, it is advantageous to implement Noah-distributed at the native spatial scale of the digital elevation data and the spheroidal Earth of the NHDPlus dataset rather than transforming the NHDPlus dataset to fit the coarser resolution and spherical Earth shape of the Noah-distributed model. 相似文献
8.
Network transport is an important aspect of geographical information science, transportation, complex networks, etc. Previous studies have shown that the transport capacity of street networks can be enhanced by improving routing algorithms. However, the upper throughput limit of street networks is unknown in detail. This article studies the transport process of networks and finds that any connected network has a maximum throughput depending on the topological and structural properties of the network. Based on this, the maximum throughput of street networks is obtained. Experiments show that when the street network remains unchanged, the maximum throughput of the street network is limited and is dependent on road capacity and average path length, regardless of adopted routing algorithms. Our findings suggest that the throughput of networks can be improved by increasing node capacity or decreasing average path length, but the maximum transport capacity of the network cannot be greater than the ratio of the sum of all the nodes' capacities to the average path length of the network, no matter what routing strategies are adopted. This study is expected to be a starting point for more sophisticated research in network transport, such as evaluating the inherent throughput of an urban street network. 相似文献
9.
Concerns over the potential negative health effects from exposure to air pollution have led to interest in assessing personal exposure and finding ways to reduce it. As journey-time exposure accounts for a disproportionately high amount of an individual's total exposure, this article assesses the potential to apply least-cost techniques within a GIS in order to identify paths of lower journey-time exposure. The methodology adopted uses pollution surfaces for PM10 and CO generated by the dispersion model ADMS, with an analysis mask derived from OS MasterMap to create a least-cost surface. Actual routes taken by a cohort of 11–13 year old children on their journeys to school are used to compare observed journey time exposure with the exposure along alternative routes generated using the least-cost path function. While the least-cost approach proved to be successful in defining low exposure routes the ability to scale up this approach is constrained by the amount of editing required to successfully create an analysis mask from OS MasterMap data. Such alternative routes have the potential to assist in promoting safer environmental choices, however, their likelihood of adoption is dependant on a number of social and environmental influences which affect an individual's route choice. 相似文献
10.
面向目标的栅格矢量一体化三维数据模型 总被引：1，自引：0，他引：1
首先对现有的三维空间数据模型进行了讨论 ,分析了栅格、矢量和混合数据模型的特点 ,提出了一种面向目标的栅格矢量一体化数据模型。该模型将栅格数据以矢量方式进行组织 ,从而同时具有矢量和栅格数据模型的优点 ,也克服了目前普遍应用的混合模型所存在的缺点。还提出了一种三维空间的三级栅格划分和行次序编码方法。该方法存储空间小 ,便于快速索引和计算。最后 ,给出了具体的数据结构 相似文献
11.
沈正军 《测绘与空间地理信息》2007,30(2):36-39
最优路径分析是GIS中基本空间分析之一,迄今为止,国内外出现不少关于最短路径/最优路径算法的研究,但其数据模型主要以矢量数据模型或网络模型为主,而建立在栅格数据模型上的最优路径算法的相关研究较少。基于栅格的最优路径算法是一些专业应用模型的基础,如道路通达度模型、城市引力模型、洪水演进过程模型等,其算法设计非常重要。本文在前人的研究基础上,提出一种用于计算栅格最优路径的算法,对其计算过程进行了详细的分析与描述,并根据实验结果总结了其优点和缺点。 相似文献
12.
An enhanced approach for surface flow routing over drainage‐constrained triangulated irregular networks 
下载免费PDF全文
下载免费PDF全文 The accuracy and efficiency of the simulations in distributed hydrological models must depend on the proper estimation of flow directions and paths. Numerous studies have been carried out to delineate the drainage patterns based on gridded digital elevation models (DEMs). The triangulated irregular network (TIN) has been increasingly applied in hydrological applications due to the advantages of high storage efficiency and multi‐scale adaptive performance. Much of the previous literature focuses mainly on filling the depressions on gridded DEMs rather than treating the special cases in TIN structures, which has hampered its applications to hydrological models. This study proposes a triangulation‐based solution for the removal of flat areas and pits to enhance the simulation of flow routing on triangulated facet networks. Based on the drainage‐constrained TIN generated from only a gridded DEM by the compound point extraction (CPE) method, the inconsistent situations including flat triangles, V‐shape flat edges and sink nodes are respectively identified and rectified. The optimization algorithm is an iterative process of TIN reconstruction, in which the flat areas are generalized into their center points and the pits are rectified by embedding break lines. To verify the proposed algorithm and investigate the potential for flow routing, flow paths of steepest descent are derived by the vector‐based tracking algorithm based on the optimized TIN. A case study of TIN optimization and flow path tracking was performed on a real‐world DEM. The outcomes indicate that the proposed approach can effectively solve the problem of inconsistencies without a significant loss in accuracy of the terrain model. 相似文献
13.
目前三维Douglas-Peucker(3D_DP)算法主要应用于单一类型的DEM综合。本文引入"弯曲调节指数"来改进3D_DP算法,提出了一种三维空间河网要素与DEM综合的新方法,即将河网线矢量提取成三维离散点数据集(增加高程属性),与DEM三维离散点数据集合并,在河网层次化选取基础上,利用改进的3D_DP算法对合并数据集进行综合操作。通过试验结果的对比和分析表明,该方法通过弯曲调节指数的调节使河流自身所具有的弯曲形态与地形的主要特征得以同时保留,试验效果良好,实现了三维空间河网要素与DEM数据在同一简化因子作用下的综合,提升了地图综合的质量。 相似文献
14.
Based on the concept of map algebra, this research developed a network neighborhood analysis framework for directed flow networks. The analysis framework has two components: the first component defines how neighborhoods are delineated on networks and the second component calculates various statistics within the neighborhoods. The power and value of the analysis framework lie in its capability to delineate versatile network neighborhoods and its flexibility in calculating various statistics within the neighborhoods. It extends the raster map algebra to networks and provides a consistent analysis framework for the raster, vector, and network data models. Using a small section of the National Hydrography Dataset (NHD) networks, a prototype Web application is implemented to experiment and demonstrate the concept and uses of the analysis framework. 相似文献
15.
Virtual globes enable the combination of heterogeneous datasets for optimal routing analyses in transportation, environmental ecology, and construction engineering. In this study, considering the advantages of the hierarchical tiling structure and topography of virtual globes, we propose a tile‐based optimal routing method for large‐scale road networks in a virtual globe. This method designs a topographically preserved road‐network tile model by partitioning roads into tiles and constructs the road‐network pyramid from the bottom to the top. During construction, a TileArc is calculated and flagged as the shortest path in a tile. Based on the built road‐network pyramid carrying hierarchical TileArcs, a multi‐level and flexible shortest path query can be executed efficiently. The proposed method is implemented with large road networks with different road grades in a virtual globe. Experimental results verify its validity, efficiency, and exactness. Moreover, the length of the shortest path with surface distance is approximately 1.3 times longer than that with Euclidean distance. 相似文献
16.
《制图学和地理信息科学》2013,40(5):300-302
The Spatial Data Transfer Standard (SDTS) was designed to transfer both vector and raster data sets. In the early development of the SDTS, the designers recognized that there was a need to transfer raster data in addition to the more challenging vector data. As a result, the SDTS includes a “raster module” that accommodates a variety of raster data structures and formats. A raster profile is being developed that will exercise a selected subset of SDTS capabilities in order to provide a simple-to-use transfer of complete raster data sets. 相似文献
17.
Big geospatial data is an emerging sub‐area of geographic information science, big data, and cyberinfrastructure. Big geospatial data poses two unique challenges. First, raster and vector data structures and analyses have developed on largely separate paths for the last 20 years. This is creating an impediment to geospatial researchers seeking to utilize big data platforms that do not promote heterogeneous data types. Second, big spatial data repositories have yet to be integrated with big data computation platforms in ways that allow researchers to spatio‐temporally analyze big geospatial datasets. IPUMS‐Terra, a National Science Foundation cyberInfrastructure project, addresses these challenges by providing a unified framework of integrated geospatial services which access, analyze, and transform big heterogeneous spatio‐temporal data. As IPUMS‐Terra's data volume grows, we seek to integrate geospatial platforms that will scale geospatial analyses and address current bottlenecks within our system. However, our work shows that there are still unresolved challenges for big geospatial analysis. The most pertinent is that there is a lack of a unified framework for conducting scalable integrated vector and raster data analysis. We conducted a comparative analysis between PostgreSQL with PostGIS and SciDB and concluded that SciDB is the superior platform for scalable raster zonal analyses. 相似文献
18.
行人路网的完整性和准确性是保障步行导航服务的关键。当前的行人路网大多是基于室外道路设施构建的,缺乏室内可步行路径的数据支持,无法在导航应用中提供准确、真实的最优路径规划服务。鉴于此,本文提出了一种基于众源数据的室内外一体化行人路网构建方法,采用智能手机定位传感器与惯性传感器记录的众源轨迹,首先对缺失或者漂移的室内步行数据进行筛选,然后使用改进的行人航位推算(PDR)方法推算出准确的室内轨迹,进而采用莫尔斯理论生成涵盖室内外行人路径的完整行人路网。试验分析中对搜集到的260条步行轨迹数据进行行人路网构建,并使用高精度测量设备采集真实路网数据进行对比分析,结合OSM数据对试验结果进行综合评价。试验结果表明,本文方法能够准确、完整地生成室内外一体化行人路网。 相似文献
19.
In this paper, we propose a method of cost distribution analysis of new consumer connections to a city power grid by accounting for spatial restrictions and characteristics of existing networks. In practice, the calculation of connection costs for each new consumer includes the network design and financial expenditure. We suggest that connection costs should be calculated for the whole city based on the normative parameters at the stage when the object location is selected by investors and when power grid development is planned by power companies. The proposed method enables the modeling of new power line connection routes from every parcel of city land to possible points of connection to the operating networks based on the raster design of the area. The optimal path is chosen by one criterion consisting of two components: the costs of both laying new power lines and providing sufficient power reserve in the chosen network connection point. Realized as a computer program, the method has been used to calculate the costs of connections to low-voltage power lines. 相似文献
20.
Voronoi图是地理空间设施分布特征提取的重要几何模型,基于不同的空间距离概念可建立不同的Voronoi图。本研究顾及城市网络空间中设施点的服务功能及相互联系发生于网络路径距离而非传统的欧式距离的事实,针对网络空间Voronoi图模型,建立一种网络空间Voronoi图生成的栅格扩展算法。首先对图结构的边目标剖分为细小的线性单元,称作网络空间的栅格化,引入水流扩展思想,将事件点发生源视为“水源”,以栅格单元长度为扩展步长,让水流方向沿着网络上的可通行路径同时向外蔓延,直至与其他水流相遇或者到达边的尽头。该算法可方便地加入网络图结构中的多种约束,如街道边的单向行驶、结点的限制性连接等实际空间限制条件。通过大规模实际数据的“数字城市”POI点服务范围的试验表明该算法的效率高。 相似文献