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

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

拓扑多边形自相交判断及纠正方法

提出了一种解决地形图处理中拓扑多边形自相交问题的方法。首先在原多边形内部构建新多边形,通过判定新多边形的顶点是否为原多边形内点实现了多边形自相交的判断。最后利用三种方式对存在自相交的多边形进行纠正。基于VC＋＋6.0实现相关功能,并以实例验证了这一方法的稳定性和可行性。     

煤矿地质成图中多边形快速生成算法

针对煤矿地质成图中左转算法生成多边形在复杂的二维图形条件下应用效率低的问题,该文提出了一种新的基于左转算法的多边形快速选取及自动生成算法,实现了2D图形环境中多边形的快速选取及自动生成。通过在进行多边形选取时的起始点,起始方向的选择和对悬挂点、线进行处理,解决了复杂图形下多边形选取及自动生成过程中存在的重复生成、效率低下和搜索回退问题。基于GeoMS3D实现该算法,实验结果表明:该算法逻辑简单、结构清晰,在实际的应用中表现出了较高的运算效率。     

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

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

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

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

并行化矢量多边形叠加算法研究

正空间数据规模的快速增长对传统地学分析方法提出了更高的计算效率和处理规模要求。作为核心的空间分析算法之一,矢量多边形叠加分析具有典型的高算法复杂性和计算密集性特征。随着计算机硬件和软件技术的进步,并行计算为提高多边形叠加分析的计算效率,扩大问题处理规模提供了有效手段。研究面向新型计算架构的多边形并行叠加分析算法对完善高性能GIS理论研究和实现方法,提升传统地学分析算法的计算效率具有重要的理论价值和实践意义。本论文针对多边形非拓扑叠加算法的并行化问题,在多种高性能计算环境下解决了     

一种基于改进遗传算法的村镇土地宗地多边形自动构建方法

针对村镇土地宗地多边形自动构建的自动化智能化程度低以及精度不高的问题,本文提出一种基于改进遗传算法的宗地多边形自动构建方法。该算法具有以下特点:根据无序界址点位置信息构建宗地多边形,充分挖掘宗地多边形内在数学约束,加入宗地转角频率分布这一关键优化参数,将宗地各个转角频率乘积作为遗传算法的适应度函数,并针对宗地多边形的自相交问题进行了检验;该算法只需要获取界址点位置坐标和宗地代码信息,比较简洁高效。实验结果表明,本算法的准确率达到了84%以上。     

基于线段操作的多边形求交算法研究

根据多边形之间的相交状态求所有目标多边形线段与源多边形边界的交点;利用点与多边形关系判别法则判断出目标多边形与源多边形的公共线段;目标多边形与源多边形对调,再次判定出公共线段;最后将公共数据选择集中的公共线段首尾连接构成闭合多边形即为两个多边形求交结果。求交算法以线段操作为核心求解两多边形的交集,通过遍历公共线段来完成交集多边形边界的构建。该算法结构简单,易于编程实现,计算工作量小,求交效率高,已成功应用在土方计算软件开发中,在地图制图和地理信息空间分析等方面有广阔的应用前景。     

基于节点序列搜索的多边形分割算法

针对多边形切割中由于切割点坐标值的取舍导致的点位偏移,从而可能出现拓扑错误的情况,提出一种基于节点序列搜索的多边形分割算法。该算法在生成多边形相交的切割线的基础上,对产生的切割点进行坐标值取舍,将进行坐标值取舍后的坐标点与被切割多边形的坐标点按照节点序列生成被切割多边形,同时切割点内插到相关多边形,从而保证多边形的拓扑关系不变。该算法能解决带岛多边形切割。该算法已经在大规模数据生产中得到应用。     

Delaunay三角形法实现面状要素自动注记初探

地图自动注记是自动制图技术的重要环节之一。本文阐述了根据Delaunay三角形的逐点自动生成算法原理进行面状要素自动注记的方法。重点论述了图斑多边形的预处理算法和求取注记定位线的算法。在与长对角线法和水平切割中点线法相比后证明,这种算法不但能够处理所有常规形状的多边形,而且能够适应诸如凹形多边形等具有特殊形状的多边形。