A TIN compression method using Delaunay triangulation

This study introduces a new Triangulated Irregular Network(TIN) compression method and a progressive visualization technique using Delaunay triangulation. The compression strategy is based on the assumption that most triangulated 2.5-dimensional terrains are very similar to their Delaunay triangulation. Therefore, the compression algorithm only needs to maintain a few edges that are not included in the Delaunay edges. An efficient encoding method is presented for the set of edges by using vertex reordering and a general bracketing method. In experiments, the compression method examined several sets of TIN data with various resolutions, which were generated by five typical terrain simplification algorithms. By exploiting the results, the connecting structures of common terrain data are compressed to 0.17 bits per vertex on average, which is superior to the results of previous methods. The results are shown by a progressive visualization method for web-based GIS.     

Representation of 3-D elevation in terrain databases using hierarchical triangulated irregular networks: a comparative analysis

3-D terrain representation plays an important role in a number of terrain database applications. Hierarchical Triangulated Irregular Networks (TINs) provide a variable-resolution terrain representation that is based on a nested triangulation of the terrain. This paper compares and analyzes existing hierarchical triangulation techniques. The comparative analysis takes into account how aesthetically appealing and accurate the resulting terrain representation is. Parameters, such as adjacency, slivers, and streaks, are used to provide a measure on how aesthetically appealing the terrain representation is. Slivers occur when the triangulation produces thin and slivery triangles. Streaks appear when there are too many triangulations done at a given vertex. Simple mathematical expressions are derived for these parameters, thereby providing a fairer and a more easily duplicated comparison. In addition to meeting the adjacency requirement, an aesthetically pleasant hierarchical TINs generation algorithm is expected to reduce both slivers and streaks while maintaining accuracy. A comparative analysis of a number of existing approaches shows that a variant of a method originally proposed by Scarlatos exhibits better overall performance.     

基于四叉树索引构建TIN的高效合成算法

不规则三角网(TIN)可以逼真的模拟地形表面,因此被广泛应用于地学领域。Delaunay三角剖分算法是构建TIN网的最优算法,该文对传统Delaunay三角网构建算法进行分析,提出了一种针对大规模离散数据点生成TIN的高效合成算法。该算法首先根据离散点的分布位置和密度对其进行四叉树区域划分;然后以每个叶子节点的边界四边形为凸包,采用逐点插入法构建三角网;最后采用顶点合并法自底向上合并具有相同父节点的4个子节点,生成Delaunay三角网。实验结果表明,该算法时间复杂度较低,有效提高了TIN网的构建效率。     

Parallel constrained Delaunay triangulation on the GPU

In this paper, we propose a new graphics processing unit (GPU) method able to compute the 2D constrained Delaunay triangulation (CDT) of a planar straight-line graph consisting of points and segments. All existing methods compute the Delaunay triangulation of the given point set, insert all the segments, and then finally transform the resulting triangulation into the CDT. To the contrary, our novel approach simultaneously inserts points and segments into the triangulation, taking special care to avoid conflicts during retriangulations due to concurrent insertion of points or concurrent edge flips. Our implementation using the Compute Unified Device Architecture programming model on NVIDIA GPUs improves, in terms of running time, the best known GPU-based approach to the CDT problem.     

自适应的IDW插值方法及其在气温场中的应用

反距离权重(Inverse Distance Weighting,IDW)插值通常采用距离搜索策略选择插值参考点,当采样点集分布不均匀时,距离搜索策略使得参考点聚集一侧影响插值精度。自然邻近关系具有良好的自适应分布特性,可有效地解决参考点分布不均匀问题。结合自然邻近关系,提出自适应的反距离权重(Adaptive-IDW,AIDW)插值方法。首先对采样数据构建初始Delaunay三角网,然后采用逐点插入法,将待插值点插入初始Delaunay三角网中,局部调整得到新的Delaunay三角网,以待插值点的一阶邻近点作为IDW插值的参考点,使参考点自适应均匀地分布在待插值点周围,再进行IDW插值计算。利用AIDW插值方法对Franke函数、全国气温观测数据进行插值实验,结果表明此方法具有较高的精度,且减少了“牛眼”现象。     

Comparison of existing methods for building triangular irregular network,models of terrain from grid digital elevation models

Abstract

Triangulated irregular networks (TINs) are increasingly popular for their efficiency in data storage and their ability to accommodate irregularly spaced elevation points for many applications of geographical information systems. This paper reviews and evaluates various methods for extracting TINs from dense digital elevation models (DEMs) on a sample DEM. Both structural and statistical comparisons show that the methods perform with different rates of success in different settings. Users of DEM to TIN conversion methods should be aware of the strengths and weaknesses of the methods in addition to their own purposes before conducting the conversion.     

Automated building generalization based on urban morphology and Gestalt theory

