Spatial Topology and its Structural Analysis based on the Concept of Simplicial Complex

This paper introduces a model that identifies spatial relationships for structural analysis based on the concept of simplicial complex. The spatial relationships are identified through overlapping two map layers, namely a primary layer and a contextual layer. The identified spatial relationships are represented as a simplical complex, in which simplices and vertices, respectively, represent two layers of objects. The model relies on the simplical complex for structural representation and analysis. To quantify structural properties of individual primary objects (or equivalently simplices), and the simplicial complex as a whole, we define a set of centrality measures by considering multidimensional chains of connectivity, i.e. the number of contextual objects shared by a pair of primary objects. With the model, the interaction and relationships with a geographic system are modeled from both local and global perspectives. The structural properties and modeling capabilities are illustrated by a simple example and a case study applied to the structural analysis of an urban system.     

Polygonal Clustering Analysis Using Multilevel Graph‐Partition

Existing methods of spatial data clustering have focused on point data, whose similarity can be easily defined. Due to the complex shapes and alignments of polygons, the similarity between non‐overlapping polygons is important to cluster polygons. This study attempts to present an efficient method to discover clustering patterns of polygons by incorporating spatial cognition principles and multilevel graph partition. Based on spatial cognition on spatial similarity of polygons, four new similarity criteria (i.e. the distance, connectivity, size and shape) are developed to measure the similarity between polygons, and used to visually distinguish those polygons belonging to the same clusters from those to different clusters. The clustering method with multilevel graph‐partition first coarsens the graph of polygons at multiple levels, using the four defined similarities to find clusters with maximum similarity among polygons in the same clusters, then refines the obtained clusters by keeping minimum similarity between different clusters. The presented method is a general algorithm for discovering clustering patterns of polygons and can satisfy various demands by changing the weights of distance, connectivity, size and shape in spatial similarity. The presented method is tested by clustering residential areas and buildings, and the results demonstrate its usefulness and universality.     

GIS中缓冲区自动生成问题研究

缓冲区分析(Buffer Analysis)是地理信息系统(GIS)重要的空间分析功能之一。地理信息系统中的缓冲区生成分点、线、面三种,其中线状目标缓冲区生成是关键和基础。本文将线状目标缓冲区的生成分为每个线状目标缓冲区多边形独立生成过程和所有线状目标缓冲区多边形重叠合并过程两个阶段,并分别给出了相应的矢量算法。     

An open source high-performance solution to extract surface water drainage networks from diverse terrain conditions

This paper describes a workflow for automating the extraction of elevation-derived stream lines using open source tools with parallel computing support and testing the effectiveness of procedures in various terrain conditions within the conterminous United States. Drainage networks are extracted from the US Geological Survey 1/3 arc-second 3D Elevation Program elevation data having a nominal cell size of 10 m. This research demonstrates the utility of open source tools with parallel computing support for extracting connected drainage network patterns and handling depressions in 30 subbasins distributed across humid, dry, and transitional climate regions and in terrain conditions exhibiting a range of slopes. Special attention is given to low-slope terrain, where network connectivity is preserved by generating synthetic stream channels through lake and waterbody polygons. Conflation analysis compares the extracted streams with a 1:24,000-scale National Hydrography Dataset flowline network and shows that similarities are greatest for second- and higher-order tributaries.     

Partial polygon pruning of hydrographic features in automated generalization

This article demonstrates a working method to automatically detect and prune portions of waterbody polygons to support creation of a multi‐scale hydrographic database. Water features are sensitive to scale change, therefore multiple representations are required to maintain visual and geographic logic at smaller scales. Partial pruning of polygonal features – such as long, sinuous reservoir arms, stream channels too narrow at the target scale, and islands that begin to coalesce – entails concurrent management of the length and width of polygonal features as well as integrating pruned polygons with other generalized point and linear hydrographic features to maintain stream network connectivity. The implementation follows data representation standards developed by the US Geological Survey (USGS) for the National Hydrography Dataset (NHD). Portions of polygonal rivers, streams, and canals are automatically characterized for width, length, and connectivity. This article describes an algorithm for automatic detection and subsequent processing, and shows results for a sample of NHD subbasins in different landscape conditions in the US.     

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.     

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

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

矢量居民地多边形多级图划分聚类方法

