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

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

An Efficient Algorithm of Line Clipping Against Polygonal Window Based on the Vertex Encoding

A new concept of the window's vertex encoding is proposed for the first time based on the essential characteristic of the line clipping against polygonal window. The line to be clipped is used as the basis of reference and the polygonal window is divided into three regions (that is, the positive region, the negative region and the near zero region). As a result, the vertexes of a polygonal window can be encoded quickly. The advantages of both vertex encoding of clipping window and traditional line segment encoding are combined in the new algorithm and all the line segments outside the window can be abandoned quickly without intersection calculation. In addition, the edge of the clipping window that intersects with the line segment can be determined directly so that the speedup of the intersection calculation can be achieved. What is more significant, two kinds of singular intersection cases that the line segment goes through the vertexes or the edges of the polygon can be accurately identified and efficiently handled. The experimental results have proved that the new algorithm further improves the clipping efficiency and it has good stability at the same time.