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.     

Envelope generation and simplification of polylines using Delaunay triangulation

As a basic and significant operator in map generalization, polyline simplification needs to work across scales. Perkal’s ε-circle rolling approach, in which a circle with diameter ε is rolled on both sides of the polyline so that the small bend features can be detected and removed, is considered as one of the few scale-driven solutions. However, the envelope computation, which is a key part of this method, has been difficult to implement. Here, we present a computational method that implements Perkal’s proposal. To simulate the effects of a rolling circle, Delaunay triangulation is used to detect bend features and further to construct the envelope structure around a polyline. Then, different connection methods within the enveloping area are provided to output the abstracted result, and a strategy to determine the best connection method is explored. Experiments with real land-use polygon data are implemented, and comparison with other algorithms is discussed. In addition to the scale-specificity inherited from Perkal’s proposal, the results show that the proposed algorithm can preserve the main shape of the polyline and meet the area-maintaining constraint during large-scale change. This algorithm is also free from self-intersection.     

The CartACom model: transforming cartographic features into communicating agents for cartographic generalisation

Our research is concerned with automated generalisation of topographic vector databases in order to produce maps. This article presents a new, agent-based generalisation model called CartACom (Cartographic generalisation with Communicating Agents), dedicated to the treatment of areas of low density but where rubber sheeting techniques are not sufficient because some eliminations or aggregations are needed. In CartACom, the objects of the initial database are modelled as agents, that is, autonomous entities, that choose and apply generalisation algorithms to themselves in order to increase the satisfaction of their constraints as much as possible. The CartACom model focuses on modelling and treating the relational constraints, defined as constraints that concern a relation between two objects. In order to detect and assess their relational constraints, the CartACom agents are able to perceive their spatial surroundings. Moreover, to make the good generalisation decisions to satisfy their relational constraints, they are able to communicate with their neighbours using predefined dialogue protocols. Finally, a hook to another agent-based generalisation model – AGENT – is provided, so that the CartACom agents can handle not only their relational constraints but also their internal constraints. The CartACom model has been applied to the generalisation of low-density, heterogeneous areas like rural areas, where the space is not hierarchically organised. Examples of results obtained on real data show that it is well adapted for this application.     

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.     

Error propagation in cartographic modelling using Boolean logic and continuous classification

Abstract

When data on environmental attributes such as those of soil or groundwater are manipulated by logical cartographic modelling, the results are usually assumed to be exact. However, in reality the results will be in error because the values of input attributes cannot be determined exactly. This paper analyses how errors in such values propagate through Boolean and continuous modelling, involving the intersection of several maps. The error analysis is carried out using Monte Carlo methods on data interpolated by block kriging to a regular grid which yields predictions and prediction error standard deviations of attribute values for each pixel. The theory is illustrated by a case study concerning the selection of areas of medium textured, non-saline soil at an experimental farm in Alberta, Canada. The results suggest that Boolean methods of sieve mapping are much more prone to error propagation than the more robust continuous equivalents. More study of the effects of errors and of the choice of attribute classes and of class parameters on error propagation is recommended.     

一体化地图制图信息系统的建立及其应用

由于新技术的发展和应用,地图制图信息系统提出了新的概念,地图生产和应用观念都发生了根本变化,地图学家在新时期下面临着新的机遇和挑战。为了促进我国地图学的发展,中科院地理所引进了美国INTERGRAPH系统,同时又开发了自己的电子地图创作系统EA-World,并研制了两系统之间的接口,使两系统结合成为一体化的地图制图信息系统。系统先后完成了多个国家级图集的印刷版和电子版的制作,取得了良好的效果。文中系统地介绍和总结了这一系统的构成、功能和特点及其工艺流程。     

Functional organization of vegetation in the system of cartographic forecasting

Presented are the results from the assessment stage of forecasting-cartographic investigations into the vegetation in the Angara-Lena interfluve. An assessment is made of the main (preferred) and secondary ecological functions of vegetation within the geosystems. We demonstrate their changes with respect to native (reconstructed) vegetation.     

