用最小回路求两个简单多边形的交、并、差集

针对求两个简单多边形交、并、差集问题,提出一种基于最小回路的新算法。首先,将初始多边形P和Q初始化为逆时针方向,并将两个多边形交点处的关联边排序。然后,从各个交点出发利用最小转角法搜索最小回路,并根据这些最小回路中包含P和Q边的方向性对它们进行分类。最终,不同类别的最小回路将对应P和Q的交、并、差集。算法的时间复杂度为O((n+m+k)logd),其中n、m 分别是P和Q的顶点数,k是两多边形的交点数,d为将多边形分割的单调链数。算法几何意义明显,对于多边形布尔运算中的重合顶点、重合边等奇异情形,具有较好的适应性。     

确定两个任意简单多边形空间关系的算法

阐述了把简单多边形的边分为奇偶边的新思想,根据一多边形的边与另一多边形的拓朴关系,划分边为5种拓朴类型:内边、外边、重叠边、相交边、复杂边,进而给出了确定两个多边形空间关系的算法,算法的时间复杂度为O((n+m)log(n+m)),其中n、m分别是两输入多边形的顶点数。该算法建立在数学理论基础之上,没有奇异情况需要处理,易于编程实现。算法的主要思想对确定两个简单多面体空间关系亦有参考价值。     

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

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

加强局部简便计算的点在多边形内的高效判定

点在多边形内的检测是计算几何中的一个基本问题,有着广泛的应用需求。已提 出许多方法减少要测试的多边形的边以加速。其中,均匀网格法具有很好的作用,因为各网格 中的边很少,而测试点可迅即定位于一个网格。我们曾提出一种均匀网格法,预计算各网格中 心点位于多边形内/外的属性,然后将测试点与所在网格的中心点连线,检测该连线与多边形的 边的相交情况即可。其预处理和检测的复杂度分别为 O(N)和 O( N ),N 为多边形的边数。本 文在此基础上进一步改进,预计算网格交点位于多边形内/外的属性,然后将测试点与其邻近网 格交点的连线,转换为与坐标轴平行的两条相连直线段,以提高与多边形边求交计算的便捷性。 实验结果表明,可将检测速度提高 2 倍多。     

基于斜率的多边形内外点快速判别算法

多边形的内外点判别是图形学的一个基础算法,为了更大限度地降低其算法复杂度和运算量,提出一种基于斜率的点与多边形位置关系的快速判别法。该方法只需计算该点到多边形各顶点的斜率,然后与多边形各顶点的邻边的斜率进行比较,即可对多边形的内外点快速做出判别。该算法无需复杂的点乘、叉乘、求交、三角函数等运算,在判别过程中仅需平均2n次减法运算和n/2次的除法运算,以及一些比较运算,即可对简单n多边形的内外点做出判别。经测试,该算法快速有效。     

大规模等值线图的任意简单多边形窗口裁剪算法

针对大规模等值线图裁剪算法面临的两个主要问题,如何减少线段求交次数和判别保留部分的起止点,提出一种针对大规模等值线图的任意多边形裁剪算法.该算法首先使用等网格分割方法,在等值线线段与裁剪多边形边之间建立网格索引,减少线段求交次数;同时,在网格数据结构基础上,采用局部射线法,很好地解决了判断交点在裁剪多边形内外时间复杂度过大的问题,使得算法可以快速判断出需要保留(剔除)的等值线部分.本文算法的优点是能够在求出交点的基础上快速获得需要保留(剔除)部分的起止点;同时,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件.本文算法易于实现且高效.     

确定两个任意简单多边形交、并、差的算法

提出了把多边形的边分为奇偶边的新思想，根据输入多边形A，B之间边的拓扑关系，划分A，B边为内边、外边、重叠边3种，揭示A，B与它们的交、并、差之间边的本质联系，进而描述了确定任意两个简单多边形交、并、差算法．算法的时间复杂度为O((n m k)log(n m k))，其中n，m分别是A，B的顶点数，k是两多边形的交点数．算法建立在数学理论基础之上，很好地处理了布尔运算的奇异情形，比如重叠边，边与边相交于边的顶点等情形．本算法易于编程实现。     

基于凸剖分的多边形窗口线裁剪算法

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

简单多边形方向识别的健壮算法

极值顶点前后相邻边矢量叉积法是识别任意简单多边形方向的最优算法 该算法存在的问题是 :当极值顶点前后相邻边夹角接近 0°或 180°时 ,叉积结果接近 0 ,因此存在二义性 ,会导致错误的方向识别 针对现有算法对奇异情形方向判别解决不彻底的问题 定义了多边形极值顶点奇异情形 ,对相邻边夹角接近 0°和 180°两种奇异情形给出了判定方法 ;提出了极点前后点坐标比较法和极点序号大小比较法 ,有效地解决了所有奇异情形下的方向识别问题 ,它们都可以发展成为独立的方向判断算法 实验结果表明 ,该算法简单高效 ,健壮性强 ,时间复杂度为O(n)     

简单多边形凸凹性自识别算法

