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

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

AN EFFICIENT ALGORITHM FOR THE LINE CLIPPING AGAINST A POLYGON

Existing line clipping algorithms are all offered based on a rectangular window or a convex polygonal window. No algorithm for line clipping against a generalized polygon (or concave polygon) is available in the literatures. It is quite valuable to develop such algorithms, because they are of practical use just like the hidden line problem. In this paper, a line clipping algorithm against a generalized polygon is presented. First a reference point is chosen on the line. Then the slope from each vertex of the polygon to the reference point is calculated. Now if the slope of the line is between the slopes from two adjacent vertexes of the polygon to the reference point, the line intersects the edge between the two vertexes. So for each edge, only one division and one subtraction as well as four comparisons are needed.