A modified binary space partitioning tree for geographic information systems

We present a reactive data structure, that is, a spatial data structure with detail levels. The two properties, spatial organization and detail levels, are the basis for a geographic information system (GIS) with a multi-scale database. A reactive data structure is a novel type of data structure catering to multiple detail levels with rapid responses to spatial queries. It is presented here as a modification of the binary space partitioning tree that includes the levels of detail. This tree is one of the few spatial data structures that does not organize space in a rectangular manner. A prototype system has been implemented. An important result of this implementation is that it shows that binary space partitioning trees of real maps have O(n) storage space complexity in contrast to the theoretical worst case O(n² ), with n the number of line segments in the map.     

Modeling uncertainty of moving objects on road networks via space–time prisms

Moving objects produce trajectories, which are typically observed in a finite sample of time‐stamped locations. Between sample points, we are uncertain about the moving objects's location. When we assume extra information about an object, for instance, a (possibly location‐dependent) speed limit, we can use space–time prisms to model the uncertainty of an object's location.

Until now, space–time prisms have been studied for unconstrained movement in the 2D plane. In this paper, we study space–time prisms for objects that are constrained to travel on a road network. Movement on a road network can be viewed as essentially one‐dimensional. We describe the geometry of a space–time prism on a road network and give an algorithm to compute and visualize space–time prisms. For experiments and illustration, we have implemented this algorithm in MATHEMATICA.

Furthermore, we study the alibi query, which asks whether two moving objects could have possibly met or not. This comes down to deciding if the chains of space–time prisms produced by these moving objects intersect. We give an efficient algorithm to answer the alibi query for moving objects on a road network. This algorithm also determines where and when two moving objects may have met.     

Spatiotemporal data model for network time geographic analysis in the era of big data

There has been a resurgence of interest in time geography studies due to emerging spatiotemporal big data in urban environments. However, the rapid increase in the volume, diversity, and intensity of spatiotemporal data poses a significant challenge with respect to the representation and computation of time geographic entities and relations in road networks. To address this challenge, a spatiotemporal data model is proposed in this article. The proposed spatiotemporal data model is based on a compressed linear reference (CLR) technique to transform network time geographic entities in three-dimensional (3D) (x, y, t) space to two-dimensional (2D) CLR space. Using the proposed spatiotemporal data model, network time geographic entities can be stored and managed in classical spatial databases. Efficient spatial operations and index structures can be directly utilized to implement spatiotemporal operations and queries for network time geographic entities in CLR space. To validate the proposed spatiotemporal data model, a prototype system is developed using existing 2D GIS techniques. A case study is performed using large-scale datasets of space-time paths and prisms. The case study indicates that the proposed spatiotemporal data model is effective and efficient for storing, managing, and querying large-scale datasets of network time geographic entities.     

Constructing Interfaces between (and within) Geographical Information Systems

Abstract

An interface is a software package used, alone or in conjunction with other interfaces, to transfer data from one geographical information system to another, or between different representations within a single GIS. The aim in this paper is to extend the traditional view of an interface to include interfaces that use communication networks to move data between (and within) GIS. We suggest that, to exchange data across a network, the best solution may be to construct a set of communicating interfaces, each able to send data to, and receive data from, other communicating interfaces. We describe a working set of communicating interfaces that transfer data between a number of GIS data representations.     

Performance evaluation and work-load estimation for geographic information systems

Abstract

Agencies acquiring GIS hardware and software are faced with uncertainty at two levels: over the degree to which the proposed system will perform the functions required, and over the degree to which it is capable of doing so within proposed production schedules. As the field matures the second concern is becoming more significant. A formal model of the process of acquiring a GIS is presented, based on the conceptual level of defining GIS sub-tasks. The appropriateness of the approach is illustrated using performance data from the Canada Land Data System. It is possible to construct reasonably accurate models of system resource utilization using simple predictors and least squares techniques, and a combination of inductive and deductive reasoning. The model has been implemented in an interactive package for MS-DOS systems.     

An inductive modelling procedure based on Bayes' theorem for analysis of pattern in spatial data

Abstract

