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

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

平面点集凸壳的一种快速算法

提出一种计算平面点集凸壳的快速算法———八方向极值快速凸壳算法。该算法首先对平面点集进行一次扫描,从而快速查找到东、南、西、北、东南、西南、东北、西北8个方向上的极值点,构造出一个更接近凸壳的初始凸壳,从而在后续的点集扫描中可以排除更多的内点,使该算法计算效率更高。该算法的空间复杂度为O(N);其时间复杂度虽然无法突破最坏情况下O(NlogN)的理论下限,但其期望时间复杂度已达到线性水平,并且可以容易地扩展到三维和高维空间。     

一种构建任意发生元Voronoi图的实用算法

针对GIS中线状、面状等复杂形态地理要素,提出一种构建任意发生元Voronoi图的实用算法.主要步骤包括:将复杂发生元离散为点集;对点集采用扫描线算法构建Voronoi图,构建过程中对所生成的Voronoi多边形以其发生点所在要素的序号赋属性值;根据拟定的规则进行Voronoi多边形的合并,得到面向复杂发生元的广义Voronoi多边形,每个复杂发生元有且仅有一个Voronoi多边形与之对应.论述了算法实现的关键过程,并结合实例验证了该方法的可行性,算法的执行效率相对较高.     

面向离散点的空间权重矩阵生成算法与实证研究

采用阈值法和k-近邻法度量空间上离散点间的空间邻接关系,针对不同的距离计算方式(欧式距离和曼哈顿距离)设计了面向离散点的空间权重矩阵生成算法,使用C#语言在计算机上实现。用该算法对收集的8 367个常州市地价样点构建了不同土地用途地价样点的空间权重矩阵,并计算出分用途的常州市城市地价空间自相关指数。     

一种基于拓扑信息的多边形数据自动生成算法

在GIS的众多应用中,多边形数据的自动生成和多边形数据拓扑关系的构建与维护都是一种高频率的操作。该文在分析和总结已有多边形数据自动生成算法和拓扑关系生成算法基础上,提出了一种基于拓扑信息的多边形数据自动生成算法(PG-TI)。介绍了该算法的数据结构以及弧段邻接关系确定、多边形搜索和拓扑关系确定3个核心过程,重点探讨了使用多边形搜索过程中建立的拓扑信息来提升拓扑关系确定过程性能,在此基础上与传统算法和ArcGIS中对应算法的时间复杂度进行了对比分析和验证。     

基于点密度分析与自适应差异检测的点群要素制图综合算法

针对点群要素制图综合的自动选取问题,提出一种基于点密度分析与自适应差异检测的点群要素制图综合算法。该算法首先利用核密度估计法对原始点群进行点密度分析,选取凸包最外侧点和重要性等级较高的点分析其点密度,进而对比两次点密度分析结果的相对密度差异,并找出相对密度差异最大的点加入选中点群中;然后重新对选中点群进行点密度分析,直到选中点数满足制图综合要求。将该算法用于实例点群数据中进行了验证,结果表明,该算法能最大限度地保持点群的分布特征和密度对比关系,并且较为简单、灵活。     

非均质栅格Voronoi图生成方法研究

提出一个非均质栅格Voronoi图的生成方法.假定在Voronoi领域扩张中,经过每个栅格的距离权值不相等.由于非均质栅格Voronoi图生成复杂,提出了一种基于A*启发式空间搜索确定每个栅格的归属来产生Voronoi区域的方法.讨论了非均质栅格Voronoi图的基本定义、启发式函数确定、具体生成方法等.利用C#语言实现了所提出的方法,并分析了该方法的时间复杂度.但该方法仅适合于简单点发生元情况,在面向复杂发生元的情况下,需进一步研究更有效的方法.     

基于MPI的最小费用流网络单纯形并行算法设计与实验

