本文涉及知识点数学 几何翻译及基础Placement 放置Strategy 策略Like 类似、像……一样的PlacementStrategyLike 意译放置策略萃取器 或 放置策略适配器。touches 通常表示 两个形状的内部不相交 但它们的边界相交共享点、边或顶点。wrapper包装器。enable_if_ttemplateclassTstd::enable_if_tstd::is_integral_vT,Tfoo(T x){std::couttypeid(T).name()\n;returnx;}foo(42);// OKTint条件为真foo((short)2);结果为intshortfoo(2.4);编译错误。usingenable_if_ttypenamestd::enable_iffalse,int::type;这段代码会编译错误在重载模板时不会报错只会忽略类或函数。如果编译不报错则std::enable_if_tstd::is_integral_v, T是T即返回值是T。std::enable_if_tstd::is_integral_v, T也合法以下代码合法voidfun(int0){}_ItemRawShape sh_; 原始图形Vertex translation_{0, 0}; 平移的矢量。Radians rotation_{0.0};旋转的弧度。Coord inflation_{0}; 是扩张/膨胀向外偏移bool has_rotation_ false, has_translation_ false, has_inflation_ false; 是否旋转、平移、膨胀由于误差的原因旋转0度和不旋转不等效。mutable VertexConstIterator rmt_; // y 最大的顶点若 y 相同取 x 最大由于是缓存故const函数可以修改。mutable VertexConstIterator lmb_; //y 最小的顶点若 y 相同取 x 最小。staticinlineboolvsort(constVertexv1,constVertexv2){TComputeVertexx1getX(v1),x2getX(v2);TComputeVertexy1getY(v1),y2getY(v2);returny1y2?x1x2:y1y2;}fixed_ 决定物品是直接放入指定箱子还是加入待排列表binid_ 决定固定物品放入哪个箱子disallowed_ 在放置器内部使用作为障碍区域。至少填充选择器对物品和障碍物的逻辑不同。priority_ 优先级。优先级高的先选择。2个物品占用三个箱子std::vectorItemitems;Itemitem1(Rectangle(10,10));item1.markAsFixedInBin(1);Itemitem2(Rectangle(10,10));item2.markAsFixedInBin(2);items.emplace_back(item1);items.emplace_back(item2);constBoxbin(mm(100),mm(100));conststd::size_t binsnest(items,bin,mm(0));物品一占用第一个箱子物品二占用第二个箱子加上空置的0号箱子共3个。基类SelectionBoilerplateItemGroup向量记录物品引用。PackGroup 两层向量记录物品。packed_bins_ 记录各箱子物品。remove_unpackable_items函数如果一个物品无法装箱则删除。_FirstFitSelectionContainer store_; 需要排样的物体。std::for_each(first,last,[this](Itemitm){if(itm.isFixed()){if(itm.binId()0)itm.binId(0);autobinidxsize_t(itm.binId());while(packed_bins_.size()binidx)packed_bins_.emplace_back();packed_bins_[binidx].emplace_back(itm);}else{store_.emplace_back(itm);}});遍历各物品如果是非固定物品放到store_。如果需要固定的箱子号为负强制转为0。如果箱子不够增加箱子。将物品放到指定的箱子中。while(!was_packed!cancelled()){for(;jplacers.size()!was_packed!cancelled();j){if((was_packedplacers[j].pack(*it,rem(it,store_)))){it-get().binId(int(j));makeProgress(placers[j],j);}}尝试已有箱子能否放得下当前物品。if(!was_packed){placers.emplace_back(bin);placers.back().configure(pconfig);packed_bins_.emplace_back();jplacers.size()-1;}当前物品占用一个完整的箱子。停止条件达到时快速解决。_FillerSelection按面积从大到小处理。忽略物品的优先级。_DJDHeuristicHeuristic启发性算法、方法。配置struct Config {bool try_reverse_order true;//尝试所有的顺序bool try_pairs true;//尝试2个一组bool try_triplets false;//尝试3个一组double initial_fill_proportion 1.0/3.0;//先用这个比例的面积填满箱子然后才开始尝试逐个、成对、三元组放置。double waste_increment 0.1;DJD 启发式允许一定的“浪费”未填充面积每次迭代放宽这个阈值允许更多浪费直到能放下更多物品或达到上限。bool allow_parallel true;//容许并行bool force_parallel false;//强制并行};成员static const unsigned MAX_ITEMS_SEQUENTIALLY 30; static const unsigned MAX_VERTICES_SEQUENTIALLY MAX_ITEMS_SEQUENTIALLY*20; 当物品数和顶点数都不超过上述值时采用串行而不时并行。以避免新线程的开销。booldo_parallelconfig_.allow_parallelbincount_guess1((glob_vertex_countMAX_VERTICES_SEQUENTIALLY||store_.size()MAX_ITEMS_SEQUENTIALLY)||config_.force_parallel);装箱忽略物品的优先级。autocheck_pair[](conststd::vectorTPairwrong_pairs,ItemRef i1,ItemRef i2){returnstd::any_of(wrong_pairs.begin(),wrong_pairs.end(),[i1,i2](constTPairpair){Itempi1std::get0(pair),pi2std::get1(pair);Itemri1i1,ri2i2;return(pi1ri1pi2ri2)||(pi1ri2pi2ri1);});};判断错误表是否包括{i1,i2}。// Method for checking if a triplet was a pack failureautocheck_triplet[](conststd::vectorTTripletwrong_triplets,ItemRef i1,ItemRef i2,ItemRef i3){returnstd::any_of(wrong_triplets.begin(),wrong_triplets.end(),[i1,i2,i3](constTTriplettripl){Itempi1std::get0(tripl);Itempi2std::get1(tripl);Itempi3std::get2(tripl);Itemri1i1,ri2i2,ri3i3;return(pi1ri1pi2ri2pi3ri3)||(pi1ri1pi2ri3pi3ri2)||(pi1ri2pi2ri1pi3ri3)||(pi1ri3pi2ri2pi3ri1);});};判断{i1,i2,i3}是否在错误三元组中。3个物品排列有6种排列代码中只列出了4种。可能是别的地方做了处理也可能是缺陷。就算是缺陷也不影响正确性只会造成性能损失。autolargestPiece[](ItemListIt it,ItemListnot_packed){returnitnot_packed.begin()?std::next(it):not_packed.begin();};autosecondLargestPiece[largestPiece](ItemListIt it,ItemListnot_packed){autoretstd::next(largestPiece(it,not_packed));returnretit?std::next(ret):ret;};autosmallestPiece[](ItemListIt it,ItemListnot_packed){autolaststd::prev(not_packed.end());returnitlast?std::prev(it):last;};autosecondSmallestPiece[smallestPiece](ItemListIt it,ItemListnot_packed){autoretstd::prev(smallestPiece(it,not_packed));returnretit?std::prev(ret):ret;};假定删除it后最大、次大、最小、次小物品。tryOneByOne依次尝试待放物品如果将当前物品装箱剩余面积小于等于可浪费面积则装箱。tryGroupsOfTwo两两尝试待放置物品如果放置这两个物品后剩余面积小于等于可浪费面积则装箱。tryGroupsOfThree三个一组进行尝试。任意组合都可能尝试。故此函数的时间复杂度是O(n 3 n^3n3)。packjob执行多轮每轮waste都增加。每轮都依次执行一初始填充。二tryOneByOne。三tryGroupsOfTwo。四tryGroupsOfThree。初始填充阶段在开始成对/三元组尝试之前先把箱子填充到大约 INITIAL_FILL_AREA默认箱子面积的 1/3。扩展阅读计算几何为骨排样优化为魂作品一亲士套料工具箱 作品二 亲士CAD工具箱经典文章推荐二维排样万物皆数学查阅鄙人的博文请点击博文下载学院导航活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。