Accuracy of contour lines using 3D bands

This article describes a new methodology for the planimetric control of contour lines. The method is based on the generation of buffers around the contour lines which define a 3D buffer around the maximum slope line. After that we analyze the quantity of points from a more accurate source which is inside this buffer. As a result, we obtain a distribution function of the control points included when we apply several widths to the buffers. We have also determined the angularity and height differences of these points. The method has been applied to several sets of contour line intervals derived from a digital elevation model (DEM) and to the contour lines of one published topographic map using the DEM as the control source. We have also analyzed the representative behaviour of the contour lines, taking into account the contour line interval and the detection of an uncertainty model based on the slope variation. This study demonstrates the viability of the proposed method for obtaining the uncertainty of the contour lines depending on a given level of confidence and the variability of this uncertainty in the map. Finally, we propose a range of contour line intervals based on the scale and slopes.     

A comparison of neighbourhood relations based on ordinary Delaunay diagrams and area Delaunay diagrams: an application to define the neighbourhood relations of buildings

ABSTRACT

The aim of this article is to describe a convenient but robust method for defining neighbourhood relations among buildings based on ordinary Delaunay diagrams (ODDs) and area Delaunay diagrams (ADDs). ODDs and ADDs are defined as a set of edges connecting the generators of adjacent ordinary Voronoi cells (points representing centroids of building polygons) and a set of edges connecting two centroids of building polygons, which are the generators of adjacent area Voronoi cells, respectively. Although ADDs are more robust than ODDs, computation time of ODDs is shorter than that of ADDs (the order of their computation time complexity is O(nlogn)). If ODDs can approximate ADDs with a certain degree of accuracy, the former can be used as an alternative. Therefore, we computed the ratio of the number of ADD edges to that of ODD edges overlapping ADDs at building and regional scales. The results indicate that: (1) for approximately 60% of all buildings, ODDs can exactly overlap ADDs with extra ODD edges; (2) at a regional scale, ODDs can overlap approximately 90% of ADDs with 10% extra ODD edges; and (3) focusing on judging errors, although ADDs are more accurate than ODDs, the difference is only approximately 1%.     

Comparison of existing triangulation methods for regularly and irregularly spaced height fields

Over the last two decades, the Delaunay triangulation has been the only choice for most geographical information system (GIS) users and researchers to build triangulated irregular networks (TINs). The classical Delaunay triangulation for creating TINs only considers the 2D distribution of data points. Recent research efforts have been devoted to generating data-dependent triangulation which incorporate information on both distribution and values of input data in the triangulation process. This paper compares the traditional Delaunay triangulations with several variant data-dependent triangulations based on Lawson's local optimization procedure (LOP). Two USGS digital elevation models (DEMs) are used in the comparison. It is clear from the experiments that the quality of TINs not only depends on the vertex placement but also on the vertex connection. Traditonal two step processes for TIN construction, which separate point selection from the triangulation, generate far worse results than the methods which iteratively select points during the triangulation process. A pure data-dependent triangulation contains a large amount of slivers and steep triangles, which greatly affect the quality of TINs constructed. Among the triangulation methods tested, the classical Delaunay triangulation is still the most successful technique for constructing TINs for approximating natural terrain surfaces.     

基于强约束Delaunay-TIN的三维地学模拟与可视化

该文以煤层为例,在分析地层底板空间信息特征的基础上,以地层底板等高线为数据源,基于强约束Delau－nay三角形研究含量断层约束的三维地学模拟的数据组织方法,设计地层底板要素的数据结构,并讨论底板各要素的拓扑关系。进而以Delphi和OPGL编程,在CeoMo^3D系统中开发插件,实现了地层底板的3D可视化和基于Voronoi图的地层体积与矿层的储量计算。     

Soil cover on the territory of the city of Angarsk: the ecologo-biochemical and cartographic aspects

Based on integral indicators, the method of isolines was used to carry out a cartographic portrayal of the ecologo-biochemical status of soil cover in the city of Angarsk. The study revealed high values of soil metabolism for an industrial city, and tendencies for a substantial shift of pH values toward the alkaline side.     

