基于简单要素模型的多边形分割算法

多边形是GIS研究和应用中使用最频繁的几何对象,该文描述了基于简单要素模型的任意多边形分割算法。从计算几何出发,结合GIS空间数据的特点,将基于简单要素模型的多边形分割算法设计为:1)对多边形及分割线的边界排序,基于扫描线及外包矩形检测查找可能相交的线段,提高相交线段的搜索效率;2)计算交点生成结点信息(包括交点坐标、线号及交点的出入),并存储在独立的单向链表中;3)根据结点链表和原多边形坐标搜索结果多边形。该算法能够分割任意简单多边形(凹凸、曲线边界和带洞的多边形)以及有共享边的多边形。最后在MapGIS7.0平台上,实现了基于简单要素类的多边形分割功能。     

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

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

GIS中矢量多边形网格化问题研究

在实际的GIS空间分析过程中,为了更加简便快捷的实现某些特定的空间分析功能,常常需要将不规则的矢量多边形区域转化为规则的格网区域。该文介绍了矢量多边形网格化的四类算法：中心点归属法、面积占优法、重要性法和面积内插法。其中面积内插法又可分为面积权重内插法、基于表面模型的面积内插法和基于统计模型的面积内插法。同时介绍了各类算法的实现思想,并比较了其优劣及应用范围,认为基于表面模型的面积内插法是一种比较理想且极具发展前景的矢量多边形网格化方法。     

基于线性和岛屿约束的Delaunay三角网构建算法研究

针对基于线性和岛屿约束的Delaunay三角网构建算法的不足,从减少算法计算机实现步骤出发,研究改进了线段相交判断、首三角形确定等影响域多边形搜索相关算法;在分析当前存在的多边形三角剖分算法基础上,给出了存在重复点(悬边)的多边形三角剖分算法;在影响域多边形搜索阶段充分利用多边形间的拓扑关系信息,消除了岛屿约束内部三角形删除时需遍历三角形数据的不足.算法涵盖线性和岛屿约束的构建,综合性强,效率高且易于实现.     

基于辛普森面积的多边形凹凸性识别算法

多边形顶点的凹凸性是其重要的形状特征,常被应用于制图综合、模式识别等方面.该文利用多边形特有的面积属性,将辛普森面积计算公式引入多边形顶点的凹凸性识别算法中,通过计算多边形中待判断顶点与其相邻两顶点所构成三角形的辛普森面积与整个多边形的辛普森面积的符号异同来判断顶点凹凸性.经推算证明,该算法对于复杂多边形的顶点凹凸性识别同样有效.     

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

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

一种基于球面QTM格网的面要素边界跟踪填充算法

为实现四元三角网(Quaternary Triangular Mesh,QTM)对球面面状要素矢量数据的离散化及可视化,该文将基于栅格单元的"边界代数法"扩展到球面三角格网单元,提出了一种基于QTM格网的边界跟踪填充算法,主要内容包括:通过ETP投影实现球面QTM格网与平面三角格网的相互转换,建立矢量线角度与三角格元邻近搜索的对应关系;"边界跟踪"并记录边界格元进行分类处理;最终给出"边界跟踪"下两种不同的填充模式。实验表明,该算法实现了球面矢量多边形在QTM格网中的填充。     

一种基于空间对象的缓冲区分析算法

在传统缓冲区分析基本思想的基础上,提出基于空间对象缓冲区分析定义,区别在于邻域半径:前者为常量,后者为变量。设计实现基于空间对象缓冲区分析算法,该算法以空间对象为计算粒度,分为计算缓冲区边界点、生成缓冲区多边形、筛选缓冲区多边形内空间对象3个步骤,并从算法执行机理的角度对其做定性与定量评估。结果表明,该算法解决了传统缓冲区分析难以处理图层内以空间实体为分析粒度的问题,时间和空间复杂度亦优于传统缓冲区分析算法。     

一种快速等面积分割平面简单多边形的算法

针对平面简单多边形按相等面积划分问题,设计了一种顾及形态特征和面积精度的快速分割算法。首先计算出多边形的最小面积外包矩形(MABR),确定其短轴方向为分割方向;然后根据MABR的长边距离与分块数计算出长边上的距离等分点,根据这些点构建初始分割线,并利用第一条分割线对多边形进行粗略分割;根据分割出的左多边形面积与目标分块面积差值转换成分割线的平移距离,沿长轴方向平移分割线,分割多边形,不断迭代,进行精细分割,直到满足面积精度要求;最后对分割出的右多边形按上述方法继续分割,直至完成分块。实验结果表明,相对于现有的两种算法,该算法的分割精度提升了1～2个数量级,处理性能分别提升了4.27倍和7.35倍。     

