Multi-Scale Representation of a Digital Line

A scheme for multi-scale geometrical representation of a digital line is proposed. A digital line is represented as a structured object in which lines at different levels of resolution are represented as lists, quadcodes are used as control mechanism for guiding line simplification at multiple scales of a pyramid, and operators for simplification and smoothing are used to generate lines at different levels of resolution. In this scheme, lines at different levels of an image pyramid can be automatically generated without specifying the so-called tolerance value. Experimental results show that up to a certain level of resolution, the simplified lines retain important information content and recognizable characteristics. Also, the image pyramid assures a legible representation at any level of representation. Future research should improve the current line simplification operator and address the correspondence between lines at different levels of an image pyramid and the lines at different map scales.     

Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation

A new method of cartographic line simplification is presented. Regular hexagonal tessellations are used to sample lines for simplification, where hexagon width, reflecting sampling fidelity, is varied in proportion to target scale and drawing resolution. Tesserae constitute loci at which new sets of vertices are defined by vertex clustering quantization, and these vertices are used to compose simplified lines retaining only visually resolvable detail at target scale. Hexagon scaling is informed by the Nyquist–Shannon sampling theorem. The hexagonal quantization algorithm is also compared to an implementation of the Li–Openshaw raster-vector algorithm, which undertakes a similar process using square raster cells. Lines produced by either algorithm using like tessera widths are compared for fidelity to the original line in two ways: Hausdorff distances to the original lines are statistically analyzed, and simplified lines are presented against input lines for visual inspection. Results show that hexagonal quantization offers advantages over square tessellations for vertex clustering line simplification in that simplified lines are significantly less displaced from input lines. Visual inspection suggests lines produced by hexagonal quantization retain informative geographical shapes for greater differences in scale than do those produced by quantization in square cells. This study yields a scale-specific cartographic line simplification algorithm, following Li and Openshaw's natural principle, which is readily applicable to cartographic linework. Open-source Java code implementing the hexagonal quantization algorithm is available online.     

顾及拓扑一致性的水系三维曲线化简

鉴于常规曲线化简方法应用于水系曲线化简时难以顾及水系要素的三维特征及其拓扑关系,本文提出了一种顾及拓扑一致性的水系三维曲线化简方法。该方法首先对D-P算法进行三维扩展,实现水系中单条河流三维曲线化简,然后构建水系树结构表达其拓扑关系,最后按照水系树的层次顺序依次进行河流曲线化简和干流与支流的拓扑关系重构。试验结果表明,该方法化简精度高,既能保持水系的三维形态特征,又能保证河流交汇处的拓扑一致性。     

A progressive line simplification algorithm

An application of line simplification considering spatial knowledge is described. A method for identifying potential conflict regions, in order to avoid the self-intersection of generalized, lines, is also discussed. Further-more, a new progressive line simplification algorithm is presented. From the view point of spatial cognition, a spatial hierarchical structure is proposed, and its application to construction of spatial knowledge related to a line is explained.     

A progressive line simplification algorithm

1　ＩｎｔｒｏｄｕｃｔｉｏｎＭａｐｇｅｎｅｒａｌｉｚａｔｉｏｎｉｓｏｎｅｏｆｔｈｅｃｌａｓｓｉｃａｌｃａｒｔｏｇｒａｐｈｉｃｐｒｏｂ ｌｅｍｓ.Ａｌｌｍａｐｓ,ａｒｅｇｅｎｅｒａｌｉｚｅｄｒｅｐｒｅｓｅｎｔａｔｉｏｎｓｏｆｔｈｅｒｅａｌｉｔｙ.Ｇｅｎｅｒａｌｉｚａｔｉｏｎｉｓｎｅｃｅｓｓａｒｙｔｏｉｍｐｒｏｖｅｔｈｅｄｉｓｐｌａｙｑｕａｌｉｔｙｏｆｓｍａｌｌｓｃａｌｅｍａｐｓ,ａｌｌｏｗａｎａｌｙｓｉｓｗｉｔｈｄｉｆｆｅｒｅｎｔｇｒａｄｅｓｏｆｄｅｔａｉｌ;ａｎｄｒｅｄｕｃｅｄａｔａｓｔｏｒａｇｅｒｅ…     

一种顾及空间关系约束的线化简算法