网络最小费用流算法常用来解决资源流最优分配问题,传统的串行算法因时间复杂度高而不能满足大规模网络对计算效率的要求。该文用时间复杂度低的网络单纯形算法(NSA)的并行化求解大规模网络的最小费用流问题。通过分析NSA的可并行性,使用MPI分布式并行技术,设计了NSA并行算法;分析了3种常用流网络的拓扑结构特征及其与地理网络的关系;在并行环境下对计算效率进行实验测试,结果表明该算法具有显著的加速效果,峰值可达5.4。NSA并行算法应用面宽,可为区域及全国性大规模网络流资源分配方案的快速制定与政务决策提供有力支持。     

基于钻孔点集Voronoi 图的矿产储量新算法

该文在分析平面点集Voronoi图特性及其生成算法的基础上,针对传统矿产储量计算方法的不足,提出了一种新的方法。该法以钻孔平面点集的Voronoi图为基础,利用Voronoi多边形的势力范围特性,实现了任意区域内矿床体积与矿产储量的计算。并给出了以Delphi编程实现的系统界面与计算实例,讨论了基于钻孔三维点集的Voronoi体进行矿产品位与经济可采性分析的前景。     

基于GIS的高质量约束Delaunay三角网格剖分

在分析现有非结构化网格剖分算法的基础上,提出了一种GIS支持下的改进分治算法实现约束Delaunay三角网格剖分.该方法利用了GIS的空间拓扑关系对算法输入数据进行预处理,基于三角形的统一数据结构实现了网格细化,对输出剖分网格进行准确的拓扑和约束条件的检查,并基于推进阵面算法思想,结合空间邻近拓扑关系实现了三角剖分节点和网格的重新编号,方便了实际问题中开边界条件的赋值,提高了计算效率.实例应用表明,该方法大大简化了数值模型非结构化网格剖分的前处理过程,集成了几种综合算法的优点,在保证原分治算法时间复杂度的基础上,提高了约束条件下Delaunay三角网格生成的质量.     

平面点集凸壳的一个性质

该文揭示了平面点集凸壳的一个性质,即如果一个子凸壳包含东、西、南、北4个方向上的极值点,则其任一条子凸壳边的外点必在该边所确定的外直角三角形中,并对该性质进行了数学证明。在此基础上,利用该性质对快速凸壳算法进行了改进,达到了良好的加速效果。     

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

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

基于凸壳原理的杭州城市扩展形态演化分析

在城市化快速推进的背景下,探索凸壳原理在城市扩展形态识别中的应用价值,并借此分析杭州市主城区1985~2010年间城市扩展形态演化规律及其机理,以期为控制城市扩展形态,指导未来城市土地开发活动提供借鉴。研究发现,凸壳原理在城市扩展形态识别上简单而明确,通过确定已有城市建设用地的凸壳,将城市所有可开发用地明确区分为凸壳内用地和凸壳外用地2类,为采取差别化的空间管理政策提供依据。构建了基于凸壳原理的城市扩展形态计算机识别方法,有利于在城市扩展模拟中实现城市扩展形态影响因素的定量化表达。1996年之前,杭州市建设用地和凸壳面积增长缓慢,城市形态相对紧凑;1996年之后,建设用地快速增长,城市不均衡扩展加剧,凸壳面积陡增,城市形态紧凑程度下降。总体来看杭州市城市扩展类型属于外延型,随着凸壳面积的增加,城市填充潜力随之增强,为促进杭州市城市紧凑化发展,应该严格控制凸壳外的城市土地开发。沿主干道的城市开发是城市形态外延式发展的主要因素,已有建设用地周边以及城市内部次要道路沿线的城市开发,以及城市中心的集聚作用和规划对城市开发的控制是城市形态填充式发展的主要因素,而郊区化发展和“东扩西进”等城市空间发展政策促使特定时期城市外延式发展。     

A comparison of geometric approaches to assessing spatial similarity for GIR

