An efficient algorithm to clip a 2D-polygon against a rectangular clip window

Polygon clipping is of great importance in computer graphics.One of the popular algorithms to clip a polygon is Cohan–Sutherland Hodgeman algorithm which is based on line clipping.Cohan–Sutherland Hodgeman algorithm clips the polygon against the given rectangular clip window with the help of line clipping method.Cohan–Sutherland algorithm requires traversing the polygon in anti clockwise direction(positive orientation).In this work we propose an efficient polygon clipping algorithm against a rectangular clip window.Proposed algorithm uses parametric representation of polygon edges.Using the concept of point clipping,we can find required intersection points of edges of polygon with clip window boundaries.Well suited numerical illustrations are used to explain the proposed polygon clipping method.The proposed algorithm is computationally less expensive and comprehensive.

基于顶点编码的多边形窗口线裁剪高效算法

从多边形窗口线裁剪的本质特征出发 ,首次提出窗口顶点编码的新概念 .以被裁剪直线为参照系 ,将多边形窗口划分为正区、负区和近零区三类区域 ,从而快速完成多边形窗口顶点编码 .通过窗口顶点编码与传统的线段编码相结合 ,无须求交即可快速排除大部分窗外线段 ;进一步可以直接得到与直线相交的窗口边 ,加快了求交进程 .更有意义的是 ,通过窗口顶点编码还可以准确判断并高效处理如下两类特殊相交情况 :裁剪直线通过多边形的顶点、裁剪直线通过多边形的边 .实验结果表明 ,新算法提高了裁剪效率并具有很好的稳定性 .

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

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

一般多边形窗口的线裁剪

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

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

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

平面多边形裁剪算法评述

裁剪是计算机图形学中许多重要问题的基础 。

任意多边形窗口的有效线裁剪算法

已有的线剪裁算法大都是针对矩形窗口或凸多边形窗口的,对于任意多边形窗口的线剪裁,目前尚无有效的算法,而这样的算法却有更普遍的应用意义.提出了一个多边形裁剪线段的有效算法,该算法运算高效、稳定.

凸多边形窗口线裁剪的新算法

凸多边形窗口的线裁剪是用多边形窗口裁剪多边形的基础 .为此 ,提出了凸 n边形窗口的线裁剪新算法 .新算法与 Cyrus- Beck算法相比 ,当 n较大时 ,新算法的乘法大约只有 Cyrus- Beck算法的 1/ 3且仅用 4次除法 .因此 ,新算法大大地加快运算速度 .

基于圆形窗口的简单多边形裁剪算法

提出了一种新颖而实用的圆形窗口Ｖ对多边形Ｐ的裁剪算法。它将多边形Ｐ的边视为有向线段，通过引入多边形顶点的入边和出边交点的概念，深入研究了Ｐ被Ｖ裁剪后的区域确定问题。

基于矩阵乘法的多边形窗口线裁剪算法

提出一种任意多边形窗口线裁剪新方法,它不解方程而通过矩阵乘法得到窗口和线段的交点。对于一组待裁剪线段,该方法先做简单的包围盒预处理,将那些和包围盒无交的线段排除在求交之外;然后引进齐次坐标,构造一组仿射变换矩阵,通过矩阵乘法对任意多边形窗口和待裁剪线段实施连续仿射变换,完成窗口和直线求交操作并从矩阵中获得交点;经过交点排序、配对等过程,得到多边形裁剪线段的结果。经实验对比,该新方法有效,并且速度得以提高。

圆形窗口的凸多边形裁剪

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

一个改进的多边形窗口裁剪算法及其应用

本文的裁剪策略是,巧妙地利用窗口与线段两种不同数学描述,将有效交点的判定、求交运算及包含性检验,归结为三个条件的判别。这三个条件形式简明,运算量小,整个裁剪过程,只有在存在有效交点时才做除法,把除法以及其它计算量减少到最低限度,从而大大提高了裁剪效率。经多次用不同类型的多边形窗口试验表明,该算法程序量少,运算速度快,不仅可以高效地裁剪,而且适用于几何图形并、交、差,立体消隐中有关多边形与线段的处理,还可以在工程CAD中利用零件图生成装配图。

