IPC平面裁剪算法的设计与实现-《计算机技术与发展》

文章信息/Info

Keywords:: plane clip; Sutherland-Hodgman arithmetic; concave polygon; IPC (Integrated Polygon Clip) arithmetic

摘要:: Sutherland-Hodgman算法是平面裁剪中常用的一种算法,其以顶点序列为基准,对多边形进行逐边裁剪,算法实现简单、效率高,但不适用于对凹多边形进行裁剪。文中以Sutherland-Hodgman算法(文中称为预处理算法)思想为基础,提出了一种亦可对凹多边形进行裁剪的综合多边形裁剪(Integrated Polygon Clip,IPC)算法,实现了对多边形裁剪的统一化操作。介绍了平面裁剪的使用对象,预处理裁剪算法的原理及实现关键步骤,分析了该算法用于对凹多边形裁剪的局限性,在此基础上提出一种适用于任意多边形裁剪的算法。以例证的方式演示了算法的过程,验证了算法的正确性。验证结果表明IPC算法实现了对多边形的统一裁剪。

Abstract:: Sutherland-Hodgman arithmetic is commonly used in clipping plane,that arithmetic implements polygon clipping one side by another in the order of vertex sequence. The arithmetic is easy to realize and high efficiency,but not support for the concave polygon clip-ping. Based upon Sutherland-Hodgman arithmetic (also called preprocessing arithmetic),rise an IPC (Integrated Polygon Clip) arithme-tic,that also can be used in concave polygon clipping,realized the unification of polygon cutting operation. Introduce the objection of plan clipping,the theory of preprocessing arithmetic and its key point in implementation,analyze the arithmetic's limitations,then rise a new arithmetic,supported in all polygon clipping. In the way of illustration,it proves the correctness of the new arithmetic. The result indicates that IPC arithmetic realizes the polygon clipping with consolidated actions.