Comparison of Different Strategies for Determining Raster‐Based Least‐Cost Paths with a Minimum Amount of Distortion

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.     

A Hybrid Link‐Node Approach for Finding Shortest Paths in Road Networks with Turn Restrictions

Turn restrictions, such as ‘no left turn’ or ‘no U‐turn’, are commonly encountered in real road networks. These turn restrictions must be explicitly considered in the shortest path problem and ignoring them may lead to infeasible paths. In the present study, a hybrid link‐node Dijkstra's (HLND) algorithm is proposed to exactly solve the shortest path problem in road networks with turn restrictions. A new hybrid link–node labelling approach is devised by using a link–based labelling strategy at restricted nodes with turn restrictions, and a node‐based labelling strategy at unrestricted nodes without turn restrictions. Computational results for several real road networks show that the proposed HLND algorithm obtains the same optimal results as the link‐based Dijkstra's algorithm, while having a similar computational performance to the classical node‐based Dijkstra's algorithm.     

A Topology‐Inferred Graph‐Based Heuristic Algorithm for Map Simplification

In this article we present a heuristic map simplification algorithm based on a novel topology‐inferred graph model. Compared with the existing algorithms, which only focus either on geometry simplification or on topological consistency, our algorithm simplifies the map composed of series of polylines and constraint points while maintaining the topological relationships in the map, maximizing the number of removal points, and minimizing error distance efficiently. Unlike some traditional geometry simplification algorithms, such as Douglas and Peucker's, which add points incrementally, we remove points sequentially based on a priority determined by heuristic functions. In the first stage, we build a graph to model the topology of points in the map from which we determine whether a point is removable or not. As map generalization is needed in different applications with different requirements, we present two heuristic functions to determine the priority of points removal for two different purposes: to save storage space and to reduce computation time. The time complexity of our algorithm is which is efficient enough to be considered for real‐time applications. Experiments on real maps were conducted and the results indicate that our algorithm produces high quality results; one heuristic function results in higher removal points saving storage space and the other improves the time performance significantly.     

顾及转向延误的时间依赖A*最短路径算法

现有的动态路径规划算法通常只考虑当前时刻交通信息,而忽略了路段行程时间依赖于进入该路段的时刻这一现实。而且,转向延误的存在使得传统的基于节点标号的最短路径算法不再有效。本文建立了基于路段的时间依赖网络模型,将转向延误时间引入到FIFO（先进先出）条件的定义中,并给出了满足FIFO条件的路段到达时间和转向延误时间计算式。以此模型为基础,并通过将时间因子引入到启发式评价函数中,发展了基于路段标号的时间依赖A*最短路径算法。实验表明,所提出的算法能预测并回避即将发生的交通拥堵,有效节省用户的出行时间。而其平均计算时间仅比传统算法增加了10%左右。此外,由于不再需要进行频繁的路径重优化,该算法能大幅提高路径规划的整体效率。     

Geo‐Social Model: A Conceptual Framework for Real‐time Geocollaboration

Synchronous geocollaboration helps geographically dispersed people to work together in a shared geospatial environment. Its real‐time nature, multiple users' interaction and diversity of work context impose some special social, organizational and technological requirements, making the development of such real‐time geocollaboration systems a challenging task. A conceptual framework is therefore needed to specify and describe what synchronous geocollaboration is, considering its social, spatial and technical aspects. The geo‐social model presented in this article describes a conceptual framework for synchronous geocollaboration systems addressing the above aspects, identifies the core elements of the system and describes how these elements collaborate with each other. This model is presented using application‐level ontology and is then applied to a multi‐agent system based prototype in which multiple users can interact and negotiate in a shared 3D geospatial environment.     

“All the World's a Stage”: A GIS Framework for Recreating Personal Time‐Space from Qualitative and Quantitative Sources

This article presents a methodological model for the study of the space‐time patterns of everyday life. The framework utilizes a wide range of qualitative and quantitative sources to create two environmental stages, social and built, which place and contextualize the daily mobilities of individuals as they traverse urban environments. Additionally, this study outlines a procedure to fully integrate narrative sources in a GIS. By placing qualitative sources, such as narratives, within a stage‐based GIS, researchers can begin to tell rich spatial stories about the lived experiences of segregation, social interaction, and environmental exposure. The article concludes with a case study utilizing the diary of a postal clerk to outline the wide applicability of this model for space‐time GIS research.     

Geometric Algebra Model for Geometry‐oriented Topological Relation Computation

