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

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

任意多边形间方向关系的计算及其可确定问题

提出了一种符合空间认知规律的栅格化处理的任意多边形间方向关系的计算方法，该方法计算结果与人眼的判断结果非常接近，在此基础上讨论了多边形间方向关系的可确定问题，并提出了一种基于8方向隶属零值个数的两个多边形方向关系可确定程度的判定方法。     

改进的边标志栅格化算法

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

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

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

梯形面片数据模型及其空间运算应用

提出一种新的基于梯形面片的空间运算方法,该方法将多边形要素预先分解成一系列的梯形面片,后续的空间运算将不再基于原始多边形要素进行操作,而是对分解产生的梯形面片进行更为简便的计算处理。梯形面片模型结合了常见矢量数据模型数据精度高、栅格数据模型运算简单等优点,在执行相关空间运算中与常见矢量和栅格模型相比具有优势。详述了该数据模型,并以点面包含分析和多边形叠置分析等实例探讨了其在空间运算中的应用,测试与分析表明该方法兼具数据精度高、算法实现简单等优点,能较有效地提高空间运算的执行效率。     

梯形面片数据模型及其空间运算应用

提出一种新的基于梯形面片的空间运算方法,该方法将多边形要素预先分解成一系列的梯形面片,后续的空间运算将不再基于原始多边形要素进行操作,而是对分解产生的梯形面片进行更为简便的计算处理。梯形面片模型结合了常见矢量数据模型数据精度高、栅格数据模型运算简单等优点,在执行相关空间运算中与常见矢量和栅格模型相比具有优势。详述了该数据模型,并以点面包含分析和多边形叠置分析等实例探讨了其在空间运算中的应用,测试与分析表明该方法兼具数据精度高、算法实现简单等优点,能较有效地提高空间运算的执行效率。     

用栅格填充法建立多边形文件

栅格填充法建立多边形文件,是基于栅格象元“蔓延”算法,从“内点”出发自动搜索多边形轮廓边的地理数据处理方法。该法能适应任意复杂(具有“飞地”或“空洞”等情况)的多边形。该软件已成功地应用于作者研制的关系型地理数据库软件系统(RGDBS)。本文简述了该法的基本原理和有关算法。     

基于GPU的任意多边形相交面积计算方法

一直以来,任意多边形相交面积的高效计算都是地理信息系统中空间分析算法研究的重点。文中提出了一种基于GPU的栅格化多边形相交面积算法GPURAS,在此基础上,分别采用蒙特卡罗方法和遮挡查询技术进一步提出GPURASMC算法和GPURASQ算法,并证明了上述算法的正确性。实验对简单多边形、任意复杂多边形及大数据量多边形进行了测试对比,结果表明:GPURAS算法精度高,通用性较好但效率受CPU与GPU通信延迟的影响;GPURASMC算法效率较高但牺牲了部分精度;GPURASQ算法精度高、效率高但局限于特定运行环境。与基于CPU的传统算法相比,文中所提3种算法效率更高,在处理包含大量顶点的多边形时,效率提升尤为明显。     

多重多边形叠置栅格算法

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

一种改进的点与多边形关系的叉乘判别法

本文针对叉乘判别法只适用于凸多边形的缺陷提出了改进,将其推广至凹多边形和自相交多边形,改进方法利用叉乘值的正负变化,选择对点的积分路径,从而判断是否有闭合的路径包围被测点。并通过检测多边形是否环绕被测点,判断点与多边形的关系,属于非零环绕数法。经过实验,改进方法被证明有较快的速度和较强的适应性。     

DDA算法在地表面积计算中的应用研究

现有的几种地表面积计算方法复杂,或欠缺考虑,或不便于在工程应用中使用。在实际应用的基础上,提出一种思路简单的地表面积计算新方法及步骤,该方法将栅格数据分成完整栅格和非完整栅格两部分。针对完整栅格,给出单元栅格划分方法及单元栅格地表面积计算理论;针对非完整栅格,详细介绍通过DDA(digital differential analyzer)算法及射线算法计算非完整栅格区域面积。该方法思路简单,并结合实际数据进行验证,取得了良好的效果。     