Building generalization is a difficult operation due to the complexity of the spatial distribution of buildings and for reasons of spatial recognition. In this study, building generalization is decomposed into two steps, i.e. building grouping and generalization execution. The neighbourhood model in urban morphology provides global constraints for guiding the global partitioning of building sets on the whole map by means of roads and rivers, by which enclaves, blocks, superblocks or neighbourhoods are formed; whereas the local constraints from Gestalt principles provide criteria for the further grouping of enclaves, blocks, superblocks and/or neighbourhoods. In the grouping process, graph theory, Delaunay triangulation and the Voronoi diagram are employed as supporting techniques. After grouping, some useful information, such as the sum of the building's area, the mean separation and the standard deviation of the separation of buildings, is attached to each group. By means of the attached information, an appropriate operation is selected to generalize the corresponding groups. Indeed, the methodology described brings together a number of well-developed theories/techniques, including graph theory, Delaunay triangulation, the Voronoi diagram, urban morphology and Gestalt theory, in such a way that multiscale products can be derived.     

三维含拓扑地质剖面三角剖分可视化研究

三维剖面是地质对象表达和地质问题分析中最基本和最常用的数据。该文分析三维复杂地质折剖面可视化存在的问题,并提出展开剖分算法。该方法保证了各点之间的水平距离与剖面拓扑关系不变,能够对由"多边形-弧段-结点"矢量结构构成的三维折剖面进行有效剖分。在此基础上实现了三维剖面的可视化,尤其合理解决了纹理映射中的纹理变形与重复接缝等问题。     

A density-based approach for detecting network-constrained clusters in spatial point events

Existing spatial clustering methods primarily focus on points distributed in planar space. However, occurrence locations and background processes of most human mobility events within cities are constrained by the road network space. Here we describe a density-based clustering approach for objectively detecting clusters in network-constrained point events. First, the network-constrained Delaunay triangulation is constructed to facilitate the measurement of network distances between points. Then, a combination of network kernel density estimation and potential entropy is executed to determine the optimal neighbourhood size. Furthermore, all network-constrained events are tested under a null hypothesis to statistically identify core points with significantly high densities. Finally, spatial clusters can be formed by expanding from the identified core points. Experimental comparisons performed on the origin and destination points of taxis in Beijing demonstrate that the proposed method can ascertain network-constrained clusters precisely and significantly. The resulting time-dependent patterns of clusters will be informative for taxi route selections in the future.     

二维Delaunay三角网的任意点删除算法研究

针对目前基于影响域多边形剖分的点删除算法缺陷,提出一种二维Delaunay三角网点删除算法。首先利用具有拓扑关系的三角网搜索影响多边形,并以三角形矢量面积为工具三角剖分影响域多边形,最后通过镶嵌优化后的剖分三角网完成点的删除,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。     

Natural trees—neighbourhood-location in a nutshell

Abstract

We present the notion of a natural tree as an efficient method for storing spatial information for quick access. A natural tree is a representation of spatial adjacency, organised to allow efficient addition of new data, access to existing data, or deletions. The nodes of a natural tree are compound elements obtained by a particular Delaunay triangulation algorithm. Improvements to that algorithm allow both the construction of the triangulation and subsequent access to neighbourhood information to be O(N log N). Applications include geographical information systems, contouring, and dynamical systems reconstruction.     

Influence of survey strategy and interpolation model on DEM quality

Accurate characterisation of morphology is critical to many studies in the field of geomorphology, particularly those dealing with changes over time. Digital elevation models (DEMs) are commonly used to represent morphology in three dimensions. The quality of the DEM is largely a function of the accuracy of individual survey points, field survey strategy, and the method of interpolation. Recommendations concerning field survey strategy and appropriate methods of interpolation are currently lacking. Furthermore, the majority of studies to date consider error to be uniform across a surface. This study quantifies survey strategy and interpolation error for a gravel bar on the River Nent, Blagill, Cumbria, UK. Five sampling strategies were compared: (i) cross section; (ii) bar outline only; (iii) bar and chute outline; (iv) bar and chute outline with spot heights; and (v) aerial LiDAR equivalent, derived from degraded terrestrial laser scan (TLS) data. Digital Elevation Models were then produced using five different common interpolation algorithms. Each resultant DEM was differentiated from a terrestrial laser scan of the gravel bar surface in order to define the spatial distribution of vertical and volumetric error. Overall triangulation with linear interpolation (TIN) or point kriging appeared to provide the best interpolators for the bar surface. Lowest error on average was found for the simulated aerial LiDAR survey strategy, regardless of interpolation technique. However, comparably low errors were also found for the bar-chute-spot sampling strategy when TINs or point kriging was used as the interpolator. The magnitude of the errors between survey strategy exceeded those found between interpolation technique for a specific survey strategy. Strong relationships between local surface topographic variation (as defined by the standard deviation of vertical elevations in a 0.2-m diameter moving window), and DEM errors were also found, with much greater errors found at slope breaks such as bank edges. A series of curves are presented that demonstrate these relationships for each interpolation and survey strategy. The simulated aerial LiDAR data set displayed the lowest errors across the flatter surfaces; however, sharp slope breaks are better modelled by the morphologically based survey strategy. The curves presented have general application to spatially distributed data of river beds and may be applied to standard deviation grids to predict spatial error within a surface, depending upon sampling strategy and interpolation algorithm.     

