From 86ba75d69253ec443e29bb0ecb0b46c163f92d8e Mon Sep 17 00:00:00 2001 From: tamasmeszaros Date: Tue, 17 Jul 2018 12:04:06 +0200 Subject: New objectfunction that makes a proper circle shaped pile on arrange. --- xs/src/libnest2d/CMakeLists.txt | 4 +- xs/src/libnest2d/examples/main.cpp | 21 +++-- xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp | 103 +++++++++------------ .../libnest2d/selections/djd_heuristic.hpp | 72 ++++++++------ 4 files changed, 102 insertions(+), 98 deletions(-) (limited to 'xs/src/libnest2d') diff --git a/xs/src/libnest2d/CMakeLists.txt b/xs/src/libnest2d/CMakeLists.txt index db4f5d99f..bfdb551fc 100644 --- a/xs/src/libnest2d/CMakeLists.txt +++ b/xs/src/libnest2d/CMakeLists.txt @@ -82,8 +82,8 @@ if(LIBNEST2D_OPTIMIZER_BACKEND STREQUAL "nlopt") ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/optimizers/genetic.hpp ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/optimizers/nlopt_boilerplate.hpp) list(APPEND LIBNEST2D_LIBRARIES ${NLopt_LIBS} - # Threads::Threads - ) +# Threads::Threads + ) list(APPEND LIBNEST2D_HEADERS ${NLopt_INCLUDE_DIR}) endif() diff --git a/xs/src/libnest2d/examples/main.cpp b/xs/src/libnest2d/examples/main.cpp index 3d3f30b76..4623a6add 100644 --- a/xs/src/libnest2d/examples/main.cpp +++ b/xs/src/libnest2d/examples/main.cpp @@ -84,7 +84,8 @@ void arrangeRectangles() { // {{0, 0}, {0, 20*SCALE}, {10*SCALE, 0}, {0, 0}} // }; - std::vector crasher = { + std::vector crasher = + { { {-5000000, 8954050}, {5000000, 8954050}, @@ -527,12 +528,12 @@ void arrangeRectangles() { }; std::vector input; -// input.insert(input.end(), prusaParts().begin(), prusaParts().end()); + input.insert(input.end(), prusaParts().begin(), prusaParts().end()); // input.insert(input.end(), prusaExParts().begin(), prusaExParts().end()); // input.insert(input.end(), stegoParts().begin(), stegoParts().end()); // input.insert(input.end(), rects.begin(), rects.end()); // input.insert(input.end(), proba.begin(), proba.end()); - input.insert(input.end(), crasher.begin(), crasher.end()); +// input.insert(input.end(), crasher.begin(), crasher.end()); Box bin(250*SCALE, 210*SCALE); @@ -545,18 +546,18 @@ void arrangeRectangles() { Packer::PlacementConfig pconf; pconf.alignment = Placer::Config::Alignment::CENTER; + pconf.starting_point = Placer::Config::Alignment::CENTER; pconf.rotations = {0.0/*, Pi/2.0, Pi, 3*Pi/2*/}; pconf.object_function = [&bin](Placer::Pile pile, double area, double norm, double penality) { auto bb = ShapeLike::boundingBox(pile); - double diameter = PointLike::distance(bb.minCorner(), - bb.maxCorner()); - - // We will optimize to the diameter of the circle around the bounding - // box and use the norming factor to get rid of the physical dimensions - double score = diameter / norm; + auto& sh = pile.back(); + auto rv = Nfp::referenceVertex(sh); + auto c = bin.center(); + auto d = PointLike::distance(rv, c); + double score = double(d)/norm; // If it does not fit into the print bed we will beat it // with a large penality @@ -568,7 +569,9 @@ void arrangeRectangles() { Packer::SelectionConfig sconf; // sconf.allow_parallel = false; // sconf.force_parallel = false; +// sconf.try_triplets = true; // sconf.try_reverse_order = true; +// sconf.waste_increment = 0.1; arrange.configure(pconf, sconf); diff --git a/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp b/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp index 5ddb3a98d..d6bd154db 100644 --- a/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp +++ b/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp @@ -26,11 +26,20 @@ struct NfpPConfig { /// Where to align the resulting packed pile Alignment alignment; + Alignment starting_point; + std::function&, double, double, double)> object_function; + /** + * @brief The quality of search for an optimal placement. + * This is a compromise slider between quality and speed. Zero is the + * fast and poor solution while 1.0 is the slowest but most accurate. + */ + float accuracy = 1.0; + NfpPConfig(): rotations({0.0, Pi/2.0, Pi, 3*Pi/2}), - alignment(Alignment::CENTER) {} + alignment(Alignment::CENTER), starting_point(Alignment::CENTER) {} }; // A class for getting a point on the circumference of the polygon (in log time) @@ -39,14 +48,6 @@ template class EdgeCache { using Coord = TCoord; using Edge = _Segment; -// enum Corners { -// BOTTOM, -// LEFT, -// RIGHT, -// TOP, -// NUM_CORNERS -// }; - mutable std::vector corners_; std::vector emap_; @@ -70,49 +71,9 @@ template class EdgeCache { void fetchCorners() const { if(!corners_.empty()) return; + // TODO Accuracy corners_ = distances_; - for(auto& d : corners_) { - d /= full_distance_; - } - -// corners_ = std::vector(NUM_CORNERS, 0.0); - -// std::vector idx_ud(emap_.size(), 0); -// std::vector idx_lr(emap_.size(), 0); - -// std::iota(idx_ud.begin(), idx_ud.end(), 0); -// std::iota(idx_lr.begin(), idx_lr.end(), 0); - -// std::sort(idx_ud.begin(), idx_ud.end(), -// [this](unsigned idx1, unsigned idx2) -// { -// const Vertex& v1 = emap_[idx1].first(); -// const Vertex& v2 = emap_[idx2].first(); - -// auto diff = getY(v1) - getY(v2); -// if(std::abs(diff) <= std::numeric_limits::epsilon()) -// return getX(v1) < getX(v2); - -// return diff < 0; -// }); - -// std::sort(idx_lr.begin(), idx_lr.end(), -// [this](unsigned idx1, unsigned idx2) -// { -// const Vertex& v1 = emap_[idx1].first(); -// const Vertex& v2 = emap_[idx2].first(); - -// auto diff = getX(v1) - getX(v2); -// if(std::abs(diff) <= std::numeric_limits::epsilon()) -// return getY(v1) < getY(v2); - -// return diff < 0; -// }); - -// corners_[BOTTOM] = distances_[idx_ud.front()]/full_distance_; -// corners_[TOP] = distances_[idx_ud.back()]/full_distance_; -// corners_[LEFT] = distances_[idx_lr.front()]/full_distance_; -// corners_[RIGHT] = distances_[idx_lr.back()]/full_distance_; + for(auto& d : corners_) d /= full_distance_; } public: @@ -167,12 +128,6 @@ public: inline double circumference() const BP2D_NOEXCEPT { return full_distance_; } -// inline double corner(Corners c) const BP2D_NOEXCEPT { -// assert(c < NUM_CORNERS); -// fetchCorners(); -// return corners_[c]; -// } - inline const std::vector& corners() const BP2D_NOEXCEPT { fetchCorners(); return corners_; @@ -400,7 +355,7 @@ public: opt::StopCriteria stopcr; stopcr.max_iterations = 1000; - stopcr.stoplimit = 0.01; + stopcr.stoplimit = 0.001; stopcr.type = opt::StopLimitType::RELATIVE; opt::TOptimizer solver(stopcr); @@ -518,11 +473,37 @@ private: void setInitialPosition(Item& item) { Box&& bb = item.boundingBox(); + Vertex ci, cb; - Vertex ci = bb.minCorner(); - Vertex cb = bin_.minCorner(); + switch(config_.starting_point) { + case Config::Alignment::CENTER: { + ci = bb.center(); + cb = bin_.center(); + break; + } + case Config::Alignment::BOTTOM_LEFT: { + ci = bb.minCorner(); + cb = bin_.minCorner(); + break; + } + case Config::Alignment::BOTTOM_RIGHT: { + ci = {getX(bb.maxCorner()), getY(bb.minCorner())}; + cb = {getX(bin_.maxCorner()), getY(bin_.minCorner())}; + break; + } + case Config::Alignment::TOP_LEFT: { + ci = {getX(bb.minCorner()), getY(bb.maxCorner())}; + cb = {getX(bin_.minCorner()), getY(bin_.maxCorner())}; + break; + } + case Config::Alignment::TOP_RIGHT: { + ci = bb.maxCorner(); + cb = bin_.maxCorner(); + break; + } + } - auto&& d = cb - ci; + auto d = cb - ci; item.translate(d); } diff --git a/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp b/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp index dcc029251..1d233cf35 100644 --- a/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp +++ b/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp @@ -41,11 +41,24 @@ public: struct Config { /** - * If true, the algorithm will try to place pair and driplets in all - * possible order. + * If true, the algorithm will try to place pair and triplets in all + * possible order. It will have a hugely negative impact on performance. */ bool try_reverse_order = true; + /** + * @brief try_pairs Whether to try pairs of items to pack. It will add + * a quadratic component to the complexity. + */ + bool try_pairs = true; + + /** + * @brief Whether to try groups of 3 items to pack. This could be very + * slow for large number of items (>100) as it adds a cubic component + * to the complexity. + */ + bool try_triplets = false; + /** * The initial fill proportion of the bin area that will be filled before * trying items one by one, or pairs or triplets. @@ -151,8 +164,8 @@ public: return std::any_of(wrong_pairs.begin(), wrong_pairs.end(), [&i1, &i2](const TPair& pair) { - Item& pi1 = std::get<0>(pair), pi2 = std::get<1>(pair); - Item& ri1 = i1, ri2 = i2; + Item& pi1 = std::get<0>(pair), &pi2 = std::get<1>(pair); + Item& ri1 = i1, &ri2 = i2; return (&pi1 == &ri1 && &pi2 == &ri2) || (&pi1 == &ri2 && &pi2 == &ri1); }); @@ -172,7 +185,7 @@ public: Item& pi1 = std::get<0>(tripl); Item& pi2 = std::get<1>(tripl); Item& pi3 = std::get<2>(tripl); - Item& ri1 = i1, ri2 = i2, ri3 = i3; + Item& ri1 = i1, &ri2 = i2, &ri3 = i3; return (&pi1 == &ri1 && &pi2 == &ri2 && &pi3 == &ri3) || (&pi1 == &ri1 && &pi2 == &ri3 && &pi3 == &ri2) || (&pi1 == &ri2 && &pi2 == &ri1 && &pi3 == &ri3) || @@ -348,6 +361,10 @@ public: // Will be true if a succesfull pack can be made. bool ret = false; + auto area = [](const ItemListIt& it) { + return it->get().area(); + }; + while (it != endit && !ret) { // drill down 1st level // We need to determine in each iteration the largest, second @@ -361,7 +378,7 @@ public: // Check if there is enough free area for the item and the two // largest item - if(free_area - it->get().area() - area_of_two_largest > waste) + if(free_area - area(it) - area_of_two_largest > waste) break; // Determine the area of the two smallest item. @@ -373,7 +390,7 @@ public: double area_of_two_smallest = smallest.area() + second_smallest.area(); - if(it->get().area() + area_of_two_smallest > free_area) { + if(area(it) + area_of_two_smallest > free_area) { it++; continue; } @@ -384,16 +401,18 @@ public: it2 = not_packed.begin(); double rem2_area = free_area - largest.area(); - double a2_sum = it->get().area() + it2->get().area(); + double a2_sum = 0; while(it2 != endit && !ret && - rem2_area - a2_sum <= waste) { // Drill down level 2 + rem2_area - (a2_sum = area(it) + area(it2)) <= waste) { + // Drill down level 2 + + if(a2_sum != area(it) + area(it2)) throw -1; if(it == it2 || check_pair(wrong_pairs, *it, *it2)) { it2++; continue; } - a2_sum = it->get().area() + it2->get().area(); if(a2_sum + smallest.area() > free_area) { it2++; continue; } @@ -429,14 +448,13 @@ public: // The 'smallest' variable now could be identical with // it2 but we don't bother with that - if(!can_pack2) { it2++; continue; } - it3 = not_packed.begin(); - double a3_sum = a2_sum + it3->get().area(); + double a3_sum = 0; while(it3 != endit && !ret && - free_area - a3_sum <= waste) { // 3rd level + free_area - (a3_sum = a2_sum + area(it3)) <= waste) { + // 3rd level if(it3 == it || it3 == it2 || check_triplet(wrong_triplets, *it, *it2, *it3)) @@ -560,8 +578,11 @@ public: if(do_parallel) dout() << "Parallel execution..." << "\n"; + bool do_pairs = config_.try_pairs; + bool do_triplets = config_.try_triplets; + // The DJD heuristic algorithm itself: - auto packjob = [INITIAL_FILL_AREA, bin_area, w, + auto packjob = [INITIAL_FILL_AREA, bin_area, w, do_triplets, do_pairs, &tryOneByOne, &tryGroupsOfTwo, &tryGroupsOfThree, @@ -573,7 +594,7 @@ public: double waste = .0; bool lasttry = false; - while(!not_packed.empty() ) { + while(!not_packed.empty()) { {// Fill the bin up to INITIAL_FILL_PROPORTION of its capacity auto it = not_packed.begin(); @@ -594,26 +615,25 @@ public: // try pieses one by one while(tryOneByOne(placer, not_packed, waste, free_area, filled_area)) { - if(lasttry) std::cout << "Lasttry monopack" << std::endl; waste = 0; lasttry = false; makeProgress(placer, idx, 1); } // try groups of 2 pieses - while(tryGroupsOfTwo(placer, not_packed, waste, free_area, + while(do_pairs && + tryGroupsOfTwo(placer, not_packed, waste, free_area, filled_area)) { - if(lasttry) std::cout << "Lasttry bipack" << std::endl; waste = 0; lasttry = false; makeProgress(placer, idx, 2); } -// // try groups of 3 pieses -// while(tryGroupsOfThree(placer, not_packed, waste, free_area, -// filled_area)) { -// if(lasttry) std::cout << "Lasttry tripack" << std::endl; -// waste = 0; lasttry = false; -// makeProgress(placer, idx, 3); -// } + // try groups of 3 pieses + while(do_triplets && + tryGroupsOfThree(placer, not_packed, waste, free_area, + filled_area)) { + waste = 0; lasttry = false; + makeProgress(placer, idx, 3); + } waste += w; if(!lasttry && waste > free_area) lasttry = true; -- cgit v1.2.3