第一部分：引言与概述

“你是否曾想过，把 Boost.Polygon 这头‘性能怪兽’塞进 Qt 的绘图管线里，让它在 QWidget 上乖乖跑起来，还要做到‘代码一眼能看懂、后续随便改’？”

今天这篇实战笔记，就带你拆解一套“Boost.Polygon + Qt”的完整范例。作者用不到 1 500 行头文件，把点、多边形、多边形集合、连通性提取、属性合并五大高频场景全部封装成“step-by-step”的可视化 Demo。读完你不仅能学会：

1. 如何把任意几何类型注册到 Boost.Polygon 的概念体系；
2. 如何让它与 QPainter 无缝衔接；
3. 还能观察到现代 C++ 模板元编程在“性能与可扩展性”上的四两拨千斤。

第二部分：代码展示与整体解析

（以下代码已合并，顺序经过微调，方便一次性阅读；原文 8 个头文件保持不变，仅删去重复宏保护行）

// --------------  0. 公共配置  --------------
#include <QPainter>
#include <boost/polygon/polygon.hpp>
namespace gtl = boost::polygon;
using namespace boost::polygon::operators;

// --------------  1. 自定义点 QPoint  --------------
namespace boost { namespace polygon {
template <> struct geometry_concept<QPoint> { typedef point_concept type; };
template <> struct point_traits<QPoint> { /* … */ };
template <> struct point_mutable_traits<QPoint> { /* … */ };
}} // namespace boost::polygon

// --------------  2. 自定义多边形 QPolygon  --------------
namespace boost { namespace polygon {
template <> struct geometry_concept<QPolygon> { typedef polygon_concept type; };
template <> struct polygon_traits<QPolygon> { /* … */ };
template <> struct polygon_mutable_traits<QPolygon> { /* … */ };
}} // namespace boost::polygon

// --------------  3. 自定义多边形集合 CPolygonSet  --------------
using CPolygonSet = std::deque<QPolygon>;
namespace boost { namespace polygon {
template <> struct geometry_concept<CPolygonSet> { typedef polygon_set_concept type; };
template <> struct polygon_set_traits<CPolygonSet> { /* … */ };
template <> struct polygon_set_mutable_traits<CPolygonSet> { /* … */ };
}} // namespace boost::polygon

// --------------  4. 功能函数（逐步绘图） --------------
bool PointUsage(QPainter&, int step);          // BoostPoint.h
bool PolygonUsage(QPainter&, int step);        // BoostPolygon.h
bool BoostPolygonSetUsage(QPainter&, int step);// BoostPolygonSet.h
bool test_point(QPainter&, int step);          // CustomPoint.h
bool test_polygon(QPainter&, int step);        // CustomPolygon.h
bool test_polygon_set(QPainter&, int step);    // CustomPolygonSet.h
void ConnectivityTest();                       // ConnectivityExtractionUsage.h
void PropertyMergeUsage(QPainter&);            // PropertyMergePainter.h

文字流程图（单线程、单窗口）

main()
 ├─ 构造 QPainter
 ├─ for step = 1..N
 │   ├─ PointUsage(painter, step)          // 原生 Boost 点
 │   ├─ PolygonUsage(...)                  // 原生 Boost 多边形
 │   ├─ BoostPolygonSetUsage(...)          // 原生多边形集合
 │   ├─ test_point(...)                    // 自定义 QPoint
 │   ├─ test_polygon(...)                  // 自定义 QPolygon
 │   ├─ test_polygon_set(...)              // 自定义 CPolygonSet
 │   └─ PropertyMergeUsage(...)            // 属性合并可视化
 └─ ConnectivityTest()                     // 仅控制台输出

第三部分：核心知识点逐行详解

1. 把 Qt 类型“塞进”Boost.Polygon——概念注册三板斧
   关键行：

   template <> struct geometry_concept<QPoint> { typedef point_concept type; };
   

   为什么：Boost.Polygon 采用“概念→特质”的泛型设计：只要你的类型满足 point_concept 的语法要求（get / set / construct），就能无痛享受算法库全部功能。
   知识点：C++20 之前“Concept”靠语法检查实现，Boost.Polygon 2009 年的实现就是“静态多态”的教科书。
   可能的坑：忘记同时提供 point_traits（只读）与 point_mutable_traits（可写），会导致 gtl::set(pt, orient, value) 编译失败。

