首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 156 毫秒
1.
王杰臣  周娅 《遥感信息》1998,(4):5-9,13
通过对简单闭曲线拓扑特性的研究,阐明了由简单闭曲线构成的多边形,该多边形的内点对各曲线段的有向夹角和为±2π,而外点为0,并将此性质应用于GIS的点面包含分析中,作为GIS空间包含分析的基础。  相似文献   

2.
基于有序简单多边形的平面点集凸包快速求取算法   总被引:32,自引:1,他引:32  
凸包问题是计算几何的基本问题之一,在许多领域均有应用。传统平面点集凸包算法和简单多边形凸包算法平行发展,互不相干。本文将改进的简单多边形凸包算法应用于平面点集凸包问题中,提出了新的点集凸包算法。该算法首先淘汰掉明显不位于凸包上的点,然后对剩余点集排序,再将点集按照一定顺序串联成有序简单多边形,最后利用前瞻回溯方法搜索多边形凸包,从而得到点集的凸包。本文算法不仅达到了O的理论时间复杂度下限,而且算法  相似文献   

3.
一种平面简单多边形核的求解算法   总被引:1,自引:0,他引:1       下载免费PDF全文
平面简单多边形的核是该多边形内部的一个点集,该点集中任意一点与多边形边界上一点的连线都处于这个多边形内部。可见核的这一性质在摄像机定位等问题上得到了应用,本文提出了一种简单多边形核求解的新方法,该方法不仅可以判断核的存在性,而且可以得到核多边形顶点序列。给出的算法容易理解,便于实现,可以广泛地应用于此类问题的求解。  相似文献   

4.
简单多边形的核是位于多边形内部的一个点集,而且这个点集中的任意一点与多边形边界上的任意点的连线都属于这个多边形的内部。核的这一性质在监视器安放等问题上得到了应用。考察了简单多边形的核在构成方面的性质,结合已有的成果,提出了一种求简单多边形核的新算法。该算法可以较快地对多边形的核为空的情况加以报告,而且在有核的情况下快速求解到核多边形的顶点序列。新的求核算法容易理解,而且易于实现,可以广泛地应用于实际问题。  相似文献   

5.
在对已有的点与多边形位置关系判断算法分析与研究的基础之上,提出一种新的判断点在多边形内外的算法。该算法用三维空间来解决二维平面问题,将二维平面内的点看作是三维空间在平面上的点,从而得出简单的待判断点与多边形顶点之间的坐标关系式。由于符号函数仅仅有三个值,巧妙地利用符号函数的特殊性来表示待判断点与多边形的顶点之间的坐标关系。最终,可以简单地由符号函数之和判断点是否位于多边形内部。程序验证表明,该算法简单、易于实现。同时,将该算法应用于基于RTK GPS定位技术的机动车驾驶证申领场地考试系统中,结果表明,判断准确率高,且实时性好。  相似文献   

6.
吴华意 《计算机学报》1999,22(12):1332-1334
研究了简单多边形P沿正则曲线б作刚体运动时是否与平面上另一固定的简单多边形Q碰撞的判断问题,给出了在最坏情况下最优时间复杂度的完备算法,并在P为凸多边形时,给出了一个基于多边形边界组合运算和环绕系数及其代数性质的简单实用算法。  相似文献   

7.
提出一个如何连接平面上n条线段与一个简单多边形或者简单多边形链的实际问题,并证明了连接平面上线段集S成一简单多边形链的一个充分条件——S中有一条线段连接凸壳CH(S)中不相领顶点。提出了连接平面上线段集S成一简单多边形或者简单多边形链的算法,其基本思想是首先农层计算线段集S的凸壳,并将这些凸壳改变为简单多边形;然后计算各多边形之间的交点,进而删去这些交点;最后俣并若干个简单多边形为一个简单多边形。当S中线段数目n较大时,用分治思想设计分治算法,较好地求解了这个问题。利用计算机求解这个问题具有实际应用价值。  相似文献   

8.
本文引入一种称为“区域树”的二叉树结构来表示若干直线由于相交而形成的对平面的剖分,并以之实现了一个“增加构造”方式的直线剖分平面算法。算法可用于解决许多与平面直线图形有关的问题,本文给出了如下应用实例:点定位问题,半平面公共交问题,简单多边形凸分解问题,简单多边形求交问题。  相似文献   

9.
判断简单多边形的核是否为空的一个快速算法   总被引:6,自引:0,他引:6  
简单多边形的核是位一这形内部的一个点集,从其中任意一点可见多边形的全部边界,文中考查了简单多边形的核在构成同性质,结构已有结果,提出了一个算法,该算法能快速地判断简单多边形是否有核,有核时间以方便地求出核中一个顶点,对算法进行简单扩展,可以求得核中一边及完整的核,给出的算法容易理解,便于实现,可以广泛地应用于一些涉及可见性的问题及许多其它问题中。  相似文献   

