当前位置： 首页 > news >正文

第10章：布尔运算执行流程

news 2026/5/3 9:48:19

第10章：布尔运算执行流程

10.1 概述

本章将详细分析 Clipper 执行布尔运算的完整流程，从输入数据的准备到最终结果的构建，深入理解 Vatti 算法在 Clipper 中的实现。

10.2 执行流程概览

用户调用 Execute()│▼
┌─────────────────────────┐
│   ExecuteInternal()     │
│         │               │
│         ▼               │
│      Reset()            │← 重置状态
│         │               │
│         ▼               │
│   PopScanbeam(botY)     │← 获取最低扫描线
│         │               │
│         ▼               │
│ InsertLocalMinimaIntoAEL│← 插入初始边
│         │               │
│         ▼               │
│ ┌───────────────────┐   │
│ │   主处理循环      │   │
│ │       │           │   │
│ │ ProcessHorizontals│   │
│ │       │           │   │
│ │ ProcessIntersections│  │
│ │       │           │   │
│ │ ProcessEdgesAtTop │   │
│ │       │           │   │
│ │ InsertLocalMinima │   │
│ └───────────────────┘   │
│         │               │
│         ▼               │
│    后处理阶段           │
└─────────────────────────┘│▼BuildResult/BuildResult2│▼返回结果

10.3 Reset 方法

