简单多边形可见点问题的快速求解算法

简单多边形可见点问题是计算几何的基本问题之一。在许多领域均有应用。本文在参考现有算法的基础上,提出了改进的方法,文中方法先用射线法求取第一个可见点,然后利用文中设定的规则搜索后续可见点。     

基于顶点可见性的凹多边形快速凸分解算法

凹多边形的凸分解问题是计算几何的基本问题之一,在许多领域均有应用。现有算法大多为全局部分算法,而局部分自救研究的很少。全局方法由于耗时太多,而不能满足所有工程应用的需要。目前局部剖分算法中最经典的是Ｒｏｇｅｒｓ算法,但由于其存在许多缺陷而在实际应用中受到限制。文中在多边形顶点可见性基础上,提出了新的局部剖分方法。凹点的局部几何特性,通过引入权函数从凹点的可见点串中选取适当的点引剖分线,或者利用凹点     

简单多边形可见核的扫描线填充算法

简单多边形的可见核是位于多边形内部的一个点集，可见核内的任意一点与多边形边界上的任意一点的连线都处于该多边形的内部。由于可见核具有这一性质，对简单多边形的可见核的计算在很多方面都有着适用。本文考察了简单多边形的核的性质与特点，在结合了其他相关的可见核顶点的算法之后，提出了一个对可见核进行填充的快速算法。这一算法由于通过避免在填充多边形的核之前进行计算可见核的顶点的过程，从而可以较快地对可见核进行填充。这一算法不仅容易理解，而且便于实现。     

多边形Voronoi图填充算法在3D打印中的研究

为了解决3D打印路径填充往复扫描时模型外壁发生形变、减少打印机喷嘴空驶及减少打印变加速次数,人们引用Voronoi图理论进行层面路径规划.这种方法现在在简单多边形的路径规划中已得到很好的应用,但是在对复杂度较高多连通多边形路径规划上容易产生大量的数据冗余.为了解决这些问题,结合利用图像分割边缘化处理技术,对构造复杂度较高的多边形Voronoi图路径填充的算法进行了改进,并用Python语言实现了该算法.     

多边形序列的最短路径算法

给定平面上一个含k个简单多边形的序列及一个起点p和一个终点q,近似地计算一条最短路径使得它开始于p点,然后按指定的次序访问每个多边形,最后终止于q点.如果多边形是两两不相交且是非凸的,那么此问题至今还没有算法解.应用一种R算法,给出复杂性为κ(ε)·O(n)的一种近似算法,这里n是给定多边形的顶点总数,函数κ(ε)定义为L0与L的差与ε的商,其中L0是初始路径长度,L是最优路径长度,ε是计算精确度.给定的R算法稍作修改也能用来近似地解决3个NP完全或NP困难的三维欧几里德最短路径问题(ESP).它们的复杂性均为κ(ε)·O(k),这里k是含有所给定的障碍物的堆的层数.     

简单多边形内线燃烧动态轨迹算法

为了模拟草场上线燃烧的动态过程,提出了分别由位于点可视区域的圆弧和方向可视区域的线段组成的多边形线的燃烧轨迹模型.首先利用点可视和方向可视技术实现简单多边形的深度方向可视划分;然后在可视划分的子多边形内,通过计算有向线段与视点或视线的极小?极大距离来实现视线到任意线段或任意可视多边形的极小?极大最短路径的计算;最后分别在点可视区域计算出有向线段与圆的17种位置关系,在方向可视区域计算出有向线段与直线的9种位置关系,再根据这些位置关系确定入点和出点,画出燃烧轨迹的圆弧或线段,并通过VC++编程实现了整个算法.算例结果表明,该算法可以计算不同时刻的火场燃烧轨迹、不同地点的燃烧时间以及火场燃烧的最远距离和最长时间等.     

基于凸片段分解和格网的点在多边形中的可见边检测

检测点在多边形中的可见边是计算几何中的一种基本计算,文中对此提出一种加速算法.首先对多边形进行凸片段分解,以利用点在凸多边形中可见边的快速计算;然后利用格网结构实现由近及远的计算,避免处理被遮挡的凸片段.该算法可基于格网结构方便地进行并行处理,并可统一处理含空洞和不含空洞的多边形,其预处理时间复杂度为O(n),空间复杂度也是很低的O(n),而检测的时间复杂度在O(logn)～O(n)之间自适应变化,其中n为多边形的边数.     

多边形外部Voronoi 图顶点和边数的上界

在对多边形P的外部Voronoi图的性质进行研究的基础上,将其表示成树结构并利用树结构的性质给出了其所含Voronoi顶点和边数的上界n+s+2×h-r-t-2和2×n+2×s+3×h-r-t-3,其中,h,n和s分别是P的边界、边和凸顶点的数目;t和r分别是位于P的凸包上的顶点和边数.同时,给出了每一个Voronoi区域所包含顶点和边数的平均值估计.文中工作在基于多边形外部Voronoi图的碰撞检测算法的复杂度分析方面有着重要作用.     

带权值目标点的可见覆盖求解算法

针对传统的艺术画廊模型及其模型的变形在实际应用中无法处理诸如可用守卫数受限、只需监控离散目标点等情形,提出一种基于带权值目标点的可见覆盖的变形模型及其求解算法.首先利用角扫描技术得到每个目标点的可见多边形,然后通过对这些可见多边形进行几何求交、几何求差操作来得到若干等价目标可见区域,再依据每个区域对应的可见目标点集将所提出的变形模型转化为经典的集合最大权值覆盖问题,最后利用整数线性规划方法对其求解,得到最终需要的守卫数及放置位置.大量的实验结果表明,该算法是正确和有效的.     

