New objectfunction that makes a proper circle shaped pile on arrange.

4 files changed, 102 insertions, 98 deletions

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<Item> crasher = {
+    std::vector<Item> crasher =
+    {
         {
             {-5000000, 8954050},
             {5000000, 8954050},
@@ -527,12 +528,12 @@ void arrangeRectangles() {
     };
 
     std::vector<Item> 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(const Nfp::Shapes<RawShape>&, 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 RawShape> class EdgeCache {
     using Coord = TCoord<Vertex>;
     using Edge = _Segment<Vertex>;
 
-//    enum Corners {
-//        BOTTOM,
-//        LEFT,
-//        RIGHT,
-//        TOP,
-//        NUM_CORNERS
-//    };
-
     mutable std::vector<double> corners_;
 
     std::vector<Edge> emap_;
@@ -70,49 +71,9 @@ template<class RawShape> class EdgeCache {
     void fetchCorners() const {
         if(!corners_.empty()) return;
 
+        // TODO Accuracy
         corners_ = distances_;
-        for(auto& d : corners_) {
-            d /= full_distance_;
-        }
-
-//        corners_ = std::vector<double>(NUM_CORNERS, 0.0);
-
-//        std::vector<unsigned> idx_ud(emap_.size(), 0);
-//        std::vector<unsigned> 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<Coord>::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<Coord>::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<double>& 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<opt::Method::L_SIMPLEX> 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,12 +41,25 @@ 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;