From d136d61edded36ad36f17ee14b4b954a55d69db5 Mon Sep 17 00:00:00 2001 From: tamasmeszaros Date: Mon, 30 Jul 2018 15:16:44 +0200 Subject: linest2d ready for arbitrary shaped beds. --- xs/src/libnest2d/examples/main.cpp | 133 ++++++++++++++++----- xs/src/libnest2d/libnest2d/boost_alg.hpp | 2 +- xs/src/libnest2d/libnest2d/geometry_traits.hpp | 77 +++++++++++- xs/src/libnest2d/libnest2d/libnest2d.hpp | 11 ++ xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp | 130 +++++++++++++------- .../libnest2d/selections/djd_heuristic.hpp | 2 +- xs/src/libnest2d/libnest2d/selections/firstfit.hpp | 2 +- 7 files changed, 276 insertions(+), 81 deletions(-) (limited to 'xs/src/libnest2d') diff --git a/xs/src/libnest2d/examples/main.cpp b/xs/src/libnest2d/examples/main.cpp index a97618578..883d12610 100644 --- a/xs/src/libnest2d/examples/main.cpp +++ b/xs/src/libnest2d/examples/main.cpp @@ -544,57 +544,126 @@ void arrangeRectangles() { // input.insert(input.end(), proba.begin(), proba.end()); // input.insert(input.end(), crasher.begin(), crasher.end()); - Box bin(250*SCALE, 210*SCALE); +// Box bin(250*SCALE, 210*SCALE); + PolygonImpl bin = { + { + {25*SCALE, 0}, + {0, 25*SCALE}, + {0, 225*SCALE}, + {25*SCALE, 250*SCALE}, + {225*SCALE, 250*SCALE}, + {250*SCALE, 225*SCALE}, + {250*SCALE, 25*SCALE}, + {225*SCALE, 0}, + {25*SCALE, 0} + }, + {} + }; auto min_obj_distance = static_cast(0*SCALE); - using Placer = NfpPlacer; + using Placer = strategies::_NofitPolyPlacer; using Packer = Arranger; Packer arrange(bin, min_obj_distance); Packer::PlacementConfig pconf; pconf.alignment = Placer::Config::Alignment::CENTER; - pconf.starting_point = Placer::Config::Alignment::BOTTOM_LEFT; + pconf.starting_point = Placer::Config::Alignment::CENTER; pconf.rotations = {0.0/*, Pi/2.0, Pi, 3*Pi/2*/}; + pconf.accuracy = 1.0; - double norm_2 = std::nan(""); - pconf.object_function = [&bin, &norm_2](Placer::Pile pile, const Item& item, + auto bincenter = ShapeLike::boundingBox(bin).center(); + pconf.object_function = [&bin, bincenter]( + Placer::Pile pile, const Item& item, double /*area*/, double norm, double penality) { using pl = PointLike; - auto bb = ShapeLike::boundingBox(pile); - auto ibb = item.boundingBox(); - auto minc = ibb.minCorner(); - auto maxc = ibb.maxCorner(); - - if(std::isnan(norm_2)) norm_2 = pow(norm, 2); - - // We get the distance of the reference point from the center of the - // heat bed - auto cc = bb.center(); - auto top_left = PointImpl{getX(minc), getY(maxc)}; - auto bottom_right = PointImpl{getX(maxc), getY(minc)}; - - auto a = pl::distance(ibb.maxCorner(), cc); - auto b = pl::distance(ibb.minCorner(), cc); - auto c = pl::distance(ibb.center(), cc); - auto d = pl::distance(top_left, cc); - auto e = pl::distance(bottom_right, cc); - - auto area = bb.width() * bb.height() / norm_2; + static const double BIG_ITEM_TRESHOLD = 0.2; + static const double GRAVITY_RATIO = 0.5; + static const double DENSITY_RATIO = 1.0 - GRAVITY_RATIO; + + // We will treat big items (compared to the print bed) differently + NfpPlacer::Pile bigs; + bigs.reserve(pile.size()); + for(auto& p : pile) { + auto pbb = ShapeLike::boundingBox(p); + auto na = std::sqrt(pbb.width()*pbb.height())/norm; + if(na > BIG_ITEM_TRESHOLD) bigs.emplace_back(p); + } - auto min_dist = std::min({a, b, c, d, e}) / norm; + // Candidate item bounding box + auto ibb = item.boundingBox(); - // The score will be the normalized distance which will be minimized, - // effectively creating a circle shaped pile of items - double score = 0.8*min_dist + 0.2*area; + // Calculate the full bounding box of the pile with the candidate item + pile.emplace_back(item.transformedShape()); + auto fullbb = ShapeLike::boundingBox(pile); + pile.pop_back(); + + // The bounding box of the big items (they will accumulate in the center + // of the pile + auto bigbb = bigs.empty()? fullbb : ShapeLike::boundingBox(bigs); + + // The size indicator of the candidate item. This is not the area, + // but almost... + auto itemnormarea = std::sqrt(ibb.width()*ibb.height())/norm; + + // Will hold the resulting score + double score = 0; + + if(itemnormarea > BIG_ITEM_TRESHOLD) { + // This branch is for the bigger items.. + // Here we will use the closest point of the item bounding box to + // the already arranged pile. So not the bb center nor the a choosen + // corner but whichever is the closest to the center. This will + // prevent unwanted strange arrangements. + + auto minc = ibb.minCorner(); // bottom left corner + auto maxc = ibb.maxCorner(); // top right corner + + // top left and bottom right corners + auto top_left = PointImpl{getX(minc), getY(maxc)}; + auto bottom_right = PointImpl{getX(maxc), getY(minc)}; + + auto cc = fullbb.center(); // The gravity center + + // Now the distnce of the gravity center will be calculated to the + // five anchor points and the smallest will be chosen. + std::array dists; + dists[0] = pl::distance(minc, cc); + dists[1] = pl::distance(maxc, cc); + dists[2] = pl::distance(ibb.center(), cc); + dists[3] = pl::distance(top_left, cc); + dists[4] = pl::distance(bottom_right, cc); + + auto dist = *(std::min_element(dists.begin(), dists.end())) / norm; + + // Density is the pack density: how big is the arranged pile + auto density = std::sqrt(fullbb.width()*fullbb.height()) / norm; + + // The score is a weighted sum of the distance from pile center + // and the pile size + score = GRAVITY_RATIO * dist + DENSITY_RATIO * density; + + } else if(itemnormarea < BIG_ITEM_TRESHOLD && bigs.empty()) { + // If there are no big items, only small, we should consider the + // density here as well to not get silly results + auto bindist = pl::distance(ibb.center(), bincenter) / norm; + auto density = std::sqrt(fullbb.width()*fullbb.height()) / norm; + score = GRAVITY_RATIO * bindist + DENSITY_RATIO * density; + } else { + // Here there are the small items that should be placed around the + // already processed bigger items. + // No need to play around with the anchor points, the center will be + // just fine for small items + score = pl::distance(ibb.center(), bigbb.center()) / norm; + } // If it does not fit into the print bed we will beat it // with a large penality. If we would not do this, there would be only // one big pile that doesn't care whether it fits onto the print bed. - if(!NfpPlacer::wouldFit(bb, bin)) score = 2*penality - score; + if(!NfpPlacer::wouldFit(fullbb, bin)) score = 2*penality - score; return score; }; @@ -638,7 +707,7 @@ void arrangeRectangles() { std::vector eff; eff.reserve(result.size()); - auto bin_area = double(bin.height()*bin.width()); + auto bin_area = ShapeLike::area(bin); for(auto& r : result) { double a = 0; std::for_each(r.begin(), r.end(), [&a] (Item& e ){ a += e.area(); }); @@ -673,7 +742,7 @@ void arrangeRectangles() { SVGWriter::Config conf; conf.mm_in_coord_units = SCALE; SVGWriter svgw(conf); - svgw.setSize(bin); + svgw.setSize(Box(250*SCALE, 210*SCALE)); svgw.writePackGroup(result); // std::for_each(input.begin(), input.end(), [&svgw](Item& item){ svgw.writeItem(item);}); svgw.save("out"); diff --git a/xs/src/libnest2d/libnest2d/boost_alg.hpp b/xs/src/libnest2d/libnest2d/boost_alg.hpp index 422616d20..67e19fcbd 100644 --- a/xs/src/libnest2d/libnest2d/boost_alg.hpp +++ b/xs/src/libnest2d/libnest2d/boost_alg.hpp @@ -358,7 +358,7 @@ inline double ShapeLike::area(const PolygonImpl& shape) #endif template<> -inline bool ShapeLike::isInside(const PointImpl& point, +inline bool ShapeLike::isInside(const PointImpl& point, const PolygonImpl& shape) { return boost::geometry::within(point, shape); diff --git a/xs/src/libnest2d/libnest2d/geometry_traits.hpp b/xs/src/libnest2d/libnest2d/geometry_traits.hpp index 568c0a766..99511d775 100644 --- a/xs/src/libnest2d/libnest2d/geometry_traits.hpp +++ b/xs/src/libnest2d/libnest2d/geometry_traits.hpp @@ -3,6 +3,7 @@ #include #include +#include #include #include #include @@ -85,6 +86,31 @@ public: inline TCoord height() const BP2D_NOEXCEPT; inline RawPoint center() const BP2D_NOEXCEPT; + + inline double area() const BP2D_NOEXCEPT { + return double(width()*height()); + } +}; + +template +class _Circle { + RawPoint center_; + double radius_ = 0; +public: + + _Circle() = default; + + _Circle(const RawPoint& center, double r): center_(center), radius_(r) {} + + inline const RawPoint& center() const BP2D_NOEXCEPT { return center_; } + inline const void center(const RawPoint& c) { center_ = c; } + + inline double radius() const BP2D_NOEXCEPT { return radius_; } + inline void radius(double r) { radius_ = r; } + + inline double area() const BP2D_NOEXCEPT { + return 2.0*Pi*radius_; + } }; /** @@ -288,8 +314,8 @@ inline RawPoint _Box::center() const BP2D_NOEXCEPT { using Coord = TCoord; RawPoint ret = { - static_cast( std::round((getX(minc) + getX(maxc))/2.0) ), - static_cast( std::round((getY(minc) + getY(maxc))/2.0) ) + static_cast( (getX(minc) + getX(maxc))/2.0 ), + static_cast( (getY(minc) + getY(maxc))/2.0 ) }; return ret; @@ -614,12 +640,34 @@ struct ShapeLike { return box; } + template + static inline _Box> boundingBox( + const _Circle>& circ) + { + using Coord = TCoord>; + TPoint pmin = { + static_cast(getX(circ.center()) - circ.radius()), + static_cast(getY(circ.center()) - circ.radius()) }; + + TPoint pmax = { + static_cast(getX(circ.center()) + circ.radius()), + static_cast(getY(circ.center()) + circ.radius()) }; + + return {pmin, pmax}; + } + template static inline double area(const _Box>& box) { return static_cast(box.width() * box.height()); } + template + static inline double area(const _Circle>& circ) + { + return circ.area(); + } + template static inline double area(const Shapes& shapes) { @@ -629,6 +677,31 @@ struct ShapeLike { }); } + template + static bool isInside(const TPoint& point, + const _Circle>& circ) + { + return PointLike::distance(point, circ.center()) < circ.radius(); + } + + template + static bool isInside(const RawShape& sh, + const _Circle>& circ) + { + return std::all_of(cbegin(sh), cend(sh), + [&circ](const TPoint& p){ + return isInside(p, circ); + }); + } + + template + static bool isInside(const _Box>& box, + const _Circle>& circ) + { + return isInside(box.minCorner(), circ) && + isInside(box.maxCorner(), circ); + } + template // Potential O(1) implementation may exist static inline TPoint& vertex(RawShape& sh, unsigned long idx) { diff --git a/xs/src/libnest2d/libnest2d/libnest2d.hpp b/xs/src/libnest2d/libnest2d/libnest2d.hpp index 37b5fea95..1aa672447 100644 --- a/xs/src/libnest2d/libnest2d/libnest2d.hpp +++ b/xs/src/libnest2d/libnest2d/libnest2d.hpp @@ -254,7 +254,13 @@ public: return sl::isInside(transformedShape(), sh.transformedShape()); } + inline bool isInside(const RawShape& sh) const + { + return sl::isInside(transformedShape(), sh); + } + inline bool isInside(const _Box>& box) const; + inline bool isInside(const _Circle>& box) const; inline void translate(const Vertex& d) BP2D_NOEXCEPT { @@ -471,6 +477,11 @@ inline bool _Item::isInside(const _Box>& box) const { return _Item::isInside(rect); } +template inline bool +_Item::isInside(const _Circle>& circ) const { + return ShapeLike::isInside(transformedShape(), circ); +} + /** * \brief A wrapper interface (trait) class for any placement strategy provider. * diff --git a/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp b/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp index 61d923b87..6ae71bb48 100644 --- a/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp +++ b/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp @@ -46,14 +46,12 @@ struct NfpPConfig { * function you can e.g. influence the shape of the arranged pile. * * \param shapes The first parameter is a container with all the placed - * polygons including the current candidate. You can calculate a bounding - * box or convex hull on this pile of polygons. + * polygons excluding the current candidate. You can calculate a bounding + * box or convex hull on this pile of polygons without the candidate item + * or push back the candidate item into the container and then calculate + * some features. * - * \param item The second parameter is the candidate item. Note that - * calling transformedShape() on this second argument returns an identical - * shape as calling shapes.back(). These would not be the same objects only - * identical shapes! Using the second parameter is a lot faster due to - * caching some properties of the polygon (area, etc...) + * \param item The second parameter is the candidate item. * * \param occupied_area The third parameter is the sum of areas of the * items in the first parameter so you don't have to iterate through them @@ -127,6 +125,8 @@ template class EdgeCache { std::vector holes_; + double accuracy_ = 1.0; + void createCache(const RawShape& sh) { { // For the contour auto first = ShapeLike::cbegin(sh); @@ -160,11 +160,25 @@ template class EdgeCache { } } + size_t stride(const size_t N) const { + using std::ceil; + using std::round; + using std::pow; + + return static_cast( + round( N/(ceil(pow(accuracy_, 2)*(N-1)) + 1) ) + ); + } + void fetchCorners() const { if(!contour_.corners.empty()) return; - contour_.corners.reserve(contour_.distances.size() / 3 + 1); - for(size_t i = 0; i < contour_.distances.size() - 1; i += 3) { + const auto N = contour_.distances.size(); + const auto S = stride(N); + + contour_.corners.reserve(N / S + 1); + auto N_1 = N-1; + for(size_t i = 0; i < N_1; i += S) { contour_.corners.emplace_back( contour_.distances.at(i) / contour_.full_distance); } @@ -174,8 +188,11 @@ template class EdgeCache { auto& hc = holes_[hidx]; if(!hc.corners.empty()) return; - hc.corners.reserve(hc.distances.size() / 3 + 1); - for(size_t i = 0; i < hc.distances.size() - 1; i += 3) { + const auto N = hc.distances.size(); + const auto S = stride(N); + auto N_1 = N-1; + hc.corners.reserve(N / S + 1); + for(size_t i = 0; i < N_1; i += S) { hc.corners.emplace_back( hc.distances.at(i) / hc.full_distance); } @@ -224,6 +241,9 @@ public: createCache(sh); } + /// Resolution of returned corners. The stride is derived from this value. + void accuracy(double a /* within <0.0, 1.0>*/) { accuracy_ = a; } + /** * @brief Get a point on the circumference of a polygon. * @param distance A relative distance from the starting point to the end. @@ -419,12 +439,12 @@ Nfp::Shapes nfp( const Container& polygons, // return nfps; } -template -class _NofitPolyPlacer: public PlacerBoilerplate<_NofitPolyPlacer, - RawShape, _Box>, NfpPConfig> { +template>> +class _NofitPolyPlacer: public PlacerBoilerplate<_NofitPolyPlacer, + RawShape, TBin, NfpPConfig> { - using Base = PlacerBoilerplate<_NofitPolyPlacer, - RawShape, _Box>, NfpPConfig>; + using Base = PlacerBoilerplate<_NofitPolyPlacer, + RawShape, TBin, NfpPConfig>; DECLARE_PLACER(Base) @@ -434,6 +454,7 @@ class _NofitPolyPlacer: public PlacerBoilerplate<_NofitPolyPlacer, const double penality_; using MaxNfpLevel = Nfp::MaxNfpLevel; + using sl = ShapeLike; public: @@ -441,7 +462,7 @@ public: inline explicit _NofitPolyPlacer(const BinType& bin): Base(bin), - norm_(std::sqrt(ShapeLike::area(bin))), + norm_(std::sqrt(sl::area(bin))), penality_(1e6*norm_) {} _NofitPolyPlacer(const _NofitPolyPlacer&) = default; @@ -452,18 +473,26 @@ public: _NofitPolyPlacer& operator=(_NofitPolyPlacer&&) BP2D_NOEXCEPT = default; #endif + bool static inline wouldFit(const Box& bb, const RawShape& bin) { + auto bbin = sl::boundingBox(bin); + auto d = bbin.center() - bb.center(); + _Rectangle rect(bb.width(), bb.height()); + rect.translate(bb.minCorner() + d); + return sl::isInside(rect.transformedShape(), bin); + } + bool static inline wouldFit(const RawShape& chull, const RawShape& bin) { - auto bbch = ShapeLike::boundingBox(chull); - auto bbin = ShapeLike::boundingBox(bin); - auto d = bbin.minCorner() - bbch.minCorner(); + auto bbch = sl::boundingBox(chull); + auto bbin = sl::boundingBox(bin); + auto d = bbin.center() - bbch.center(); auto chullcpy = chull; - ShapeLike::translate(chullcpy, d); - return ShapeLike::isInside(chullcpy, bbin); + sl::translate(chullcpy, d); + return sl::isInside(chullcpy, bin); } bool static inline wouldFit(const RawShape& chull, const Box& bin) { - auto bbch = ShapeLike::boundingBox(chull); + auto bbch = sl::boundingBox(chull); return wouldFit(bbch, bin); } @@ -472,6 +501,17 @@ public: return bb.width() <= bin.width() && bb.height() <= bin.height(); } + bool static inline wouldFit(const Box& bb, const _Circle& bin) + { + return sl::isInside(bb, bin); + } + + bool static inline wouldFit(const RawShape& chull, + const _Circle& bin) + { + return sl::isInside(chull, bin); + } + PackResult trypack(Item& item) { PackResult ret; @@ -510,7 +550,10 @@ public: std::vector> ecache; ecache.reserve(nfps.size()); - for(auto& nfp : nfps ) ecache.emplace_back(nfp); + for(auto& nfp : nfps ) { + ecache.emplace_back(nfp); + ecache.back().accuracy(config_.accuracy); + } struct Optimum { double relpos; @@ -540,14 +583,16 @@ public: // customizable by the library client auto _objfunc = config_.object_function? config_.object_function : - [this](Nfp::Shapes& pile, Item, + [this](Nfp::Shapes& pile, const Item& item, double occupied_area, double /*norm*/, double penality) { - auto ch = ShapeLike::convexHull(pile); + pile.emplace_back(item.transformedShape()); + auto ch = sl::convexHull(pile); + pile.pop_back(); // The pack ratio -- how much is the convex hull occupied - double pack_rate = occupied_area/ShapeLike::area(ch); + double pack_rate = occupied_area/sl::area(ch); // ratio of waste double waste = 1.0 - pack_rate; @@ -569,22 +614,17 @@ public: d += startpos; item.translation(d); -// pile.emplace_back(item.transformedShape()); - double occupied_area = pile_area + item.area(); double score = _objfunc(pile, item, occupied_area, norm_, penality_); -// pile.pop_back(); - return score; }; opt::StopCriteria stopcr; stopcr.max_iterations = 1000; stopcr.absolute_score_difference = 1e-20*norm_; -// stopcr.relative_score_difference = 1e-20; opt::TOptimizer solver(stopcr); Optimum optimum(0, 0); @@ -702,34 +742,35 @@ public: m.reserve(items_.size()); for(Item& item : items_) m.emplace_back(item.transformedShape()); - auto&& bb = ShapeLike::boundingBox(m); + auto&& bb = sl::boundingBox(m); Vertex ci, cb; + auto bbin = sl::boundingBox(bin_); switch(config_.alignment) { case Config::Alignment::CENTER: { ci = bb.center(); - cb = bin_.center(); + cb = bbin.center(); break; } case Config::Alignment::BOTTOM_LEFT: { ci = bb.minCorner(); - cb = bin_.minCorner(); + cb = bbin.minCorner(); break; } case Config::Alignment::BOTTOM_RIGHT: { ci = {getX(bb.maxCorner()), getY(bb.minCorner())}; - cb = {getX(bin_.maxCorner()), getY(bin_.minCorner())}; + cb = {getX(bbin.maxCorner()), getY(bbin.minCorner())}; break; } case Config::Alignment::TOP_LEFT: { ci = {getX(bb.minCorner()), getY(bb.maxCorner())}; - cb = {getX(bin_.minCorner()), getY(bin_.maxCorner())}; + cb = {getX(bbin.minCorner()), getY(bbin.maxCorner())}; break; } case Config::Alignment::TOP_RIGHT: { ci = bb.maxCorner(); - cb = bin_.maxCorner(); + cb = bbin.maxCorner(); break; } } @@ -745,31 +786,32 @@ private: void setInitialPosition(Item& item) { Box&& bb = item.boundingBox(); Vertex ci, cb; + auto bbin = sl::boundingBox(bin_); switch(config_.starting_point) { case Config::Alignment::CENTER: { ci = bb.center(); - cb = bin_.center(); + cb = bbin.center(); break; } case Config::Alignment::BOTTOM_LEFT: { ci = bb.minCorner(); - cb = bin_.minCorner(); + cb = bbin.minCorner(); break; } case Config::Alignment::BOTTOM_RIGHT: { ci = {getX(bb.maxCorner()), getY(bb.minCorner())}; - cb = {getX(bin_.maxCorner()), getY(bin_.minCorner())}; + cb = {getX(bbin.maxCorner()), getY(bbin.minCorner())}; break; } case Config::Alignment::TOP_LEFT: { ci = {getX(bb.minCorner()), getY(bb.maxCorner())}; - cb = {getX(bin_.minCorner()), getY(bin_.maxCorner())}; + cb = {getX(bbin.minCorner()), getY(bbin.maxCorner())}; break; } case Config::Alignment::TOP_RIGHT: { ci = bb.maxCorner(); - cb = bin_.maxCorner(); + cb = bbin.maxCorner(); break; } } @@ -780,7 +822,7 @@ private: void placeOutsideOfBin(Item& item) { auto&& bb = item.boundingBox(); - Box binbb = ShapeLike::boundingBox(bin_); + Box binbb = sl::boundingBox(bin_); Vertex v = { getX(bb.maxCorner()), getY(bb.minCorner()) }; diff --git a/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp b/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp index 17ac1167d..e3ad97c10 100644 --- a/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp +++ b/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp @@ -535,7 +535,7 @@ public: // then it should be removed from the not_packed list { auto it = store_.begin(); while (it != store_.end()) { - Placer p(bin); + Placer p(bin); p.configure(pconfig); if(!p.pack(*it)) { it = store_.erase(it); } else it++; diff --git a/xs/src/libnest2d/libnest2d/selections/firstfit.hpp b/xs/src/libnest2d/libnest2d/selections/firstfit.hpp index f34961f80..665b9da9f 100644 --- a/xs/src/libnest2d/libnest2d/selections/firstfit.hpp +++ b/xs/src/libnest2d/libnest2d/selections/firstfit.hpp @@ -59,7 +59,7 @@ public: // then it should be removed from the list { auto it = store_.begin(); while (it != store_.end()) { - Placer p(bin); + Placer p(bin); p.configure(pconfig); if(!p.pack(*it)) { it = store_.erase(it); } else it++; -- cgit v1.2.3