10.
有向回路法和网格法:多边形内外点判别的新算法   总被引:4,自引:0,他引:4  
该文把简单多边形视作一个有向回路,利用多边形的环绕方向和区域划分提出了两种判别内外点的新算法:有向回路法和网格法。有向回路法利用了多边形的方向性,在某些情况下可以不必遍历多边形的所有边。该算法程序简单,时间复杂度为O(n),平均性能优于复杂度为Θ(n)的射线法和标号法,但只能处理凸多边形。网格法是有向回路法的改进算法,利用了多边形的方向性和区域划分。网格法将n边形的包围盒划分为(n-1)×(n-1)个网格:如果待处理的点在某个网格内,则仅根据经过该网格的所有边就可以判断该点的内外性。网格法可以处理任意简单多边形,包括带孔的多边形;最坏情况下的时间复杂度为O(lgn),空间复杂度为Θ(n2)。  相似文献   

11.
一个改进的简单多边形凸包算法   总被引:9,自引:0,他引:9       下载免费PDF全文
凸包问题是计算几何的基本问题之一,在许多领域均有应用。该文通过给出反例,证明文献[4]提出的简单多边形凸包的双动线检测算法不能正确求出任意多边形的凸包,并分析了其缺点,提出了一个改进的算法。改进的算法解决了线性算法所不能解决的自交问题,且实现简单。  相似文献   

12.
Consider a simple polygon P containing disjoint convex polygons each of which shares an edge with P. The Zookeeper's Problem then asks for the shortest route in P that visits all convex polygons without entering their interiors. Existing algorithms that solve this problem run in time super-linear in the size of P and the convex polygons. They also suffer from numerical problems.In this paper, we shed more light on the problem and present a simple linear time algorithm for computing an approximate solution. The algorithm mainly computes shortest paths and intersections between lines using basic data structures. It does not suffer from numerical problems. We prove that the computed approximation route is at most 6 times longer than the shortest route in the exact solution.  相似文献   

13.
基于凸剖分的多边形窗口线裁剪算法   总被引:1,自引:0,他引:1  
以不增加新点的方式将多边形剖分为一些凸多边形,并基于这些多边形的边建立二叉树进行管理.裁剪计算时,根据二叉树快速地找到与被裁剪线有相交的凸多边形,然后运用高效的凸多边形裁剪算法进行线裁剪.该方法能自适应地降低裁剪计算的复杂度,使其在O(logn)和O(n)之间变化,并在大多数情况下小于O(n),其中n是多边形边数.虽然该方法需要进行预处理,但在许多应用(如多边形窗口对多边形的裁剪)中,其总执行时间(包括预处理时间和裁剪时间)比已有的不需要预处理的裁剪算法少很多.  相似文献   

14.
集成电路物理设计的测试需随机生成直角多边形以覆盖所有的情况。基于此,提出一种基于解开操作的直角多边形随机生成算法,可应用于超大规模集成电路物理设计算法的测试和分析。该算法随机生成一个点序列,逐一将每对相交的线段解开,直至找不到任何相交线段。对该算法的有穷性作出证明,并以实验证明该算法简单有效。  相似文献   

15.
一般多边形窗口的线裁剪   总被引:17,自引:2,他引:15  
已有的线裁剪算法都是针对矩形窗口或凸多边形窗口的。对于一般的多边形窗口(包括凹多边形)的线裁剪,目前尚无有效的算法。开发这种算法是很必要的,因为它在计算机图形学中有很广泛的应用,如物体的消隐处理等。因此,提出一个对于一般多边形窗口的线裁剪算法,并给出了最优实现。  相似文献   

16.
多边形旋转时的可移动性   总被引:6,自引:2,他引:4  
本文讨论多边形旋转时是否发生碰撞及在发生碰撞时确定最初碰撞顶点和边的问题,给出了相应的最优判定算法与求解算法。  相似文献   

17.
平面多边形方向及内外点判断的新方法   总被引:39,自引:4,他引:35  
提出了一种通过构造一个与平面多边形拓扑同构的、严格凸多边形判断方向的新方法,分析了退化情况并给出了处理方法,基于受约束的三角划分的思想,提出了一种新的判断点在多边形内的准则,并给出了算法,实际应用表明,这两个算法隐定,可靠,而且简单。  相似文献   

18.
寻求简单多边形凸壳的线性时间算法   总被引:7,自引:0,他引:7       下载免费PDF全文
本文提出在线性时间内构造简单多边形顶点凸壳的两种算法。第一个算法的基本思想是利用一种技巧对多边形顶点进行筛选,使剩余顶点的角的大小排成递增序,然后用Graham扫描方法删去非凸壳顶点,最后得到多边形凸壳的顶点序列.第二个算法不断删去多边形的凹点及新产生的 凹点,最后得到凸壳顶点序列。这两种算法简单,易于实现,时间复杂性都是O(n)。  相似文献   

19.
The clipping operation is still the bottleneck of the graphics pipeline in spite of the latest developments in graphical hardware and a significant increase in performance. Algorithms for line and line segment clipping have been studied for a long time and many research papers have been published so far. This paper presents a new robust approach to line and line segment clipping using a rectangular window. A simple extension for the case of convex polygon clipping is presented as well. The presented approach does not require a division operation and uses homogeneous coordinates for input and output point representation. The proposed algorithms can take advantage of operations supported by vector–vector hardware. The main contribution of this paper is a new approach to intersection computations applied to line and line segment clipping. This approach leads to algorithms that are simpler, robust, and easy to implement.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号