本文涉及知识点数学 几何说明本文所附图片x的正方向向右y的正方向向上和Cad的坐标系同右手坐标系。DoTopOfScanbeam通过e遍历整个活动边表。更新curr_x即活动边与扫描线交点的横坐标。e.top.y扫描线局部最大值DoMaximae.top.y扫描线不是局部最大值如果是活动边将点增加到所属区域。更新边。水平边入队简单成员structLocalMinima{Vertex*vertex;PathType polytype;constboolis_open;LocalMinima(Vertex*v,PathType pt,boolopen):vertex(v),polytype(pt),is_open(open){}};PathType 是Subject还是clips。is_open是多义线折线还是闭合多边形。AddOpenSubject 加的是折线其它两个函数是多边形。voidAddSubject(constPaths64subjects){AddPaths(subjects,PathType::Subject,false);}voidAddOpenSubject(constPaths64open_subjects){AddPaths(open_subjects,PathType::Subject,true);}voidAddClip(constPaths64clips){AddPaths(clips,PathType::Clip,false);}C代码可以通过不同的函数决定布尔运算的第一个参数是否是开闭对象。IsHotEdge是否是活动边有所属区域。Vertexstruct Vertex {Point64 pt;Vertex* next nullptr;Vertex* prev nullptr;VertexFlags flags VertexFlags::Empty;};通过next指针可以逆时针访问所有端点prev指针顺时针访问所有端点。VertexFlagsenum class VertexFlags : uint32_t { Empty 0, OpenStart 1, OpenEnd 2, LocalMax 4, LocalMin 8 }; VertexFlags::LocalMax 字面的上意思是局部最大点即y值比前驱后继顶点的y值都大。调试的结果是局部最小值。if(curr_v-pt.yprev_v-pt.ygoing_up){prev_v-flags(prev_v-flags|VertexFlags::LocalMax);going_upfalse;}elseif(curr_v-pt.yprev_v-pt.y!going_up){going_uptrue;AddLocMin(locMinList,*prev_v,polytype,is_open);}going_up 是否是上升状态。上升状态变下降状态或下降状态变上升状态时前驱节点一定时极值。 y相等时状态不变。 同理VertexFlags::LocalMin 实际上是局部最大值。去掉重复点templatetypenameTinlinevoidStripDuplicates(PathTpath,boolis_closed_path){path.erase(std::unique(path.begin(),path.end()),path.end());if(is_closed_path)while(path.size()1path.back()path.front())path.pop_back();}无需也不能排序。相邻的重复点才能删除。符号函数inlineintTriSign(int64_tx)// returns 0, 1 or -1{return(x0)-(x0);}x0: 1-01x0: 0-00x0: 0-1-1线段和扫描线的交点inlineint64_tTopX(constActiveae,constint64_tcurrentY){if((currentYae.top.y)||(ae.top.xae.bot.x))returnae.top.x;elseif(currentYae.bot.y)returnae.bot.x;elsereturnae.bot.xstatic_castint64_t(nearbyint(ae.dx*(currentY-ae.bot.y)));// nb: std::nearbyint (or std::round) substantially *improves* performance here// as it greatly improves the likelihood of edge adjacency in ProcessIntersectList().}求线段ae和扫描线currentY的交点横坐标。双向循环链表节点结构structOutPt{Point64 pt;// 顶点坐标OutPt*nextnullptr;// 逆时针下一个节点OutPt*prevnullptr;// 逆时针上一个节点OutRec*outrec;// 所属的输出区域HorzSegment*horznullptr;// 关联的水平段可选OutPt(constPoint64pt_,OutRec*outrec_):pt(pt_),outrec(outrec_){nextthis;prevthis;}};扫描线算法中的一条活动边structActive{Point64 bot;Point64 top;int64_tcurr_x0;//current (updated at every new scanline)doubledx0.0;intwind_dx1;//1 or -1 depending on winding directionintwind_cnt0;intwind_cnt20;//winding count of the opposite polytypeOutRec*outrecnullptr;//AEL: active edge list (Vattis AET - active edge table)// a linked list of all edges (from left to right) that are present// (or active) within the current scanbeam (a horizontal beam that// sweeps from bottom to top over the paths in the clipping operation).Active*prev_in_aelnullptr;Active*next_in_aelnullptr;//SEL: sorted edge list (Vattis ST - sorted table)// linked list used when sorting edges into their new positions at the// top of scanbeams, but also (re)used to process horizontals.Active*prev_in_selnullptr;Active*next_in_selnullptr;Active*jumpnullptr;Vertex*vertex_topnullptr;LocalMinima*local_minnullptr;// the bottom of an edge bound (also Vatti)boolis_left_boundfalse;JoinWith join_withJoinWith::NoJoin;};几何信息topbot当前活动边的上下端点。当扫描线到达下端时激活到达上端时移除。curr_x 扫描线与当前活动边交点的横坐标。会随着扫描线的变化而变化。dx:斜率的倒数。绕数信息wind_dx边的方向对绕数的贡献。y大的端点是bottom,y小的是top从bom到bot,dx小的那条边逆时针 1dx大的那条边(顺时针 -1。左边界-1右边界1。wind_cnt当前扫描线位置上这条边所在类型的累积绕数。wind_cnt2相反多边形类型比如 clip 和 subject的绕数。subject是主体对象clip是裁剪对象如差集就是subject 减 clip对象。归属信息outrec 这条边当前属于哪个输出环。两套链表AEL 和 SELAELActive Edge ListActive*prev_in_aelnullptr;Active*next_in_aelnullptr;按 curr_x 从左到右排序表示当前扫描线上所有活动边SELSorted Edge ListActive*prev_in_selnullptr;Active*next_in_selnullptr;用于在扫描线顶部重新排序边也用于处理水平边其它辅助字段Active* jump nullptr; 跳跃指针跳跃指针用于快速跳过一段已知顺序的边。下一个非相交活动边。Vertex* vertex_top nullptr;边的上端对应的顶点对象保存该顶点的更多信息。非水平线段和top相等水平线还要继续查看。LocalMinima* local_min nullptr; 这条边所属的局部极小点。局部极小点是扫描线算法的起点从它开始激活一整串边。bool is_left_bound false; 标记这条边是否为某个“边束”的左边界。Vatti 中局部极小点会引出一对左右边左边界决定多边形内部方向。极端情况下(cur_x相同,方向相同或相反)活动边的顺序。JoinWith join_with JoinWith::NoJoin;表示这条边在合并阶段是否需要与其它边连接比如用于处理复杂交点、水平边、重叠边时的连接策略。相连的边和sel有关。SetWindCountForClosedPathEdge 核心代码没有路径类型subject或clip)相同的左邻e2由其它分支处理本代码无需考虑。奇偶填充方式走其它分之。//NonZero, positive, or negative filling here ...//if es WindCnt is in the SAME direction as its WindDx, then polygon//filling will be on the right of e.//NB neither e2.WindCnt nor e2.WindDx should ever be 0.if(e2-wind_cnt*e2-wind_dx0){//opposite directions so e is outside e2 ...if(abs(e2-wind_cnt)1){//outside prev poly but still inside another.if(e2-wind_dx*e.wind_dx0)//reversing direction so use the same WCe.wind_cnte2-wind_cnt;else//otherwise keep reducing the WC by 1 (ie towards 0) ...e.wind_cnte2-wind_cnte.wind_dx;}else//now outside all polys of same polytype so set own WC ...e.wind_cnt(IsOpen(e)?1:e.wind_dx);}else{//e must be inside e2if(e2-wind_dx*e.wind_dx0)//reversing direction so use the same WCe.wind_cnte2-wind_cnt;else//otherwise keep increasing the WC by 1 (ie away from 0) ...e.wind_cnte2-wind_cnte.wind_dx;}e.wind_cnt2e2-wind_cnt2;e2e2-next_in_ael;// ie get ready to calc WindCnt2wind_dx 左侧-1右侧1不会是0。无论那种填充方式缠绕数为0是不需要保留故活动边表的边wind_cnt不为0。e2-wind_cnt * e2-wind_dx 0 有两种情况,e都在e2内部。一,e2是左侧e2所在的path是逆时针。二e2是右侧e2所在path是顺时针。e2-wind_dx * e.wind_dx 0如果左右侧不同则范围完全相同故e.wind_cnte2-wind_cnt;左右侧相同e.wind_cnte2-wind_cnte.wind_dx;e右边的点比e2右边的点多穿过e。e在e2所在path外部abs(e2-wind_cnt) 1 说明可能在其它同类型被裁剪对象、裁剪对象活动边之中。异侧时缠绕数相同。同侧相差边e:等于1不收其它活动边影响。故e.wind_cnt(IsOpen(e)?1:e.wind_dx);处理交点BuildIntersectListif(right-curr_xleft-curr_x)新增活动边删除活动边已处理curr_x 的大小发生变化说明有交点。ProcessIntersectList 处理交点if(!EdgesAdjacentInAEL(*node_iter)){node_iter2node_iter1;while(!EdgesAdjacentInAEL(*node_iter2))node_iter2;std::swap(*node_iter,*node_iter2);}找到第一个相交边在活动边表相邻的交点并处理。最坏复杂度O(nn)平均复杂度O(n)。如果有交点则一定有边相邻的交点两条扫描线之间不会有增加线段故p3所在线段至少一条和p1p2的活动边相交不失一般性令和p1的活动边相交。则问题变成p1p3之间是否有其它活动边。p1p3比p1p2短不断迭代直到两点之间没有空隙。AdjustCurrXAndCopyToSEL所有的currx都会更新。OutRecowner OutRec* 所属的父 OutRec主要用于孔洞与外环的嵌套关系front_edge Active* 当前 OutRec 在 AEL 中的前边界边左侧back_edge Active* 当前 OutRec 在 AEL 中的后边界边右侧SwapOutrecsvoidSwapOutrecs(Activee1,Activee2){OutRec*or1e1.outrec;OutRec*or2e2.outrec;if(or1or2){Active*eor1-front_edge;or1-front_edgeor1-back_edge;or1-back_edgee;return;}if(or1){if(e1or1-front_edge)or1-front_edgee2;elseor1-back_edgee2;}if(or2){if(e2or2-front_edge)or2-front_edgee1;elseor2-back_edgee1;}e1.outrecor2;e2.outrecor1;}SwapOutrecs 的作用是交换两条活动边 e1 和 e2 所归属的输出环 OutRec。当扫描线处理到 e1、e2 的交点时两条边会穿过对方原来属于 e1 的区域现在归 e2反之亦然所以它们的 outrec 要互换。同时OutRec 里记录的前后边界边指针也要跟着换。ti表示第i线段向上bi表示第i条线段向下。在快要到达交点c之前有三个区域。一t4b5。二t5t1b6。三,t6b2.刚刚经过交点。一t4b6。三t6b5t3.三,t5b2。AddLocalMaxPoly一个区域处理结束。 e2拼接到e1指针会置空。e2.outrec-front_edgenullptr;e2.outrec-back_edgenullptr;e2.outrec-ptsnullptr;SwapSides翻转一个输出环 OutRec 的方向左右边界互换并调整其输出点链表的起始指针。inlinevoidSwapSides(OutRecoutrec){Active*e2outrec.front_edge;outrec.front_edgeoutrec.back_edge;outrec.back_edgee2;outrec.ptsoutrec.pts-next;}InsertLocalMinimaIntoAEL(核心函数建议好好体会)对每个 bot_y 处的 LocalMinima├─ 创建 left_bound下降边wind_dx -1├─ 创建 right_bound上升边wind_dx 1├─ 必要时交换左右使 left_bound 真正在左├─ 只有一条边时把它当 left_bound├─ left_bound 插入 AEL├─ 设置绕数判断 contributing├─ 有 right_bound│ ├─ 插入 right_bound 到 AEL│ ├─ 若 contributing创建新 OutRecAddLocalMinPoly│ ├─ 处理 right_bound 与后续边的交点│ └─ 水平边推入水平队列 / 普通边插入扫描线└─ 无 right_bound 但有 contributing└─ 开始开放路径└─ 处理 left_bound水平边入队 / 普通边插入扫描线CleanCollinearif(IsCollinear(op2-prev-pt,op2-pt,op2-next-pt)(op2-ptop2-prev-pt||op2-ptop2-next-pt||!preserve_collinear_||DotProduct(op2-prev-pt,op2-pt,op2-next-pt)0))条件一必须满足条件二到五满足任意一条。条件一当前点、前一点、后一点共线。条件二当前点和前驱点重合。条件三当前点和后继点重合。条件四preserve_collinear_ 为假。条件五三个形成180度角如下图。DoSplitOp如果不满足拆分条件说明这个自交只是一个小凸起或退化情况直接删除 splitOp 和 splitOp-next相当于去掉这个小环。FixSelfIntersects这个不是通用的处理自交的函数是对扫描线的结果进行处理。由于Clipper是整数坐标故删除共线点不会产生误差但计算交点时会四舍五入产生误差。数学模型计算机中故只需要判断AC是否相交无法判断所有边。TrimHorz从一条水平活动边出发沿路径向下检查所有 y 相同的顶点把它们合并到这条水平边里。类名、函数名翻译类名函数名翻译ReusableDataContainer64可复用数据容器LocalMinima局部最小值Scanline扫描线Duplicate复制、创建副本Uncouple使分离preserve保留collinear共线的scanbeam扫描带扫描束hot_edge条活动边如果它的 outrec 非空并且它被 OutRec 记录为 front_edge 或 back_edge它就是热边。CheckJoinLeft 与 CheckJoinRight 解析当两条热边在扫描线处理过程中变得非常接近、几乎共线或重叠时判断它们是否应该合并join如果应该就执行合并操作。扩展阅读计算几何为骨排样优化为魂作品亲士CAD工具箱经典文章推荐二维排样万物皆数学查阅鄙人的博文请点击博文下载学院导航活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。