GPU加速的多边形叠加分析

叠加分析是地理信息系统最重要的分析功能之一,对多边形图层进行叠加分析要花费大量时间。为此,将GPU用于多边形叠加分析过程中的MBR过滤及多边形剪裁两个阶段。对MBR过滤阶段,提出了基于GPU的通过直方图及并行前置和实现的MBR过滤算法。对多边形剪裁阶段,通过改进Weiler-Atherton算法,使用新的焦点插入方法和简化的出入点标记算法,并结合并行前置和算法,提出了基于GPU的多边形剪裁算法。对实现过程中可能出现的负载不均衡情况,给出了基于动态规划的负载均衡方法。通过对这些算法的应用,实现对过滤阶段及精炼阶段的加速。实验结果表明,基于GPU的MBR过滤方法相对CPU实现的加速比为3.8,而基于GPU的多边形剪裁的速度比CPU实现快3.4倍。整体上,与CPU实现相比,GPU加速的多边形叠加提供了3倍以上的加速比。     

3D tree modeling from incomplete point clouds via optimization and L1-MST

Reconstruction of 3D trees from incomplete point clouds is a challenging issue due to their large variety and natural geometric complexity. In this paper, we develop a novel method to effectively model trees from a single laser scan. First, coarse tree skeletons are extracted by utilizing the L₁-median skeleton to compute the dominant direction of each point and the local point density of the point cloud. Then we propose a data completion scheme that guides the compensation for missing data. It is an iterative optimization process based on the dominant direction of each point and local point density. Finally, we present a L₁-minimum spanning tree (MST) algorithm to refine tree skeletons from the optimized point cloud, which integrates the advantages of both L₁-median skeleton and MST algorithms. The proposed method has been validated on various point clouds captured from single laser scans. The experiment results demonstrate the effectiveness and robustness of our method for coping with complex shapes of branching structures and occlusions.     

基于机载激光点云数据的电力线自动提取算法

设计并开发了一种从机载激光扫描的三维点云数据中自动提取电力线的算法,采用局部高程分布直方图模式分类滤波、Hough特征空间中全局方向特征优先的线特征提取、悬挂点位置数学推算和局部分段多项式拟合的方法,有效解决了电力线提取过程中电力线点云与电塔点云的自动分类、电力线平面位置提取、电力线悬挂点提取、电力线拟合问题。最后通过实际的工程数据验证了该算法的实用性。     

A cell-based algorithm for evaluating directional distances in GIS

Directional distance is commonly used in geographical information systems as a measure of openness. In previous works, the sweep line method and the interval tree method have been employed to evaluate the directional distances on vector maps. Both methods require rotating original maps and study points in every direction of interest. In this article, we propose a cell-based algorithm that pre-processes a map only once; that is, it subdivides the map into a group of uniform-sized cells and records each borderline of the map into the cells traversed by its corresponding line segment. Based on the pre-processing result, the neighbouring borderlines of a study point can be directly obtained through the neighbouring cells of the point, and the borderlines in a definite direction can be simply acquired through the cells traversed by the half line as well. As a result, the processing step does not need to enumerate all the borderlines of the map when determining whether a point is on a borderline or finding the nearest intersection between a half line and the borderlines. Furthermore, we implement the algorithm for determining fetch length in coastal environment. Once the pre-processing is done, the algorithm can work in a complex archipelago environment such as to calculate the fetch lengths in multiple directions, to determine the inclusion property of a point, and to deal with the singularity of a study point on a borderline.     

Characterisation and generalisation of cartographic lines using Delaunay triangulation

A method is presented for generalising cartographic lines using an approach based on determination of their structure. Constrained Delaunay triangulation is used to construct a skeleton of the space surrounding the lines and hence represent line features in terms of skeleton branches. Several statistical measures are used to characterise the triangulation branches. The measures enable selective generalisation of different types of line feature, leading to the possibility of user-specification of the style of generalisation. In our implementation of the approach, the triangulation is updated dynamically to allow both sides of multiple lines to be processed, while guaranteeing topological consistency between the resulting generalised lines.     

基于无人机的胡杨(Populus euphratica)结构参数获取技术研究

快速准确获取森林结构参数具有重要的科学意义。通过使用大疆精灵4 Pro无人机通过倾斜摄影测量和正射摄影测量方式获取塔里木河下游胡杨林样地的冠层高度模型,提出一种自适应窗口最大值算法来分析处理,获取了研究区胡杨(Populus euphratica)的树高、冠幅和株数等结构参数。最后,使用地面实测数据对以上结构数据进行精度评价。结果表明:(1)自适应窗口最大值算法计算效果优于传统的固定窗口最大值算法。(2)倾斜摄影测量方式获取的树高、冠幅和株数精度均优于正射摄影测量方式。(3)倾斜摄影测量获取的结构数据与实测值比较,树高、冠幅和株数R2分别为0.9002,0.8403和0.9405,均方根误差分别是0.4457、0.6815和4.2500,证明使用消费级无人机可以有效获取单木尺度森林结构参数。     

