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

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

A general framework for error analysis in measurement-based GIS Part 1: The basic measurement-error model and related concepts

This is the first of a four-part series of papers which proposes a general framework for error analysis in measurement-based geographical information systems (MBGIS). The purpose of the series is to investigate the fundamental issues involved in measurement error (ME) analysis in MBGIS, and to provide a unified and effective treatment of errors and their propagation in various interrelated GIS and spatial operations. Part 1 deals with the formulation of the basic ME model together with the law of error propagation. Part 2 investigates the classic point-in-polygon problem under ME. Continuing to Part 3 is the analysis of ME in intersections and polygon overlays. In Part 4, error analyses in length and area measurements are made. In this present part, a simple but general model for ME in MBGIS is introduced. An approximate law of error propagation is then formulated. A simple, unified, and effective treatment of error bands for a line segment is made under the name of covariance-based error band. A new concept, called maximal allowable limit, which guarantees invariance in topology or geometric-property of a polygon under ME is also advanced. To handle errors in indirect measurements, a geodetic model for MBGIS is proposed and its error propagation problem is studied on the basis of the basic ME model as well as the approximate law of error propagation. Simulation experiments all substantiate the effectiveness of the proposed theoretical construct.This project was supported by the earmarked grant CUHK 4362/00H of the Hong Kong Research grants Council.     

Tile‐based polygon overlay of vector data in a virtual globe

The demand for analysis of large‐scale data has increased with increased access to spatial vector data. Polygon overlay of vector data in a virtual globe requires proprietary data structures and proprietary analysis algorithms. A vector data structure is designed for rapid polygon overlay in a virtual globe by recording the metadata of the triangles (TriMeta) that constitute polygons. A polygon overlay algorithm is proposed based on this data structure. The overlay of two complex GIS polygons is transformed into the intersection computation of their 3D triangular presentations. The intersection computation of two sets of triangles is reduced considerably by utilizing TriMeta to filter out the disjoint triangle pairs and rapidly identify the contained triangle. The new method improves the overlay efficiency in a virtual globe because the amount of computation required to calculate the intersections of two large polygons and drape the intersections onto a terrain surface is reduced.     

矢量GIS环境下多边形叠置中位置误差的传播分析

本文首先推导出多边形叠置中两条随机边相交后交点坐标及其方差的计算通式,然后讨论了多边形叠置后交点多边形几何特征的误差状态,并给出了交点多边形物理特征的估算解析表达式,最后以三角形和五边形随机叠置为例,说明了在ＧＩＳ环境下实现交点多边形误差状态评价的具体方法。     

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

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

基于三角网的"种子法"多边形生成

将传统上广泛使用的“种子法”和“矢量求交法”的思想相结合 ,提出了一种基于约束Delaunay三角网结构的多边形生成算法。详细描述了该方法的基本思想 ,在实验基础上分析了算法的特点。     

凹边形地标参照的主方向关系推理方法

空间推理是地球空间信息、人工智能、自然语言处理等相关领域的热点研究内容。主方向关系的表达与推理是空间推理的重要组成部分。针对空间方向关系矩阵对凹边形对象方向关系表达、推理的不足,研究依据目标对象与凹边形地标方向关系表达的不确定性,提出了凹边形地标参照的外部性主方向关系与内部性主方向关系推理方法。利用凹边形三等分仿射变换矩阵、自适应分割算法实现凹边形地标外部性、内部性参照对象表达;基于向量三角形法则与方向关系谓词,以方向关系的逻辑和、逻辑差合成代数运算推理2个地标、1个地标参照下目标对象与参照对象之间的主方向关系。通过实验与算例验证,证明凹边形地标参照下目标对象与参照对象的主方向关系推理可行性。     

利用约束D-TIN进行建筑物多边形凹部结构识别与渐进式化简

分析了位于建筑物多边形外侧的凹部结构特征及其类型,探讨了一种基于凹部层次结构的建筑物多边形渐进式化简方法,即以三角形为形状基元,用约束Delaunay三角化方法对建筑物多边形进行空间剖分,从凹部三角形树中提取三角形序列,通过匹配特征序列识别凹部的基本模式,以确定和实施相应的凹部化简方法,在此基础上迭代执行识别-化简过程,以实现对建筑物复杂凹部的渐进式化简。实验分析表明,该方法具有结构化和渐进综合的特点。     