复杂多边形窗口的多边形裁剪的改进算法

多边形裁剪是计算机图形学中较为热点研究的问题,针对复杂多边形窗口的复杂多边形裁剪提出一个可靠有效算法。算法通过添加虚边来消去孔洞,并且为恢复裁剪结果的原貌改进了遍历方法。新的遍历算法只需遍历多边形一次就可巧妙地求得所有裁剪结果,并恢复带孔洞的裁剪结果的内外边界的拓扑结构,无需解环、并环,也不用对裁剪边界重新组合。     

一般多边形的碰撞算法

文章首先对凸多边形碰撞问题进行了仔细的考查，然后对一般多边形碰撞问题进行了深入细致的研究，在此基础上提出了求解凸多边形碰撞问题和一般多边形碰撞问题的最优算法。     

一个有效的多边形裁剪算法

多边形裁剪与线剪裁相比具有更广泛的实用意义,因此它是目前裁剪研究的主要课题.提出了一个多边形裁剪多边形的有效算法.其中的多边形都可以是一般多边形,既可以是凹多边形,也可以是有内孔的多边形.该算法不仅可以求多边形的"交"(多边形裁剪),而且可以求多边形的"并"和"差".它是以所提出的一系列新方法和新技术为基础而形成的.首先,该算法使用单线性链表数据结构,与其他使用双链表或树结构的算法相比,具有占用空间少及处理速度快的特点;其次,找到了两个多边形之间进、出点之间的关系.再通过合理的数据结构处理,减少了算法对多边形链表的遍历次数,而且允许多边形既可以按顺时针方向也可以按逆时针方向输入.最后,判断和计算交点是裁剪算法的主要工作.提出了一个具有最少计算量的交点判断和计算方法,进一步加快了算法的运行速度.与其他同类算法进行了比较,结果表明,新算法具有最简单的结构和最快的执行速度.     

一种有效的任意多边形裁剪算法

介绍了一种基于改进的Weiler算法的任意多边形裁剪算法，该算法通过引入图形部件和合理的数据结构来组织裁剪后的多边形，减少了遍历多边形顶点链表的次数，并有效减少求交点的时间，具有占用存储空间少和处理速度快的特点。经过实例测试，算法对同时处理单个和多个任意多边形裁剪具有良好的稳定性、可靠性和较高的效率。     

A Parallel Algorithm for the Visibility of a Simple Polygon Using Scan Operations

This paper describes a parallel algorithm for computing the visible portion of a simple planar polygon with N vertices from a given point on or inside the polygon. The algorithm accomplishes this in O(k log N) time using O(N/log N) processors, where k is the link-diameter of the polygon in consideration. The link-diameter of a polygon is the maximum number of straight line segments needed to connect any two points within the polygon, where all line segments lie completely within the polygon. The algorithm can also be used to compute the visible portion of the plane given a point outside of the polygon. Except in this case, the parameter k in the asymptotic bounds would be the link diameter of a different polygon. The algorithm is optimal for sets of polygons that have a constant link diameter. It is a rather simple algorithm, and has a very small run time constant, making it fast and practical to implement. The interprocessor communication needed involves only local neighbor communication and scan operations (i.e., parallel prefix operations). Thus the algorithm can be implemented not only on an EREW PRAM, but also on a variety of other more practical machine architectures, such as hypercubes, trees, butterflies, and shuffle exchange networks. The algorithm was implemented on the Connection Machine as well as the MasPar MP- 1, and various performance tests were conducted.     

基于拓扑映射的点集在凸多边形内外判断算法

通过拓扑映射 ,点在凸多边形内外的判别可以转化为映射点在射影直线上的位置关系问题 .首先通过设置中心点 ,获取凸多边形各顶点的拓扑映射点 ,对于每个检测点 ,根据其映射点与顶点拓扑映射点的相对位置关系 ,即可确定检测点位于多边形哪条边的范围内 ;然后将检测点与该边进行包围盒测试 ,对于点在边包围盒外的情况 ,只需根据比较判别即可得到结果 ,对于点在边包围盒边界上或内部的情况 ,则需通过叉积运算进行判别 .该方法几何意义清晰 ,实验结果表明 ,该算法运行可靠 ,对于单个点或多点组成的点集均有较高的检测速度 .     

GIS环境中一种高效的多边形剪裁方法

论文在Weiler算法的基础上提出了一种在GIS环境中计算非凸多边形之让的剪裁区域的新算法。该算法前提是多边形已根据梯形分解法被分解成若干个梯形,计算过程与Weiler算法类似。该算法主要通过减少交点的计算时间来提高Weiler算法的效率。在GIS这种具有频繁拓扑关系运算的环境中可以很好地提高运算效率,最后通过实验验证,即使在接近最坏的情况下,该算法也优于传统的Weiler算法。     

一个有效的多边形裁剪算法

通过对相交多边形交点的完备分类,给出了一个可靠的任意多边形裁剪算法.结果表明,该算法非常稳定可靠,且能处理各种奇异情况.     

任意多边形窗口的圆裁剪算法

圆的裁剪广泛应用于诸如计算机图形学、二维计算机动画以及机器人运动学等领域.讨论了圆关于任意多边形窗口的一个裁剪算法,按逆时针方向依次求出多边形裁剪窗口的每条边与圆的交点并且保证交点正确排序,对于交点序列中的任意两相邻的交点,采用"中点检测法"来判定以它们为端点的圆弧与裁剪窗口的位置关系,最后给出完整的裁剪算法.实现结果表明,不论从效率还是稳定性方面都取得了比较理想的效果.