Classical topological relation expressions and computations are primarily based on abstract algebra. In this article, the representation and computation of geometry‐oriented topological relations (GOTR) are developed. GOTR is the integration of geometry and topology. The geometries are represented by blades, which contain both algebraic expressions and construction structures of the geometries in the conformal geometric algebra space. With the meet, inner, and outer products, two topology operators, the MeetOp and BoundOp operators, are developed to reveal the disjoint/intersection and inside/on‐surface/outside relations, respectively. A theoretical framework is then formulated to compute the topological relations between any pair of elementary geometries using the two operators. A multidimensional, unified and geometry‐oriented algorithm is developed to compute topological relations between geometries. With this framework, the internal results of the topological relations computation are geometries. The topological relations can be illustrated with clear geometric meanings; at the same time, it can also be modified and updated parametrically. Case studies evaluating the topological relations between 3D objects are performed. The result suggests that our model can express and compute the topological relations between objects in a symbolic and geometry‐oriented way. The method can also support topological relation series computation between objects with location or shape changes.     

A New 3‐D Solar Radiation Model for 3‐D City Models

Estimates of solar radiation distribution in urban areas are often limited by the complexity of urban environments. These limitations arise from spatial structures such as buildings and trees that affect spatial and temporal distributions of solar fluxes over urban surfaces. The traditional solar radiation models implemented in GIS can address this problem only partially. They can be adequately used only for 2‐D surfaces such as terrain and rooftops. However, vertical surfaces, such as facades, require a 3‐D approach. This study presents a new 3‐D solar radiation model for urban areas represented by 3‐D city models. The v.sun module implemented in GRASS GIS is based on the existing solar radiation methodology used in the topographic r.sun model with a new capability to process 3‐D vector data representing complex urban environments. The calculation procedure is based on the combined vector‐voxel approach segmenting the 3‐D vector objects to smaller polygon elements according to a voxel data structure of the volume region. The shadowing effects of surrounding objects are considered using a unique shadowing algorithm. The proposed model has been applied to the sample urban area with results showing strong spatial and temporal variations of solar radiation flows over complex urban surfaces.     

整体最小二乘线性回归模型与算法

从平差模型的角度,研究整体最小二乘线性回归模型条件平差与间接平差的解算方法,并在理论上证明两种解算方法的等价性。最后通过算例验证解算方法的正确性。     

适用于关阀分析算法的供水管网单元-阀门图模型

关阀分析在供水管网施工中用来快速确定最佳的关阀停水方案,对于供水安全具有重要意义。在管网传统结点-A立图模型的基础上,提出了优化实体数量并简洁表达拓扑结构的单元一阀门图模型。该模型是结点A立图的一种伪对偶图,它将管网内被阀门区隔形成的封闭连通区域归为顶点,将分隔两个区域的阀门作为边。设计了关断单元生成算法,从而实现单元一阀门图的构建,并提出基于该模型的高效供水管网关阀分析算法。实验表明,与基于结点-A立图的传统算法相比较,结合单元一阀门图模型的新算法能够大幅度提高关阀分析效率,并且可以在多施工点情况下得出正确的关阀方案。     

A Triangular Form‐based Multiple Flow Algorithm to Estimate Overland Flow Distribution and Accumulation on a Digital Elevation Model

In this study, we present a newly developed method for the estimation of surface flow paths on a digital elevation model (DEM). The objective is to use a form‐based algorithm, analyzing flow over single cells by dividing them into eight triangular facets and to estimate the surface flow paths on a raster DEM. For each cell on a gridded DEM, the triangular form‐based multiple flow algorithm (TFM) was used to distribute flow to one or more of the eight neighbor cells, which determined the flow paths over the DEM. Because each of the eight facets covering a cell has a constant slope and aspect, the estimations of – for example – flow direction and divergence/convergence are more intuitive and less complicated than many traditional raster‐based solutions. Experiments were undertaken by estimating the specific catchment area (SCA) over a number of mathematical surfaces, as well as on a real‐world DEM. Comparisons were made between the derived SCA by the TFM algorithm with eight other algorithms reported in the literature. The results show that the TFM algorithm produced the closest outcomes to the theoretical values of the SCA compared with other algorithms, derived more consistent outcomes, and was less influenced by surface shapes. The real‐world DEM test shows that the TFM was capable of modeling flow distribution without noticeable ‘artefacts’, and its ability to track flow paths makes it an appropriate platform for dynamic surface flow simulation.     

A Spatio‐Temporal Graph Model for Marine Dune Dynamics Analysis and Representation

Defining a model for the representation and the analysis of spatio‐temporal dynamics remains an open domain in geographical information sciences. In this article we investigate a spatio‐temporal graph‐based model dedicated to managing and extracting sets of geographical entities related in space and time. The approach is based on spatial and temporal local relations between neighboring entities during consecutive times. The model allows us to extract sets of connected entities distant in time and space over long periods and large spaces. From GIS concepts and qualitative reasoning on space and time, we combine the graph model with a dedicated spatial database. It includes information on geometry and geomorphometric parameters, and on spatial and temporal relations. This allows us to extend classical measurements of spatial parameters, with comparisons of entities linked by complex relations in space and time. As a case study, we show how the model suggests an efficient representation of dunes dynamics on a nautical chart for safe navigation.     

