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

根据多边形窗口各顶点与被裁剪线段的两端点分别在x轴、y轴上的坐标,首次提出窗口边界与被裁剪线段相交的必要条件,有效地排除与被裁剪线段不相交的多边形窗口边界,避免了求交带来的大量乘除法运算.算法思想简单,极大地提高了裁剪的效率.     

一种基于截距的圆形窗口线裁剪算法

在圆形窗口圆心为坐标原点的前提下,确定两端点同时在外切正方形某边 界之外或至少有一端点在圆形窗口之内的线段之后,当线段两端点都在圆形窗口之外时：如 果线段所在直线在x 或y 任意坐标轴上截距的绝对值小于或等于圆半径r,则可快速判断线 段与圆形窗口是否相交;否则,再根据点-线位置关系以及所引切线与线段分别相交外切正 方形边的交点坐标相比较判断线段与圆形窗口是否相交。该方法可以加快线段与圆形窗口的 求交进程,避免复杂的辅助操作,显著提高裁剪效率。     

一种有效的圆形窗口线裁剪算法

根据线段两端点相对于圆形窗口的可能位置讨论裁剪结果。当两端点都在圆形窗口之外时,通过圆切线斜率与线段斜率的比较,及点区域判别来判断线段与窗口的相交情况。在确定线段与圆形窗口有交点的情况下,应用参数化形式求交运算,简化求交方程的构造。实验结果表明,新算法显著提高了裁剪效率。     

基于适应性相关测试和点斜式查表求交的圆形窗口快速裁剪方法

在智能CAD、图形识别与理解等复杂图形应用系统中,由于图元数量多、 图元间关系复杂,且系统实时交互响应要求较高,现有圆形窗口裁剪算法较难满足要求。为 此提出圆形窗口对线段的一种新的快速裁剪算法。该算法由基于切线分隔的圆外线段快速适 应性测试方法、基于最小范围的圆内线段测试方法和基于点斜式查表的线段与窗口圆快速求 交方法三部分组成。通过按端点位置选择适应的测试方法、尽量避免不必要的操作、尽量以 简单操作代替复杂操作等措施,大大提高了圆形窗口对线段的裁剪速度。在图形识别及智能 CAD 等应用中的实验结果表明,采用文中算法可较大地提高效率。     

采用区域编码的椭圆对直线裁剪算法

裁剪算法的核心问题是速度问题,而求裁剪窗口和裁剪对象的交点是影响裁剪速度的主要因素。特别是椭圆对线段的裁剪,由于椭圆的方程是二次的,求椭圆与线段的交点 需要求解一元二次方程,涉及开方运算,非常浪费机器时间。为提高裁剪速度,设计出5位的区域编码,利用此技术能够迅速而准确地判断出椭圆和线段的位置关系。对于完全可见 或显然完全不可见的线段立即做出保留或弃掉的决定,避免求交运算;对于能够明确断定与椭圆相交的线段,采用中点分割算法求椭圆和线段的近似交点,避免求解一元二次方程 和开方运算;对于其他情形的线段通过求解一元二次方程来完成裁剪。基于前述思想设计出的椭圆对线段裁剪算法与现有的同类算法相比,算法实现简单,裁剪速度具有较大提高 。     

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

针对任意多边形窗口内圆的裁剪问题,本文提出一种更加全面、有效的裁剪算法.该方法提出借助x-扫描线算法来判断圆和多边形窗口的位置关系,排除圆完全在窗口内或者窗口外的情况;针对多边形窗口和圆相交的情况,按照逆时针方向依次求出多边形各边与圆的交点;最终,通过判断两点间的关系,决定两点之间画线还是画弧,完成圆的裁剪.实验结果表明,该方法能够有效全面的完成多边形窗口的圆裁剪.     

扫视法的引进及应用