This paper describes an inductive modelling procedure integrated with a geographical information system for analysis of pattern within spatial data. The aim of the modelling procedure is to predict the distribution within one data set by combining a number of other data sets. Data set combination is carried out using Bayes’ theorem. Inputs to the theorem, in the form of conditional probabilities, are derived from an inductive learning process in which attributes of the data set to be modelled are compared with attributes of a variety of predictor data sets. This process is carried out on random subsets of the data to generate error bounds on inputs for analysis of error propagation associated with the use of Bayes’ theorem to combine data sets in the GIS. The statistical significance of model inputs is calculated as part of the inductive learning process. Use of the modelling procedure is illustrated through the analysis of the winter habitat relationships of red deer in Grampian Region, north-east Scotland. The distribution of red deer in Deer Management Group areas in Gordon and in Kincardine and Deeside Districts is used to develop a model which predicts the distribution throughout Grampian Region; this is tested against red deer distribution in Moray District. Habitat data sets used for constructing the model are accumulated frost and altitude, obtained from maps, and land cover, derived from satellite imagery. Errors resulting from the use of Bayes’ theorem to combine data sets within the GIS and introduced in generalizing output from 50 m pixel to 1 km grid squares resolution are analysed and presented in a series of maps. This analysis of error trains is an integral part of the implemented analytical procedure and provides support to the interpretation of the results of modelling. Potential applications of the modelling procedure are discussed.     

Land cover classification by an artificial neural network with ancillary information

Abstract

Remote sensing is an important source of land cover data required by many GIS users. Land cover data are typically derived from remotely–sensed data through the application of a conventional statistical classification. Such classification techniques are not, however, always appropriate, particularly as they may make untenable assumptions about the data and their output is hard, comprising only the code of the most likely class of membership. Whilst some deviation from the assumptions may be tolerated and a fuzzy output may be derived, making more information on class membership properties available, alternative classification procedures are sometimes required. Artificial neural networks are an attractive alternative to the statistical classifiers and here one is used to derive a fuzzy classification output from a remotely–sensed data set that may be post–processed with ancillary data available in a GIS to increase the accuracy with which land cover may be mapped. With the aid ancillary information on soil type and prior knowledge of class occurrence the accuracy of an artificial neural network classification was increased by 29–93 to 77–37 per cent. An artificial neural network can therefore be used generate a fuzzy classification output that may be used with other data sets in a GIS, which may not have been available to the producer of the classification, to increase the accuracy with which land cover may be classified.     

Mapping glacier velocities on Svalbard using ERS tandem DInSAR data

The results presented show how glacier velocities can be measured and calculated from Earth Resources Satellite (ERS) tandem interferometric synthetic aperture radar (InSAR) data by the use of geographical information systems (GIS) and non-interferometric software. A semi-automatic algorithm using existing and newly implemented modules in ESRI's GIS software Arc has been developed to unwrap existing height differentiated interferometric SAR (DInSAR) data. The algorithm is applied to a data set covering glaciers from the arctic archipelago Svalbard. Estimated DInSAR velocities are decomposed into the glacier surface flow direction using a digital elevation model (DEM). Velocity fields for the glaciers Isachsenfonna, Akademikerbreen and Nordbreen on Svalbard are presented.     

Integration of genetic algorithms and GIS for optimal location search

Optimal location search is frequently required in many urban applications for siting one or more facilities. However, the search may become very complex when it involves multiple sites, various constraints and multiple‐objectives. The exhaustive blind (brute‐force) search with high‐dimensional spatial data is infeasible in solving optimization problems because of a huge combinatorial solution space. Intelligent search algorithms can help to improve the performance of spatial search. This study will demonstrate that genetic algorithms can be used with Geographical Information systems (GIS) to effectively solve the spatial decision problems for optimally sitting n sites of a facility. Detailed population and transportation data from GIS are used to facilitate the calculation of fitness functions. Multiple planning objectives are also incorporated in the GA program. Experiments indicate that the proposed method has much better performance than simulated annealing and GIS neighborhood search methods. The GA method is very convenient in finding the solution with the highest utility value.     

Mineral Prospectivity Prediction from High-Dimensional Geoscientific Data Using a Similarity-Based Density Estimation Model

Assuming a study region in which each cell has associated with it an N-dimensional vector of values corresponding to N predictor variables, one means of predicting the potential of some cell to host mineralization is to estimate, on the basis of historical data, a probability density function that describes the distribution of vectors for cells known to contain deposits. This density estimate can then be employed to predict the mineralization likelihood of other cells in the study region. However, owing to the curse of dimensionality, estimating densities in high-dimensional input spaces is exceedingly difficult, and conventional statistical approaches often break down. This article describes an alternative approach to estimating densities. Inspired by recent work in the area of similarity-based learning, in which input takes the form of a matrix of pairwise similarities between training points, we show how the density of a set of mineralized training examples can be estimated from a graphical representation of those examples using the notion of eigenvector graph centrality. We also show how the likelihood for a test example can be estimated from these data without having to construct a new graph. Application of the technique to the prediction of gold deposits based on 16 predictor variables shows that its predictive performance far exceeds that of conventional density estimation methods, and is slightly better than the performance of a discriminative approach based on multilayer perceptron neural networks.     

Radial Basis Function Network for Ore Grade Estimation