针对复杂居民地多边形的信息挖掘问题,提出了一种多级图划分聚类分析方法,构造居民地多边形的图模型,并通过对图模型进行粗化匹配与重构、初始化分和细化得到聚类结果.首先构建研究区域内居民地建筑物的Delaunay三角网,生成包含研究对象之间的邻接信息图;然后结合空间认知准则和人类认知的特点,采用形状狭长度、面积比、凹凸性、距...     

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

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

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

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

空间关系中两相邻实体间最近距离算法研究

空间距离关系是最基本、最重要的一类空间关系。通过先考虑二维空间中两任意实体之间不同的相对位置关系,再利用构建Delaunay三角网寻找两者的邻近区域,从而计算出两者之间的最近距离。本文还提出了基于约束圆寻找并计算任意两个实体多边形之间的最近距离方法,并给出了约束圆的特征。这种方法适用于不用区分实体多边形的形状与位置的各种情况。     

Number of Polygons Generated by Map Overlay: The Case of Convex Polygons

This paper analyzes the number of polygons generated by map overlay. Overlay of maps yields a number of small polygons, and often causes problems in computation, handling, and storage of derived polygons. One method to deal with these problems is to estimate the number of derived polygons before executing overlay operation. To this end, a stochastic model is proposed by which the expected number of derived polygons is calculated. The results are summarized as follows: (1) the number of polygons generated by map overlay depends on the number of original polygons and their perimeters; (2) the number of derived polygons increases with the perimeters of original polygons; (3) McAlpine and Cook's (1971) earlier method underestimated the number of derived polygons; and (4) the number of polygons generated by the overlay of maps having the same lattice system is proportional to the square of the number of overlaid maps and the number of polygons on the map, and inversely proportional to the area-perimeter ratio of the unit cell.     

复合地块的拓扑类型计算与应用

按照简单地块的8种拓扑关系分类定义,计算简单地块的拓扑关系。将复合地块的外边界与空洞分离为m＋1个（m是空洞数）简单多边形,分别计算外边界之间、空洞之间、外边界与空洞之间的拓扑关系,并且按照不同的拓扑关系组合,计算复合地块的8种拓扑关系。     

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.     

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     

基于ArcEngine的林地图斑拓扑查错研究

针对森林资源二类调查内业流程,利用空间拓扑分析,解决图斑面属性赋值的难题,并且分析其一一对应关系,记录查错信息。在VB编程环境下,采用ArcEngine组件库,提出林地图斑拓扑查错算法流程,按照空间包含关系,将属性点记录的属性信息一一赋值到满足条件的图斑面内,自动获取包含属性信息的林地图斑面数据。     

曲边多边形中轴提取的新方法

针对现有多边形中轴提取方法在处理复杂图形和特殊图形上有较大困难的不足以及中轴连通性和位置准确性难以保证等问题,提出了一种曲边多边形中轴提取的新方法。首先在简单多边形的基础上进行拓展,提出曲边多边形的概念,并相应地定义了曲边多边形的中轴,然后在栅格距离变换的基础上引申出最近边缘点集距离均值变换,最后结合曲边多边形中轴点的特征和距离变换的原理制定出高效中轴点判定规则,利用种子点生长判别法提取曲边多边形的中轴,并给出具体实现步骤和流程。通过多组不同类型多边形及道路网与河网的实例验证,新方法不仅能适用于各类多边形,且能较好地抑制图形边界噪声的干扰,提取出具有良好的光滑性、准确性和连通性的多边形中轴,弥补了传统方法的不足。     

面向对象的形态学建筑物指数及其高分辨率遥感影像建筑物提取应用

高分辨率遥感影像建筑物提取是摄影测量与遥感领域的一个热门研究主题。本文综合利用影像分割、基于图的数学形态学top-hat重建技术,提出了面向对象的形态学建筑物指数OBMBI,并将其应用于高分辨率遥感影像建筑物提取。首先,建立像素-对象-图节点的双向映射关系;然后,基于图的白top-hat重建和上述映射关系来构建OBMBI图像;接着,对该OBMBI图像二值化、矢量化以获取建筑物多边形;最后,对结果进行后处理优化。使用一景航空、一景卫星全色影像对本文方法和PanTex方法进行性能测试。试验表明,本文方法的建筑物提取精度显著的优于PanTex方法。其中,本文方法平均比PanTex方法的正确率高9.49%、完整率高11.26%、质量高14.11%。     

基于层次性邻近分析的农用地分等数据库综合

以农用地分等数据库综合为例,提出了图斑归并同时顾及几何距离和多种专题属性的层次性邻近分析方法,及基于层次性邻近分析的多边形聚合和融合方法,并以实例验证了其有效性.     

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

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