基于全球离散网格框架的局部网格划分

从全球离散网格系统的应用需求出发,分析全球框架下建立局部网格的重要性,在此基础上提出全球离散网格系统下同构化的局部网格生成的基本思路,详细分析局部网格的复杂球面边界问题,从点与球面三角形的位置关系入手,讨论点与任意球面多边形的相对位置关系,研究基于球面任意多边形的边缘简化算法、判断点与球面任意多边形相互关系的算法、考虑跨面问题的网格区域裁减以及网格数据的层次生成算法.通过实验证明这些方法的效率和准确性.

Abstract：

Firstly, the paper analyzed the essentiality of generating partial grids based on the application and requirement of discrete global grid systems. And then, we brought forward the fundermental thought of generating partial grid which is under the discrete global grid frame, and discussed the detailed edge problems of partial highprecision grid. Started with the ubiety between a point and a spherical triangle, we discussed the ubiety between a point and a spherical random polygon, and then edge simplifying algorithm of spherical random polygon are studied, as well as co-relationship between points and spherical random polygon, grid district clipping based on spanning the developed surface and grid data hierarchical creating algorithm. In the end we prove exactness and efficiency of the algorithm through the experiments.     

基于遥感任务的凹多边形区域无人机航迹规划算法

针对遥感观测的需求与特点,提出一种基于遥感任务的凹多边形区域无人机 (UAV) 航迹规划算法,旨在保证UAV不相撞与区域全覆盖的前提下,总耗时更短. 根据遥感影像获取的特点,采用统一主飞行方向,定点拍摄进行UAV航迹规划. 通过航线分割点求取、多边形划分、UAV分配、碎片多边形合并与UAV再分配以及航点信息求取五个步骤,得到在选定主飞行方向的情况下UAV航迹的优化. 通过选取凹多边形及其凸包的边所在的方向分别为主方向,得到全局最优解. 实验结果表明:该算法能合理分配UAV并进行航迹规划,比传统方法更为高效、适用性更强.      

大数据量遥感分类图像的动态矢量化算法

针对大数据量遥感图像矢量化时间效率低和空间瓶颈问题,采用顶点提取过程中同时进行图斑矢量化的策略,提出一种适应大数据量遥感图像的动态矢量化算法。首先,统计图像中各图斑的顶点个数,将其作为图斑顶点集合能否构成封闭多边形的判定条件;然后,在顶点提取的过程中发现有能够成封闭多边形的图斑顶点集合,立即将其矢量化并释放其所占内存,图斑矢量化时直接将顶点构建成多边形无需生成中间弧段,并即时形成拓扑关系。实验表明,文中算法能快速高效地完成大数据量遥感图像矢量化,速度是ARCGIS（9.2版本）矢量化算法的3~4倍。     

A general framework for error analysis in measurement-based GIS Part 3: Error analysis in intersections and overlays

This is the third of a four-part series on the development of a general framework for error analysis in measurement-based geographic information systems (MBGIS). In this paper, we study the characteristics of error structures in intersections and polygon overlays. When locations of the endpoints of two line segments are in error, we analyze errors of the intersection point and obtain its error covariance matrix through the propagation of the error covariance matrices of the endpoints. An approximate law of error propagation for the intersection point is formulated within the MBGIS framework. From simulation experiments, it appears that both the relative positioning of two line segments and the error characteristics of the endpoints can affect the error characteristics of the intersection. Nevertheless, the approximate law of error propagation captures nicely the error characteristics under various situations. Based on the derived results, error analysis in polygon-on-polygon overlay operation is also performed. The relationship between the error covariance matrices of the original polygons and the overlaid polygons is approximately established.This project was supported by the earmarked grant CUHK 4362/00H of the Hong Kong Research grants Council.     

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

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

DEM 地形描述误差的概率分布特征研究