线要素化简在制图表达与综合领域一直是研究的热点和难点之一。然而,经典化简算法多针对单独线要素进行处理,缺乏对该线要素与周边线要素之间整体空间关系的考虑,并且,存在计算结果生硬(D-P算法)、局部极值点缺失,特别是在曲度较大之处出现相交异常(L-O算法)等问题。为此,本文提出一种顾及空间关系约束的线化简算法,建立线要素全局化简方法(LGSM)和矢量位移、面积位移等5类评价指标。采用等高线、河流和道路3类线要素实际数据进行了试验,充分检验了本文算法的优越性,其处理结果符合开方根模型规律,降低了曲线复杂度,在保证全局空间关系不变条件下,不仅更好地保持了曲线整体形状特征,而且光滑美观、精度高。     

Area‐preservation Simplification of Polygonal Boundaries by the Use of the Structured Total Least Squares Method with Constraints

This article presents an area‐preservation approach for polygonal boundary simplification by the use of structured total least squares adjustment with constraints (STLSC), with the aim being to maintain the area of the original polygons after the simplification. Traditionally, a simplified line is represented by critical points selected from the original one. However, this study focuses on maintaining the areas of the polygons in the process of simplification of polygonal boundaries. Therefore, the proposed method in this article is a supplement to the existing line simplification methods, and it improves the quality of the simplification of polygonal boundaries in terms of positional and area errors. Based on the sub‐divisions of the original polyline, using the critical points detected from the polyline by the use of line simplification methods, the framework of the proposed method includes three main components, as follows: (1) establishment of the straight‐line‐segment fitting model based on both the critical and intermediate points on the sub‐polyline; (2) introduction of both area and end‐point constraints to reduce the geometric distortions due to the line simplification; and (3) derivation of the solution of boundary simplification by the use of STLSC. An empirical example was conducted to test the applicability of the proposed method. The results showed that: (1) by imposing the linear fitting model on both the critical and intermediate points on the sub‐polylines in the proposed STLSC method, the positional differences between the original points and the simplified line are approximately in a normal distribution; and (2) by introducing both end‐point and area constraints in the proposed STLSC method, the areas of the simplified polygons are the same as those of the original ones at different scales, and the two neighboring fitted lines are connected to each other at the optimized position.     

Cartographic News

This paper reports the results of an in-depth study which investigated two algorithms for line simplification and caricatural generalization (namely, those developed by Douglas and Peucker, and Visvalingam, respectively) in the context of a wider program of research on scale-free mapping. The use of large-scale data for man-designed objects, such as roads, has led to a better understanding of the properties of these algorithms and of their value within the spectrum of scale-free mapping. The Douglas-Peucker algorithm is better at minimal simplification. The large-scale data for roads makes it apparent that Visvalingam's technique is not only capable of removing entire scale-related features, but that it does so in a manner which preserves the shape of retained features. This technique offers some prospects for the construction of scale-free databases since it offers some scope for achieving balanced generalizations of an entire map, consisting of several complex lines. The results also suggest that it may be easier to formulate concepts and strategies for automatic segmentation of in-line features using large-scale road data and Visvalingam's algorithm. In addition, the abstraction of center lines may be facilitated by the inclusion of additional filtering rules with Visvalingam's algorithm.     

Multi‐Scale Qualitative Location: A Topology‐Based Model

Qualitative locations describe spatial objects by relating the spatial objects to a frame of reference (e.g. a regional partition in this study) with qualitative relations. Existing models only formalize spatial objects, frames of reference, and their relations at one scale, thus limiting their applicability in representing location changes of spatial objects across scales. A topology‐based, multi‐scale qualitative location model is proposed to represent the associations of multiple representations of the same objects with respect to the frames of reference at different levels. Multi‐scale regional partitions are first presented to be the frames of reference at multiple levels of scale. Multi‐scale locations are then formalized to relate multiple representations of the same objects to the multiple frames of reference by topological relations. Since spatial objects, frames of reference, and topological relations in qualitative locations are scale dependent, scale transformation approaches are presented to derive possible coarse locations from detailed locations by incorporating polygon merging, polygon‐to‐line and polygon‐to‐point operators.     

Contour line simplification method based on the two‐level Bellman–Ford algorithm

