C17 / Qt6 实现 · 端点 / 圆心 / 交点 / 切点捕捉 · 切线几何 · 与画线交互同源本文档聚焦 sketch-cad-cppC17 / Qt 6.10.1 / MinGW-w64 GCC 13.1.0本轮新增的「直线绘制智能捕捉」功能画直线时端点可吸附到五种几何特征点——直线/弧的端点、圆/弧的圆心、两图元的交点、以及由已知另一端点向圆作切线的切点。重点探讨「几何计算如何保证精度」「与现有画线交互如何无缝集成」「精度如何通过无界面自测确保」。更庞大的架构基线见综合文档。验证基线干净构建 0 警告 0 错误核心自测 139 项全通过其中 §19 共 14 项用例专门覆盖本功能。一、五种捕捉方式的几何归类需求列出的五种点按其几何来源可归为两类计算引擎避免在 UI 层各自实现捕捉类型几何来源计算引擎依赖anotherEnd?直线/弧端点图元控制点snapHandles取真实点否圆/弧圆心图元控制点snapHandles 取 center否两图元交点图元求交intersectElements复用否切点切于圆由外部点作切线tangentPointsFromPointToCircle是首端点关键决策交点直接复用既有的 geo::intersectElements直线×直线、直线×圆、圆×圆、含圆弧角度过滤均已实现不另写求交逻辑——再次印证「core 层几何下沉」的价值新交互只是换个触发条件底层零新增代码。二、切点几何由外部点向圆作切线需求 1 的「直线与选定圆相切端点为该圆切点」在数学上等价于已知一个端点 P已确定的另一端点求从 P 向圆 (C, r) 所作切线的切点 T。T 必须满足 |T−C|r 且 PT ⟂ CT。int tangentPointsFromPointToCircle(const Vec3 P, const Vec3 C, double r, Vec3 out[2]) { const double d hypot(P.x-C.x, P.y-C.y); // 计算点P到圆心C的距离 if (d r - 1e-9) return 0; // 点在圆内无实切线 const double phi atan2(P.y-C.y, P.x-C.x); // 圆心指向P的方向角 const double alpha acos(min(1.0, r/d)); // 半张角 out[0] C r*(cos(phialpha), sin(phialpha)); // 第一个切点 out[1] C r*(cos(phi-alpha), sin(phi-alpha)); // 第二个切点 return 2; // 返回切点数量 }2.1 边界与精度点在圆内dr返回 0——不存在实切线自测 §19.1 验证。点在圆上d≈ralpha≈0两切点重合于 P 投影点退化为单点不崩溃。弧的切点必须落在其角度扫掠范围内对 arc 类型再用 angleInSweep 过滤圆则恒通过。垂直性由构造保证T−C 与 P−T 的点积理论为 0自测 §19.1 断言 |dot|1e-6 且 |T−C−r|1e-6把「在圆上且垂直」钉死。三、综合捕捉 snap()最近者胜snap(elems, w, otherEnd, tol) 在容差 tol 内收集所有候选端点/圆心、交点、切点取离光标 w 最近者。之所以「最近距离优先」而非「按类型排优先级」是因为它最贴近主流 CAD 的体感且实现最省端点/圆心遍历每个可见图元的 snapHandles逐个 consider圆仅 center弧含 center起/终直线两端矩形四角多边形/样条全顶点。交点先以 distanceToElement(A,w)tol*6 粗筛靠近光标的图元O(n²) 但 n 通常很小再对筛选后的两两对求交并 consider。切点仅当 otherEnd 非空时对每个圆/弧算 tangentPointsFromPointToCircle过滤弧角范围后 consider。auto consider [](const Vec3 p, SnapType tp, int a, int b-1) { const double d p.distTo(w); // 计算候选点到光标w的距离 if (d bestD) { // 如果距离更近更新最佳捕捉结果 bestD d; // 更新最小距离 best.point p; // 更新捕捉点坐标 best.snapped true; // 标记已捕捉 best.type tp; // 记录捕捉类型 best.elemA a; // 记录第一个相关图元索引 best.elemB b; // 记录第二个相关图元索引默认为-1 } };3.1 已知设计权衡交点与端点重合时端点胜若交点恰好与某图元端点重合如两线在 (0,0) 相接二者到光标距离相等consider 顺序上端点先入栈、交点距离相等不更新最终返回端点。这是「最近者胜」的天然结果。自测 §19.5 专门用「交点不落在任一端点上」的配置来验证 Intersection 类型既覆盖功能又避免与端点捕捉在退化情形下互相干扰。若未来需要『交点恒优先』只需在 consider 里给 Intersection 一个微小距离折扣即可改动局部。下图展示了snap()函数的完整决策流程关键节点备注粗筛使用 tol*6 范围减少求交计算量将 O(n²) 降为局部候选集两两求交。consider统一距离比较入口最近者胜交点与端点重合时端点先入栈胜出。端点/圆心捕捉直接遍历 snapHandles 取真实控制点零额外几何计算。切点捕捉仅当 otherEnd 非空时触发对弧额外做 angleInSweep 角度过滤。流程说明初始化设置最佳距离为无穷大捕捉状态为 false。三类候选并行收集端点/圆心直接遍历所有图元的控制点交点先粗筛靠近光标的图元再两两求交切点仅当另一端点已知时计算。统一距离比较所有候选点通过 consider lambda 比较距离最近者胜。返回结果最终返回距离光标最近的特征点及其类型。四、与画线交互的咬合GraphicsView捕捉不是独立功能而是「拾取点」的前置滤波器snapWorld(w)以 pendingPts_.back() 作为 otherEnd 调用 snap返回的 point 替换原始光标坐标。首点时 pendingPts_ 为空 → otherEndnull → 仅做端点/圆心/交点捕捉无切线。handlePress画线分支把 snapWorld(w) 推入 pendingPts_于是落定的端点已是吸附点后续镜像/联动/标注都吃到正确坐标。mouseMove画线预览改为 updatePreview(snapWorld(w))预览线段的游离端实时吸附所见即所得。drawForeground按 snapNow_.type 画不同颜色/形状的标记端点/圆心方框交点×切点圆圈约 10px 恒定屏幕大小帮助用户确认吸附类型。resetPending / Esc清空 snapNow_状态机不残留。容差复用worldTol() PICK_TOL_PX / zoom_与端点拖拽捕捉、命中检测同一把尺避免「能抓端点却吸不上交点」的割裂。五、精度如何被自测钉死§1914 项切线外部点→圆返回 2 切点每点 |T−C−r|1e-6 且在圆上PT·CT1e-6垂直圆内点返回 0。圆心光标贴 (100,100) r40 圆心 → Center 且坐标精确为 (100,100)。直线端点/弧端点贴 (0,0) 与弧起/终点 → Endpoint 且坐标精确弧端点不含圆心snapHandles 对 arc 给 center起终但端点判定 i!0。交点两轴交 (0,0) → Intersection且 elemA/elemB 记录两条线 id供后续自动加「相交」约束可扩展。切点给定首端点 P(40,0)、圆 (0,0) r25光标近切点 → Tangent 且精确落在圆上。自由点远离任何特征 → snappedfalsepointw不污染自由绘制。这些断言全部基于几何解析值圆心、半径、切线公式不依赖浮点拟合因此一旦有人把容差或过滤写错测试立刻变红。六、刻意留白非本轮范围「同时切两圆」的切线本实现只允许第二点切于一个圆另一端点已知。若需画一条同时外切两圆的公切线需要 『选圆A→选圆B』的双圆切线求解留待后续。捕捉命中后自动加约束如「端点重合」「相切」snap 已记录 elemA/elemB 与类型未来可据其自动建约束与需求3的拓扑保持呼应。三维/非笛卡尔平面下的捕捉当前 model 仅标准平面snap 直接吃世界坐标若引入多工作平面需先把 w 投影到目标平面再算。七、验证结论干净构建CMake Ninja MinGW GCC 13.1.00 警告 / 0 错误。核心自测 SketchSelfTest139 项通过 / 0 失败。新增文件src/core/Snap.h / src/core/Snap.cpp已注册进 SketchCAD 与 SketchSelfTest 两目标改动src/ui/GraphicsView.cpp/.hsnapWorld 标记绘制、tests/selftest.cpp§19。生成脚本sketch-cad-cpp/tools/gen_deepthink_snap.py可重跑复现本文档。—— 聚焦文档由深度思考过程自动导出sketch-cad-cpp / C17 / Qt6八、性能优化与扩展思考当前snap()函数在交点计算环节存在潜在的 O(n²) 复杂度瓶颈首先以distanceToElement(A,w) tol*6粗筛靠近光标的图元再对筛选后的图元两两求交。当场景中图元数量 n 很大时如复杂装配图、大型地形网格即使粗筛能过滤掉大部分远离光标的图元最坏情况下仍需对 O(n²) 对图元进行求交检测可能成为实时交互的性能瓶颈。8.1 空间划分优化一种可行的优化策略是引入空间划分数据结构如四叉树2D或网格空间索引预处理阶段将场景中所有图元的包围盒注册到空间索引中。粗筛加速在snap()调用时先查询以光标 w 为中心、tol*6为半径的范围内有哪些图元直接获得候选集避免遍历全部 n 个图元。求交优化对候选集中的图元可利用空间索引进一步减少不必要的两两检测——若两个图元的包围盒不相交则不可能有交点。实现代价需要维护图元增删改时的索引更新并处理动态场景如拖拽中的图元。对于 sketch-cad-cpp 这类轻量级 CAD可在图元数量超过阈值如 1000时自动启用空间索引。8.1.1 四叉树加速图元筛选QuadTree下面给出一个简化的四叉树QuadTreeC 类用于加速snap()中的图元粗筛。核心思路把场景包围盒递归四等分每个节点只保存与其包围盒相交的图元 id查询时沿光标所在区域向下递归只返回可能靠近光标的候选集从而把「遍历全部 n 个图元」降为「只访问局部节点」。// QuadTree.h —— 简化四叉树以图元包围盒为粒度做空间索引 class QuadTree { public: struct Box { double x0, y0, x1, y1; }; // 轴对齐包围盒 QuadTree(const Boxamp; region, int maxDepth 8, int maxItems 8) : region_(region), maxDepth_(maxDepth), maxItems_(maxItems) {} // 插入把图元 id 及其包围盒注册进树 void insert(int elemId, const Boxamp; bbox) { insertRec(elemId, bbox, region_, 0); } // 查询返回与查询框 query 相交的所有图元 id去重 std::vectorlt;intgt; query(const Boxamp; query) const { std::vectorlt;intgt; out; queryRec(query, region_, out); return out; } private: struct Node { std::vectorstd::pairint, Box items; // 本节点直接持有的图元 std::unique_ptrNode children[4]; // 四个子象限 }; void insertRec(int elemId, const Boxamp; bbox, const Boxamp; region, int depth) { if (depth gt; maxDepth_ || node_.items.size() lt; maxItems_ || !subdivide(region)) { node_.items.emplace_back(elemId, bbox); // 达到深度/容量上限则就地保存 return; } // 否则把图元下推到与其相交的子象限 for (int i 0; i lt; 4; i) { Box child childBox(region, i); if (intersects(bbox, child)) { if (!node_.children[i]) node_.children[i] std::make_uniquelt;Nodegt;(); node_.children[i]-gt;insertRec(elemId, bbox, child, depth 1); } } } void queryRec(const Boxamp; query, const Boxamp; region, std::vectorlt;intgt;amp; out) const { if (!intersects(query, region)) return; // 查询框与当前区域不相交剪枝 for (autoamp; [id, bbox] : node_.items) if (intersects(query, bbox)) out.push_back(id); // 命中本节点图元 for (int i 0; i lt; 4; i) if (node_.children[i]) node_.children[i]-gt;queryRec(query, childBox(region, i), out); } static bool intersects(const Boxamp; a, const Boxamp; b) { return a.x0 lt; b.x1 amp;amp; b.x0 lt; a.x1 amp;amp; a.y0 lt; b.y1 amp;amp; b.y0 lt; a.y1; } static Box childBox(const Boxamp; r, int i) { /* 按 i 取四分之一象限 */ } Node node_; // 根节点 Box region_; // 场景总包围盒 int maxDepth_; // 最大深度防止退化 int maxItems_; // 节点容量超过则分裂 };在snap()中替换原有的 O(n²) 粗筛逻辑预处理阶段把所有图元包围盒注册进四叉树每次调用时以光标 w 为中心、tol*6为半径构造查询框一次拿到候选集再对候选集两两求交。// Snap.cpp —— 用四叉树替换 O(n²) 粗筛 QuadTree tree(sceneBounds); // 场景总包围盒 for (int i 0; i (int)elems.size(); i) tree.insert(i, bboxOf(elems[i])); // 预处理注册所有图元 // snap() 内部替代原来的「遍历全部 n 个图元粗筛」 QuadTree::Box query{ w.x - tol6, w.y - tol6, w.x tol6, w.y tol6 }; auto candidates tree.query(query); // 只返回光标附近的图元 id for (int a : candidates) { for (int b : candidates) { if (b a) continue; // 避免重复对 // 仅对候选集中的图元两两求交而非全量 O(n²) auto pts geo::intersectElements(elems[a], elems[b]); for (auto p : pts) consider(p, SnapType::Intersection, a, b); } }性能提升效果粗筛阶段从「遍历全部 n 个图元」降为「只访问光标所在局部区域的节点」平均复杂度由 O(n) 降为 O(log n k)k 为局部候选数求交阶段从全量 O(n²) 降为 O(k²)其中 k 通常远小于 n。以 1000 个图元、光标附近平均 20 个候选为例粗筛比较次数约减少 50 倍求交对数从约 50 万对降为约 200 对整体帧耗时可下降一个数量级以上为实时拖拽数百图元留出充足余量。8.2 增量缓存与惰性求交另一种思路是缓存最近的计算结果避免重复求交交点缓存对静态场景图元位置未变可缓存图元之间的交点计算结果。当光标移动时只需检查缓存中哪些交点落在容差范围内无需重新计算。增量更新若场景中只有少数图元被移动/编辑可仅更新受影响的相关交点缓存而非全量重建。惰性求交将交点计算推迟到真正需要时。例如先收集所有可能产生交点的图元对但仅在光标靠近该区域时才实际计算交点坐标。适用场景适合图元拓扑相对稳定、光标移动连续的交互场景可显著降低每帧的计算量。权衡与选型建议对于中小规模图纸n 500当前的 O(n²) 粗筛求交在现代化硬件上仍可保持 60fps过早优化可能增加代码复杂度。若预期处理大型图纸或需要支持实时拖拽数百个图元可优先实现空间划分四叉树因其对动态更新友好且通用性更强。缓存方案更适合静态分析场景如批量标注、自动约束推导等离线任务。无论采用哪种优化都应在SketchSelfTest中增加性能基准用例确保优化后捕捉精度不变且在大规模场景下帧率稳定。
C17 / Qt6 实现 · 端点 / 圆心 / 交点 / 切点捕捉 · 切线几何 · 与画线交互同源本文档聚焦 sketch-cad-cppC17 / Qt 6.10.1 / MinGW-w64 GCC 13.1.0本轮新增的「直线绘制智能捕捉」功能画直线时端点可吸附到五种几何特征点——直线/弧的端点、圆/弧的圆心、两图元的交点、以及由已知另一端点向圆作切线的切点。重点探讨「几何计算如何保证精度」「与现有画线交互如何无缝集成」「精度如何通过无界面自测确保」。更庞大的架构基线见综合文档。验证基线干净构建 0 警告 0 错误核心自测 139 项全通过其中 §19 共 14 项用例专门覆盖本功能。一、五种捕捉方式的几何归类需求列出的五种点按其几何来源可归为两类计算引擎避免在 UI 层各自实现捕捉类型几何来源计算引擎依赖anotherEnd?直线/弧端点图元控制点snapHandles取真实点否圆/弧圆心图元控制点snapHandles 取 center否两图元交点图元求交intersectElements复用否切点切于圆由外部点作切线tangentPointsFromPointToCircle是首端点关键决策交点直接复用既有的 geo::intersectElements直线×直线、直线×圆、圆×圆、含圆弧角度过滤均已实现不另写求交逻辑——再次印证「core 层几何下沉」的价值新交互只是换个触发条件底层零新增代码。二、切点几何由外部点向圆作切线需求 1 的「直线与选定圆相切端点为该圆切点」在数学上等价于已知一个端点 P已确定的另一端点求从 P 向圆 (C, r) 所作切线的切点 T。T 必须满足 |T−C|r 且 PT ⟂ CT。int tangentPointsFromPointToCircle(const Vec3 P, const Vec3 C, double r, Vec3 out[2]) { const double d hypot(P.x-C.x, P.y-C.y); // 计算点P到圆心C的距离 if (d r - 1e-9) return 0; // 点在圆内无实切线 const double phi atan2(P.y-C.y, P.x-C.x); // 圆心指向P的方向角 const double alpha acos(min(1.0, r/d)); // 半张角 out[0] C r*(cos(phialpha), sin(phialpha)); // 第一个切点 out[1] C r*(cos(phi-alpha), sin(phi-alpha)); // 第二个切点 return 2; // 返回切点数量 }2.1 边界与精度点在圆内dr返回 0——不存在实切线自测 §19.1 验证。点在圆上d≈ralpha≈0两切点重合于 P 投影点退化为单点不崩溃。弧的切点必须落在其角度扫掠范围内对 arc 类型再用 angleInSweep 过滤圆则恒通过。垂直性由构造保证T−C 与 P−T 的点积理论为 0自测 §19.1 断言 |dot|1e-6 且 |T−C−r|1e-6把「在圆上且垂直」钉死。三、综合捕捉 snap()最近者胜snap(elems, w, otherEnd, tol) 在容差 tol 内收集所有候选端点/圆心、交点、切点取离光标 w 最近者。之所以「最近距离优先」而非「按类型排优先级」是因为它最贴近主流 CAD 的体感且实现最省端点/圆心遍历每个可见图元的 snapHandles逐个 consider圆仅 center弧含 center起/终直线两端矩形四角多边形/样条全顶点。交点先以 distanceToElement(A,w)tol*6 粗筛靠近光标的图元O(n²) 但 n 通常很小再对筛选后的两两对求交并 consider。切点仅当 otherEnd 非空时对每个圆/弧算 tangentPointsFromPointToCircle过滤弧角范围后 consider。auto consider [](const Vec3 p, SnapType tp, int a, int b-1) { const double d p.distTo(w); // 计算候选点到光标w的距离 if (d bestD) { // 如果距离更近更新最佳捕捉结果 bestD d; // 更新最小距离 best.point p; // 更新捕捉点坐标 best.snapped true; // 标记已捕捉 best.type tp; // 记录捕捉类型 best.elemA a; // 记录第一个相关图元索引 best.elemB b; // 记录第二个相关图元索引默认为-1 } };3.1 已知设计权衡交点与端点重合时端点胜若交点恰好与某图元端点重合如两线在 (0,0) 相接二者到光标距离相等consider 顺序上端点先入栈、交点距离相等不更新最终返回端点。这是「最近者胜」的天然结果。自测 §19.5 专门用「交点不落在任一端点上」的配置来验证 Intersection 类型既覆盖功能又避免与端点捕捉在退化情形下互相干扰。若未来需要『交点恒优先』只需在 consider 里给 Intersection 一个微小距离折扣即可改动局部。下图展示了snap()函数的完整决策流程关键节点备注粗筛使用 tol*6 范围减少求交计算量将 O(n²) 降为局部候选集两两求交。consider统一距离比较入口最近者胜交点与端点重合时端点先入栈胜出。端点/圆心捕捉直接遍历 snapHandles 取真实控制点零额外几何计算。切点捕捉仅当 otherEnd 非空时触发对弧额外做 angleInSweep 角度过滤。流程说明初始化设置最佳距离为无穷大捕捉状态为 false。三类候选并行收集端点/圆心直接遍历所有图元的控制点交点先粗筛靠近光标的图元再两两求交切点仅当另一端点已知时计算。统一距离比较所有候选点通过 consider lambda 比较距离最近者胜。返回结果最终返回距离光标最近的特征点及其类型。四、与画线交互的咬合GraphicsView捕捉不是独立功能而是「拾取点」的前置滤波器snapWorld(w)以 pendingPts_.back() 作为 otherEnd 调用 snap返回的 point 替换原始光标坐标。首点时 pendingPts_ 为空 → otherEndnull → 仅做端点/圆心/交点捕捉无切线。handlePress画线分支把 snapWorld(w) 推入 pendingPts_于是落定的端点已是吸附点后续镜像/联动/标注都吃到正确坐标。mouseMove画线预览改为 updatePreview(snapWorld(w))预览线段的游离端实时吸附所见即所得。drawForeground按 snapNow_.type 画不同颜色/形状的标记端点/圆心方框交点×切点圆圈约 10px 恒定屏幕大小帮助用户确认吸附类型。resetPending / Esc清空 snapNow_状态机不残留。容差复用worldTol() PICK_TOL_PX / zoom_与端点拖拽捕捉、命中检测同一把尺避免「能抓端点却吸不上交点」的割裂。五、精度如何被自测钉死§1914 项切线外部点→圆返回 2 切点每点 |T−C−r|1e-6 且在圆上PT·CT1e-6垂直圆内点返回 0。圆心光标贴 (100,100) r40 圆心 → Center 且坐标精确为 (100,100)。直线端点/弧端点贴 (0,0) 与弧起/终点 → Endpoint 且坐标精确弧端点不含圆心snapHandles 对 arc 给 center起终但端点判定 i!0。交点两轴交 (0,0) → Intersection且 elemA/elemB 记录两条线 id供后续自动加「相交」约束可扩展。切点给定首端点 P(40,0)、圆 (0,0) r25光标近切点 → Tangent 且精确落在圆上。自由点远离任何特征 → snappedfalsepointw不污染自由绘制。这些断言全部基于几何解析值圆心、半径、切线公式不依赖浮点拟合因此一旦有人把容差或过滤写错测试立刻变红。六、刻意留白非本轮范围「同时切两圆」的切线本实现只允许第二点切于一个圆另一端点已知。若需画一条同时外切两圆的公切线需要 『选圆A→选圆B』的双圆切线求解留待后续。捕捉命中后自动加约束如「端点重合」「相切」snap 已记录 elemA/elemB 与类型未来可据其自动建约束与需求3的拓扑保持呼应。三维/非笛卡尔平面下的捕捉当前 model 仅标准平面snap 直接吃世界坐标若引入多工作平面需先把 w 投影到目标平面再算。七、验证结论干净构建CMake Ninja MinGW GCC 13.1.00 警告 / 0 错误。核心自测 SketchSelfTest139 项通过 / 0 失败。新增文件src/core/Snap.h / src/core/Snap.cpp已注册进 SketchCAD 与 SketchSelfTest 两目标改动src/ui/GraphicsView.cpp/.hsnapWorld 标记绘制、tests/selftest.cpp§19。生成脚本sketch-cad-cpp/tools/gen_deepthink_snap.py可重跑复现本文档。—— 聚焦文档由深度思考过程自动导出sketch-cad-cpp / C17 / Qt6八、性能优化与扩展思考当前snap()函数在交点计算环节存在潜在的 O(n²) 复杂度瓶颈首先以distanceToElement(A,w) tol*6粗筛靠近光标的图元再对筛选后的图元两两求交。当场景中图元数量 n 很大时如复杂装配图、大型地形网格即使粗筛能过滤掉大部分远离光标的图元最坏情况下仍需对 O(n²) 对图元进行求交检测可能成为实时交互的性能瓶颈。8.1 空间划分优化一种可行的优化策略是引入空间划分数据结构如四叉树2D或网格空间索引预处理阶段将场景中所有图元的包围盒注册到空间索引中。粗筛加速在snap()调用时先查询以光标 w 为中心、tol*6为半径的范围内有哪些图元直接获得候选集避免遍历全部 n 个图元。求交优化对候选集中的图元可利用空间索引进一步减少不必要的两两检测——若两个图元的包围盒不相交则不可能有交点。实现代价需要维护图元增删改时的索引更新并处理动态场景如拖拽中的图元。对于 sketch-cad-cpp 这类轻量级 CAD可在图元数量超过阈值如 1000时自动启用空间索引。8.1.1 四叉树加速图元筛选QuadTree下面给出一个简化的四叉树QuadTreeC 类用于加速snap()中的图元粗筛。核心思路把场景包围盒递归四等分每个节点只保存与其包围盒相交的图元 id查询时沿光标所在区域向下递归只返回可能靠近光标的候选集从而把「遍历全部 n 个图元」降为「只访问局部节点」。// QuadTree.h —— 简化四叉树以图元包围盒为粒度做空间索引 class QuadTree { public: struct Box { double x0, y0, x1, y1; }; // 轴对齐包围盒 QuadTree(const Boxamp; region, int maxDepth 8, int maxItems 8) : region_(region), maxDepth_(maxDepth), maxItems_(maxItems) {} // 插入把图元 id 及其包围盒注册进树 void insert(int elemId, const Boxamp; bbox) { insertRec(elemId, bbox, region_, 0); } // 查询返回与查询框 query 相交的所有图元 id去重 std::vectorlt;intgt; query(const Boxamp; query) const { std::vectorlt;intgt; out; queryRec(query, region_, out); return out; } private: struct Node { std::vectorstd::pairint, Box items; // 本节点直接持有的图元 std::unique_ptrNode children[4]; // 四个子象限 }; void insertRec(int elemId, const Boxamp; bbox, const Boxamp; region, int depth) { if (depth gt; maxDepth_ || node_.items.size() lt; maxItems_ || !subdivide(region)) { node_.items.emplace_back(elemId, bbox); // 达到深度/容量上限则就地保存 return; } // 否则把图元下推到与其相交的子象限 for (int i 0; i lt; 4; i) { Box child childBox(region, i); if (intersects(bbox, child)) { if (!node_.children[i]) node_.children[i] std::make_uniquelt;Nodegt;(); node_.children[i]-gt;insertRec(elemId, bbox, child, depth 1); } } } void queryRec(const Boxamp; query, const Boxamp; region, std::vectorlt;intgt;amp; out) const { if (!intersects(query, region)) return; // 查询框与当前区域不相交剪枝 for (autoamp; [id, bbox] : node_.items) if (intersects(query, bbox)) out.push_back(id); // 命中本节点图元 for (int i 0; i lt; 4; i) if (node_.children[i]) node_.children[i]-gt;queryRec(query, childBox(region, i), out); } static bool intersects(const Boxamp; a, const Boxamp; b) { return a.x0 lt; b.x1 amp;amp; b.x0 lt; a.x1 amp;amp; a.y0 lt; b.y1 amp;amp; b.y0 lt; a.y1; } static Box childBox(const Boxamp; r, int i) { /* 按 i 取四分之一象限 */ } Node node_; // 根节点 Box region_; // 场景总包围盒 int maxDepth_; // 最大深度防止退化 int maxItems_; // 节点容量超过则分裂 };在snap()中替换原有的 O(n²) 粗筛逻辑预处理阶段把所有图元包围盒注册进四叉树每次调用时以光标 w 为中心、tol*6为半径构造查询框一次拿到候选集再对候选集两两求交。// Snap.cpp —— 用四叉树替换 O(n²) 粗筛 QuadTree tree(sceneBounds); // 场景总包围盒 for (int i 0; i (int)elems.size(); i) tree.insert(i, bboxOf(elems[i])); // 预处理注册所有图元 // snap() 内部替代原来的「遍历全部 n 个图元粗筛」 QuadTree::Box query{ w.x - tol6, w.y - tol6, w.x tol6, w.y tol6 }; auto candidates tree.query(query); // 只返回光标附近的图元 id for (int a : candidates) { for (int b : candidates) { if (b a) continue; // 避免重复对 // 仅对候选集中的图元两两求交而非全量 O(n²) auto pts geo::intersectElements(elems[a], elems[b]); for (auto p : pts) consider(p, SnapType::Intersection, a, b); } }性能提升效果粗筛阶段从「遍历全部 n 个图元」降为「只访问光标所在局部区域的节点」平均复杂度由 O(n) 降为 O(log n k)k 为局部候选数求交阶段从全量 O(n²) 降为 O(k²)其中 k 通常远小于 n。以 1000 个图元、光标附近平均 20 个候选为例粗筛比较次数约减少 50 倍求交对数从约 50 万对降为约 200 对整体帧耗时可下降一个数量级以上为实时拖拽数百图元留出充足余量。8.2 增量缓存与惰性求交另一种思路是缓存最近的计算结果避免重复求交交点缓存对静态场景图元位置未变可缓存图元之间的交点计算结果。当光标移动时只需检查缓存中哪些交点落在容差范围内无需重新计算。增量更新若场景中只有少数图元被移动/编辑可仅更新受影响的相关交点缓存而非全量重建。惰性求交将交点计算推迟到真正需要时。例如先收集所有可能产生交点的图元对但仅在光标靠近该区域时才实际计算交点坐标。适用场景适合图元拓扑相对稳定、光标移动连续的交互场景可显著降低每帧的计算量。权衡与选型建议对于中小规模图纸n 500当前的 O(n²) 粗筛求交在现代化硬件上仍可保持 60fps过早优化可能增加代码复杂度。若预期处理大型图纸或需要支持实时拖拽数百个图元可优先实现空间划分四叉树因其对动态更新友好且通用性更强。缓存方案更适合静态分析场景如批量标注、自动约束推导等离线任务。无论采用哪种优化都应在SketchSelfTest中增加性能基准用例确保优化后捕捉精度不变且在大规模场景下帧率稳定。
)