以黄土丘陵1:1万DEM为基础数据,通过稀疏抽点法获取不同格网点布设位置下的DEM,进而分析不同分辨率DEM中单个地面点和区域地形单元的Et概率分布特征。实验结果表明:对于任意格网分辨率DEM,无论是不同布设方案下的单个地面点,还是区域地形单元,其Et的概率密度均呈现正态分布特征。对于单个地面点,如果以其为中心的3×3DEM格网单元区域以凸地形为主,其Et概率密度呈现出右偏正态分布特征;如果以凹地形为主,则呈现左偏正态分布特征,其他区域则呈现标准正态分布特征。     

伪形心多边形形心距离计算方法

针对多边形形心距离计算过程中存在的形心位于多边形外的问题,该文提出伪形心的概念,通过三角剖分的方式,计算多边形边界到多边形形心距离最小的点,将形心合理地平移到边界上,进而计算多边形形心距离。针对伪形心存在于邻接边的特殊情况,又提出将形心平移到多边形主骨架线上的改进算法。该文提出的算法简单,易于实现,适用性强,进一步扩展了多边形形心距离计算的思路。     

Communications From Readers

The peak-pit-pass polygon line-shading procedure partitions any concave polygon into a series of triangles and trapezoids that are shaded independently. These convex subpolygons are identified by processing each vertex of the polygon outline in descending rank order. Alternative actions are initiated whenever a local maximum (peak), a local minimum (pit), or neither (pass) is encountered. Being relatively insensitive to the topology of the polygon and to the density of shade lines while minimizing storage and time requirements, this algorithm achieves a balance between efficiency and flexibility.     

Knowledge based reconstruction of building models from terrestrial laser scanning data

This paper presents an automatic method for reconstruction of building façade models from terrestrial laser scanning data. Important façade elements such as walls and roofs are distinguished as features. Knowledge about the features’ sizes, positions, orientations, and topology is then introduced to recognize these features in a segmented laser point cloud. An outline polygon of each feature is generated by least squares fitting, convex hull fitting or concave polygon fitting, according to the size of the feature. Knowledge is used again to hypothesise the occluded parts from the directly extracted feature polygons. Finally, a polyhedron building model is combined from extracted feature polygons and hypothesised parts. The reconstruction method is tested with two data sets containing various building shapes.     

A general framework for error analysis in measurement-based GIS Part 4: Error analysis in length and area measurements

This is the final of a series of four papers on the development of a general framework for error analysis in measurement-based geographic information systems (MBGIS). In this paper, we discuss the error analysis problems in length and area measurements under measurement error (ME) of the defining points. In line with the basic ME model constructed in Part 1 of this series, we formulate the ME models for length and area measurements. For length measurement and perimeter measurement, the approximate laws of error propagation are derived. For area measurement, the exact laws of error propagation are obtained under various conditions. An important result is that area measurement is distributed as a linear combination of independent non-central chi-square variables when the joint ME vectors of vertices coordinates are normal. In addition, we also give a necessary and sufficient condition under which the area measurement estimator is unbiased. As a comparison, the approximate law of error propagation in area measurement is also considered and its approximation is substantiated by numerical experiments.This project was supported by the earmarked grant CUHK 4362/00H of the Hong Kong Research grant Council.     

基于方向因子和方向边的多边形内外点判断算法

本文在概述已有多边形内外点判断算法的基础上,提出了方向因子和方向边的概念,并利用方向因子和方向边,设计了一种判断点在多边形内外的新算法。该方法首先找出点的方向边,再计算该点与其方向边组成的三角形的方向因子,然后利用计算的方向因子来判断点与多边形的位置关系,其可以有效地解决射线法中的临界位置问题。实验结果表明,该方法易于理解,计算简单,具有较高的可靠性、稳定性和执行效率。     

基于反向射线与顶点退化判断点在多边形内外的算法及应用

利用射线法判断点在多边形内外的方法简单易用,但是对于交点中含有顶点的情况,使用这种方法将产生奇异性,大大降低判断的准确性。鉴于这种情况,通过对已有的判断点在多边形内外算法的分析与研究,提出了基于反向射线和顶点退化处理相结合判断点在多边形内外的算法,并给出了具体的程序设计以及将该算法推广到了复杂多边形的情况。同时,将该算法应用于某市基础地理信息系统数据预编辑中,结果表明,判断准确率大大提高。