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

摘要

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