An efficient solution for building polygonal objects

Polygonal object is a fundamental type of geometric data in vector GIS. The key step cleaning topological relationship after data collection of polygonal layer is to build polygonal objects from digital arcs. The raw digital arcs may intersect with each other. The algorithm for building polygonal objects after the raw arcs have been split at all intersections is presented. The build-up of polygonal objects in this paper is designed to be implemented by two steps. The first step is to extract all the polygons needed for build-up of polygonal objects from arcs. The second step is to organize polygonal objects from these polygons. For the first step, a tracing algorithm is proposed. The algorithm merely extracts the polygons needed for the build-up of polygonal objects, which is a subset of all the possible polygons that can be induced from the arcs. For the second step, an algorithm based on a specially designed order of polygons is advanced. All the topological relationships among the polygons are shown in a single scan. Experiments show that the two algorithms together offer a robust and efficient solution for building polygonal objects from intersected arcs.     

简单多边形间最大距离的求解算法

求解任意两个简单多边形间的最大距离,在几何图形计算中,一直是一个基本问题。在对多边形自身的特性以及两多边形间关系进行深入分析的基础上,提出了一个基于折线凸包的单调性的简单多边形间最大距离的求解算法。根据封闭折线内部所具有的特性,把封闭折线拆分成两个断开的折线,使一条折线在另一条折线左边。两个多边形分别被拆分成四条折线,两个分为一组。分别求出每组中两条折线的凸包,利用凸包的单调性可以快速地找出两个距离最远的顶点,其中较大的是两个简单多边形间的最大距离。算法的时间复杂度是线性的。     

基于二叉树思想的任意多边形三角剖分递归算法

提出了一种基于二叉树思想的任意多边形三角剖分递归算法。该算法采用二叉树思想，确定剖分三角形的二叉树状结构，并采用递归算法实现。这算法可适用于任意形状的凹或凸多边形，也适用于包含岛屿的多边形。此外，在考虑边界点高程的基础上，可充分顾及地形特征。该算法完全适用于长距离河流流域的三维面状表达。     

基于约束Delaunay三角网的线、面群目标分布边界计算

群组目标的分布边界在空间方向关系判断、相似度计算以及地图自动综合等领域有着重要的应用,但目前的分布边界计算主要是针对空间点群目标,鲜有涉及空间线、面群目标。在约束Delaunay三角网的基础上,利用动态阈值"剥皮"法实现线、面群目标的分布边界计算。方法得到的分布边界多边形符合人们的空间认知习惯,能够较好地描述线、面群目标的空间形态和分布范围。     

支持地图综合的面状目标约束Delaunay三角网剖分

针对多边形面状目标的综合问题,建立了二维空间中约束Ｄｅｌａｕｎａｙ三角网剖分结构,融入多边形的环、岛屿、边界、顶点的描述,通过形式化条件检索,在该结构上提取二维空间中各种感兴趣的由剖分三角形组成的区域,用于支持地图综合中邻近多边形的搜索、多边形弯曲部位的识别、冲突关系探测、多边形合并等操作。并对基于骨架线的图结构建立、分枝宽度计算等几何问题进行了详细讨论,指出了其在诸如双线河中轴化、街道中轴线网络模型建立、多边形合并中的邻近关系分析、面状目标注记自动定位领域的支持作用。     

An efficient solution for building polygonal objects

Polygonal object is a fundamental type of geometric data in vector GIS. The key step of cleaning topological relationship after data collection of polygonal layer is to build polygonal objects from digital arcs. The raw digital arcs may intersect with each other. The algorithm for building polygonal objects after the raw arcs have been split at all intersections is presented. The build-up of polygonal objects in this paper is designed to be implemented by two steps. The first step is to extract all the polygons needed for build-up of polygonal objects from arcs. The second step is to organize polygonal objects from these polygons. For the first step, a tracing algorithm is proposed. The algorithm merely extracts the polygons needed for the build-up of polygonal objects, which is a subset of all the possible polygons that can be induced from the arcs. For the second step, an algorithm based on a specially designed order of polygons is advanced. All the topological relationships among the polygons are sho     

克服双重约束的面目标位置聚类方法

面目标的聚集模式识别是空间聚类研究的重要方向之一,但因多边形几何信息和空间障碍阻隔的双重约束,目标的位置相似性难以快速而准确地计算。扩展点目标多尺度聚类方法,通过构建面目标的强度函数计算目标与邻近目标的位置聚集程度,提出了有效作用于双重约束下的面目标位置聚类法,并以判断相邻尺度下同一面目标类的强度函数阈值相等作为算法的收敛条件。经试验分析与比较发现,算法无须自定义参数,能够识别密度不均、任意形状分布,以及"桥"链接的面目标集群,同时能够准确判断障碍约束对面目标簇的阻隔和划分。     

基于滚球法的面要素聚合

