基于编码与分类技术的任意多边形裁剪新算法

首次将编码与分类技术引入任意多边形的矩形窗口裁剪,通过编码分类技术根据多边形边与裁剪窗口的相对位置将边分为六类。采用一次编码技术获取一类窗内边,舍弃二类窗外边,得到必须求交的三类边;采用二次编码技术舍弃四类窗外边,得到需要求交的五、六类边;进一步提出裁剪窗口顶点相对于多边形的分类,利用窗口顶点分类和多边形边的编码特征快速处理三类、五类、六类窗口相交边。通过编码分类技术减少了多边形裁剪的运算量,并有效地维护了多边形的拓扑关系。实验结果表明算法稳定可靠,可实现对任意凹凸多边形的裁剪,在多边形与窗口的各种相对位置均具有较高的运算效率。

A High Efficient Polygon Clipping Algorithm Against Rectangular Window Based on Encoding and Classification Technique

Encoding classification technique is firstly applied to polygon-clipping against rectangle window,through which edges of polygon is divided into six kinds according to position relationship between polygon and rectangle window.The first edge located in window is obtained,and the second is abandoned,and the third is sure to need intersection calculation,by use of once encoding technique.Then the forth edge is discarded,the fifth and the sixth are brought about ,which perhaps need for intersection calculation,on basis of twice encoding technique.Further the vertexes of rectangle window are classified,which is based on its position whether in polygon or not.So the third,the fifth,the sixth edge can be quickly handled as well as according to encoding character of polygon edges.As a result,encoding classification is not only reduce calculation in polygon -clipping but also maintain correct topological attributes.The experiment results have proved that new algorithm,which can be used for general concave polygon and convex polygon,further improves the clipping efficiency and it has good stability at same time.