2. 让 QPainter “看懂”Boost 几何——无痛转换
   关键行：

   QPolygon qPoly;
   for (auto it = gtl::begin_points(poly); it != gtl::end_points(poly); ++it)
       qPoly << QPoint(gtl::x(*it), gtl::y(*it));
   

   为什么：Boost.Polygon 提供统一的顶点迭代器，与 Qt 的容器完全解耦；你只需要一次拷贝即可。
   性能提示：若只想绘制、不想备份，可自定义 QPaintEngine 直接读取 Boost 迭代器，省掉一次 QVector 拷贝，但复杂度陡增，多数场景“先拷贝再绘”是性价比最高的折中。

3. 多边形集合运算——operator+ 与 operator^ 的背后
   关键行：

   ps4 += ps + ps2;        // 并集
   ps3 = ps * ps2;         // 交集
   xor_result = ps ^ ps2;  // 对称差
   

   知识点：Boost.Polygon 采用“扫描线 + 活跃边表”经典算法，时间复杂度 O((n+k) log n)，其中 k 为交点数目；对轴对齐矩形（polygon_90_set_data）还能再优化到 O(n log n)。
   边界坑：浮点坐标需改用 polygon_set_data<double> 并打开 GTL_USE_TUPLE，否则整数溢出直接 core dump。

4. 属性合并（Property Merge）——模板元编程的小高潮
   关键行：

   typedef std::map<std::set<int>, polygon_set_type> property_merge_result_type;
   pm.merge(result);
   

   设计亮点：

   • 用 std::set<int> 作为“属性键”，天然支持多标签；
   • 通过 lookup_polygon_set_type 元函数在编译期决定返回类型（90° 矩形走 polygon_90_set_data，普通多边形走 polygon_set_data），实现“同一份代码，两种优化”。
     拓展思考：如果属性不是 int，而是自定义结构体，只要实现 operator< 即可无缝替换；这就是“策略模式 + 模板”的威力。

5. 连通性提取——45° 与 90° 的“邻接”差异
   关键行：

   ce.extract(graph);
   

   原理：对输入矩形做“膨胀 1 像素 → 扫描线求交 → 缩回”的 morphological 操作，得到真正的像素级邻接关系；connectivity_extraction_90 只认边接触，connectivity_extraction_45 把对角线也纳入。
   性能提示：算法内部复用同一套扫描线框架，所以即便开启 45°，时间增长也不到 15%，却能解决“对角相邻也算连通”的 PCB 走线、游戏地图场景。

第四部分：设计模式与优化讨论

设计模式盘点

• Concept-Traits（静态多态）——核心主线
• Strategy——property_merge_90 vs property_merge
• Template Method——所有 test_* 函数统一 step 参数，方便外部循环驱动

优点

1. 零虚函数开销：全部靠模板内联，Release 版性能接近手写 C。
2. 可扩展性极强：新加一种“自定义几何”只需写 traits，无需改算法。
3. 可视化友好：一步一图，调试时肉眼即可验证算法正确性。

可改进方向

1. 错误处理：目前所有算法假定输入合法，可追加 is_valid() 检查并抛出 std::runtime_error，让 UI 层弹出友好提示。
2. 增量更新：在交互式场景中（用户拖拽矩形），可把 polygon_set_data 换成 polygon_90_set_data<int, std::vector, property_merge_90>，并调用 insert(...) / erase(...) 做局部更新，避免全量重建。
3. 多线程：扫描线算法天然按行独立，可尝试对 y 方向做并行分区；Boost.Polygon 官方实验分支已提供 parallel_polygon_set_op，开启 TBB 即可。

第五部分：总结与扩展

回顾：本文范例用“概念注册 → 算法调用 → Qt 可视化”三步走，把 Boost.Polygon 的硬核能力包装成“能看还能改”的教程级代码；你学到的不仅是几何算法，更是“模板元编程 + 静态多态”在实际工程中的落地套路。

实际应用

• PCB/IC 布局布线中的 DRC（设计规则检查）
• 地图栅格化、行政区划合并与裁切
• 游戏服务器的“视野”与“碰撞”粗筛

扩展阅读

1. Boost.Polygon 官方文档与示例
   https://www.boost.org/doc/libs/release/libs/polygon/
2. “Sweep-Line Algorithms for Proximity Problems” —— 经典扫描线综述，助你深入理解交集/合并背后的 O(n log n) 优雅实现。

把代码拉下来，把 step 调成 1，亲自跑一遍，你会发现：
“原来看似高大上的计算几何，也能像搭积木一样好玩。”
代码地址: https://gitcode.com/ma-xiaoxu/qtBoostDemo