本文涉及知识点数学 几何翻译CLOCKWISE 顺时针COUNTER_CLOCKWISE 逆时针Boilerplate 样板、模板、脚手架、固定套话。后来引申为“重复使用的标准模板代码”。rawShape 直译原始形状 / 裸形状。Raw 原始的、未加工的、裸的Shape 形状、几何体预习及复习C981998 年C112011 年曾叫 C0xC172017 年C202020 年usingstd::forward;usingstd::tuple;usingstd::make_tuple;可以只简写一个类、函数而不是整个命名空间。remove_referencetypedefstd::remove_referenceT::type T1;typedefstd::remove_cvT1::type T2;constchar*p1typeid(T1).name();constchar*p2typeid(T2).name();VS2019 C14 运行结果intint利用偏特性实现的很简单。消除引用templateclass_Tystructremove_reference{usingtype_Ty;using_Const_thru_ref_typeconst_Ty;};templateclass_Tystructremove_reference_Ty{usingtype_Ty;using_Const_thru_ref_typeconst_Ty;};templateclass_Tystructremove_reference_Ty{usingtype_Ty;using_Const_thru_ref_typeconst_Ty;};消除常量和跨线程变量structremove_cvconst_Ty{usingtype_Ty;templatetemplateclassclass_Fnusing_Applyconst_Fn_Ty;};templateclass_Tystructremove_cvvolatile_Ty{usingtype_Ty;templatetemplateclassclass_Fnusing_Applyvolatile_Fn_Ty;};templateclass_Tystructremove_cvconstvolatile_Ty{usingtype_Ty;templatetemplateclassclass_Fnusing_Applyconstvolatile_Fn_Ty;};NAN和INFdoubleaNAN;doublebstd::nan(123);doublecstd::strtod(NAN(123),nullptr);doubledstd::numeric_limitsdouble::quiet_NaN();doubleestd::numeric_limitsdouble::signaling_NaN();doublef1E300*1E300;前5个是非数字不确定数字)第6个是无穷大。doublea1/F(0);doubleb0/F(0);doublecstd::sqrt(-1);doubledstd::numeric_limitsdouble::infinity()-std::numeric_limitsdouble::infinity();doubleestd::numeric_limitsdouble::infinity()/std::numeric_limitsdouble::infinity();doublefstd::sqrt(std::numeric_limitsdouble::infinity());a和f是INFbcde是NAN。libnest2d克隆代码发现有大量有文件只有一个源文件且此源文件只有二十余行。猜测是仅仅头文件HEADER_ONLY。头文件中有_MSC_VER 1800说明支持VS。LIBNEST2D_GEOMETRIES_clipper 宏决定是否使用Clipper裁剪库此宏必须存在否则一些基础类没有定义。LIBNEST2D_OPTIMIZER_nlopt 宏决定是否使用非线性优化库nlopt 作为优化器后端。必定定义否则只能使用基础功能。平时都是用VS,不熟悉makelist所以几小时没编译通过似乎nplot版本不对。最终群友给我一个VS2019编译好的libdll,include。带孔多边形攻略上说目前只支持凸多边形不支持凹多边形也不支持带孔多边形。inlinePolygon(constPathcont,constPathsholes):Contour(cont),Holes(holes){}可以构造带孔多边形但默认参数似乎没正确除了孔洞。可能保留接口为自定义放置器准备。并发库TBB 与 OpenMP 对比两者都是 C 中常用的并行编程技术。TBBIntel Threading Building Blocks是一个第三方 C 库需要单独安装、包含头文件并链接库。它提供高级并行算法和数据结构如 parallel_for、parallel_reduce、并发容器等。OpenMP是一个并行编程 API 规范它由编译器实现支持如 GCC 的 -fopenmp、Clang 的 -fopenmp、MSVC 的 /openmp。#ifdefLIBNEST2D_THREADING_tbb#includetbb/parallel_for.h#endif#ifdefLIBNEST2D_THREADING_omp#includeomp.h#endif下面还有LIBNEST2D_THREADING_std由于是刚开始熟悉代码故暂时用std。这三个宏是三选一不能多选也不能少选。enumerate 直译是枚举实际是每个函数启动一个线程。核心代码很容易理解以stl为例启动线程并等待。std::vectorstd::futurevoidrets(N);autoitfrom;for(TN b0;bN;b){rets[b]std::async(policy,fn,*it,unsigned(b));}for(TN fi0;fiN;fi)rets[fi].wait();优化templateclassT,classBvoidstructlimits{inlinestaticTmin(){returnstd::numeric_limitsT::min();}inlinestaticTmax(){returnstd::numeric_limitsT::max();}};templateclassTstructlimitsT,enable_if_tstd::numeric_limitsT::has_infinity,void{inlinestaticTmin(){return-std::numeric_limitsT::infinity();}inlinestaticTmax(){returnstd::numeric_limitsT::infinity();}};如果本数据类型支持无穷大则最大值最小值是正负无穷大。否则调用 std::min和std::max一些简单类、结构体下面的类是一个简单的类没有放到源文件。classDouble{protected:doubleval_;public:Double():val_(double{}){}Double(doubled):val_(d){}operatordouble()constBP2D_NOEXCEPT{returnval_;}operatordouble()BP2D_NOEXCEPT{returnval_;}};Radians 记录弧度。Degrees记录度数。template struct ContourType { using Type S; }template struct ContourType { using Type PathImpl; };template struct ContourTypeDefaultMultiShape {using Type typename ContourType::Type;};需要排样的物品项Itemusing Item _Item;using PolygonImpl ClipperLib::Polygon;items.emplace_back(Rectangle(mm(30),mm(30)));ClipperLib::Path path{{0,0},{1000,0},{50,80}};items.emplace_back(Item(path));上述方法增加矩形和凸多边形。主函数(排样)templateclassPlacerNfpPlacer,classSelectorFirstFitSelection,classContainerstd::vectorItemstd::size_tnest(Containercont,consttypenamePlacer::BinTypebin,Coord dist0,constNestConfigPlacer,Selectorcfg{},NestControl ctl{})externtemplatestd::size_tnest(std::vectorItem::iterator from,std::vectorItem::iterator to,constBoxbin,Coord dist,constNestConfigBottomLeftPlacer,FirstFitSelectioncfg,NestControl ctl);Placer 放置器类型决定当前物品放在那。Selector选择器从未完成物品中选择当前物品。Container ,放置容器。Coord dist 0 物品见最小距离。 物品外扩⌈ d i s t ÷ 2 ⌉ \lceil dist \div 2 \rceil⌈dist÷2⌉NestConfigPlacer, Selector 排样参数。NestControl 排样过程的控制参数。放置器BottomLeftPlacer 左下角放置器实现简单NfpPlacer NFP 放置器功能强选择器_FirstFitSelection首次适应选择。按照物品在列表中的原始顺序依次尝试放置。它会遍历物品列表对每个物品调用放置器找到第一个能成功放入箱子或当前箱子的位置就放置然后继续下一个。_FillerSelection填充选择。通常会维护一个待选物品列表在每个放置步骤中评估所有剩余物品选择那个“最能填充当前可用空间”的物品进行放置。这种策略有助于减少碎片空间。_DJDHeuristicDJD 启发式选择。这是一种更复杂的启发式选择算法旨在通过智能地选择物品放置顺序来获得更优的排样结果。StopCriteria停止标准。structStopCriteria{/// If the absolute value difference between two scores.doubleabsolute_score_differencestd::nan();/// If the relative value difference between two scores.doublerelative_score_differencestd::nan();/// Stop if this value or better is found.doublestop_scorestd::nan();/// A predicate that if evaluates to true, the optimization should terminate/// and the best result found prior to termination should be returned.std::functionbool()stop_condition[]{returnfalse;};/// The max allowed number of iterations.unsignedmax_iterations0;};如果 |score_new - score_old| absolute_score_difference则停止认为分数不再变化。如果 |score_new - score_old| / max(|score_old|, |score_new|) relative_score_difference停止如果找到的得分 stop_score或更优停止。stop_condition通过函数自定义停止条件。max_iterations 最大迭代次数。扩展阅读计算几何为骨排样优化为魂作品亲士CAD工具箱经典文章推荐二维排样万物皆数学查阅鄙人的博文请点击博文下载学院导航活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。