基于Hilbert曲线层次分解的空间数据划分方法

针对现有空间数据划分方法普遍存在的不考虑空间对象自身大小和相邻对象空间关系对数据划分的影响等问题,提出一种基于Hilbert空间填充曲线层次分解的空间数据划分方法。该方法使用Hilbert曲线保持划分后空间数据之间的邻近性,利用少数子网格的层次分解避免对整个空间范围的密集划分,减少空间对象的Hilbert编码计算和排序时间;通过计算划分区域平均数据量和子网格内空间对象大小,确定合适的层次分解参数,实现各划分区域内空间数据量均衡。实验表明,该方法提高了空间数据的划分效率,能够保持划分后空间数据之间的邻近性和各个分区数据量的平衡。     

武汉都市圈经济联系的空间结构

都市圈空间结构是城市体系中最综合、最富于变化的热点部分。基于武汉都市圈近年来的统计资料,构建经济联系强度模型,定量分析武汉都市圈空间竞争与范围的动态性特征:中心城市对外经济联系存在主要方向,具有时间惯性,空间极化明显;地域空间上经济联系作用强度距离衰减,形成圈层结构分异。从点、线、面组合关系角度,构建节点中心性、通道网络性、范围系统性指标,定量揭示出武汉都市圈经济联系的空间结构等级层次性特征:中心城市中心性等级差异明显,空间分布不均,与交通地理区位紧密相关;主要通道与侍服能力也存在等级层次性,明显形成两城际交通走廊;中心城市腹地范围与自身外向经济联系强度密切相关,受自然地理、行政区划影响明显。     

Enabling point pattern analysis on spatial big data using cloud computing: optimizing and accelerating Ripley’s K function

Performing point pattern analysis using Ripley’s K function on point events of large size is computationally intensive as it involves massive point-wise comparisons, time-consuming edge effect correction weights calculation, and a large number of simulations. This article presented two strategies to optimize the algorithm for point pattern analysis using Ripley’s K function and utilized cloud computing to further accelerate the optimized algorithm. The first optimization sorted the points on their x and y coordinates and thus narrowed the scope of searching for neighboring points down to a rectangular area around each point in estimating K function. Using the actual study area in computing edge effect correction weights is essential to estimate an unbiased K function, but is very computationally intensive if the study area is of complex shape. The second optimization reused the previously computed weights to avoid repeating expensive weights calculation. The optimized algorithm was then parallelized using Open Multi-Processing (OpenMP) and hybrid Message Passing Interface (MPI)/OpenMP on the cloud computing platform. Performance testing showed that the optimizations effectively accelerated point pattern analysis using K function by a factor of 8 using both the sequential version and the OpenMP-parallel version of the optimized algorithm. While the OpenMP-based parallelization achieved good scalability with respect to the number of CPU cores utilized and the problem size, the hybrid MPI/OpenMP-based parallelization significantly shortened the time for estimating K function and performing simulations by utilizing computing resources on multiple computing nodes. Computational challenge imposed by point pattern analysis tasks on point events of large size involving a large number of simulations can be addressed by utilizing elastic, distributed cloud resources.     

地图矢量数据拓扑关系生成算法

拓扑关系的建立是地图矢量数据管理和更新的重要内容。在综合多种典型拓扑算法优点的基础上,详细描述了拓扑关系生成算法的主要过程,并在线要素互相交断链、结点匹配和特殊情况处理等方面对算法进行了改进。最后以1∶25万济宁市地形图数据进行了实验,结果表明该算法在效率方面优于传统算法。     

不同水分胁迫下几种春小麦种子根形态结构的研究

实验采用快速冷冻切片法及显微摄像系统观察法对甘肃陇中地区6个品种春小麦在不同水分状况下的种子根进行了形态结构研究。结果表明,在不同程度水分胁迫下的同一品种春小麦,种子根后生木质部导管(中央大导管)直径有显著的差异,但这种变化趋势并不是简单的线性关系。随着水分胁迫的增大,不同品种春小麦种子根中央大导管的直径有不同的变化趋势。不同品种春小麦在不同程度的水分胁迫下,随着胁迫的增大,各品种中央大导管直径的变化都逐渐趋于同一区域,这一区域很可能是春小麦在形态结构上适应水分亏缺在导管直径上表现出的最佳直径范围。