基于点区域分布的多边形窗口线裁剪算法

通过判断多边形窗口顶点相对于裁剪线段所在直线的区域分布,明确窗口的哪些边与裁剪线段所在直线相交;再通过判断裁剪线段两端点相对于这些多边形窗口相交边的区域分布,最后确定裁剪线段与多边形窗口的实际交点。避免大量不必要的求交运算和其他复杂的辅助操作。实验结果表明:新算法提高了裁剪效率,对各种情况都能快速、正确地得到结果。

关于凸多边形的修剪算法研究

读文研究并提出了一种凸多边形的裁剪算法，它不同于传统的多边形裁剪算法，仅需对视口之外顶点所关税的边检查与视口的相交性。裁剪速度快，简单易行。

圆形窗口直线段裁剪算法

提出了一种具有普遍适用意义的圆形窗口的直线段裁剪算法.利用圆外切正方形先排除大部分位于圆形窗口外的线段,再将位于圆内接16边形中的线段接受为完全位于圆形窗口内的线段,然后,通过平移、旋转几何变换二次排除位于圆形窗口外的线段,从而使参与求交的直线段减少,提高算法效率.试验结果表明,该算法高效、稳定.

圆形窗口的凸多边形填充算法

给出了一种基于圆形窗口的凸多边形填充算法，它集裁剪与填充功能于一体，也可完成单纯地裁剪功能。

基于端点与交点编码的矩形窗口多边形裁剪新算法

从矩形窗口裁剪任意多边形的本质特征出发,提出多边形各边端点编码技术。通过对多边形各边端点的一次及二次编码,可快速得到所有窗内边并舍弃绝大部分窗外边,还可快速判断该端点是内点还是外点。在已获取的窗内边、相交边的交点以及交点编码的基础上,可以得到正确的裁剪结果。同时考虑了矩形窗口与多边形相互包容的特殊情形。实验结果表明,新算法稳定可靠,实现了对任意凹凸多边形的裁剪,具有通用性强、算法简捷、裁剪效率较高的优点。

圆形窗口上一般多边形的内/外裁剪算法

本文详尽地分析了圆形窗口上一般多边形(凹/凸)的内/外裁剪问题,并通过构造顶交表、圆交表、入点表、出点表等给出了一般多边形(凹/凸)的内/外裁剪算法。

基于交点参数的任意多边形窗口对圆裁剪

现有的任意多边形窗口的圆裁剪算法存在算法繁琐等问题,且没有考虑多边形是带内环的情况,本文提出了一种基于交点参数分析的多边形窗口的圆裁剪算法,只需对多边形边与圆的交点在边所在直线的参数值进行比较,即可判断出交点的进出点特性,交点排序后,通过进点出点组合,即可获得裁剪窗口内的圆弧,完成裁剪.编程实践的实例结果也证明本算法是切实可行的,本文的方法既适用于仅有外环的一般多边形裁剪窗口,也适用于带内环的任意多边形裁剪窗口的圆裁剪,因此,算法更具有通用性.

用于DCS的任意多边形截幅方法

在DCS中,对绘图数据不仅需要有矩形截幅功能,而且还常常碰到需要进行任意多边形截幅的情况。本文引入了广义多边形截幅窗口的概念,提出了一种以方位角判别点与多边形关系的方法;为了提高截幅运算的速度,给出了适用于DCS的自动生成截幅窗口的原理和方法,最后还讨论了对圆形符号进行截幅处理的问题。使用本文提出的任意多边形截幅方法不仅使DCS的图形处理功能更加完善,而且可改进采样方法,避免了地籍图上跨越界址线的地物符号可能出现的不合理现象。