约束Delaunay四面体剖分在三维地质建模中的应用

简要介绍了地质建模概念及层状地质体建模方法,考虑到Delaunay三角剖分良好的边界约束适应能力,提出了一种以地质层面Delaunay三角网为约束条件进行约束四面体剖分构建地质模型的方法。在通过对南京河西地区钻孔数据进行自适应插值处理后,应用此算法构建该地区的三维地下浅层空间地质体模型,实践证明该方法能够得到可视化效果较好的地质模型,并可高效地支撑地学空间分析与计算,为城市规划提供更好的决策支持。     

地图投影与地缘政治理论构建——以麦金德地缘政治思想为例

地缘政治理论的提出和发展深刻烙印了地图的影响。在地缘政治发展史中,不同地图投影既服务于各思想家的理论提出,也深入到各思想家在不同时期对自身理论的动态修正。地图投影到底是如何参与到地缘政治理论构建过程中的?本文在既有地缘政治地图研究的基础上,从空间性和文本性两大地图基本属性出发,通过阐释并沟通地图的空间分析与话语分析功能,探讨地图投影与地缘政治理论构建间的关系。一方面,地图投影变形抽象后的心象地图框架为构建地缘政治理论提供了空间依托;另一方面,地图投影通过地图变形在复杂情境中聚集了丰富的文本性含义。在地图投影各层次文本性的互文（互补性叙事）下,新的地图话语得以产生并渗透进心象地图,具象式推动了地缘政治理论核心概念的生成和逻辑关系的构建。综合考虑麦金德的地图观影响,本文对麦金德“心脏地带”地缘政治思想变迁各阶段（1904年、1919年、1943年）地图投影透视的分析验证了该关系框架的解释力。这启示该分析框架在其他地缘政治理论研究中的潜在适用性,更期待在百年变局和复兴全局等交织下的复杂情境中,基于地图投影创新互文下的中国地缘政治理论构建。     

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

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

二维Delaunay三角网局部更新:点插入与点删除

二维Delaunay三角网的局部更新在地学分析、道路CAD、城市规划等领域有着广泛的用途,点插入和点删除则是其中最重要、最基本的操作。该文针对原有逐点插入法和凸耳权值点删除算法存在的不足,利用动态包围三角形和特征三角形分别对其进行改进,在设计的具有拓扑关系Delaunay的三角网数据结构基础上,实现Delaunay三角网的快速局部更新,且使之满足Delaunay特性。最后通过模拟实验验证了算法的正确性和高效性。     

Comparing historical and contemporary maps - a methodological framework for a cartographic map comparison applied to Swiss maps

Topographic maps are powerful tools for the purpose of identifying land use and cover change (LUCC) as they are among the most reliable representations of past landscapes for the time prior to the existence of aerial photography. In light of the increased availability of historical maps, we argue that there is a need for a standardized process to assess map comparability in a systematic way in order to avoid, or at least minimize, the detection of spurious landscape changes due to incompatible map series. A full understanding of map quality, background and error distributions is fundamental to attain reliable LUCC results. The conceptual framework presented in this study considers the context, distortion and cartographic generalization of topographic maps. Furthermore, it includes an approach to homogenize the level of generalization of landscape elements (e.g. forests) from maps with different scales. To demonstrate its application, we assessed the comparability of seven topographic maps from Canton Zurich covering a time span of 336 years (1664–2000). Overall, for the maps of Canton Zurich, a wall-to-wall comparison of forest cover based on the topographic maps presented here can be problematic for the oldest map from 1664. Based on the results, a wall-to-wall comparison with the later maps is not recommended, due to its substantial distortion. Yet, after re-generalization of natural landscape elements, such as forests, a comparison based on landscape indices is possible, even for the oldest map. Furthermore, our results demonstrate that maps from the mid-19^th century onward possess an acceptable level of accuracy. This framework can be applied to a wide range of maps at regional, national, or global levels, providing the opportunity to look at land cover history over multiple centuries.