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.     

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

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

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.     

改进的边标志栅格化算法

矢量多边形的栅格化算法是地理信息系统的基础算法之一。本文通过分析比较,认为边标志算法于众多栅格化算法中最为适合地理信息系统,并通过简化边界标志过程进行了改进,使得处理流程更为简单清晰,实现更为方便,算法更为精确有效。该改进算法使用统一的相加方法进行边界标志,无需对特殊顶点、尖锐多边形、带岛多边形等进行判断和边界转换,便可一次性正确标志,且无需顾及多边形边的存储顺序,更加适合地理信息系统矢量多边形的数据结构。     

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

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

基于单调链和STR树的简单要素模型多边形叠置分析算法

针对简单要素类叠置分析的特点,利用STR(sort-tile-recursive)树索引改进算法能够将尽量多的多边形节点存储在STR树的叶节点中,减少在空间数据库中检索多边形时的磁盘读取次数。算法对多边形边界进行关于坐标轴的单调链分割,并在多边形求交过程中引入平面图的概念,利用平面图元素与各个多边形的拓扑关系来组织叠加后的多边形。该算法能有效减少求交点的时间,在线段求交中加入对连续出入点特殊数据的处理。同时该算法使用单调链减少多边形求交过程的比较次数,与其他使用双链表或单链表的算法相比具有占用空间少及处理速度快的特点。     

基于特征边重构的建筑物化简方法

针对轮廓模糊建筑物多边形的化简问题,提出一种基于特征边重构的建筑物化简方法。该方法定义了建筑物的主方向和控制其整体结构的特征边,以保持建筑物的规则形态。首先利用统计加权方法计算建筑物的主方向,基于主方向对建筑物执行直角化操作。然后按照特征边的定义检测直角化建筑物的特征边,将特征边组合并抽象出几种局部结构,建立重组规则。最后通过判别特征边组合的空间关系,选择合适的结构重组规则来化简建筑物。结合真实数据进行多组试验,结果表明该方法有效还原了建筑物的直角特征,面积和形状保持良好,适用性强。     

论多边形中轴问题和算法

比较了当前国内外GIS中和计算几何中关于多边形中轴的定义,讨论了它们的主要特点,指出多边形中轴应是到两个以上边距离相等点的轨迹,并据此分析了相应的各种算法和实际应用场合,提出了理论上较为严密、能够广泛满足实际应用需要的几何方法———点对序列法和地图代数多边形中轴法。     

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

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

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

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

Cartographic Design Matters – A Comparison of Thematic Polygon Design

The number of web services providing cartographic data is increasing. A main challenge is to enable a user to combine these services, not only from a technical perspective, but also from a cartographic one. One common use case for these services is to create mashups based on thematic polygons on top of background maps. In this study we compare four cartographic designs of thematic polygons: only boundaries, transparencies, hatches and icons. The aim of the comparison is to investigate whether the designs are good for identifying the extent of the polygons and if the design disturbs the reading of the background map. The comparison is based on an eye-tracking study, where 24 participants performed polygon identification tasks as well as background search tasks. The study revealed that hatches were more efficient than the other designs for polygon identification. Hatches had significantly shorter total fixation times as well as scanpath lengths, possibly since the participants were able to identify the extent of the polygon solely based on the interior (i.e. the hatches), while for the other designs the participants were extensively reliant on the boundaries. However, the results also indicate that the hatches design disturbs the reading of the background map more than the other designs; hatches also appear visually unpleasant for many users. Since each design had its strengths and weaknesses, we recommend producers of services for thematic data to provide several designs so users can select an appropriate design for their own use cases.     

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.     

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.     

道路网络示意图的多边形生长算法

道路网络示意图是实体网络的抽象表示,因其更加符合人的认知习惯,在地图服务与地图制图领域已得到初步应用。以路径为单位的网络示意图自动生成算法只顾及节点与线段的局部布置,且较难以维护网络拓扑一致性。本文以闭合多边形(网眼)为基本单位,利用网眼的独立性与邻接性,提出了多边形生长算法,核心思想是将道路网络分类为闭合多边形与非闭合线段,以闭合多边形提取、映射、优化为主线,辅助组合非闭合线段。算例分析验证,本算法在网络均衡分布及拓扑一致性方面具有优势。     

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

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

GIS中多边形图拓扑信息生成的数学基础

本文从ＧＩＳ应用角度给出了多边形图的定义，简述了多边形图的性质；论述了多边形图拓扑信息自动自下而上的数学原理及拓扑信息正确性的检验准则。     

一种基于几何特征的面状地理要素变化检测方法

利用分类方法快速更新基础地理信息数据是保持其现势性的一种重要方法,分类后变化检测是其中一个难点.文章提出一种基于几何特征的面状地理要素变化检测方法,将提取的面状地理要素与待更新要素对比,计算两者多边形质心距离、形状系数、周长和面积相似程度等几何特征来判断要素是否发生变化,从而进行更新.实验结果表明,该方法能处理分类后多...     

一种有效的复杂多边形裁剪算法

提出了一种基于扫描线思想和梯形分割技术的多边形裁剪算法,其主要步骤包括:计算主多边形(集)与窗口多边形(集)的交点,提取所有交点和多边形边界结点的纵坐标(y)并进行排序;以排序后的y作水平扫描线,分别对主多边形和窗口多边形进行梯形分割,获得两组梯形集合;对这两组梯形集合逐行执行梯形单元"交"运算,最后对结果交集进行边界追踪建立裁剪多边形。实验结果表明,该算法具有较好的计算效率,是一种比较实用的多边形裁剪算法。     

基于结构特征的地图上带晕线多边形的识别

在建立GIS的过程中,从现有的各种比例尺的地形图上获取地理信息是必不可少的工作。带晕线多边形是基本比例尺地形图上最主要的地物要素类别之一,文中在地图二值图像的基础上,根据带晕线多边形的结构特征,利用一系列图像变换技术,首次成功地实现了带晕线多边形的自动识别与提取。提出并实现了用于带晕线类多边形影像分割的4方向RLS变换方法,详细讨论了收缩变换、扩张变换、细化、开图形删除和带晕线类多边形的识别等算法。实验表明,利用文中所述方法进行带晕线多边形识别与提取的正确率可达96%左右。