【计算几何】clipper库之扫描线、活动边、输出区域-平芜编程栈

本文涉及知识点

数学几何

裁剪算法

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_queue<int64_t> scanline_list_：扫描线的纵坐标。默认是大根堆，故扫描线的y是从大到小。
minima_list_：记录局部最小值，数学的局部最大值。本文不采用数学的说法。
outrec_list_：记录最终的结果，区域。

扫描线

观察结论：一，交点没扫描线。二，顶点全部有扫描线。
红色扫描线是初始化扫描线，两个多边形局部最小值。
黄色扫描线是新的局部最小值。当处理新的局部最小值时，如果左右边界非水平，则左右边界的的top.y是新的扫描线。InsertLocalMinimaIntoAEL函数处理。
绿色扫描线是更新边，添加的扫描线。DoTopOfScanbeam，扫描线和线段bottom相同时，将线段t加到扫描线。
红色圆圈处是局部最大点，所有扫描线加了两次，InsertLocalMinimaIntoAEL和DoTopOfScanbeam各加一次。

活动边y大的是bom，y小的是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

处理完44

44 处理完局部最小点

处理完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%的进士能当上堂官(副部及更高)；能当上堂官的举人只有十余人。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。