提出一种基于极值顶点构造凸多边形和矢量叉乘的自动识别简单多边形方向性，凸凹性的算法，该算法在稳定性方面采取了有效的措施，避免因极值顶点的奇异性而导致多边形方向性，凸凹性的错误识别，具有良好的可靠性和稳定性，算法原理直观简单，效率高，时间复杂度为O（n).     

一种快速相容三角剖分算法

提出了一种基于凹多边形凸分解的相容三角剖分方法。先将凹边形分解成凸多边形,再对子多边形进行三角剖分,即可实现相容三角剖分。在最坏的情况下添加O（jk)个辅助点,时间复杂度为O(jn+n log n+jk log n)     

简单多边形分解成凸多边形差组合的算法

本文说明一种把简单多边形分斛成凸多边形的差形式的组合的算法。该算法在求一简单多边形凸包的同时求出凸包和原多边形的差(把差称为内多边形),再对内多边形递归地作同样计算便可得到最终结果。最后证明了运算法的时间复杂性为O(N~2),其中N为原多边形的边数。     

A Fast Hidden-line Removal Algorithm for 3-Dimensional Buildings

ＡＦＡＳＴＨＩＤＤＥＮ－ＬＩＮＥＲＥＭＯＶＡＬＡＬＧＯＲＩＴＨＭＦＯＲ３－ＤＩＭＥＮＳＩＯＮＡＬＢＵＩＬＤＩＮＧＳＱｉｎＫａｉｈｕａｉ；ＴｏｎｇＧｅｌｉａｎｇ；ＺｈａｎｇＮａｎ；ＣｈｅｎＤａｉｌｉｎ；ＬｉＹｕｎｇｕｉ；ＳｈｅｎＷｅｎｄｕＡＦＡＳＴＨＩ...     

An Efficient Adaptive Algorithm for Constructing the Convex Differences Tree of a Simple Polygon

The convex differences tree (CDT) representation of a simple polygon is useful in computer graphics, computer vision, computer aided design and robotics. The root of the tree contains the convex hull of the polygon and there is a child node recursively representing every connectivity component of the set difference between the convex hull and the polygon. We give an O(n log K + K log² n) time algorithm for constructing the CDT, where n is the number of polygon vertices and K is the number of nodes in the CDT. The algorithm is adaptive to a complexity measure defined on its output while still being worst case efficient. For simply shaped polygons, where K is a constant, the algorithm is linear. In the worst case K = O(n) and the complexity is O(n log² n). We also give an O(n log n) algorithm which is an application of the recently introduced compact interval tree data structure.     

Efficient geometric algorithms on the EREW PRAM

We present a technique that can be used to obtain efficient parallel geometric algorithms in the EREW PRAM computational model. This technique enables us to solve optimally a number of geometric problems in O(log n) time using O(n/log n) EREW PRAM processors, where n is the input size of a problem. These problems include: computing the convex hull of a set of points in the plane that are given sorted, computing the convex hull of a simple polygon, computing the common intersection of half-planes whose slopes are given sorted, finding the kernel of a simple polygon, triangulating a set of points in the plane that are given sorted, triangulating monotone polygons and star-shaped polygons, and computing the all dominating neighbors of a sequence of values. PRAM algorithms for these problems were previously known to be optimal (i.e., in O(log n) time and using O(n/log n) processors) only on the CREW PRAM, which is a stronger model than the EREW PRAM     

圆弧和直线段组成的封闭曲线凸凹性快速判定

首先通过构造一中介凸多边形求出封闭曲线的方向，然后根据封闭曲线方向确定顶点及圆弧的凸凹性，进而确定封闭曲线的凸凹性．文中算法快速稳定，其时间复杂度为O(n)，计算量最多为15n 33k 25次判断、12n-6k 14次乘除法、10n 16k 21次加减法、2次求正余弦和k次开方运算，其中n为封闭曲线顶点和圆弧圆心的个数、k为圆弧个数．     

平面上简单多边形平移时确定碰撞部位的最优算法

本文提出一种时间复杂性为O(m+n)的算法,在一个多边形的凸包不和另一个多边形相交的条件下,该算法可确定二个多边形是否相撞,在相撞时可确定全部碰撞部位.本文还证明了确定碰撞部位问题算法的时间复杂性的下界为O(m+n),因而本文提出的算法是最佳的.     

一种新的凸多边形不干涉算法

求解Packing问题、计算机辅助设计、机器人路径规划、虚拟装配等经常用到凸多边形的不干涉算法。该文根据不适合多边形的概念,通过给定的平移规则控制平移多边形中心的移动方向和位移量而计算出两凸多边形的不适合多边形,进而提出了一种新的凸多边形不干涉算法。最后用实例说明了它在布局求解中的应用。文中方法不存在斜率图算法的缺陷,其计算复杂度为O（n+m）。     

一种求凸多边形宽度的优化算法

提出了一种优化的线性时间算法计算凸多边形的宽度。首先证明了凸多边形的宽度只可能介于“点边式”跨度之间,缩小了宽度的计算范围。其次提出了一种距离比较算法,降低了凸多边形跨度的计算量。最后,在“点边式”基本算法和距离比较算法的基础上,提出了计算宽度的优化算法。仿真分析表明,提出的优化算法提高了计算凸多边形宽度的效率,算法的时间复杂性降为O(n)。