Assessing the implications of the recent community opening policy on the street centrality in China: A GIS-based method and case study

Recently, the Chinese government raised an urban planning policy which suggests communities open their private roads for public transport and establish street networks with high spatial density in cities. In this context, the purpose of this study is to analyze the potential changes to street network accessibility using GIS techniques and to provide spatial information that may influence the decision making of urban managers. In addition to the existing street network data in the case study city, Shenzhen, intra-community roads are extracted from building footprints in GIS topographic database and used to construct a potential street network with respect to the community opening policy. An automatic GIS-based method is proposed here to analyze the location advantage information in the simulated urban environment, by combining Delaunay triangulation model and graph theory concepts. Specifically, we establish a two-step framework based on the spatial relationships between roads and buildings. Firstly, intra-community roads between neighboring building footprints are generated using a Delaunay triangulation skeleton model, and with the existing inter-community roads they form the simulated network. Secondly, street centrality indices of the current and simulated networks are compared in terms of closeness, betweenness and straightness. Results indicate that after applying the policy the global accessibility in the city would be increased at some places and decreased at others, and places' directness among others would be generally improved. In addition, the skeleton of central routes for through traffic would not change much. The presented method can also be applied to other cities.     

An efficient incremental algorithm for generating the characteristic shape of a dynamic set of points in the plane

Several algorithms have been proposed to generate a polygonal ‘footprint’ to characterize the shape of a set of points in the plane. One widely used type of footprint is the χ-shape. Based on the Delaunay triangulation (DT), χ-shapes guaranteed to be simple (Jordan) polygons. This paper presents for the first time an incremental χ-shape algorithm, capable of processing point data streams. Our incremental χ-shape algorithm allows both insertion and deletion operations, and can handle streaming individual points and multiple point sets. The experimental results demonstrated that the incremental algorithm is significantly more efficient than the existing, batch χ-shape algorithm for processing a wide variety of point data streams.     

Tagging-the-triangle algorithm for partitioning features with inconsistent boundaries

In spatial data sets, gaps or overlaps among features are frequently found in spatial tessellations due to the non-abutting edges with adjacent features. These non-abutting edges in loose tessellations are also called inconsistent boundaries or slivers; polygons containing at least one inconsistent boundary are called inconsistent polygons or sliver polygons. The existing algorithms to solve topological inconsistencies in sliver polygons suffer from one or more of three major issues, namely determination of tolerances, excessive CPU processing time for large data sets and loss of vertex history. In this article, we introduce a new algorithm that mitigates these three issues. Our algorithm efficiently searches the features with inconsistent polygons in a given spatial data set and logically partitions them among adjacent features. The proposed algorithm employs the constrained Delaunay triangulation technique to generate labelled triangles from which inconsistent polygons with gaps and overlaps are identified using label counts. These inconsistent polygons are then partitioned using the straight skeleton method. Moreover, each of these partitioned gaps or overlaps is distributed among the adjacent features to improve the topological consistency of the spatial data sets. We experimentally verified our algorithm using the real land cadastre data set. The comparison results show that the proposed algorithm is four times faster than the existing algorithm for data sets with 200,000 edges.     

基于圈层结构的游客活动空间边界提取新方法

准确刻画游客活动空间边界对于优化景区结构、实施界限管控、提高资源利用效益均有重要意义。由于游客行为的复杂性与边界模糊性,利用传统地理边界提取方法难以有效识别游客活动空间边界。基于层次聚类算法优化后的Delaunay三角网进行核密度估计,解决了多尺度下点核密度对空间边界拟合不精确的问题,同时借鉴圈层结构理论,依据游客空间集聚特征建立景区层次结构,利用大量游客长时间签到蕴含的时空信息,分析游客空间分布扩张规律,挖掘地理要素关系,建立“Hie-Density”模型,提出基于圈层结构理论的游客活动空间边界定量提取新方法。本文通过微观视角下圈层子系统的协同作用探究主体系统的宏观演化,证明了“Hie-Density”模型支持对多种游客分布模式进行描述,同时能够依据模型变化曲线定量识别游客活动最佳边界、空间集散状态、中心分裂特征及边界演化方向。多案例实证表明,本方法适用于各类景区的多尺度复杂游客活动空间边界提取,为地理时空数据挖掘提供了新视角和新方法。     

多边形主骨架线提取算法的设计与实现

在Delaunay三角网的基础上对骨架线节点进行了分类,通过确定主骨架线的两个端点,运用回溯法提取了多边形的主骨架线,同时给出了详细的算法步骤,并在Visual C++2003环境下实现了该算法。较之其他算法,该算法思路简捷,易于编程,生成的主骨架线形态优良,较好地反映了多边形的主体形状特征和主延伸方向。