The contour line is one of the basic elements of a topographic map. Existing contour line simplification methods are generally applied to maps without topological errors. However, contour lines acquired from a digital elevation model (DEM) may contain topological errors before simplification. Targeted at contour lines with topological errors, a progressive simplification method based on the two‐level Bellman–Ford algorithm is proposed in this study. Simplified contour lines and elevation error bands were extracted from the DEM. The contour lines of the elevation error bands were initially simplified with the Bellman–Ford (BF) algorithm. The contour lines were then segmented using the vertices of the initial simplification result and connected curves with the same bending direction were merged into a new curve. Subsequently, various directed graphs of the merged curves were constructed and a second simplification was made using the BF algorithm. Finally, the simplification result was selected based on the similarity between several simplification results and adjacent contour lines. The experimental results indicate that the main shapes of the contour groups can be maintained with this method and original topological errors are resolved.     

多条海岸线协同化简的层次化三角网分区法

针对当前海岸线自动综合方法仅考虑单条线要素,未有效考虑其与附近海岸线之间的空间邻近关系,提出一种用于多条海岸线协同化简的层次化三角网分区法。首先,利用约束Delaunay三角网对能否化简的区域进行划分和标识;然后,利用二叉树构建层次关系模型,对各区域实体进行有序组织;最后,有序地对可化简的标识区域进行渐进式化简,并对局部狭窄区域进行自适应夸大,从而实现多海岸线的协同化简。试验结果表明:本文方法可克服复杂区域海岸线化简产生的图理性问题,可明显提高海岸线的化简质量。     

保持移动速度特征的轨迹线化简方法

轨迹线数据实施化简处理对于缓解数据存储、传输压力以及后期的分析可视化效率具有重要意义。常规方法(如Douglas-Peucker算法)主要考虑线目标的几何形态结构,直接应用到轨迹线化简中容易丢失移动物体的运动状态特征。本研究从保持轨迹线隐含速度特征出发,提出了一种基于移动速度相似性原则的轨迹线层次化剖分与分区化简处理方法。首先,以相邻轨迹点构成的直线段为基本单元,在拓扑连接关系约束下基于速度指标对轨迹直线段进行层次化聚类,并将聚类结果组织为层次树结构;然后,以建立的层次树结构为约束条件对原始轨迹线实施分区处理,使得同一区域内轨迹线片段的中间点距首尾基准线的最大时间同步偏移距离小于设定的阈值;最后,依次连接各分区轨迹线片段首尾点导出化简结果。采用真实的车辆轨迹线作为试验数据,通过与其他多种方法进行对比分析验证了本文提出方法的有效性。     

利用化简分割生成示意性网络地图

从整体到局部相互协调是示意性网络地图的关键所在,已有方法多是单纯地将线段作为示意基本单元,当空间要素分布不均衡时,容易产生示意结果全局表达不一致以及局部要素过于紧凑而变形的现象。考虑网络连通与网络闭合这两个性质,提出了一种化简分割生成方法,核心思想是根据连通化简网络,进而依据闭合构建网眼与线段两种基本示意单元。首先,对网络节点化简以及方向、长度调整,形成整体一致的化简网络;其次,将化简网络分割为网眼集合与线段集合;第三,建立从网眼至线段的示意化过程,通过网眼局部控制以避免要素过于紧凑。实验讨论了本文方法在不同示意约束规则之下的表现效果,与经典迭代寻优方法的对比分析表明,在网络整体形态保持与局部要素布置方面具有一定的优势。     

The use of cartographic control points in the harmonization and revision of MRDBs

The main purpose of the research is to achieve fully automated approach for supplying multi-resolution databases with linear objects in each scale. Moreover, the proposed solutions maintain the repeatability and accuracy of output data wherever possible according to the input scale. These properties are achieved by keeping the minimal object dimensions as well as the appropriate data pre-processing, based on the classification of source points. The classification distinguishes three classes of points: constant (unchangeable), temporary, and inherited. These classes build a structure of cartographic control points. Based on these solutions, the authors proposed an algorithm for linear object simplification based on minimal object dimensions and cartographic control points. It was also confirmed that the simplification between constant points does not cause geometry discrepancies in relation to the global simplification of the whole line.     

以直角方式转折的面状要素图形简化方法