一种基于边界搜索的栅格矢量化算法

栅格数据的矢量化是GIS领域重要的研究内容。针对栅格数据矢量化准确率低和效率低等问题,该文提出了一种基于边界搜索的矢量化算法,通过对栅格图像的一次遍历,提取结点和中间点,生成弧段,构建多边形;并在构建多边形中,提出了一种简单易行的最右侧方向判断方法,综合运用最小外接矩形和射线法判定逆时针多边形的归属。实验表明,该文提出的矢量化算法能够较准确矢量化复杂的栅格图像,具有较好的效率,可为多值栅格图像快速矢量化及相关研究提供借鉴。     

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

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

复杂多边形中轴构建方法!

多边形中轴是指与多边形不同边(或边的延长线)上的两个或两个以上点等距离的点轨迹。多边形中轴的图形结构表明,在多边形凸顶点处存在中轴线,而在凹顶点处不存在中轴线(中轴线在多边形外)。采用左右点法实现对多边形顶点凹凸性的判断,进而定义和标注多边形不同边界线段。借助ArcGIS软件,提出了构建任意复杂多边形中轴的两种逼近方法:一种是基于Voronoi图的矢量方法;另一种是基于欧氏距离区域分配的栅格方法。实验表明这两种方法都是有效的、可行的。     

基于绘制-检出的矢量数据栅格化方法研究

对于前人提出但未被重视的绘制-检出栅格化方法进行了阐述,给出了其实现步骤与关键语句,并赋予其一个新的名称——基于绘制-检出的矢量数据栅格化方法。对该方法实现中的一些技术问题,如正确性、精度、内存位图大小限制、分块栅格化、栅格化效率等问题进行了深入的探讨。笔者认为,该方法可以成为一种普适的工业方法。     

复杂三维建筑物模型稳健栅格化方法

针对复杂三维建筑物模型的栅格化问题,在分析、比较当前主流的几种矢量栅格化方法的基础上,提出基于区域连通性和置信度分析的可疑区域生长法实现建筑物模型表面栅格化,再采用奇异值分解(SVD)方法解算建筑物空间平面描述参数,内插DBM栅格的高程。试验结果表明,可疑区域生长法可以完全避免栅格化产生的噪音,复杂度低;采用SVD方法可以抵抗各种病态,稳健求解表面参数。     

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

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

微机土地适宜性评价信息系统的设计

本文较系统地研究了微机土地适宜性评价信息系统的设计,同时讨论了几种土地适宜性评价方法。空间数据处理中的DTM的建立和多边形栅格化都采用了较简单而科学的方法,以便在微机上可运算数据量较大的数字地图。本系统为县级土地评价和土地规划服务。     

CPU+GPU异构环境下数据密集型矢量多边形地理大数据并行框架

本文提出了面向CPU+GPU异构环境的数据密集型矢量多边形地理大数据并行计算框架(PFGAP)。PFGAP将数据密集型矢量多边形地理大数据的并行计算分解为算子、数据、粒度、并行环境及任务调度5个模块,分别设计相应的负载均衡并行计算策略;通过封装并行计算实现细节及数据密集型多边形算子的快速并行化。试验采用多边形三角剖分、栅格化及投影变换作为测试算例,采用土地利用数据作为测试数据,在不同类型的并行环境中计算并行效率。结果表明,PFGAP能很好地适用于不同类型的数据集、算子及并行计算环境。利用PFGAP实现的并行算法显著地降低了串行执行时间,取得了40.03的最优并行加速比。试验还分别测试了各个模块涉及的并行策略,结果表明取得的并行效率优于现有并行策略。     

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

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