共查询到19条相似文献,搜索用时 62 毫秒
1.
提出一种基于线段操作的简单多边形求差算法。该算法的主要过程为:应用基于单调链的扫描线求交算法,求取交点,该过程减少了求交过程中的比较次数,从而提高了求交效率。基于线段操作的结果多边形连接算法,该过程利用基础的计算几何理论,寻找构成结果多边形的边,得到两个多边形的差。实验表明该算法思路简单,数据结构简单,易于编程实现,对于简单多边形求差问题具有普适性。 相似文献
2.
3.
采用了双向链表这种数据结构,对两简单多边形的顶点及交点进行存储,在对交点进行插入时,可直接插入链表中,避免了利用单向链表或数组进行存储时对点的重复查找。通过遍历两个顶点、交点混合表,可得到两多边形的交及多边形的顶点,从而得到两多边形的交集。相对其他类似的算法,该算法具有较快的计算速度和较高的效率。 相似文献
4.
5.
6.
7.
建立在多边形约束性Dolaunoy三角网的基础上,针对确定多边形中轴线的特点,提出了表层三度单元、内核三度单元、单入口路径表层三度单元、双入口路径表层三度单元、三入口路径表层三度单元等概念体系,最后提出了确定多边形中轴线的算法模型,并进行了实验性验证。理论与实验表明该模型逻辑严密,结论正确,研究成果对多边形的形态分析、地图上面状要素的注记定位等问题具有基础支持作用。 相似文献
8.
针对Visual C++环境下多边形裁剪算法实际应用中出现的问题,分析了其产生的原因,给出了具体的解决方法.同时指出可以通过判断矢量多边形面积的正负值将多边形的顶点按照顺时针或逆时针方向排序. 相似文献
9.
10.
11.
一直以来,任意多边形相交面积的高效计算都是地理信息系统中空间分析算法研究的重点。文中提出了一种基于GPU的栅格化多边形相交面积算法GPURAS,在此基础上,分别采用蒙特卡罗方法和遮挡查询技术进一步提出GPURASMC算法和GPURASQ算法,并证明了上述算法的正确性。实验对简单多边形、任意复杂多边形及大数据量多边形进行了测试对比,结果表明:GPURAS算法精度高,通用性较好但效率受CPU与GPU通信延迟的影响;GPURASMC算法效率较高但牺牲了部分精度;GPURASQ算法精度高、效率高但局限于特定运行环境。与基于CPU的传统算法相比,文中所提3种算法效率更高,在处理包含大量顶点的多边形时,效率提升尤为明显。 相似文献
12.
13.
14.
给出了一组空间离散点三维凸边界的定义,提出了基于八叉树的空间分块索引方法。在此基础上发展了一种生成三维凸边界的算法,并利用实验对算法进行了验证。 相似文献
15.
射线法判断点与包含简单曲线多边形关系的完善 总被引:2,自引:0,他引:2
点与多边形关系的判断问题一直是计算机图形学中的基本问题之一,目前判断点与多边形关系的射线法只考虑多边形边界全部由直线组成,而在实际应用中,多边形边界经常包含简单曲线。本文以圆弧为例,在分析已有射线法基础上,提出对射线法的完善算法,解决了点与包含圆弧的复杂多边形关系的正确判定。 相似文献
16.
17.
18.
The algorithm we present here is useful for measuring the planimetric discrepancy between two models which can be represented by contours. In cartography the paradigm of such models is represented by digital terrain models (DTMs). The measure we propose is based on an area enclosed between homologous contours (two level contours, each belonging to two different models). Our measure is similar to another used previously, although, in the previous studies, the area enclosed between homologous contours was computed manually or it was restricted to particular conditions. The innovation of our approach consists of the automation of the entire process and in the constraint elimination. The main problem to solve before computing the horizontal shift measure is how to determine the area enclosed between homologous contours. This is a problem because there is no bijective correspondence between homologous contours, and therefore the identification of the homologous contours is not a trivial task. Our approach overcomes this difficulty by closing following the limit of the DTM the open contours (the contours which cut the limit of the DTM) and classifying them by the external level. We achieve the automation assisted by the Boolean polygon operations, specifically using the symmetric difference operation. Our algorithm facilitates the computation of accuracy of a DTM by comparison with another and it is applicable in such fields as hydrology (precision estimation of the hydrological features), cartographic generalization, and civil engineering. Finally we use our measure for estimating the planimetric discrepancy between the same streams derived from different DEMs (different sources and precisions). 相似文献