This paper highlights the performance of a radial basis function (RBF) network for ore grade estimation in an offshore placer gold deposit. Several pertinent issues including RBF model construction, data division for model training, calibration and validation, and efficacy of the RBF network over the kriging and the multilayer perceptron models have been addressed in this study. For the construction of the RBF model, an orthogonal least-square algorithm (OLS) was used. The efficacy of this algorithm was testified against the random selection algorithm. It was found that OLS algorithm performed substantially better than the random selection algorithm. The model was trained using training data set, calibrated using calibration data set, and finally validated on the validation data set. However, for accurate performance measurement of the model, these three data sets should have similar statistical properties. To achieve the statistical similarity properties, an approach utilizing data segmentation and genetic algorithm was applied. A comparative evaluation of the RBF model against the kriging and the multilayer perceptron was then performed. It was seen that the RBF model produced estimates with the R ² (coefficient of determination) value of 0.39 as against of 0.19 for the kriging and of 0.18 for the multilayer perceptron.     

城市虚拟现实研究初探

虚拟城市是 3维城市地理信息系统的前沿领域 ,该文对在微机上如何建立虚拟城市作了初步探讨 ,把建立虚拟城市的方法分为 3维真实场景建模、海量数据环境下的场景漫游以及确定任意时刻声音文件的调入时机三个部分。重点介绍了控制三维场景漫游、自适应层次细节模型、简单碰撞检测的实现方法 ,并提出了采用泰森模型调用声音文件的新思路。最后给出在VC 开发环境下用OpenGL建立虚拟城市的应用实例。     

三角网的生成与简化算法

在三维地理信息系统的开发与研究中 ,要求三角网模型的支持 ,而高效的三角网生成算法是三角网模型的基础。该文综述各类三角网的生成算法 ,对以往被人忽视但简明高效的算法———径向扫描算法进行阐释 ,并对它的实现进行改进 ;对地形数据的简化及建立地形层次对象模型是实现高效的三维地理信息系统的关键 ,而三角网的简化是地形数据简化的基石之一 ,文中提供三种简化三角网的算法供同行讨论 ;并在微机上实现上述算法。     

摄影测量三维重建中多源信息融合方法探讨

分析摄影测量三维重建中不同数据源的特点,针对现有多源数据融合存在的有限数据源低层次融合问题,提出一种基于影像特征、GIS信息和3D TIN模型融合的层次结构与算法流程 .该算法主要包括多边形区域增长、几何推理和建筑物几何模型平差等处理,为基于摄影测 量的三维城市模型自动重建提供了一种新的思路与方法.     

Weight matrices and spatial autocorrelation statistics using a topological vector data model

Abstract

This paper reports on software to construct alternative weight matrices and to compute spatial autocorrelation statistics, namely the Moran coefficient and the Geary coefficient using Arc/Info’s data structure. As such it is an addition to recent efforts in linking GIS with exploratory spatial data analysis. The software is interfaced with Arc/Info via the Arc Macro Language (AML) so that it can be run in the ARC environment. This allows the user to perform exploratory analysis within GIS which may provide insights in subsequent spatial analysis and modelling.     

An information systems approach to the preservation of biological diversity

Abstract

Although biological diversity has emerged in the 1980s as a major scientific and political issue, efforts at scientific assessment have been hampered by the lack of cohesive sets of data. We describe, in concept, a comprehensive national diversity information system, using geographical information system (GIS) techniques to organize existing data and improve spatial aspects of the assessment. One potential GIS analysis, to identify gaps in the network of nature reserves for California, is discussed in greater detail. By employing an information systems approach, available data can be used more effectively and better management strategies can be formulated.     

A partition‐based serial algorithm for generating viewshed on massive DEMs

As increasingly large‐scale and higher‐resolution terrain data have become available, for example air‐form and space‐borne sensors, the volume of these datasets reveals scalability problems with existing GIS algorithms. To address this problem, a kind of serial algorithm was developed to generate viewshed on large grid‐based digital elevation models (DEMs). We first divided the whole DEM into rectangular blocks in row and column directions (called block partitioning), then processed these blocks with four axes followed by four sectors sequentially. When processing the particular block, we adopted the ‘reference plane’ algorithm to calculate the visibility of the target point on the block, and adjusted the calculation sequence according to the different spatial relationships between the block and the viewpoint since the viewpoint is not always inside the DEM. By adopting the ‘Reference Plane’ algorithm and using a block partitioning method to segment and load the DEM dynamically, it is possible to generate viewshed efficiently in PC‐based environments. Experiments showed that the divided block should be dynamically loaded whole into computer main memory when partitioning, and the suggested approach retains the accuracy of the reference plane algorithm and has near linear compute complexity.