共查询到20条相似文献，搜索用时 31 毫秒
1.
传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O(Nlog N)~O(N2)之间,且计算过程与特定的复杂数据结构耦合紧密,难以进行底层优化和细粒度并行化。在满足一定误差要求的前提下,采用栅格化处理思想可以实现多边形快速裁剪。本文在已有多边形裁剪算法特征的基础上,提出了一种基于栅格化处理思想的多边形裁剪算法——RaPC算法,并对其误差进行了分析和讨论。试验结果显示,RaPC算法的计算效率随网格单元增大呈幂函数规律降低;当网格大小恒定时,RaPC算法效率随多边形顶点数量呈线性增长,计算时间复杂度为O(N);在处理小数据集时Vatti算法表现出了较高效率,但是在处理包含大量顶点的多边形叠加时,RaPC算法更为高效;RaPC算法的面积误差与网格大小直接相关,提高网格空间分辨率可以有效地降低面积误差。RaPC算法在处理包含大量顶点的多边形叠加分析时比Vatti算法更为高效。 相似文献
2.
3.
在保证多边形之间拓扑关系完整的基础上,分别使用垂距限值法和Douglas-Peucker算法对多边形形状进行了简化,同时从多边形常规参数以及相似度等方面对简化后多边形的质量进行了评价。实验结果表明Douglas-Peucker算法的简化效果较好。 相似文献
4.
提出了一种符合空间认知规律的栅格化处理的任意多边形间方向关系的计算方法，该方法计算结果与人眼的判断结果非常接近，在此基础上讨论了多边形间方向关系的可确定问题，并提出了一种基于8方向隶属零值个数的两个多边形方向关系可确定程度的判定方法。 相似文献
5.
6.
针对大数据量遥感图像矢量化时间效率低和空间瓶颈问题,采用顶点提取过程中同时进行图斑矢量化的策略,提出一种适应大数据量遥感图像的动态矢量化算法。首先,统计图像中各图斑的顶点个数,将其作为图斑顶点集合能否构成封闭多边形的判定条件;然后,在顶点提取的过程中发现有能够成封闭多边形的图斑顶点集合,立即将其矢量化并释放其所占内存,图斑矢量化时直接将顶点构建成多边形无需生成中间弧段,并即时形成拓扑关系。实验表明,文中算法能快速高效地完成大数据量遥感图像矢量化,速度是ARCGIS（9.2版本）矢量化算法的3~4倍。 相似文献
7.
一直以来,任意多边形相交面积的高效计算都是地理信息系统中空间分析算法研究的重点。文中提出了一种基于GPU的栅格化多边形相交面积算法GPURAS,在此基础上,分别采用蒙特卡罗方法和遮挡查询技术进一步提出GPURASMC算法和GPURASQ算法,并证明了上述算法的正确性。实验对简单多边形、任意复杂多边形及大数据量多边形进行了测试对比,结果表明:GPURAS算法精度高,通用性较好但效率受CPU与GPU通信延迟的影响;GPURASMC算法效率较高但牺牲了部分精度;GPURASQ算法精度高、效率高但局限于特定运行环境。与基于CPU的传统算法相比,文中所提3种算法效率更高,在处理包含大量顶点的多边形时,效率提升尤为明显。 相似文献
8.
This research develops a parallel scheme to adopt multiple graphics processing units (GPUs) to accelerate large‐scale polygon rasterization. Three new parallel strategies are proposed. First, a decomposition strategy considering the calculation complexity of polygons and limited GPU memory is developed to achieve balanced workloads among multiple GPUs. Second, a parallel CPU/GPU scheduling strategy is proposed to conceal the data read/write times. The CPU is engaged with data reads/writes while the GPU rasterizes the polygons in parallel. This strategy can save considerable time spent in reading and writing, further improving the parallel efficiency. Third, a strategy for utilizing the GPU's internal memory and cache is proposed to reduce the time required to access the data. The parallel boundary algebra filling (BAF) algorithm is implemented using the programming models of compute unified device architecture (CUDA), message passing interface (MPI), and open multi‐processing (OpenMP). Experimental results confirm that the implemented parallel algorithm delivers apparent acceleration when a massive dataset is addressed (50.32 GB with approximately 1.3 × 108 polygons), reducing conversion time from 25.43 to 0.69 h, and obtaining a speedup ratio of 36.91. The proposed parallel strategies outperform the conventional method and can be effectively extended to a CPU‐based environment. 相似文献
9.
利用Oracle Spatial提供的简单的空间关系查询操作算子,对九交模型所描述的任意两个2维空间不自相交的线目标与面目标(不含空洞)的拓扑关系判断设计了算法,最终进行了试验验证,实现了线目标与面目标间的19种空间拓扑关系的判断。 相似文献
10.
建筑物白模多边形数据可广泛应用于许多领域,但在实际应用中,由于数据太过细致,且目前使用的建筑物白模多边形数据存在拓扑关系错误,不满足生产要求,这给地图综合中建筑物群的自动合并提出了新的要求.因此提出了一种基于约束性Delaunay三角网的建筑物白模多边形自动合并方法,在保持建筑物整体结构和视觉效果的前提下减少不必要的细... 相似文献
11.
利用OracleSpatial提供的简单的空间关系查询操作算子,对九交模型所描述的任意两个2维空间不自相交的线目标与面目标（不合空洞）的拓扑关系判断设计了算法,最终进行了试验验证,实现了线目标与面目标间的19种空间拓扑关系的判断。 相似文献
12.
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. 相似文献
13.
14.
从地理空间数据不确定性理论出发,提出了矢量化多边形的优化方法。该方法通过对矢量多边形进行"磨角插值"和基于可接受域限定的自适应滤波平滑处理,以此来削弱由空间数据表示不确定性造成的误差,使矢量化多边形最大限度地逼近地理实体真实轮廓。采用基于全局阈值的DP算法进行压缩处理,消除了数据冗余。从压缩比、位置误差及处理效率3个方面进行对比实验,验证了所提方法的有效性。 相似文献
15.
按照简单地块的8种拓扑关系分类定义,计算简单地块的拓扑关系。将复合地块的外边界与空洞分离为m＋1个（m是空洞数）简单多边形,分别计算外边界之间、空洞之间、外边界与空洞之间的拓扑关系,并且按照不同的拓扑关系组合,计算复合地块的8种拓扑关系。 相似文献
16.
支持地图综合的面状目标约束Delaunay三角网剖分 总被引：6，自引：0，他引：6
针对多边形面状目标的综合问题,建立了二维空间中约束Ｄｅｌａｕｎａｙ三角网剖分结构,融入多边形的环、岛屿、边界、顶点的描述,通过形式化条件检索,在该结构上提取二维空间中各种感兴趣的由剖分三角形组成的区域,用于支持地图综合中邻近多边形的搜索、多边形弯曲部位的识别、冲突关系探测、多边形合并等操作。并对基于骨架线的图结构建立、分枝宽度计算等几何问题进行了详细讨论,指出了其在诸如双线河中轴化、街道中轴线网络模型建立、多边形合并中的邻近关系分析、面状目标注记自动定位领域的支持作用。 相似文献
17.
本文提出了面向CPU+GPU异构环境的数据密集型矢量多边形地理大数据并行计算框架(PFGAP)。PFGAP将数据密集型矢量多边形地理大数据的并行计算分解为算子、数据、粒度、并行环境及任务调度5个模块,分别设计相应的负载均衡并行计算策略;通过封装并行计算实现细节及数据密集型多边形算子的快速并行化。试验采用多边形三角剖分、栅格化及投影变换作为测试算例,采用土地利用数据作为测试数据,在不同类型的并行环境中计算并行效率。结果表明,PFGAP能很好地适用于不同类型的数据集、算子及并行计算环境。利用PFGAP实现的并行算法显著地降低了串行执行时间,取得了40.03的最优并行加速比。试验还分别测试了各个模块涉及的并行策略,结果表明取得的并行效率优于现有并行策略。 相似文献
18.
A general framework for error analysis in measurement-based GIS Part 3: Error analysis in intersections and overlays 总被引：3，自引：1，他引：2
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. 相似文献
19.
20.
点、多边形拓扑关系与多边形顺、逆判断优化算法 总被引：7，自引：0，他引：7
刘梁 《测绘与空间地理信息》2007,30(1):84-86
点与多边形拓扑关系判断是空间拓扑分析的重要内容之一,基于以往算法不可靠和过于复杂的缺点,本文提出了面积判断法,很好地解决了上述问题,且对于含有孤岛的多边形仍然有效。矢量多边形坐标存储顺、逆时针的判断是数据验证、数据转换必不可少的一项,但对于此种算法少有提及,为此本文提出了外围判断法,可以较为简单地完成此项任务,填补了此类算法的空白。 相似文献