共查询到20条相似文献,搜索用时 125 毫秒
1.
传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O(Nlog N)~O(N2)之间,且计算过程与特定的复杂数据结构耦合紧密,难以进行底层优化和细粒度并行化。在满足一定误差要求的前提下,采用栅格化处理思想可以实现多边形快速裁剪。本文在已有多边形裁剪算法特征的基础上,提出了一种基于栅格化处理思想的多边形裁剪算法——RaPC算法,并对其误差进行了分析和讨论。试验结果显示,RaPC算法的计算效率随网格单元增大呈幂函数规律降低;当网格大小恒定时,RaPC算法效率随多边形顶点数量呈线性增长,计算时间复杂度为O(N);在处理小数据集时Vatti算法表现出了较高效率,但是在处理包含大量顶点的多边形叠加时,RaPC算法更为高效;RaPC算法的面积误差与网格大小直接相关,提高网格空间分辨率可以有效地降低面积误差。RaPC算法在处理包含大量顶点的多边形叠加分析时比Vatti算法更为高效。 相似文献
2.
分析了目前常用的空间索引算法的缺点,提出了一种利用Windows API 提供的区域、路径、裁剪操作来建立网格空间索引的算法,对比实例证明,其具有简单易行,构建网格索引效率高、精度高等特点. 相似文献
3.
基于单调链和STR树的简单要素模型多边形叠置分析算法 总被引:2,自引:0,他引:2
针对简单要素类叠置分析的特点,利用STR(sort-tile-recursive)树索引改进算法能够将尽量多的多边形节点存储在STR树的叶节点中,减少在空间数据库中检索多边形时的磁盘读取次数。算法对多边形边界进行关于坐标轴的单调链分割,并在多边形求交过程中引入平面图的概念,利用平面图元素与各个多边形的拓扑关系来组织叠加后的多边形。该算法能有效减少求交点的时间,在线段求交中加入对连续出入点特殊数据的处理。同时该算法使用单调链减少多边形求交过程的比较次数,与其他使用双链表或单链表的算法相比具有占用空间少及处理速度快的特点。 相似文献
4.
5.
6.
目前在空间关系查询中常用的Plane Sweep算法是一种串行算法,在处理海量空间数据时效率较低,而已有的并行计算方法对于普通的计算机并不适用。本文针对这个问题,提出了一种多边形间空间关系查询的异构多核架构并行算法,该算法先利用STR树索引过滤掉不相交的多边形,然后将过滤后的多边形数据集合分解为点集合和边集合,并对其构建四叉树索引;在保证数据浮点运算精度符合要求的情况下,利用GPU强大的批量运算能力快速处理边与边的相交情况并据此逐步计算得到环间的拓扑关系,再根据环间拓扑关系计算得到多边形间的维度扩展九交模型(DE-9IM)参数值;根据DE-9IM参数值与空间关系查询条件相比对,输出查询结果。最后通过试验验证了算法的准确性与高效性。 相似文献
7.
8.
本文根据专题要素的新分类和编码以及它的空间信息描述,提出了一种类似于四叉树结构的网格索引的膨胀算法,针对交通专题数据库而言,它是一种高效的索引技术,兼有四叉树索引和网格索引的优点。文章重点介绍了它的索引机制。 相似文献
9.
首先介绍全球网格系统的应用需求,讨论采用正多面体剖分的基本要素。在此基础上,提出一种新型的便于存储,具有多分辨率层次索引、管理能力的六边形剖分全球网格系统的设计思路、产生步骤和生成算法。分析现有六边形索引机制的缺陷,给出一种新的球面六边形网格层次结构,在该结构的基础上设计网格的层次化编码方式,成功建立网格的编码空间,详细探讨经纬度坐标与网格地址编码的转换问题,给出并实现基于递归层次离散网格坐标系统的互换算法,严格保证计算的准确性和可靠性。该结构能够无缝地表达和处理不同分辨率的全球网格空间数据。 相似文献
10.
11.
讨论了建立约束Delaunay三角网算法的研究现状,采用“逐点插入法”和“多对角线交换算法”构成“两步法”,在此基础上,从建立高精度三角网模型的需求出发,研究以大数据量等高线为约束边进行Delaunay三角剖分的改进算法。针对“逐点插入法”,采用网格分块的方法对构网点集和已生成的三角网建立索引,提高了点的查询速度和点在三角网中的定位速度,提高了三角网的生成效率;针对“多对角线交换算法”,增加了一些特殊情况的处理,提高了算法的健壮性和交换速度。 相似文献
12.
空间数据捕捉是地图制图、空间数据编辑中的一个重要的功能。快捷、高效的空间数据捕捉算法可极大地提升空间数据编辑的效率,减少时间成本。目前常用的空间查询捕捉算法往往算法复杂,I/O操作频繁,增加了计算资源的消耗,降低了运行效率。针对这些缺点,本文提出了一种新型的空间目标动态捕捉算法。该算法建立一种自适应性和动态性的格网索引机制,该机制基于区域变化提取新格网,用新格网对原有数据和新数据进行提取,并把提取结果反映到新的四叉树格网索引中,实现索引数据动态更新。通过实验对比,我们发现该算法在缩短捕捉时间、提高矢量点线面捕捉精度方面非常有效,且捕捉稳定性较高,极大地提高了外业采集人员和数据处理人员的工作效率。 相似文献
13.
高分辨率光学遥感几何与纹理约束的线段优化算法 总被引:1,自引:1,他引:0
针对高分辨率光学遥感影像线段断裂问题,提出一种基于几何与纹理约束的线段优化算法。首先,将线段视为地物轮廓表达的一种方式,由此从同一地物边缘角度出发,提出线段断裂的几何与纹理规律;其次,提出线段优化算法,以提取线段结果为处理基元,依据线段长度确定初始优化线段,设定跟踪矩形,建立针对断裂线段的几何纹理约束模型,构建动态优化模型,并给出完整的线段优化流程。最后,通过多幅不同实际场景、不同类型高分辨率遥感影像的试验结果分析,表明本文算法不仅能够解决由地物遮挡、边缘模糊及边缘锯齿化造成的线段断裂问题,并且在优化线段长度以及抑制线段过提取问题方面,均表现出较大的优势。 相似文献
14.
导航数据库中空间索引建立方法研究 总被引:1,自引:0,他引:1
孙晓光 《测绘与空间地理信息》2008,31(3)
针对导航数据库中传统空间索引建立方法存在的问题,提出了一种基于两级交错式网格划分的空间索引建立方法。详细分析了该算法的实现原理,并讨论了与之相关的网络路段信息的提取与存储技术。实验结果表明,采用该方法可有效减少空间数据索引表的数据量,提高检索效率,增强空间数据提取的准确性。 相似文献
15.
利用DEM边缘检测进行黄土地貌沟沿线自动提取 总被引:6,自引:0,他引:6
在分析黄土地貌沟沿线形态特征的基础上,提出了基于规则格网DEM,通过引入边缘检测算子提取并连接沟沿线候选点,并借助形态学方法滤除细碎线段,最终生成沟沿线的方法。黄土丘陵沟壑区的实验结果显示,Sobel、Roberts、Prewitt梯度算子检测得到的沟沿线封闭性较差,线段较零碎,与实际沟沿线不符,不适用于沟沿线的自动提取;而LOG算子提取的线段连续、精度高,是理想的沟沿线检测算子,能够实现黄土地貌沟沿线较准确、有效的自动提取。 相似文献
16.
对地图分区域构图特点进行了研究,结合嵌入式电子地图数据组织与图形特点,提出了一种集成行程长度与多段扫描转换算法的高效绘线方法,利用地图格网索引技术对算法进行了集成,验证了算法的效率。 相似文献
17.
徐文武 《测绘与空间地理信息》2017,(3)
针对当前GIS道路选线缺乏定制化的问题,本文设计并实现了基于DEM的高程最优路径选取算法,该算法将高程作为道路选线因素,以匀坡作为选线标准,采用上下行算法和内分插值算法进行道路选线。基于ArcGIS Engine平台,对设计的算法进行了编程,最终实现了卓呼线的自动选取。实验证明,该算法可以利用DEM格网点高程自动绘制匀坡线,从而生成高程成本最优路径。同时,该算法时间复杂度较低,计算速度快,健壮性良好,运算成果正确,不失为一种快速的道路选线新方法。 相似文献
18.
19.
20.
通信、导航、遥感一体的天基信息服务系统的建设将对跨境实时通信、动目标全球跟踪、灾害快速响应等提供有力保障,同时也对高效的网络通信,特别是卫星路由规划算法提出了新的要求.为优化通信链路,进一步降低时延,充分利用网格空间关系直视、编码计算效率高的优势,提出了卫星星座空间互联网格化计算方法.基于 GeoSOT-3D(geog... 相似文献