讨论了面状要素图形轮廓简化的一些规则以及面的空间知识获取方法,结合以直角方式转折的面状要素图形轮廓的特点,重点讨论了其图形渐进式简化方法。     

线要素多尺度表达的一种新方法

本文依据多比例尺条件下矢量数据的绘制原理,提出了多尺度线化简与线选取方法。多尺度线化简算法依比例尺将空间坐标转换为像素坐标,根据像素坐标删除曲线中重合点与共线点,综合后的曲线与原始曲线在各比例尺下绘制结果相同;多尺度线选取算法利用仿射变换结果快速计算线要素之间的连通关系,然后渐进删除长度小于阈值的悬线与孤立弧段,保持了线要素的连通性。对不同类型数据的实验验证了本文算法的有效性和可行性。     

空间数据连续尺度表达的矢量金字塔模型

连续多尺度表达是当前地图制图领域中的热点问题之一,常规地图采用多级瓦片剖分、多版本存储技术实现空间多尺度表达,存在数据量冗余、跨级别不一致、瓦片间尺度跳跃大等问题。结合传统地图综合、多尺度表达数据结构和空间索引建立等多种策略,在目标数据模型中加入尺度维和操作信息,记录地图综合的过程和尺度变换,建立空间数据矢量金字塔模型。该模型离线综合获取多级基态尺度表达数据,确定每个目标的尺度表达空间范围,并通过面向对象建模技术将目标表达状态及其纵向关联关系、算子类型及控制参量等信息封装在多尺度目标中;同时,建立一端或两端控制的尺度变换结构。基于该模型可快速获取适应用户需求的连续尺度表达状态。     

Visual Evaluation of GIS Algorithms Using a Reference Grid

Geographic Information Systems (GIS) algorithms are used to simplify, edge match, and overlay large data sets. Some of these GIS processes can cause considerable positional changes to spatial data which are sometimes difficult to assess. This study presents a visualization technique for the evaluation of GIS algorithms and their positional effects on spatial data. The technique is applicable to vector representations and can be used with any GIS operation that changes vector geometry. The technique employs a uniform reference grid to exploit the visual skills of human operators in the evaluation of positional changes in spatial databases after applying GIS transformations. Changes in grid cell length, area, and shape, along with a set of displacement vectors, can be analyzed to evaluate positional changes in spatial data and to compare the behaviors of different algorithms. The technique can assist GIS users in the documentation of positional changes and in the comparison and selection of algorithms for various mapping tasks. Such a technique may assist software developers in creating and selecting appropriate GIS algorithms.     

利用地形开度算子自动提取激光雷达点云断裂线

基于机载激光雷达（LiDAR）点云生产高质量的数字高程模型（DEM）,需要地形特征线的约束。本文针对现有断裂线提取算法仅仅考虑了地表的局部变化,错提取率高的现状,从人工解译的角度出发,引入地形开度（topographic openness）作为一种定量描述地表整体变化的地形特征,提出了基于地形开度的断裂线自动提取算法。首先将原始地面点按高程采样成距离图像,然后通过地形开度算子获取地表的主体结构变化,最后结合形态学算子和边缘提取算子提取断裂线种子点并跟踪断裂线矢量。试验结果表明,该算法无需人工干预,能够快速提取较完整的断裂线。     

利用质心Voronoi图对地形自适应简化的算法

地形简化算法利用少量有效的地形信息表达整体地形,能很好地解决海量地形数据与计算机硬件之间的矛盾,同时满足多尺度地形应用需求。针对现有地形简化算法难以兼顾局部地形起伏与地形整体特征的问题,提出一种基于质心Voronoi图的地形自适应简化算法。首先,利用质心Voronoi图的特点,以地形起伏度作为密度函数生成质心Voronoi图;然后,利用分布在地形起伏较大区域的质心Voronoi图种子点及大多分布在地形特征线上的Voronoi区域顶点重构地形;最后,通过原始地形与重构地形的特征线验证地形简化的效果,并与三维道格拉斯-普克（3D DouglasPeucker,3D DP）算法进行精度对比。实验结果表明,从简化地形中提取的山脊线、山谷线、等高线等地形特征线与原始地形的重叠度均较高,算法能较好地保持地形整体特征;且在相同的简化级别下,算法的简化误差小于3D DP算法,具有较高的地形简化精度。