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

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

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

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

平面点集凸壳的实时算法

本文提出平面点集凸壳的实时算法。该算法利用平衡二叉树来代表凸壳的顶点序列,使每次更新凸壳所需计算复杂度为O(log m)。因而n个点的凸壳的计算复杂度为O(n log m),空间复杂度为O(log m),当点服从均匀分布时,算法期望的计算复杂度为O(n)。     

基于EREW的后序遍历二叉树算法

针对单处理器后序遍历二叉树的时间复杂度为O（n）问题,提出了在EREW PRAM并行计算模型下一种后序遍历二叉树的算法。将后序遍历二叉树的边构造一个单链表,使用指针跳越技术对单链表进行表序问题求解,从而得到后序遍历二叉树结点的顺序。得出了运用该算法将时间复杂度从O（n）减少到O（logn）的结论。     

求两个相交凸多边形并的凸包及交的算法

凸多边形交、并求解的难点在于如何维护结果多边形的顶点序列。利用坐标的极值将凸多边形分成几个段,利用凸壳顶点有序性,分段计算凸壳顶点而得到凸壳。两个相交的凸多边形P和Q,求P和Q并的凸壳通过计算它的4个单调段来进行。每个单调段的点是否是凸壳上的点只与2个凸多边形中的同一类型的单调段有关。该算法充分地利用了凸多边形顶点的有序性,使算法的时间复杂度达到最小。     

一个复杂度为max(O(|C||U|),O(|C|2|U/C|))的快速属性约简算法

以基数排序的思想设计了一个新的求U／C的算法,其时间复杂度被降为O（｜C｜｜U｜）．经研究发现,以近似质量作为启发信息并非十分理想,故以快速缩小搜索空间为目的设计了一个新的较为合理的度量属性重要性的计算公式,并给出了该公式的递归计算公式．计算该公式的算法复杂度被降低到O（｜C-P｜｜U＇-Up＇｜）．用新公式作为启发信息,设计了一个时间复杂度为max（o（O（｜C｜｜U｜）,O（｜C^2｜U／C｜））的快速属性约简算法,并用一个实例说明了算法．实验结果表明新算法不仅具有高效性而且能处理大型决策表．     

基于启发式搜索分离向量的凸多面体碰撞检测

碰撞检测是计算机模拟物理过程的基础，在计算机图形学、CAD／CAM、虚拟现实和机器人等领域有着广泛的应用．该文给出了一个新的用于凸多面体碰撞检测的算法——HP-jump．HP-jump建立了一个有效的碰撞检测模型用于报告物体的碰撞，同时提供了一个快速的启发式的策略用于搜索两个凸多面体的分离向量．该算法是利用凸多面体的层次表示来搜索支撑顶点对，用平衡二叉树来记录球面凸多边形的顶点，同时还利用了时间、空间相关性，这些都加速了算法的执行．该文的最后给出了HP-jump与GJK，I-COLLIDE算法的比较．     

一种基于几何关系编码的高效凸多边形线裁剪算法

提出了基于直线与凸多边形几何位置关系编码的一种新的凸多边形线裁剪算法,用凸n边形窗口对m条直线进行裁剪.实验结果表明,当n较大时,该算法所用的时间大约是著名的Cyrus-Beck算法所用时间的1/3左右.如果m的数值也较大时,该算法的速度还将大大提高.所以在实际应用中,新算法提高了裁剪效率并具有很好的稳定性.     

求凸多边形直径的改进算法

求凸多边形直径是计算几何中的一个基本问题,在Preparata-Shamos算法的基础上,提出了采用动态规划和二分查找的算法,不需要对凸多边形进行预处理,使整个算法的时间复杂度降低到O(n)级别。对算法实现的理论分析结果进行了验证,实验结果表明算法具有较高效率。     

构造二叉树的两个改进算法

在数据结构中,已知一棵二叉树的先序序列和中序序列,可唯一确定此二叉树.本文在分析建立二叉树经典算法的时间复杂度的基础上,给出了两个改进算法:①利用哈希函数,使得改进后的算法在最差情况下,时间复杂度由O(n2)降为O(n);②利用栈和控制输入的结点序列构造二叉树,时间复杂度也由O(n2)降为O(n).     

An efficient algorithm for line and polygon clipping

We present an algorithm for clipping a polygon or a line against a convex polygonal window. The algorithm demonstrates the practicality of various ideas from computational geometry. It spendsO(logp) time on each edge of the clipped polygon, wherep is the number of window edges, while the Sutherland-Hodgman algorithm spendsO(p) time per edge. Theoretical and experimental analyses show that the constants involved are small enough to make the algorithm competitive even for windows with four edges. The algorithm enables image-space clipping against windows whose boundaries are convex spline curves. The paper contains detailed pseudo-code implementation of the algorithm and an adaptation of the simulation of simplicity method for handling degenerate cases.     

一种改进的点在多边形内外判断算法

为解决多边形内外算法中BSP树退化为链表的问题,提出一种改进的点在多边形内外的判断算法。在构建水平扫描线的BSP树之前,对水平扫描线按照Y值进行排序,将排好序的水平扫描线按照二分法的顺序插入到BSP树中,其查找时间复杂度为O(lbn)。实验结果表明,该算法在不增加BSP构建时间复杂度的前提下,能够保证BSP树的查找效果总是最优的,且简单易行,具有较好的通用性。     

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

已有的线剪裁算法都是针对矩形窗口或凸多边形窗口的,对于一的多边形窗口（包括凹多边形）的线剪裁,目前尚无有效的算法,而这样的算法却有更普遍的应用意义。该文提出一个对于一般多边形窗口的线剪裁算法。该算法在被裁剪直线的延长线上取一固定点,然后求多边形窗口的每一顶点到该固定点引线的斜率。这样对于每个窗口边只需判断被裁剪直线的斜率是否在该边两顶点到固定点引线斜率之间,就可判定直线与边是否相交,因此,每处理一     

基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法

针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题,减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍,本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立R-树索引和均匀Cell索引,应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数。在此基础上,基于均匀网格索引,提出局部射线法,简化交点出入属性计算和无交点矢量线的取舍。本文在传统算法基础上提出三点改进:首先提出基于两种空间索引模型进行线段求交计算,保证算法在理论上具有较低的时间复杂度;其次,在射线法和网格索引基础上提出局部射线法,使得判断每个交点出入属性的时间复杂度为O(1)～ O(n~(1/2)),与参考文献中的算法相比,此方法的优点是避免判断多边形上顶点的方向;最后,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件。     

一般多边形窗口的线裁剪

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

圆形窗口的凸多边形裁剪

已有的多边形裁剪算法都是针对矩形窗口或凸多边形窗口进行的。但是，在实际应用中，也常常使用圆形窗口对多边形区域进行裁剪和填充。因此，本文提出一个对干圆形窗口的凸多边形区域裁剪法，并且给出作出凸多边形Ｐ在窗口Ｖ之内部分的定理。     

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

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

A comparison of three shadow volume algorithms

This paper describes and compares three different approaches to computing shadows. Each is based on the idea of shadow volumes: basic algorithm, Shadow Volume BSP Tree algorithm, and Shadow Tiling, based on 2D space subdivision. Binary Space Partition trees are used to organise the polygons in the scene in a front-toback order from the point of view of the light source, and then shadows on a polygon are computed by clipping the polygon to the shadow volumes of polygons closer to the light source. The three algorithms differ in their approach to minimising the number of comparisons of a polygon with the shadow volumes of its predecessors, and one of the algorithms represents the total shadow volume itelf by a BSP tree. The algorithms are compared analytically and statistically.