在自动制图综合中,面要素聚合较为常用的方法是利用聚类方法将面要素聚类为若干个类簇,进而将每个类簇合并为更大的多边形图斑。针对地图制图领域的前沿研究课题——地图自动综合,该文提出了一种基于滚球法的面状要素聚合的新方法,通过实验阐述了该方法在居民地等面要素综合中的应用,并与传统的聚合算法进行了效率上的对比分析。该方法较传统的聚合方法效率上有很大提高,在大数据量聚合中有一定的应用前景,当选择合适的滚球半径进行综合时,有较理想的结果。     

A topology-preserving polygon rasterization algorithm

Conventional algorithms for polygon rasterization are typically designed to maintain non-topological characteristics. Consequently, topological relationships, such as the adjacency between polygons, may also be lost or altered, creating topological errors. This paper proposes a topology-preserving polygon rasterization algorithm to avoid topological errors. Four types of topological error may occur during polygon rasterization. The algorithm starts from an initial polygon rasterization and uses a set of preserving strategies to increase topological accuracy. The count of the four types of error measures the topological errors of the conversion. Topological accuracy is summarized as 1 minus the ratio of actual topological errors to the total number of possible error cases. When applied to a land-use dataset with a data volume of 128 MB, 127,836 polygons, and extending 1352 km², the algorithm achieves a topological accuracy of more than 99% when raster cell size is 30 m or smaller (100% for 5 and 10 m). The effects of cell size, polygon shape, and number of iterations on topological accuracy are also examined.     

Building footprint database improvement for 3D reconstruction: A split and merge approach and its evaluation

We present a general framework to improve a vectorial building footprint database consisting of a set of 2D polygons. The aim of this improvement is to make the database more proper to subsequent 3D building reconstruction at a large scale. Each polygon is split into several simple polygons guided by a digital elevation model (DEM). We say that this segmentation is vectorial as we produce segmentations that intrinsically have simple polygonal shapes, instead of doing a raster segmentation of the DEM within the polygon then trying to simplify it in a vectorization step. The method is based on a Mumford and Shah like energy functional characterizing the quality of the segmentation. We simplify the problem by imposing that the segmentation edges have directions present in the input polygon over which the DEM is defined. We evaluate the validity of the proposed method on a very large dataset and discuss its pros and cons based on this evaluation.     

Improving Representation of Land‐use Maps Derived from Object‐oriented Image Classification

Object‐oriented (OO) image analysis provides an efficient way to generate vector‐format land‐cover and land‐use maps from remotely sensed images. Such image‐derived vector maps, however, are generally presented with congested and twisted polygons with step‐like boundaries. They include unclassified polygons and polygons with geometric conflicts such as unreadable small areas and narrow corridors. The complex and poorly readable representations usually make such maps not comply well with the Gestalt principle of cartography. This article describes a framework designed to improve the representation by resolving these problematic polygons. It presents a polygon similarity model integrating semantic, geometric and spectral characteristics of the image‐derived polygons to eliminate small and unclassified polygons. In addition, an outward‐inward‐buffering approach is presented to resolve the narrow‐corridor conflicts of a polygon and improve its overall appearance. A case study demonstrates that the implementation of the framework reduces the number of the polygons by 32% and the length of the polygon boundaries by 20%. At the same time, it does not cause distinct changes the distribution of land‐use types (less than 0.05%) and the overall accuracy (decreased only 0.02%) as compared with the original image‐derived land‐use maps. We conclude that the presented framework and models effectively improve the overall representation of image‐derived maps without distinct changes in their semantic characteristics and accuracy.     

一种基于条件极值的建筑多边形直角化的方法

在地图综合中,许多建筑多边形化简的方法都是针对于直角多边形的,建筑多边形的直角化也是地图数据在进入GIS之前对数据完整性检验的必经过程.本文介绍了一种利用条件极值来计算直角地物中各点坐标改正数的方法.该方法成功用于大比例综合缩编软件GenTool,并获得了满意的效果.     

Optimizing multi-resolution segmentation scale using empirical methods: Exploring the sensitivity of the supervised discrepancy measure Euclidean distance 2 (ED2)

Multiresolution segmentation (MRS) has proven to be one of the most successful image segmentation algorithms in the geographic object-based image analysis (GEOBIA) framework. This algorithm is relatively complex and user-dependent; scale, shape, and compactness are the main parameters available to users for controlling the algorithm. Plurality of segmentation results is common because each parameter may take a range of values within its parameter space or different combinations of values among parameters. Finding optimal parameter values through a trial-and-error process is commonly practiced at the expense of time and labor, thus, several alternative supervised and unsupervised methods for supervised automatic parameter setting have been proposed and tested. In the case of supervised empirical assessments, discrepancy measures are employed for computing measures of dissimilarity between a reference polygon and an image object candidate. Evidently the reliability of the optimal-parameter prediction heavily relies on the sensitivity of the segmentation quality metric. The idea behind pursuing optimal parameter setting is that, for instance, a given scale setting provides image object candidates different from the other scale setting; thus, by design the supervised quality metric should capture this difference. In this exploratory study, we selected the Euclidean distance 2 (ED2) metric, a recently proposed supervised metric, whose main design goal is to optimize the geometrical discrepancy (potential segmentation error (PSE)) and arithmetic discrepancy between image objects and reference polygons (number-of segmentation ratio (NSR)) in two dimensional Euclidean space, as a candidate to investigate the validity and efficacy of empirical discrepancy measures for finding the optimal scale parameter setting of the MRS algorithm. We chose test image scenes from four different space-borne sensors with varying spatial resolutions and scene contents and systematically segmented them using the MRS algorithm at a series of parameter settings. The discriminative capacity of the ED2 metric across different scales groups was tested using non-parametric statistical methods. Our results showed that the ED2 metric significantly discriminates the quality of image object candidates at smaller scale values but it loses the sensitivity at larger scale values. This questions the meaningfulness of the ED2 metric in the MRS algorithm’s parameter optimization. Our contention is that the ED2 metric provides some notion of the optimal scale parameter at the expense of time. In this respect, especially in operational-level image processing, it is worth to re-think the trade-off between execution time of the processor-intensive MRS algorithm at series of parameter settings targeting a less-sensitive quality metric and an expert-lead trial-and-error approach.     

