Sutherland-Hodgman多边形裁剪算法
是将多边形顶点以此传递给每一个裁剪阶段,每一个裁剪后的顶点可以理解传递给下一个阶段,这取消了每一次裁剪阶段对组顶点的需求,从而允许边界裁剪子程序并行的执行,最终的输出描述裁剪后的多边形填充区边界的顶点队列
由于算法最终会生成一个输出顶点队列,因此不能生成裁剪图中凹多边形边界的结构,可以为之添加一个处理来获取多个输出顶点队列,从而完成对一般凹多边形的裁剪
总体策略是顺序的每一多边形的一对顶点算给一组裁剪器左、右、上、下一个裁剪器完成对一对顶点的处理后,该边裁剪后留下的坐标值立即送给下一个裁剪器,然后第一个裁剪器处理下一对定带你,这样就可以并行的工作
在用裁剪边界对多边形的边裁剪时有四种情况需要考虑,
- 多边形边的第一个顶点在裁剪边界外部而第二端点在内部
- 两个端点都在裁剪边界内部
- 第一个端点在裁剪内二第二端点在外部
- 两个端点都在裁剪边界外部
要实现将顶点从一个裁剪阶段传递给下一个,每个裁剪器的输出要按照指定的格式进行指定,在每对端点通过四个裁剪器之一时,按下列测试结果为以下裁剪器生成输出
- 多边形边的第一个顶点在裁剪边界外部而第二端点在内部,将多边形的边与窗口百年的交点与第二顶点一起送给下一裁剪器
- 两个端点都在裁剪边界内部,仅将第二个顶点送给下一裁剪器
- 第一个端点在裁剪内二第二端点在外部仅将多变形的边与窗口边的交点送给下一裁剪器
- 两个端点都在裁剪边界外部,不传递任何的顶点信息

注意,使用该算法可能会显示一条对于的直线,这种情况是在裁剪后的多边形有两个或这个分离的部分的时候将会出现,因为只有一个输出顶点