文章目录一、No-Fit PolygonNFP原理速览1.1 什么是NFP1.2 NFP的数学构造1.3 本代码的目标二、头文件结构与前置声明三、命名空间 __nfp内部辅助函数四、命名空间 nfp核心接口4.1 类型定义与枚举4.2 辅助函数合并、求顶点极值4.3 核心凸多边形NFPCuninghame-Green算法4.4 未完成的通用算法 nfpSimpleSimple五、特化接口 NfpImpl六、C模板编程亮点解析6.1 特质Traits与概念Concepts6.2 默认模板参数6.3 引用包装器 reference_wrapper6.4 静态断言6.5 算法泛型七、总结与启发7.1 NFP的价值7.2 本代码的设计哲学7.3 对读者的启示在二维不规则排样nesting问题中No-Fit PolygonNFP是核心几何工具。它能高效判断两个多边形是否重叠并为优化布局提供依据。libnest2d 是一个开源C库提供了NFP的通用框架其中geometries/nofitpolygon.hpp文件包含了基于模板的NFP计算核心。本文将以该头文件为蓝本逐段注释代码剖析其设计思想并深入讲解NFP原理及C模板编程技巧。一、No-Fit PolygonNFP原理速览1.1 什么是NFP设有两个多边形固定多边形Astationary和移动多边形Borbiting。我们将B的一个参考点通常取B的某个顶点沿A的边界进行平移即B的朝向保持不变仅位置变化同时保持B与A不相交允许接触。B的参考点所经过的所有位置形成的区域就是No-Fit Polygon。若参考点位于NFP内部则A与B必然重叠。若位于NFP边界则A与B恰好接触相切。若位于NFP外部则A与B分离。因此NFP将两个多边形之间的位置关系转化为“点与多边形”的包含测试极大简化了碰撞检测。1.2 NFP的数学构造从几何上讲NFP A ⊕ (-B)Minkowski和其中 -B 是B相对于其参考点取反后的多边形。如果A和B均为凸多边形则NFP也是凸多边形可通过对两条边按角度排序并连接得到这就是Cuninghame-Green算法的核心思想。对于凹多边形NFP可能由多个环组成计算更为复杂通常需要分解为凸片段或采用滑动轨迹法。1.3 本代码的目标nofitpolygon.hpp提供了一个泛型框架默认实现针对凸多边形nfpConvexOnly。预留了可特化的NfpImpl结构允许用户为不同类型含孔、凹多边形等提供高效实现。尝试实现了一种通用简单多边形算法nfpSimpleSimple基于论文“An Algorithm for the No-Fit Polygon” (Bennell et al.)但当前版本似乎并未完成含有调试输出和占位逻辑。我们重点分析凸NFP算法并理解其C模板设计。二、头文件结构与前置声明#ifndefGEOMETRIES_NOFITPOLYGON_HPP#defineGEOMETRIES_NOFITPOLYGON_HPP#includealgorithm#includefunctional#includevector#includeiterator#includelibnest2d/geometry_traits.hpp标准头文件algorithm排序、functional引用包装、vector、iterator。geometry_traits.hpp提供了对多边形类型RawShape的统一访问接口如shapelike::cbegin、shapelike::contour等这是libnest2d的几何特质层使得算法可以适配不同几何库如CGAL、Boost.Geometry等。三、命名空间__nfp内部辅助函数namespace__nfp{// Do not specialize this...templateclassRawShape,classUnitTComputeRawShapeinlinebool_vsort(constTPointRawShapev1,constTPointRawShapev2){Unit x1getX(v1),x2getX(v2),y1getY(v1),y2getY(v2);returny1y2?x1x2:y1y2;}功能比较两个顶点用于找出最左下先按y升序若y相等则按x升序或最右上配合std::max_element可得到最右上顶点。模板参数RawShape是多边形类型Unit是坐标数值类型从特质中推导。C语法templateclass RawShape, class Unit TComputeRawShape使用默认模板参数TCompute是特质中计算坐标的类型。函数返回bool。templateclassEdgeList,classRawShape,classVertexTPointRawShapeinlinevoidbuildPolygon(constEdgeListedgelist,RawShaperpoly,Vertextop_nfp){// 取出轮廓引用autorshsl::contour(rpoly);sl::reserve(rsh,2*edgelist.size());// 添加第一条边的两个端点sl::addVertex(rsh,edgelist.front().first());sl::addVertex(rsh,edgelist.front().second());// 寻找最右上顶点作为参考autocmp_vsortRawShape;top_nfp*std::max_element(sl::cbegin(rsh),sl::cend(rsh),cmp);autotmpstd::next(sl::begin(rsh));// 遍历剩余边将每条边平移到上一终点for(autoeitstd::next(edgelist.begin());eit!edgelist.end();eit){autod*tmp-eit-first();// 平移量Vertex peit-second()d;sl::addVertex(rsh,p);if(cmp(top_nfp,p))top_nfpp;tmpstd::next(tmp);}}功能根据排序后的边列表构造NFP多边形。边列表已按极角排序构建时依次连接并记录最右上顶点用于后续参考。关键点每条边都平移使其起点与上一终点重合形成连续多边形。这对应Minkowski和的“边拼接”过程。templateclassContainer,classIteratortypenameContainer::iteratorvoidadvance(Iteratorit,Containercont,booldirection){intdirdirection?1:-1;if(dir0itcont.begin())itstd::prev(cont.end());elseitdir;if(dir0itcont.end())itcont.begin();}功能在容器中循环前进或后退一个位置实现环形迭代。用于nfpSimpleSimple中的遍历。四、命名空间nfp核心接口4.1 类型定义与枚举constdoubleBP2D_CONSTEXPR TwoPi2*Pi;enumclassNfpLevel:unsigned{CONVEX_ONLY,ONE_CONVEX,BOTH_CONCAVE,ONE_CONVEX_WITH_HOLES,BOTH_CONCAVE_WITH_HOLES};templateclassRawShapeusingNfpResultstd::pairRawShape,TPointRawShape;NfpLevel标识算法能处理的多边形复杂度等级。NfpResult返回NFP多边形及其参考顶点最右上点。4.2 辅助函数合并、求顶点极值templateclassRawShapeinlineTPointRawShapeleftmostDownVertex(constRawShapesh){...}templateclassRawShapeTPointRawShaperightmostUpVertex(constRawShapesh){...}templateclassRawShapeinlineTPointRawShapereferenceVertex(constRawShapesh){returnrightmostUpVertex(sh);}使用_vsort配合std::min_element/max_element获取特定顶点。4.3 核心凸多边形NFPCuninghame-Green算法templateclassRawShape,classRatiodoubleinlineNfpResultRawShapenfpConvexOnly(constRawShapesh,constRawShapeother){usingVertexTPointRawShape;usingEdge_SegmentVertex;namespaceslshapelike;RawShape rsh;// 最终NFPVertex top_nfp;std::vectorEdgeedgelist;// 将sh的所有边正向加入// 将other的所有边反向加入因为需要 -B// 按边向量极角排序std::sort(edgelist.begin(),edgelist.end(),[](constEdgee1,constEdgee2){// 比较两个向量方向实现极角排序// 详细比较逻辑使用象限和cos值});__nfp::buildPolygon(edgelist,rsh,top_nfp);return{rsh,top_nfp};}算法精髓输入必须为严格凸多边形。将A的边按原方向加入列表将B的边取反方向反转后加入。按边的方向角0~2π排序。首尾相接形成凸NFP。C模板细节Ratio参数用于避免精度损失可替换为有理数类型如Boost.Rational。Lambda 比较器内部使用dot、dotperp和象限映射避免atan2的浮点误差。类型TComputeVertex确保运算精度。4.4 未完成的通用算法nfpSimpleSimpletemplateclassRawShapeNfpResultRawShapenfpSimpleSimple(constRawShapecstationary,constRawShapecother){// 引用论文https://eprints.soton.ac.uk/36850/1/CORMSIS-05-05.pdf// 算法步骤// 1. 标准化方向stationary逆时针orbiter顺时针或取反// 2. 构建带标记的边列表标记转向点// 3. 使用Minkowski和分解为若干“轨道”// 4. 合并轨道形成NFP// 但代码中有大量调试输出且逻辑未闭合seqlist处理不完整}该函数当前不完整多处使用std::cout输出调试信息且seqlist仅取第一个元素构建NFP。这可能是开发中状态但框架设计值得借鉴。五、特化接口NfpImpltemplateclassRawShape,NfpLevel nfptypestructNfpImpl{NfpResultRawShapeoperator()(constRawShapesh,constRawShapeother){static_assert(nfptypeNfpLevel::CONVEX_ONLY,Nfp::noFitPolygon() unimplemented!);returnnfpConvexOnly(sh,other);}};用途用户可针对不同NfpLevel特化此结构提供自己的实现。默认仅支持凸多边形。templateNfpLevel nfptype,classRawShapeinlineNfpResultRawShapenoFitPolygon(constRawShapesh,constRawShapeother){NfpImplRawShape,nfptypenfps;returnnfps(sh,other);}统一入口函数通过模板参数指定多边形复杂度等级。六、C模板编程亮点解析6.1 特质Traits与概念Concepts通过TComputeRawShape、TPointRawShape、shapelike::contour等将多边形操作抽象化。这种设计称为静态多态编译时绑定具体类型性能优于虚函数。6.2 默认模板参数templateclassRawShape,classUnitTComputeRawShape让用户可覆盖计算类型如使用高精度有理数。6.3 引用包装器reference_wrapper在nfpSimpleSimple中使用std::reference_wrapper存储对MarkedEdge的引用便于在不同容器间共享数据而避免拷贝。6.4 静态断言static_assert在编译期检查模板参数是否合理提高错误信息清晰度。6.5 算法泛型排序、查找、变换均使用标准库算法并配合自定义比较器使代码高度可复用。七、总结与启发7.1 NFP的价值NFP是二维布局优化中的基石它将复杂的几何碰撞转化为点-多边形包含判断大幅降低计算复杂度。凸NFP有简洁的闭式解而凹NFP则需更精细的算法如分解为凸片或轨道法。7.2 本代码的设计哲学层次化通过NfpLevel区分算法能力便于扩展。模板化适应任意多边形数据类型只需实现必要的特质接口。渐进实现先提供凸方案再逐步添加凹方案尽管未完成但框架留白。7.3 对读者的启示阅读此类模板库时应首先理解特质接口即多边形应具备哪些操作再深入算法核心。同时注释中引用的论文是理解复杂算法的钥匙。后记libnest2d 的 NFP 实现仍在持续完善中。作为开发者我们可以借鉴其设计模式在自己的几何计算库中实现类似的可扩展架构。希望本文的解析能帮助您理清代码脉络掌握 NFP 原理及 C 模板实践。本文基于 libnest2d 源码 commit2026年编写代码可能后续有变动但核心思想不变。