一种面向室内导航的通行区域模型及其自动提取算法

面向室内位置服务中路径规划与导航的应用需求,提出一种基于栅格空间的通行区域模型及其自动提取算法。首先,在栅格模型基础上引入了相邻栅格和途经栅格,结合具体示例阐述了通行区域模型的基本原理;然后,根据室内地图数据特征,通过室内栅格模型初始化、通行区域初次提取和邻域融合,设计了通行区域的自动提取算法;最后,选取西单大悦城一楼室内地图数据进行了不同栅格尺度的通行区域自动提取和路径规划试验。结果表明,该算法针对走廊内存在障碍等复杂室内环境具有较好的适用性,并且通行区域模型相比网络模型的路径规划结果更加符合复杂室内环境的路径行走特征。     

SAR图像立体定位原理与精度分析

本文在导出ＳＡＲ图像成像方程式的基础上提出了ＳＡＲ立体定位的原理和方法,并从理论上分析了影响ＳＡＲ立体定位的主要因素。实验结果表明,本文提出的立体定位方法是正确的,影响定位精度的主要因素是交会角的大小与距离向量测误差,其与理论分析模型一致。     

Towards Real‐Time Geodemographics: Clustering Algorithm Performance for Large Multidimensional Spatial Databases

Geodemographic classifications provide discrete indicators of the social, economic and demographic characteristics of people living within small geographic areas. They have hitherto been regarded as products, which are the final “best” outcome that can be achieved using available data and algorithms. However, reduction in computational cost, increased network bandwidths and increasingly accessible spatial data infrastructures have together created the potential for the creation of classifications in near real time within distributed online environments. Yet paramount to the creation of truly real time geodemographic classifications is the ability for software to process and efficiency cluster large multidimensional spatial databases within a timescale that is consistent with online user interaction. To this end, this article evaluates the computational efficiency of a number of clustering algorithms with a view to creating geodemographic classifications “on the fly” at a range of different geographic scales.     

地理空间数据版本管理模型设计与算法研究

版本管理系统是用来记录数据变化历史的系统,地理空间数据版本管理系统主要依托关系数据库,而关系数据库的短事务提交模型并不支持地理空间数据版本管理所需要的长事务工作流方式的提交模型。以此问题为背景,讨论地碑空间数据版本管理的理论模型,并通过对现有模型设计的改进和对算法的研究以及试验,验证该模型设计的合理性。     

A Multi‐granularity Parallel Model for Unified Remote Sensing Image Processing WebServices

The growth of the Web has resulted in the Web‐based sharing of distributed geospatial data and computational resources. The Geospatial Processing Web (GeoPW) described here is a set of services that provide a wide array of geo‐processing utilities over the Web and make geo‐processing functionalities easily accessible to users. High‐performance remote sensing image processing is an important component of the GeoPW. The design and implementation of high‐performance image processing are, at present, an actively pursued research topic. Researchers have proposed various parallel strategies for single image processing algorithm, based on a computer science approach to parallel processing. This article proposes a multi‐granularity parallel model for various remote sensing image processing algorithms. This model has four hierarchical interfaces that are labeled the Region of Interest oriented (ROI‐oriented), Decompose/Merge, Hierarchical Task Chain and Dynamic Task interfaces or sub‐models. In addition, interfaces, definitions, parallel task scheduling and fault‐tolerance mechanisms are described in detail. Based on the model and methods, we propose an open‐source online platform named OpenRS‐Cloud. A number of parallel algorithms were uniformly and efficiently developed, thus certifying the validity of the multi‐granularity parallel model for unified remote sensing image processing web services.     

The Influence of Digital Surface Model Choice on Visibility‐based Mobile Geospatial Applications

In this work we investigate the effectiveness of different types of visibility models for use within location‐based services. This article outlines the methodology and results for our experiments, which were designed to understand the accuracy and effects of model choices for mobile visibility querying. Harnessing a novel mobile media consumption and authoring application called Zapp, the levels of accuracy of various digital surface representations used by a line of sight visibility algorithm are extensively examined by statistically assessing randomly sampled viewing sites across the 1 km² study area, in relation to points of interest (POI) across the University of Nottingham campus. Testing was carried out on three different surface models derived from 0.5 m LiDAR data by visiting physical sites on each surface model with 14 random point of interest masks being viewed from between 10 and 16 different locations, totalling 190 data points. Each site was ground‐truthed by determining whether a given POI could be seen by the user and could also be identified by the mobile device. Our experiments in a semi‐urban area show that choice of surface model has important implications for mobile applications that utilize visibility in geospatial query operations.