利用骨架线端点匹配进行面状要素渐变变换

面向空间数据连续地图综合问题,提出了一种基于骨架线端点匹配的面状要素渐变方法,通过在两个关键表达之间进行尺度内插,实时、动态地派生任意中间比例尺地图数据。首先,对面状要素在大小比例尺下的两重表达分别进行约束Delaunay三角网剖分并提取各自的骨架线特征;然后,使用最优子序双射优化技术对骨架端点进行匹配获得多边形边界上相对应的特征点序列;最后,在剖分边界的基础上进行分段常规线性内插,获得面状要素介于始末尺度之间的多尺度表达。实验结果表明,该算法充分顾及了空间数据弯曲结构特征,对于光滑边界面状要素的渐变变换具有良好的渐变效果,可用于空间数据的连续地图综合和多尺度表达。     

建筑物白模多边形的自动合并

建筑物白模多边形数据可广泛应用于许多领域,但在实际应用中,由于数据太过细致,且目前使用的建筑物白模多边形数据存在拓扑关系错误,不满足生产要求,这给地图综合中建筑物群的自动合并提出了新的要求.因此提出了一种基于约束性Delaunay三角网的建筑物白模多边形自动合并方法,在保持建筑物整体结构和视觉效果的前提下减少不必要的细...     

基于拓扑构建的多边形区域间运算的新方法

提出了一种新的直观的方法进行多边形区域之间的运算。首先将需要计算的多边形区域的边进行自动拓扑构建,利用多边形区域的边将平面划分为n个小多边形区域;然后生成这些多边形区域的内点,通过判断小多边形区域的内点是否在原始多边形区域内来确定小多边形区域是否选取;最后合并选取的小多边形即为所求。试验结果表明,该方法思路清晰、鲁棒性强,在GIS中得到了有效的运用。     

多边形自动生成的一种改进算法

本文提出了一种多边形自动生成的改进算法,对不参与组成多边形的弧段和结点进行分类处理,在搜索多边形之前,排除悬挂结点、悬挂弧段、假悬挂结点和假悬挂弧段的干扰,在搜索多边形的过程中,为弧段建立搜索标志,并对桥进行判断和排除,较好地解决了问题,提高了自动生成多边形的效率。     

制图综合中建筑物多边形的合并与化简

讨论了数字环境下顾及建筑物矩形几何特征的多边形自动综合算法,针对多边形之间的拓扑邻近与视觉邻近两种空间关系,提出了基于矢量和基于栅格的两种建筑物多边形合并方法。关于建筑物形状的化简,本文提出了矩形差分方法,并在此基础上建立了建筑物多边形化简的层次化途径。     

多边形形状简化及其质量评价

在保证多边形之间拓扑关系完整的基础上,分别使用垂距限值法和Douglas-Peucker算法对多边形形状进行了简化,同时从多边形常规参数以及相似度等方面对简化后多边形的质量进行了评价。实验结果表明Douglas-Peucker算法的简化效果较好。     

Proximity-based grouping of buildings in urban blocks: a comparison of four algorithms

Grouping of buildings based on proximity is a pre-processing step of urban pattern (structure) recognition for contextual cartographic generalization. This paper presents a comparison of grouping algorithms for polygonal buildings in urban blocks. Four clustering algorithms, Minimum Spanning Tree (MST), Density-Based Spatial Clustering Application with Noise (DBSCAN), CHAMELEON and Adaptive Spatial Clustering based on Delaunay Triangulation (ASCDT) are reviewed and analysed to detect building groups. The success of the algorithms is evaluated based on group distribution characteristics (i.e. distribution of the buildings in groups) with two methods: S_Dbw and newly proposed Cluster Assessment Circles. A proximity matrix of the nearest distances between the building polygons, and Delaunay triangulation of building vertices are created as an input for the algorithms. A topographic data-set at 1:25,000 scale is used for the experiments. Urban block polygons are created to constrain the clustering processes from topological aspect. Findings of the experiment demonstrate that DBSCAN and ASCDT are superior to CHAMELEON and MST. Among them, MST has exhibited the worst performance for finding meaningful building groups in urban blocks.