利用CUDA实现矢量地图栅格化的并行处理

为了解决矢量地图栅格化的计算效率问题,提出了基于CUDA（Compute Unified Device Architecture,计算统一设备架构）实现矢量地图栅格化的并行处理方案。根据矢量地图中多边形的数目和GPU（Graphic Processing Unit,图形处理器）的硬件性能,定义并行执行的线程数目,每一个线程对相应的多边形进行边填充栅格化。实验结果表明加速比达到了10倍以上。相比CPU（Central Processing Unit,中央处理器）栅格化的处理方法,运算效率有显著提升。     

RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析

传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O(Nlog N)~O(N2)之间,且计算过程与特定的复杂数据结构耦合紧密,难以进行底层优化和细粒度并行化。在满足一定误差要求的前提下,采用栅格化处理思想可以实现多边形快速裁剪。本文在已有多边形裁剪算法特征的基础上,提出了一种基于栅格化处理思想的多边形裁剪算法——RaPC算法,并对其误差进行了分析和讨论。试验结果显示,RaPC算法的计算效率随网格单元增大呈幂函数规律降低;当网格大小恒定时,RaPC算法效率随多边形顶点数量呈线性增长,计算时间复杂度为O(N);在处理小数据集时Vatti算法表现出了较高效率,但是在处理包含大量顶点的多边形叠加时,RaPC算法更为高效;RaPC算法的面积误差与网格大小直接相关,提高网格空间分辨率可以有效地降低面积误差。RaPC算法在处理包含大量顶点的多边形叠加分析时比Vatti算法更为高效。     

无边界游程编码及其矢栅直接相互转换算法

本文提出了无边界游程（ＮＢＲＬ）编码的栅格压缩格式及其与矢量格式之间直接相互转换的算法。无边界游程编码具有无矩形边框限制的特点,可随意扩展而无须改变整体参数,特别适合范围不同的两个栅格的各种组合运算。提出的提取多边形算法,可直接在游程上作标记,而不必先还原成非压缩格式,从而节省了内存,提高了速度。     

以节点操作实现多边形求交的算法

根据多边形之间的交点状态确定与交点相关的节点信息,以节点操作为核心求解两多边形之间的交集。在此基础上,考虑重叠边、边边相交于边节点等情形,通过遍历交点来完成交集多边形边界的构建,从而提出一种多边形求交运算的改进算法。该算法结构简单,具有较快的计算速度和较高的效率,适合于地理信息系统中的空间叠置分析、缓冲区分析应用,对于地图制图中区域要素的截取操作也具有重要的参考价值。     

多重多边形叠置栅格算法

讨论了传统的矢量叠置分析在初始化、数据冗余、误差等方面存在的问题,而基于栅格模式的叠置分析则可以消除这些问题,在此基础上给出了多重多边形叠置栅格算法,运用此算法进行了湖北省城镇化水平的实证分析。     

矢量数据栅格化的一种有效方法——环绕数法

矢量数据栅格化是GIS数据处理的一项重要任务。目前,已存在多种栅格化方法,但是每种方法都有各自的局限性。本文首次提出了环绕数法,它基于计算几何转角理论,通过计算跨越数来确定环绕数,是一种简单、高效、易于实现的栅格化方法。应用环绕数法,不但可以完成简单多边形的栅格化,而且可以完成自交多边形的栅格化。     

面积误差最小约束下矢量数据向栅格数据转换的优化算法

在总结现有的矢量数据向栅格数据转换算法的基础上,提出一种面积误差最小约束下的优化算法。该算法保证了多边形矢量数据在栅格化后的面积误差尽可能最小,从而提高所得栅格数据在面积分析相关领域中应用的可信度。     

栅格矢量一体化数据结构设计

在遥感与地理信息系统集成的研究中，适合集成系统的一体化数据结构的研究始终是个热门话题。虽然关于一体化数据结构的内容及含义并没有一个明确和统一的定义，但却有许多相关的研究成果已经成功的应用于商业GIS软件中。本文总结了栅格矢量一体化数据结构研究过程出现的三种主要的数据结构。在分析已有成果的基础上，改进了矢量栅格化型数据结构编码方法，利用二阶B 树建立了线、面要素的索引结构。     

多边形拓扑关系构建的栅格算法

矢量数据拓扑关系的自动建立是GIS软件的核心模块之一，也是技术难点之一。简要分析传统算法的优缺点，在此基础上，借鉴基栅格的种子点填充算法和矢量数据求交的栅格探测法的思想，提出建立图幅多边形与弧段所属关系的栅格算法，给出算法的各主要步骤和实现方法。分析与试验表明，新算法在特殊情况处理、多边形内点自动建立、处理效率、简化编程等方面有一定优势。     

融合直角点和直角边特征的高分辨率遥感影像居民点提取方法

提出了一种融合直角点和直角边两种特征的高分辨率遥感影像居民点提取方法:首先,分别检测高分辨率遥感影像的角点和直线段,通过两种特征交叉验证确定直角点和直角边,并对二者进行栅格化;然后,基于局部直角点和直角边点的密度和距离特征生成居民点指数图像;最后,通过指数图像二值化、栅格转矢量、剔除小图斑等操作确定居民点多边形。使用3景影像进行了试验。试验结果表明,本文方法提高了居民点提取精度,其正确率、完整率、质量等3个指标的平均值比已有方法的相关值分别高6.76%、10.12%、12.14%。     

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.     

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

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

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

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

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

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

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.     

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

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

利用骨架线端点匹配进行面状要素渐变变换

面向空间数据连续地图综合问题,提出了一种基于骨架线端点匹配的面状要素渐变方法,通过在两个关键表达之间进行尺度内插,实时、动态地派生任意中间比例尺地图数据。首先,对面状要素在大小比例尺下的两重表达分别进行约束Delaunay三角网剖分并提取各自的骨架线特征;然后,使用最优子序双射优化技术对骨架端点进行匹配获得多边形边界上相对应的特征点序列;最后,在剖分边界的基础上进行分段常规线性内插,获得面状要素介于始末尺度之间的多尺度表达。实验结果表明,该算法充分顾及了空间数据弯曲结构特征,对于光滑边界面状要素的渐变变换具有良好的渐变效果,可用于空间数据的连续地图综合和多尺度表达。     

多边形自动生成的一种改进算法

本文提出了一种多边形自动生成的改进算法,对不参与组成多边形的弧段和结点进行分类处理,在搜索多边形之前,排除悬挂结点、悬挂弧段、假悬挂结点和假悬挂弧段的干扰,在搜索多边形的过程中,为弧段建立搜索标志,并对桥进行判断和排除,较好地解决了问题,提高了自动生成多边形的效率。     

栅格数据矢量化及其存在问题的解决

矢量结构和栅格结构是GIS的两种主要数据结构形式，而栅格数据的矢量化在GIS中具有十分重要的意义。本文在总结前人算法的基础上，以拓扑关系的原理为指导，提出了改进的栅格结构数据矢量化方法，即在提取结点和坐标点过程中同时提取水平和垂直的所有线段信息，以便于快速、有效地实现栅格数据的矢量化。此外，还采用动态打断和粗网格法等方法，解决了在栅格数据矢量化过程中经常出现的诸如多边形自交、岛等问题。