internal virtual void Reset()
{m_CurrentLM = m_MinimaList;if (m_CurrentLM == null) return;m_Scanbeam = null;LocalMinima lm = m_MinimaList;while (lm != null){// 添加局部极小值的 Y 坐标到扫描线InsertScanbeam(lm.Y);// 重置左边界TEdge e = lm.LeftBound;if (e != null){e.Curr = e.Bot;e.OutIdx = Unassigned;}// 重置右边界e = lm.RightBound;if (e != null){e.Curr = e.Bot;e.OutIdx = Unassigned;}lm = lm.Next;}m_ActiveEdges = null;
}

功能：

  1. 设置当前局部极小值指针
  2. 初始化扫描线列表
  3. 重置所有边的状态
  4. 清空活动边表

10.4 主处理循环

while (PopScanbeam(out topY) || LocalMinimaPending())
{ProcessHorizontals();m_GhostJoins.Clear();if (!ProcessIntersections(topY)) return false;ProcessEdgesAtTopOfScanbeam(topY);botY = topY;InsertLocalMinimaIntoAEL(botY);
}

10.4.1 循环条件

  • PopScanbeam(out topY)：获取下一个扫描线 Y 坐标
  • LocalMinimaPending()：检查是否还有未处理的局部极小值

10.4.2 每次迭代的操作

  1. ProcessHorizontals：处理当前扫描线上的水平边
  2. ProcessIntersections：计算并处理边交点
  3. ProcessEdgesAtTopOfScanbeam：处理到达顶部的边
  4. InsertLocalMinimaIntoAEL：插入新到达的局部极小值

10.5 IsContributing 判断

判断边是否对输出多边形有贡献：

private bool IsContributing(TEdge edge)
{PolyFillType pft, pft2;// 根据边的类型获取填充规则if (edge.PolyTyp == PolyType.ptSubject){pft = m_SubjFillType;pft2 = m_ClipFillType;}else{pft = m_ClipFillType;pft2 = m_SubjFillType;}// 根据填充规则检查边的缠绕数switch (pft){case PolyFillType.pftEvenOdd:if (edge.WindDelta == 0 && edge.WindCnt != 1) return false;break;case PolyFillType.pftNonZero:if (Math.Abs(edge.WindCnt) != 1) return false;break;case PolyFillType.pftPositive:if (edge.WindCnt != 1) return false;break;default: // pftNegativeif (edge.WindCnt != -1) return false; break;}// 根据裁剪类型和另一类多边形的缠绕数判断switch (m_ClipType){case ClipType.ctIntersection:switch (pft2){case PolyFillType.pftEvenOdd:case PolyFillType.pftNonZero:return (edge.WindCnt2 != 0);case PolyFillType.pftPositive:return (edge.WindCnt2 > 0);default:return (edge.WindCnt2 < 0);}case ClipType.ctUnion:switch (pft2){case PolyFillType.pftEvenOdd:case PolyFillType.pftNonZero:return (edge.WindCnt2 == 0);case PolyFillType.pftPositive:return (edge.WindCnt2 <= 0);default:return (edge.WindCnt2 >= 0);}case ClipType.ctDifference:if (edge.PolyTyp == PolyType.ptSubject)// Subject 边：必须在 Clip 外部switch (pft2){case PolyFillType.pftEvenOdd:case PolyFillType.pftNonZero:return (edge.WindCnt2 == 0);case PolyFillType.pftPositive:return (edge.WindCnt2 <= 0);default:return (edge.WindCnt2 >= 0);}else// Clip 边：必须在 Subject 内部switch (pft2){case PolyFillType.pftEvenOdd:case PolyFillType.pftNonZero:return (edge.WindCnt2 != 0);case PolyFillType.pftPositive:return (edge.WindCnt2 > 0);default:return (edge.WindCnt2 < 0);}case ClipType.ctXor:if (edge.WindDelta == 0)// 开放路径switch (pft2){case PolyFillType.pftEvenOdd:case PolyFillType.pftNonZero:return (edge.WindCnt2 == 0);case PolyFillType.pftPositive:return (edge.WindCnt2 <= 0);default:return (edge.WindCnt2 >= 0);}elsereturn true;}return true;
}

10.5.1 判断逻辑图解

Intersection（交集）：Subject ∩ Clip边有贡献 ⟺ 边在自己类型的多边形内 AND 在对方类型的多边形内Union（并集）：Subject ∪ Clip边有贡献 ⟺ 边在自己类型的多边形边界上 AND 不在对方类型的多边形内Difference（差集）：Subject - ClipSubject边有贡献 ⟺ 边在Subject内 AND 不在Clip内Clip边有贡献 ⟺ 边在Clip边界上 AND 在Subject内Xor（异或）：Subject ⊕ Clip边有贡献 ⟺ 边在任一多边形边界上

10.6 SetWindingCount 方法

计算边的缠绕数：

private void SetWindingCount(TEdge edge)
{TEdge e = edge.PrevInAEL;// 找到同类型的前一条边while (e != null && ((e.PolyTyp != edge.PolyTyp) || (e.WindDelta == 0))) e = e.PrevInAEL;if (e == null){// 没有同类型的边在前面PolyFillType pft;pft = (edge.PolyTyp == PolyType.ptSubject ? m_SubjFillType : m_ClipFillType);if (edge.WindDelta == 0) edge.WindCnt = (pft == PolyFillType.pftNegative ? -1 : 1);else edge.WindCnt = edge.WindDelta;edge.WindCnt2 = 0;e = m_ActiveEdges;  // 从头计算 WindCnt2}else if (edge.WindDelta == 0 && m_ClipType != ClipType.ctUnion){edge.WindCnt = 1;edge.WindCnt2 = e.WindCnt2;e = e.NextInAEL;}else if (IsEvenOddFillType(edge)){// 奇偶填充规则if (edge.WindDelta == 0){bool Inside = true;TEdge e2 = e.PrevInAEL;while (e2 != null){if (e2.PolyTyp == e.PolyTyp && e2.WindDelta != 0)Inside = !Inside;e2 = e2.PrevInAEL;}edge.WindCnt = (Inside ? 0 : 1);}else{edge.WindCnt = edge.WindDelta;}edge.WindCnt2 = e.WindCnt2;e = e.NextInAEL;}else{// 非零/正向/负向填充规则if (e.WindCnt * e.WindDelta < 0){// 前一条边正在减少缠绕数if (Math.Abs(e.WindCnt) > 1){if (e.WindDelta * edge.WindDelta < 0) edge.WindCnt = e.WindCnt;else edge.WindCnt = e.WindCnt + edge.WindDelta;}elseedge.WindCnt = (edge.WindDelta == 0 ? 1 : edge.WindDelta);}else{// 前一条边正在增加缠绕数if (edge.WindDelta == 0)edge.WindCnt = (e.WindCnt < 0 ? e.WindCnt - 1 : e.WindCnt + 1);else if (e.WindDelta * edge.WindDelta < 0)edge.WindCnt = e.WindCnt;else edge.WindCnt = e.WindCnt + edge.WindDelta;}edge.WindCnt2 = e.WindCnt2;e = e.NextInAEL;}// 计算 WindCnt2（另一类多边形的缠绕数）if (IsEvenOddAltFillType(edge)){while (e != edge){if (e.WindDelta != 0)edge.WindCnt2 = (edge.WindCnt2 == 0 ? 1 : 0);e = e.NextInAEL;}}else{while (e != edge){edge.WindCnt2 += e.WindDelta;e = e.NextInAEL;}}
}

10.6.1 缠绕数计算示例

         AEL 顺序 →
扫描线 ─────e1─────e2─────e3─────e4─────│      │      │      │↓      ↓      ↓      ↓
Subject:  +1     +1      -1     -1
WindCnt:   1      2       1      0e1: WindCnt = WindDelta = 1
e2: WindCnt = e1.WindCnt + WindDelta = 1 + 1 = 2
e3: WindCnt = e2.WindCnt + WindDelta = 2 + (-1) = 1
e4: WindCnt = e3.WindCnt + WindDelta = 1 + (-1) = 0

10.7 IntersectEdges 方法

处理两条边的交点：

private void IntersectEdges(TEdge e1, TEdge e2, IntPoint pt)
{bool e1Contributing = (e1.OutIdx >= 0);bool e2Contributing = (e2.OutIdx >= 0);#if use_xyzSetZ(ref pt, e1, e2);
#endif#if use_lines// 处理开放路径的交点if (e1.WindDelta == 0 || e2.WindDelta == 0){// ... 开放路径处理逻辑 ...return;}
#endif// 更新缠绕数if (e1.PolyTyp == e2.PolyTyp){// 同类型多边形if (IsEvenOddFillType(e1)){int oldE1WindCnt = e1.WindCnt;e1.WindCnt = e2.WindCnt;e2.WindCnt = oldE1WindCnt;}else{if (e1.WindCnt + e2.WindDelta == 0) e1.WindCnt = -e1.WindCnt;else e1.WindCnt += e2.WindDelta;if (e2.WindCnt - e1.WindDelta == 0) e2.WindCnt = -e2.WindCnt;else e2.WindCnt -= e1.WindDelta;}}else{// 不同类型多边形if (!IsEvenOddFillType(e2)) e1.WindCnt2 += e2.WindDelta;else e1.WindCnt2 = (e1.WindCnt2 == 0) ? 1 : 0;if (!IsEvenOddFillType(e1)) e2.WindCnt2 -= e1.WindDelta;else e2.WindCnt2 = (e2.WindCnt2 == 0) ? 1 : 0;}// 根据贡献状态处理输出// ... 详细的输出处理逻辑 ...
}

10.8 后处理阶段

10.8.1 方向修正

foreach (OutRec outRec in m_PolyOuts)
{if (outRec.Pts == null || outRec.IsOpen) continue;if ((outRec.IsHole ^ ReverseSolution) == (Area(outRec) > 0))ReversePolyPtLinks(outRec.Pts);
}

确保输出多边形具有正确的方向：

  • 外轮廓：正面积（逆时针）
  • 孔洞：负面积（顺时针）

10.8.2 JoinCommonEdges

处理共边的多边形：

private void JoinCommonEdges()
{for (int i = 0; i < m_Joins.Count; i++){Join join = m_Joins[i];OutRec outRec1 = GetOutRec(join.OutPt1.Idx);OutRec outRec2 = GetOutRec(join.OutPt2.Idx);if (outRec1.Pts == null || outRec2.Pts == null) continue;if (outRec1.IsOpen || outRec2.IsOpen) continue;OutRec holeStateRec;if (outRec1 == outRec2) holeStateRec = outRec1;else if (OutRec1RightOfOutRec2(outRec1, outRec2)) holeStateRec = outRec2;else if (OutRec1RightOfOutRec2(outRec2, outRec1)) holeStateRec = outRec1;else holeStateRec = GetLowermostRec(outRec1, outRec2);if (!JoinPoints(join, outRec1, outRec2)) continue;// 处理连接结果if (outRec1 == outRec2){// 分割多边形outRec1.Pts = join.OutPt1;outRec1.BottomPt = null;outRec2 = CreateOutRec();outRec2.Pts = join.OutPt2;// ... 更新孔洞状态 ...}else{// 合并多边形outRec2.Pts = null;outRec2.BottomPt = null;outRec2.Idx = outRec1.Idx;// ...}}
}

10.8.3 输出清理

foreach (OutRec outRec in m_PolyOuts)
{if (outRec.Pts == null) continue;else if (outRec.IsOpen)FixupOutPolyline(outRec);  // 清理开放路径elseFixupOutPolygon(outRec);   // 清理闭合多边形
}

FixupOutPolygon：移除重复点和共线边。

10.8.4 DoSimplePolygons（可选）

if (StrictlySimple) DoSimplePolygons();

处理自相交的多边形，将其分割为简单多边形。

10.9 BuildResult 方法

构建最终的 Paths 结果：

private void BuildResult(Paths polyg)
{polyg.Clear();polyg.Capacity = m_PolyOuts.Count;for (int i = 0; i < m_PolyOuts.Count; i++){OutRec outRec = m_PolyOuts[i];if (outRec.Pts == null) continue;OutPt p = outRec.Pts.Prev;int cnt = PointCount(p);if (cnt < 2) continue;Path pg = new Path(cnt);for (int j = 0; j < cnt; j++){pg.Add(p.Pt);p = p.Prev;}polyg.Add(pg);}
}

10.10 本章小结

本章详细分析了 Clipper 布尔运算的执行流程：

  1. 初始化：Reset 准备所有数据结构

  2. 主循环：

    • 处理水平边
    • 计算和处理交点
    • 处理扫描线顶部的边
    • 插入新的局部极小值

  3. 核心判断：

    • IsContributing：判断边是否贡献输出
    • SetWindingCount：计算缠绕数
    • IntersectEdges：处理边交点

  4. 后处理：

    • 方向修正
    • 连接处理
    • 输出清理
    • 简单多边形处理

  5. 结果构建：

    • BuildResult：构建 Paths
    • BuildResult2：构建 PolyTree

上一章：Clipper类结构 | 返回目录 | 下一章：活动边表管理

http://www.jsqmd.com/news/622402/

相关文章：

  • NotaGen AI音乐生成：5分钟快速部署，零基础创作古典音乐
  • 深入理解 V8 引擎：C++ 与 JavaScript 的跨界传送门
  • 2026停车场照明改造品牌推荐及行业选择参考 - 品牌排行榜
  • 为什么AI时代真正稀缺的不是代码, 而是 Idea. 我因此做了一个“发现+判断”的项目
  • 2026年GESP3月认证C++五级真题解析
  • 第11章：活动边表 AEL 管理
  • SQL UPDATE 语句详解
  • 别再死记硬背了！用Python代码复现Photoshop 27种混合模式（附完整源码）
  • HTML5中Mediastream实现摄像头画面实时捕获
  • PowerPaint-V1 Gradio实现.NET图像处理应用：跨平台开发实战
  • 2026年4月酸性清洗剂品牌推荐，润滑剂/酸性清洗剂/氢氧化钠/碱性清洗剂/过氧乙酸，酸性清洗剂企业选哪家 - 品牌推荐师
  • SpringCloud快速入门--GateWay路由网关与Config配置中心型
  • 第13章：水平边处理算法
  • 如何轻松重置IDE试用期：终极JetBrains插件配置指南
  • NVIDIA Profile Inspector完全指南：解锁显卡隐藏性能的终极教程
  • Phi-4-mini-reasoning实战：分析并优化开源项目中的C++代码结构
  • Autovisor：智慧树课程自动化学习终极指南
  • 装了 QClaw 之后，我卸掉了好几个 Mac 软件
  • Phi-4-mini-reasoning完整指南：含health接口检测、日志定位、重启命令
  • 第14章：输出多边形构建
  • Eino-Workflow 实战详解
  • AI证书在面试中的价值分析
  • 投资者情绪指数（ISI与CICSI）二十年趋势解析：从数据到市场洞察
  • ICPC竞赛中的字符串优化技巧：以香港站K题LR String为例，详解预处理与加速查询
  • 【AI创意应用】AI创意， 个人实践的内容和结果汇总
  • all-MiniLM-L6-v2新手入门：从零到一搭建语义相似度计算环境
  • DCT-Net卡通化实战案例：从自拍到漫画头像的完整生成流程
  • 写作柚助力高效论文写作之路
  • SOONet模型Node.js后端服务开发：环境配置与API接口封装
  • Flash内容访问难题如何解决？CefFlashBrowser提供完整兼容方案