This research compares the geographic information retrieval (GIR) performance of a set of logistic regression models with those of five non‐probabilistic methods that compute a spatial similarity score for a query–document pair. All methods are applied to a test collection of queries and documents indexed spatially by two convex conservative geometric approximations: the minimum bounding box (MBB) and the convex hull. In the comparison, the tested logistic regression models outperform, in terms of standard information retrieval recall and precision measures, all of the non‐probabilistic methods. The retrieval performance achieved by the logistic regression models on MBB approximations is similar to that achieved by the use of the non‐probabilistic methods on convex hulls. Although these results are valid only for the test collection used in this study, they suggest that a logistic regression approach to GIR provides an alternative to the use of higher‐quality geometric representations that are more difficult to obtain, implement, and process. Additionally, this research demonstrates the ability of a probabilistic approach to effectively incorporate information about geographic context in the spatial ranking process.     

凸壳原理用于城市用地空间扩展类型识别

针对目前尚缺乏定量方法确定城市用地扩展类型的问题,首次提出了利用计算几何中凸壳原理识别城市用地扩展类型的新方法,阐述了该方法实现步骤和判别标准,凸壳方法可以区分城市用地扩展的两种类型,即填充类型和延伸类型。基于国家资源环境数据库,应用研究的结果表明,从1990年到2000年,安徽省城市用地扩展类型以填充类型为主,而用地扩展的结果导致城市形态的变化,这一时期安徽省城市轮廓平面形态逐渐趋于紧凑。     

Object-based spatial cluster analysis of urban landscape pattern using nighttime light satellite images: a case study of China

Previous studies have demonstrated urban built-up areas can be derived from nighttime light satellite (DMSP-OLS) images at the national or continent scale. This paper presents a novel object-based method for detecting and characterizing urban spatial clusters from nighttime light satellite images automatically. First, urban built-up areas, derived from the regionally adaptive thresholding of DMSP-OLS nighttime light data, are represented as discrete urban objects. These urban objects are treated as basic spatial units and quantified in terms of geometric and shape attributes and their spatial relationships. Next, a spatial cluster analysis is applied to these basic urban objects to form a higher level of spatial units – urban spatial clusters. The Minimum Spanning Tree (MST) is used to represent spatial proximity relationships among urban objects. An algorithm based on competing propagation of objects is proposed to construct the MST of urban objects. Unlike previous studies, the distance between urban objects (i.e., the boundaries of urban built-up areas) is adopted to quantify the edge weight in MST. A Gestalt Theory-based method is employed to partition the MST of urban objects into urban spatial clusters. The derived urban spatial clusters are geographically delineated through mathematical morphology operation and construction of minimum convex hull. A series of landscape ecologic and statistical attributes are defined and calculated to characterize these clusters. Our method has been successfully applied to the analysis of urban landscape of China at the national level, and a series of urban clusters have been delimited and quantified.     

An efficient method for single-facility location and path-connecting problems in a cell map

This article presents an efficient method for simultaneously finding both the Weber cell and optimal connective paths in a grid. As numerous barriers of arbitrary shape and weighted regions are distributed in the cell map of this research, the problem scenario is similar to working out a real-life facility location selection and path-routing problems in a geographical map. In this study, the Weber problem of finding a single-facility location from an accumulation cost table is generated by a grid wave propagation method (higher-geometry maze router). After finding the Weber point (cell), optimal connective paths with minimum total weighted cost are backtracked between the Weber location cell and the demand cells. This new computation algorithm with linear time and space complexity can be integrated as a spatial analytical function within GIS.     

流域径流离散处理和提取算法研究

通过对流域进行离散处理,从集合论角度出发,将流域看成点的集合,对流域进行离散化处理,在其上对流域源点、交汇点、出口点、单径流及复合径流各流域要素进行约束和定义,提出并实现了算法。该算法基于流域水文模拟方法,较好地解决了流域出口点和环流判别问题,使追踪出的径流更符合实际,具有简单、高效、实用的特点。根据算法设计开发了软件系统,并且应用到黄土丘陵沟壑区小流域分布式水文和侵蚀预报模型中,取得了较好的模拟效果。