摘要
多边形裁剪是计算机图形处理及辅助设计的典型课题之一。所谓凹边形裁剪是指凹多边形被矩形窗口裁去位于窗口范围以外的部分。凹多边形经裁剪后的输出应仍然是多边形。但这种多边形应消除退化边界,并且是成(?)的、封闭的、一个或多个多边形。这就是凹多边形裁剪的主要困难。国外已发表了多种凹多边形裁算法。 本文提出一种多边形裁剪的新概念,即不仅凹多边形被矩形窗口裁剪,而且矩形窗口要被凹多边形反裁剪。这是一种相互裁剪算法。 该算法的特点是计算速度快,功能强,程序简单,占用内存少,并能极简便地解决多边形裁剪中最为困难的问题——退化边界问题及多边形的成块输出问题。 该算法用FORTRAN77编程,在微机IBM—PC上运引,取得了良好效果,并已装入机械CAD软件包中。
The major point of reentrant polygon clipping is to remove those parts of the polygon that lie outside the rectangular window. The output of a reentrant polygon clipping is also polygons, that should be eliminated degenerate boundary and closed blocking ones. It is the major difficulty of reentrant polygon clipping.This algorithm presented, a new concept on polygon clipping, It is called that not only reentrant polygon is clipped by rectangular window, but also rectangular window is clipped by reentrant polygon, so it is a interactive clipping algorithm. Rapid computing rate, good functional completeness, Simple programming and saving memony are adventages of the new algorithm. The very difficult problems of reentrant polygon clipping-degenerate boundary and blocked output of closed polygons have been very successfully implemented.The algolithm is coded in FORTRAN 77 and could be executed smoothly on IBM-PC. It has been applied in CAD software package.
