本文涉及知识点数学 几何裁剪算法Sutherland-Hodgman (1974)这是最经典的算法之一。它的核心限制是裁剪多边形必须是凸多边形因此它非常适合矩形窗口裁剪这类简单场景。Weiler-Atherton (1977)这是第一个能够处理任意多边形包括凹多边形、带孔多边形 的通用算法。它通过构建多边形间的图结构来追踪边界功能强大但数据结构和实现都比较复杂。Vatti (1992)Vatti算法同样面向任意多边形并且是首个能够处理自相交多边形的算法之一。它基于扫描线Scanline思想功能非常全面但算法本身也相当复杂。Greiner-Hormann (1998)这个算法可以被看作是Weiler-Atherton的简化版本。它的目标是提供一种更简单、更快速的方式来处理任意包括自相交多边形。其核心数据结构是双向链表比Weiler的图结构和Vatti的复杂状态机要轻量得多。Clipper使用的是Vatti clipping算法和计算几何讲的略有区别。ClipperBase成员变量actives_ 是 AEL活动边表 的头指针sel_ 是 SEL排序边表 的头指针intersect_nodes_ 记录交点。horz_seg_list_水平段候选列表horz_join_list_水平连接配对列表std::priority_queueint64_t scanline_list_ 扫描线的纵坐标。默认是大根堆故扫描线的y是从大到小。minima_list_ 记录局部最小值数学的局部最大值。本文不采用数学的说法。outrec_list_记录最终的结果区域。扫描线观察结论一交点没扫描线。二顶点全部有扫描线。红色扫描线是初始化扫描线两个多边形局部最小值。黄色扫描线是新的局部最小值。当处理新的局部最小值时如果左右边界非水平则左右边界的的top.y是新的扫描线。InsertLocalMinimaIntoAEL函数处理。绿色扫描线是更新边添加的扫描线。DoTopOfScanbeam扫描线和线段bottom相同时将线段t加到扫描线。红色圆圈处是局部最大点所有扫描线加了两次InsertLocalMinimaIntoAEL和DoTopOfScanbeam各加一次。活动边y大的是bomy小的是bot。当扫描线是bom时将top放到扫描线队列。局部最小点的纵坐标大于相邻点的纵坐标故无法通过此法增加到扫描线队列故必须提前放到扫描线队列。非局部最小点p一定可以被枚举到性质一p到两个或一个临接点p1,p2。p到p1和p2不会都下降否则p就是局部最小点。不失一般性令p到p1上升。性质二从p到p1方向移动一定会遇到局部最小点令遇到的第一个局部最小点是q。比如y最大的点。性质三p到q一定全部是上升路径否则p到q之间有其它局部最小点与假设矛盾。即q直接或间接能找到p。活动边图例扫描线选中的是当前扫描线蓝色的是当前活动边。扫描线207处理完毕处理完164处理完119处理完81处理完46处理完4444 处理完局部最小点处理完23处理完21处理完1处理完-40处理完-47观察结论当扫描线经过局部最小点时增加一组活动边。观察结论当扫描线经过局部最大点时一组活动边消失。显然交点也会影响活动边交点会交换活动边的顺序。并集的输出区更改扫描线之前扫描线处于被选中状态蓝线、紫色是输出区域。填充规则非0FillRule::NonZero.扫描线纵坐标207。扫描线164扫描线119扫描线81扫描线46扫描线44两个区域第二个区域只有一个点扫描线23扫描线21扫描线1扫描线-40扫描线-47扫描线-64异或输出区扫描线23扫描线21扫描线1扫描线-40扫描线-47交集的输出区域扫描线23之前全部为空。扫描线23扫描线扫描线1扫描线-40差集的输出区域扫描线44扫描线23扫描线21扫描线1扫描线-40扫描线-47扩展阅读计算几何为骨排样优化为魂作品亲士CAD工具箱经典文章推荐二维排样万物皆数学查阅鄙人的博文请点击博文下载学院导航活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。