我们引入扫视法的思想,在某种程度上降低了线段求交问题的复杂度。其基本思想是:设想有一纵坐标轴(y)自左向右扫过所有线段,当y处于某一位置时,所有与y接触线段可按此时y值的大小建立一全序关系,若当y轴移近某两相交线段的交点时,这两线段在全序关系中一定相邻。因此只需检查全序关系中相邻两线段是否相交即可。我们可假定线段的左端点为靠近交点的已知点,扫视线在任一状态所接触线段的全序关系可按这些线段的左端点y     

一种圆形窗口裁剪的新方法

通过对直线段相对圆的各种位置关系和深入的研究，提出了一种简单而迅速的圆形窗口裁剪算法。该算法的基本思想是，首先利用圆心到直线段所在直线的距离及从圆心向直线段所引的垂直射线，判别直线段与圆的位置关系，在确定直线段与圆形窗口有交点的情况下，用旋转矢量法求出交点。     

一种高效的一般多边形线段裁剪算法

直线段的裁剪是图形绘制中的基本问题,针对当前主流的直线段裁剪算法,或者不能适应一般多边形窗口的裁剪,或者在复杂裁剪情况下裁剪效率低下的问题,提出了一种高效的一般多边形线段裁剪算法.该算法排除掉明显不在裁剪窗口内的直线段,以及相交于伪交点的情况,再利用改进的交点计数法确定位于窗口内的区间.实验结果表明,该算法不仅具有高效性,还能适应于复杂的裁剪情况.     

基于VC的任意不自相交多边型新裁剪算法

计算机图形学的基础经典裁剪算法的改进是添加一些附加的判断条件以提高效率或只是适用于某种特殊条件环境的应用。对常用的线段裁剪算法和多边形之间的裁剪算法进行简单的原理描述与比较,提出一个新的任意不自相交多边形之间的裁剪算法,该算法以基本线段单元为控制对象,在线段求交中使用梁友栋-barskey算法,然后从裁剪之后的线段单元组中寻找多边形的线段单元组合。分带环多边形之间的裁剪和不带环多边形之间的裁剪来详细描述算法的实施步骤和算法流程;最后用C++语言实现该裁剪算法,结合工程应用解决了多边形裁剪实例,通过测试证明该算法对不自相交多边形之间的裁剪是很有效的,同时使用该算法解决了多边形与折线之间的裁剪问题,改善工程应用。     

凸多边形窗口线裁剪的折半查找算法

在Skala算法基础上,提出了一个更加快速的线裁剪算法．该算法将裁剪窗口分割成4条折线,依据折线的两个端点与被裁剪直线的位置关系,确定折线是否与直线相交;采用折半查找方法,快速确定与直线相交的窗口边界线,并求出交点位置．与Cyrus-Beck算法相比,该算法在乘除法次数和计算速度方面具有非常明显的优势,也比、Skala算法的效率更高。     

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

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

线段相交性问题求解的新算法与原理

本文根据线段的半平面方程特性,提出了一种“多重半平面”原理来研究线段的相交性问题,建立了线段是否相交的判别准则,同时根据该原理给出了两线段求交的新算法－“曲线的双向裁剪算法”。     

2D line and polygon clipping based on space subdivision

This paper introduces a new approach to 2D line and polygon clipping against a rectangular clipping region, using space subdivision into cells, with the clipping region as the central cell. The line segment path is traced through the cells, and entries into and out of the cell corresponding to the clipping region enable computation of the intersection of the line segment with crossed cell edges. Tracing the line segment path is computationally very simple, leading to an algorithm that only computes intersections that the are part of the clipped line segment. The new algorithm is compared to other standard line clipping algorithms with simulations and operation counts.     

圆形窗口的凸多边形裁剪

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

Circular Separability of Polygons

Two planar sets are circularly separable if there exists a circle enclosing one of the sets and whose open interior disk does not intersect the other set. This paper studies two problems related to circular separability. A linear-time algorithm is proposed to decide if two polygons are circularly separable. The algorithm outputs the smallest separating circle. The second problem asks for the largest circle included in a preprocessed, convex polygon, under some point and/ or line constraints. The resulting circle must contain the query points and it must lie in the halfplanes delimited by the query lines. Received October 25, 1998; revised April 21, 1999.