diff options
| author | tamasmeszaros <meszaros.q@gmail.com> | 2018-08-09 10:59:05 +0300 |
|---|---|---|
| committer | tamasmeszaros <meszaros.q@gmail.com> | 2018-08-09 11:59:00 +0300 |
| commit | e678368b233670ab6a707f87b42306964f12d463 (patch) | |
| tree | 5b5277b3a2347fa8dcd0517909456adfb41e6513 | |
| parent | 1764f3b57b49e6c9c4c0a0c86bacf9befe3839d2 (diff) | |
fix compilation on linux and macbefore_parallel_arrange
18 files changed, 590 insertions, 543 deletions
diff --git a/xs/src/libnest2d/CMakeLists.txt b/xs/src/libnest2d/CMakeLists.txt index 835e8311d..0a181f4ab 100644 --- a/xs/src/libnest2d/CMakeLists.txt +++ b/xs/src/libnest2d/CMakeLists.txt @@ -31,6 +31,7 @@ set(LIBNEST2D_SRCFILES ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/common.hpp ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/optimizer.hpp ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/metaloop.hpp + ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/rotfinder.hpp ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/placers/placer_boilerplate.hpp ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/placers/bottomleftplacer.hpp ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/placers/nfpplacer.hpp diff --git a/xs/src/libnest2d/examples/main.cpp b/xs/src/libnest2d/examples/main.cpp index 11f8f50cf..37096019d 100644 --- a/xs/src/libnest2d/examples/main.cpp +++ b/xs/src/libnest2d/examples/main.cpp @@ -9,6 +9,8 @@ #include "tests/printer_parts.h" #include "tools/benchmark.h" #include "tools/svgtools.hpp" +#include "libnest2d/rotfinder.hpp" + //#include "tools/libnfpglue.hpp" using namespace libnest2d; @@ -64,7 +66,7 @@ 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}, @@ -80,12 +82,12 @@ void arrangeRectangles() { // {} // }; - _Circle<PointImpl> bin({0, 0}, 125*SCALE); +// _Circle<PointImpl> bin({0, 0}, 125*SCALE); auto min_obj_distance = static_cast<Coord>(0*SCALE); using Placer = strategies::_NofitPolyPlacer<PolygonImpl, decltype(bin)>; - using Packer = Arranger<Placer, FirstFitSelection>; + using Packer = Nester<Placer, FirstFitSelection>; Packer arrange(bin, min_obj_distance); @@ -112,7 +114,9 @@ void arrangeRectangles() { // svgw.writePackGroup(arrange.lastResult()); // svgw.save("debout"); std::cout << "Remaining items: " << r << std::endl; - })/*.useMinimumBoundigBoxRotation()*/; + }); + +// findMinimumBoundingBoxRotations(input.begin(), input.end()); Benchmark bench; @@ -120,7 +124,7 @@ void arrangeRectangles() { Packer::ResultType result; try { - result = arrange.arrange(input.begin(), input.end()); + result = arrange.execute(input.begin(), input.end()); } catch(GeometryException& ge) { std::cerr << "Geometry error: " << ge.what() << std::endl; return ; @@ -134,7 +138,7 @@ void arrangeRectangles() { std::vector<double> eff; eff.reserve(result.size()); - auto bin_area = ShapeLike::area<PolygonImpl>(bin); + auto bin_area = sl::area(bin); for(auto& r : result) { double a = 0; std::for_each(r.begin(), r.end(), [&a] (Item& e ){ a += e.area(); }); @@ -156,7 +160,7 @@ void arrangeRectangles() { std::cout << ") Total: " << total << std::endl; for(auto& it : input) { - auto ret = ShapeLike::isValid(it.transformedShape()); + auto ret = sl::isValid(it.transformedShape()); std::cout << ret.second << std::endl; } @@ -177,7 +181,7 @@ void arrangeRectangles() { int main(void /*int argc, char **argv*/) { arrangeRectangles(); -// findDegenerateCase(); +//// findDegenerateCase(); return EXIT_SUCCESS; } diff --git a/xs/src/libnest2d/libnest2d.h b/xs/src/libnest2d/libnest2d.h index c9e21ecfb..05677afd7 100644 --- a/xs/src/libnest2d/libnest2d.h +++ b/xs/src/libnest2d/libnest2d.h @@ -22,6 +22,7 @@ using Point = PointImpl; using Coord = TCoord<PointImpl>; using Box = _Box<PointImpl>; using Segment = _Segment<PointImpl>; +using Circle = _Circle<PointImpl>; using Item = _Item<PolygonImpl>; using Rectangle = _Rectangle<PolygonImpl>; @@ -36,9 +37,6 @@ using DJDHeuristic = strategies::_DJDHeuristic<PolygonImpl>; using NfpPlacer = strategies::_NofitPolyPlacer<PolygonImpl>; using BottomLeftPlacer = strategies::_BottomLeftPlacer<PolygonImpl>; -//template<NfpLevel lvl = NfpLevel::BOTH_CONCAVE_WITH_HOLES> -//using NofitPolyPlacer = strategies::_NofitPolyPlacer<PolygonImpl, lvl>; - } #endif // LIBNEST2D_H diff --git a/xs/src/libnest2d/libnest2d/boost_alg.hpp b/xs/src/libnest2d/libnest2d/boost_alg.hpp index 67e19fcbd..7da1036f0 100644 --- a/xs/src/libnest2d/libnest2d/boost_alg.hpp +++ b/xs/src/libnest2d/libnest2d/boost_alg.hpp @@ -36,7 +36,7 @@ using libnest2d::setX; using libnest2d::setY; using Box = libnest2d::_Box<PointImpl>; using Segment = libnest2d::_Segment<PointImpl>; -using Shapes = libnest2d::Nfp::Shapes<PolygonImpl>; +using Shapes = libnest2d::nfp::Shapes<PolygonImpl>; } @@ -241,11 +241,11 @@ template<> struct tag<bp2d::PolygonImpl> { template<> struct exterior_ring<bp2d::PolygonImpl> { static inline bp2d::PathImpl& get(bp2d::PolygonImpl& p) { - return libnest2d::ShapeLike::getContour(p); + return libnest2d::shapelike::getContour(p); } static inline bp2d::PathImpl const& get(bp2d::PolygonImpl const& p) { - return libnest2d::ShapeLike::getContour(p); + return libnest2d::shapelike::getContour(p); } }; @@ -271,13 +271,13 @@ struct interior_rings<bp2d::PolygonImpl> { static inline libnest2d::THolesContainer<bp2d::PolygonImpl>& get( bp2d::PolygonImpl& p) { - return libnest2d::ShapeLike::holes(p); + return libnest2d::shapelike::holes(p); } static inline const libnest2d::THolesContainer<bp2d::PolygonImpl>& get( bp2d::PolygonImpl const& p) { - return libnest2d::ShapeLike::holes(p); + return libnest2d::shapelike::holes(p); } }; @@ -311,83 +311,78 @@ struct range_value<bp2d::Shapes> { namespace libnest2d { // Now the algorithms that boost can provide... +namespace pointlike { template<> -inline double PointLike::distance(const PointImpl& p1, - const PointImpl& p2 ) +inline double distance(const PointImpl& p1, const PointImpl& p2 ) { return boost::geometry::distance(p1, p2); } template<> -inline double PointLike::distance(const PointImpl& p, - const bp2d::Segment& seg ) +inline double distance(const PointImpl& p, const bp2d::Segment& seg ) { return boost::geometry::distance(p, seg); } +} +namespace shapelike { // Tell libnest2d how to make string out of a ClipperPolygon object template<> -inline bool ShapeLike::intersects(const PathImpl& sh1, - const PathImpl& sh2) +inline bool intersects(const PathImpl& sh1, const PathImpl& sh2) { return boost::geometry::intersects(sh1, sh2); } // Tell libnest2d how to make string out of a ClipperPolygon object template<> -inline bool ShapeLike::intersects(const PolygonImpl& sh1, - const PolygonImpl& sh2) +inline bool intersects(const PolygonImpl& sh1, const PolygonImpl& sh2) { return boost::geometry::intersects(sh1, sh2); } // Tell libnest2d how to make string out of a ClipperPolygon object template<> -inline bool ShapeLike::intersects(const bp2d::Segment& s1, - const bp2d::Segment& s2) +inline bool intersects(const bp2d::Segment& s1, const bp2d::Segment& s2) { return boost::geometry::intersects(s1, s2); } #ifndef DISABLE_BOOST_AREA template<> -inline double ShapeLike::area(const PolygonImpl& shape) +inline double area(const PolygonImpl& shape, const PolygonTag&) { return boost::geometry::area(shape); } #endif template<> -inline bool ShapeLike::isInside<PolygonImpl>(const PointImpl& point, - const PolygonImpl& shape) +inline bool isInside<PolygonImpl>(const PointImpl& point, + const PolygonImpl& shape) { return boost::geometry::within(point, shape); } template<> -inline bool ShapeLike::isInside(const PolygonImpl& sh1, - const PolygonImpl& sh2) +inline bool isInside(const PolygonImpl& sh1, const PolygonImpl& sh2) { return boost::geometry::within(sh1, sh2); } template<> -inline bool ShapeLike::touches( const PolygonImpl& sh1, - const PolygonImpl& sh2) +inline bool touches(const PolygonImpl& sh1, const PolygonImpl& sh2) { return boost::geometry::touches(sh1, sh2); } template<> -inline bool ShapeLike::touches( const PointImpl& point, - const PolygonImpl& shape) +inline bool touches( const PointImpl& point, const PolygonImpl& shape) { return boost::geometry::touches(point, shape); } #ifndef DISABLE_BOOST_BOUNDING_BOX template<> -inline bp2d::Box ShapeLike::boundingBox(const PolygonImpl& sh) +inline bp2d::Box boundingBox(const PolygonImpl& sh, const PolygonTag&) { bp2d::Box b; boost::geometry::envelope(sh, b); @@ -395,7 +390,7 @@ inline bp2d::Box ShapeLike::boundingBox(const PolygonImpl& sh) } template<> -inline bp2d::Box ShapeLike::boundingBox<PolygonImpl>(const bp2d::Shapes& shapes) +inline bp2d::Box boundingBox<PolygonImpl>(const bp2d::Shapes& shapes) { bp2d::Box b; boost::geometry::envelope(shapes, b); @@ -405,7 +400,7 @@ inline bp2d::Box ShapeLike::boundingBox<PolygonImpl>(const bp2d::Shapes& shapes) #ifndef DISABLE_BOOST_CONVEX_HULL template<> -inline PolygonImpl ShapeLike::convexHull(const PolygonImpl& sh) +inline PolygonImpl convexHull(const PolygonImpl& sh) { PolygonImpl ret; boost::geometry::convex_hull(sh, ret); @@ -413,7 +408,7 @@ inline PolygonImpl ShapeLike::convexHull(const PolygonImpl& sh) } template<> -inline PolygonImpl ShapeLike::convexHull(const bp2d::Shapes& shapes) +inline PolygonImpl convexHull(const bp2d::Shapes& shapes) { PolygonImpl ret; boost::geometry::convex_hull(shapes, ret); @@ -423,7 +418,7 @@ inline PolygonImpl ShapeLike::convexHull(const bp2d::Shapes& shapes) #ifndef DISABLE_BOOST_ROTATE template<> -inline void ShapeLike::rotate(PolygonImpl& sh, const Radians& rads) +inline void rotate(PolygonImpl& sh, const Radians& rads) { namespace trans = boost::geometry::strategy::transform; @@ -437,7 +432,7 @@ inline void ShapeLike::rotate(PolygonImpl& sh, const Radians& rads) #ifndef DISABLE_BOOST_TRANSLATE template<> -inline void ShapeLike::translate(PolygonImpl& sh, const PointImpl& offs) +inline void translate(PolygonImpl& sh, const PointImpl& offs) { namespace trans = boost::geometry::strategy::transform; @@ -451,26 +446,15 @@ inline void ShapeLike::translate(PolygonImpl& sh, const PointImpl& offs) #ifndef DISABLE_BOOST_OFFSET template<> -inline void ShapeLike::offset(PolygonImpl& sh, bp2d::Coord distance) +inline void offset(PolygonImpl& sh, bp2d::Coord distance) { PolygonImpl cpy = sh; boost::geometry::buffer(cpy, sh, distance); } #endif -#ifndef DISABLE_BOOST_NFP_MERGE -template<> -inline bp2d::Shapes Nfp::merge(const bp2d::Shapes& shapes, - const PolygonImpl& sh) -{ - bp2d::Shapes retv; - boost::geometry::union_(shapes, sh, retv); - return retv; -} -#endif - #ifndef DISABLE_BOOST_SERIALIZE -template<> inline std::string ShapeLike::serialize<libnest2d::Formats::SVG>( +template<> inline std::string serialize<libnest2d::Formats::SVG>( const PolygonImpl& sh, double scale) { std::stringstream ss; @@ -482,14 +466,14 @@ template<> inline std::string ShapeLike::serialize<libnest2d::Formats::SVG>( Polygonf::ring_type ring; Polygonf::inner_container_type holes; - ring.reserve(ShapeLike::contourVertexCount(sh)); + ring.reserve(shapelike::contourVertexCount(sh)); - for(auto it = ShapeLike::cbegin(sh); it != ShapeLike::cend(sh); it++) { + for(auto it = shapelike::cbegin(sh); it != shapelike::cend(sh); it++) { auto& v = *it; ring.emplace_back(getX(v)*scale, getY(v)*scale); }; - auto H = ShapeLike::holes(sh); + auto H = shapelike::holes(sh); for(PathImpl& h : H ) { Polygonf::ring_type hf; for(auto it = h.begin(); it != h.end(); it++) { @@ -512,21 +496,37 @@ template<> inline std::string ShapeLike::serialize<libnest2d::Formats::SVG>( #ifndef DISABLE_BOOST_UNSERIALIZE template<> -inline void ShapeLike::unserialize<libnest2d::Formats::SVG>( +inline void unserialize<libnest2d::Formats::SVG>( PolygonImpl& sh, const std::string& str) { } #endif -template<> inline std::pair<bool, std::string> -ShapeLike::isValid(const PolygonImpl& sh) +template<> inline std::pair<bool, std::string> isValid(const PolygonImpl& sh) { std::string message; bool ret = boost::geometry::is_valid(sh, message); return {ret, message}; } +} + +namespace nfp { + +#ifndef DISABLE_BOOST_NFP_MERGE +template<> +inline bp2d::Shapes Nfp::merge(const bp2d::Shapes& shapes, + const PolygonImpl& sh) +{ + bp2d::Shapes retv; + boost::geometry::union_(shapes, sh, retv); + return retv; +} +#endif + +} + } diff --git a/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.hpp b/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.hpp index 15ceb1576..4238212ad 100644 --- a/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.hpp +++ b/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.hpp @@ -21,6 +21,9 @@ struct PolygonImpl { PathImpl Contour; HoleStore Holes; + using Tag = libnest2d::PolygonTag; + using PointType = PointImpl; + inline PolygonImpl() = default; inline explicit PolygonImpl(const PathImpl& cont): Contour(cont) {} @@ -113,35 +116,32 @@ template<> struct CountourType<PolygonImpl> { using Type = PathImpl; }; +namespace pointlike { + // Tell binpack2d how to extract the X coord from a ClipperPoint object -template<> inline TCoord<PointImpl> PointLike::x(const PointImpl& p) +template<> inline TCoord<PointImpl> x(const PointImpl& p) { return p.X; } // Tell binpack2d how to extract the Y coord from a ClipperPoint object -template<> inline TCoord<PointImpl> PointLike::y(const PointImpl& p) +template<> inline TCoord<PointImpl> y(const PointImpl& p) { return p.Y; } // Tell binpack2d how to extract the X coord from a ClipperPoint object -template<> inline TCoord<PointImpl>& PointLike::x(PointImpl& p) +template<> inline TCoord<PointImpl>& x(PointImpl& p) { return p.X; } // Tell binpack2d how to extract the Y coord from a ClipperPoint object -template<> -inline TCoord<PointImpl>& PointLike::y(PointImpl& p) +template<> inline TCoord<PointImpl>& y(PointImpl& p) { return p.Y; } -template<> -inline void ShapeLike::reserve(PolygonImpl& sh, size_t vertex_capacity) -{ - return sh.Contour.reserve(vertex_capacity); } #define DISABLE_BOOST_AREA @@ -175,16 +175,28 @@ inline double area<Orientation::COUNTER_CLOCKWISE>(const PolygonImpl& sh) { return ClipperLib::Area(sh.Contour) + a; } + +} + +template<> struct HolesContainer<PolygonImpl> { + using Type = ClipperLib::Paths; +}; + +namespace shapelike { + +template<> inline void reserve(PolygonImpl& sh, size_t vertex_capacity) +{ + return sh.Contour.reserve(vertex_capacity); } // Tell binpack2d how to make string out of a ClipperPolygon object -template<> -inline double ShapeLike::area(const PolygonImpl& sh) { +template<> inline double area(const PolygonImpl& sh, const PolygonTag&) +{ return _smartarea::area<OrientationType<PolygonImpl>::Value>(sh); } -template<> -inline void ShapeLike::offset(PolygonImpl& sh, TCoord<PointImpl> distance) { +template<> inline void offset(PolygonImpl& sh, TCoord<PointImpl> distance) +{ #define DISABLE_BOOST_OFFSET using ClipperLib::ClipperOffset; @@ -234,7 +246,8 @@ inline void ShapeLike::offset(PolygonImpl& sh, TCoord<PointImpl> distance) { } // Tell libnest2d how to make string out of a ClipperPolygon object -template<> inline std::string ShapeLike::toString(const PolygonImpl& sh) { +template<> inline std::string toString(const PolygonImpl& sh) +{ std::stringstream ss; ss << "Contour {\n"; @@ -256,38 +269,31 @@ template<> inline std::string ShapeLike::toString(const PolygonImpl& sh) { return ss.str(); } -template<> -inline TVertexIterator<PolygonImpl> ShapeLike::begin(PolygonImpl& sh) +template<> inline TVertexIterator<PolygonImpl> begin(PolygonImpl& sh) { return sh.Contour.begin(); } -template<> -inline TVertexIterator<PolygonImpl> ShapeLike::end(PolygonImpl& sh) +template<> inline TVertexIterator<PolygonImpl> end(PolygonImpl& sh) { return sh.Contour.end(); } template<> -inline TVertexConstIterator<PolygonImpl> ShapeLike::cbegin( - const PolygonImpl& sh) +inline TVertexConstIterator<PolygonImpl> cbegin(const PolygonImpl& sh) { return sh.Contour.cbegin(); } -template<> -inline TVertexConstIterator<PolygonImpl> ShapeLike::cend( +template<> inline TVertexConstIterator<PolygonImpl> cend( const PolygonImpl& sh) { return sh.Contour.cend(); } -template<> struct HolesContainer<PolygonImpl> { - using Type = ClipperLib::Paths; -}; - -template<> inline PolygonImpl ShapeLike::create(const PathImpl& path, - const HoleStore& holes) { +template<> +inline PolygonImpl create(const PathImpl& path, const HoleStore& holes) +{ PolygonImpl p; p.Contour = path; @@ -308,8 +314,7 @@ template<> inline PolygonImpl ShapeLike::create(const PathImpl& path, return p; } -template<> inline PolygonImpl ShapeLike::create( PathImpl&& path, - HoleStore&& holes) { +template<> inline PolygonImpl create( PathImpl&& path, HoleStore&& holes) { PolygonImpl p; p.Contour.swap(path); @@ -331,49 +336,49 @@ template<> inline PolygonImpl ShapeLike::create( PathImpl&& path, return p; } -template<> inline const THolesContainer<PolygonImpl>& -ShapeLike::holes(const PolygonImpl& sh) +template<> +inline const THolesContainer<PolygonImpl>& holes(const PolygonImpl& sh) { return sh.Holes; } -template<> inline THolesContainer<PolygonImpl>& -ShapeLike::holes(PolygonImpl& sh) +template<> inline THolesContainer<PolygonImpl>& holes(PolygonImpl& sh) { return sh.Holes; } -template<> inline TContour<PolygonImpl>& -ShapeLike::getHole(PolygonImpl& sh, unsigned long idx) +template<> +inline TContour<PolygonImpl>& getHole(PolygonImpl& sh, unsigned long idx) { return sh.Holes[idx]; } -template<> inline const TContour<PolygonImpl>& -ShapeLike::getHole(const PolygonImpl& sh, unsigned long idx) +template<> +inline const TContour<PolygonImpl>& getHole(const PolygonImpl& sh, + unsigned long idx) { return sh.Holes[idx]; } -template<> inline size_t ShapeLike::holeCount(const PolygonImpl& sh) +template<> inline size_t holeCount(const PolygonImpl& sh) { return sh.Holes.size(); } -template<> inline PathImpl& ShapeLike::getContour(PolygonImpl& sh) +template<> inline PathImpl& getContour(PolygonImpl& sh) { return sh.Contour; } template<> -inline const PathImpl& ShapeLike::getContour(const PolygonImpl& sh) +inline const PathImpl& getContour(const PolygonImpl& sh) { return sh.Contour; } #define DISABLE_BOOST_TRANSLATE template<> -inline void ShapeLike::translate(PolygonImpl& sh, const PointImpl& offs) +inline void translate(PolygonImpl& sh, const PointImpl& offs) { for(auto& p : sh.Contour) { p += offs; } for(auto& hole : sh.Holes) for(auto& p : hole) { p += offs; } @@ -381,7 +386,7 @@ inline void ShapeLike::translate(PolygonImpl& sh, const PointImpl& offs) #define DISABLE_BOOST_ROTATE template<> -inline void ShapeLike::rotate(PolygonImpl& sh, const Radians& rads) +inline void rotate(PolygonImpl& sh, const Radians& rads) { using Coord = TCoord<PointImpl>; @@ -402,9 +407,11 @@ inline void ShapeLike::rotate(PolygonImpl& sh, const Radians& rads) } } +} // namespace shapelike + #define DISABLE_BOOST_NFP_MERGE -inline Nfp::Shapes<PolygonImpl> _merge(ClipperLib::Clipper& clipper) { - Nfp::Shapes<PolygonImpl> retv; +inline nfp::Shapes<PolygonImpl> _merge(ClipperLib::Clipper& clipper) { + nfp::Shapes<PolygonImpl> retv; ClipperLib::PolyTree result; clipper.Execute(ClipperLib::ctUnion, result, ClipperLib::pftNegative); @@ -438,8 +445,10 @@ inline Nfp::Shapes<PolygonImpl> _merge(ClipperLib::Clipper& clipper) { return retv; } -template<> inline Nfp::Shapes<PolygonImpl> -Nfp::merge(const Nfp::Shapes<PolygonImpl>& shapes) +namespace nfp { + +template<> inline nfp::Shapes<PolygonImpl> +merge(const nfp::Shapes<PolygonImpl>& shapes) { ClipperLib::Clipper clipper(ClipperLib::ioReverseSolution); @@ -461,6 +470,8 @@ Nfp::merge(const Nfp::Shapes<PolygonImpl>& shapes) } +} + //#define DISABLE_BOOST_SERIALIZE //#define DISABLE_BOOST_UNSERIALIZE diff --git a/xs/src/libnest2d/libnest2d/geometry_traits.hpp b/xs/src/libnest2d/libnest2d/geometry_traits.hpp index 1c0d44c9f..0826cbd4b 100644 --- a/xs/src/libnest2d/libnest2d/geometry_traits.hpp +++ b/xs/src/libnest2d/libnest2d/geometry_traits.hpp @@ -60,6 +60,10 @@ struct PointPair { RawPoint p2; }; +struct PolygonTag {}; +struct BoxTag {}; +struct CircleTag {}; + /** * \brief An abstraction of a box; */ @@ -69,6 +73,9 @@ class _Box: PointPair<RawPoint> { using PointPair<RawPoint>::p2; public: + using Tag = BoxTag; + using PointType = RawPoint; + inline _Box() = default; inline _Box(const RawPoint& p, const RawPoint& pp): PointPair<RawPoint>({p, pp}) {} @@ -98,6 +105,9 @@ class _Circle { double radius_ = 0; public: + using Tag = CircleTag; + using PointType = RawPoint; + _Circle() = default; _Circle(const RawPoint& center, double r): center_(center), radius_(r) {} @@ -123,6 +133,8 @@ class _Segment: PointPair<RawPoint> { mutable Radians angletox_ = std::nan(""); public: + using PointType = RawPoint; + inline _Segment() = default; inline _Segment(const RawPoint& p, const RawPoint& pp): @@ -156,36 +168,36 @@ public: inline double length(); }; -// This struct serves as a namespace. The only difference is that is can be +// This struct serves almost as a namespace. The only difference is that is can // used in friend declarations. -struct PointLike { +namespace pointlike { template<class RawPoint> - static TCoord<RawPoint> x(const RawPoint& p) + inline TCoord<RawPoint> x(const RawPoint& p) { return p.x(); } template<class RawPoint> - static TCoord<RawPoint> y(const RawPoint& p) + inline TCoord<RawPoint> y(const RawPoint& p) { return p.y(); } template<class RawPoint> - static TCoord<RawPoint>& x(RawPoint& p) + inline TCoord<RawPoint>& x(RawPoint& p) { return p.x(); } template<class RawPoint> - static TCoord<RawPoint>& y(RawPoint& p) + inline TCoord<RawPoint>& y(RawPoint& p) { return p.y(); } template<class RawPoint> - static double distance(const RawPoint& /*p1*/, const RawPoint& /*p2*/) + inline double distance(const RawPoint& /*p1*/, const RawPoint& /*p2*/) { static_assert(always_false<RawPoint>::value, "PointLike::distance(point, point) unimplemented!"); @@ -193,7 +205,7 @@ struct PointLike { } template<class RawPoint> - static double distance(const RawPoint& /*p1*/, + inline double distance(const RawPoint& /*p1*/, const _Segment<RawPoint>& /*s*/) { static_assert(always_false<RawPoint>::value, @@ -202,13 +214,13 @@ struct PointLike { } template<class RawPoint> - static std::pair<TCoord<RawPoint>, bool> horizontalDistance( + inline std::pair<TCoord<RawPoint>, bool> horizontalDistance( const RawPoint& p, const _Segment<RawPoint>& s) { using Unit = TCoord<RawPoint>; - auto x = PointLike::x(p), y = PointLike::y(p); - auto x1 = PointLike::x(s.first()), y1 = PointLike::y(s.first()); - auto x2 = PointLike::x(s.second()), y2 = PointLike::y(s.second()); + auto x = pointlike::x(p), y = pointlike::y(p); + auto x1 = pointlike::x(s.first()), y1 = pointlike::y(s.first()); + auto x2 = pointlike::x(s.second()), y2 = pointlike::y(s.second()); TCoord<RawPoint> ret; @@ -228,13 +240,13 @@ struct PointLike { } template<class RawPoint> - static std::pair<TCoord<RawPoint>, bool> verticalDistance( + inline std::pair<TCoord<RawPoint>, bool> verticalDistance( const RawPoint& p, const _Segment<RawPoint>& s) { using Unit = TCoord<RawPoint>; - auto x = PointLike::x(p), y = PointLike::y(p); - auto x1 = PointLike::x(s.first()), y1 = PointLike::y(s.first()); - auto x2 = PointLike::x(s.second()), y2 = PointLike::y(s.second()); + auto x = pointlike::x(p), y = pointlike::y(p); + auto x1 = pointlike::x(s.first()), y1 = pointlike::y(s.first()); + auto x2 = pointlike::x(s.second()), y2 = pointlike::y(s.second()); TCoord<RawPoint> ret; @@ -252,36 +264,36 @@ struct PointLike { return {ret, true}; } -}; +} template<class RawPoint> TCoord<RawPoint> _Box<RawPoint>::width() const BP2D_NOEXCEPT { - return PointLike::x(maxCorner()) - PointLike::x(minCorner()); + return pointlike::x(maxCorner()) - pointlike::x(minCorner()); } template<class RawPoint> TCoord<RawPoint> _Box<RawPoint>::height() const BP2D_NOEXCEPT { - return PointLike::y(maxCorner()) - PointLike::y(minCorner()); + return pointlike::y(maxCorner()) - pointlike::y(minCorner()); } template<class RawPoint> -TCoord<RawPoint> getX(const RawPoint& p) { return PointLike::x<RawPoint>(p); } +TCoord<RawPoint> getX(const RawPoint& p) { return pointlike::x<RawPoint>(p); } template<class RawPoint> -TCoord<RawPoint> getY(const RawPoint& p) { return PointLike::y<RawPoint>(p); } +TCoord<RawPoint> getY(const RawPoint& p) { return pointlike::y<RawPoint>(p); } template<class RawPoint> void setX(RawPoint& p, const TCoord<RawPoint>& val) { - PointLike::x<RawPoint>(p) = val; + pointlike::x<RawPoint>(p) = val; } template<class RawPoint> void setY(RawPoint& p, const TCoord<RawPoint>& val) { - PointLike::y<RawPoint>(p) = val; + pointlike::y<RawPoint>(p) = val; } template<class RawPoint> @@ -303,7 +315,7 @@ inline Radians _Segment<RawPoint>::angleToXaxis() const template<class RawPoint> inline double _Segment<RawPoint>::length() { - return PointLike::distance(first(), second()); + return pointlike::distance(first(), second()); } template<class RawPoint> @@ -356,124 +368,124 @@ enum class Formats { // This struct serves as a namespace. The only difference is that it can be // used in friend declarations and can be aliased at class scope. -struct ShapeLike { +namespace shapelike { template<class RawShape> using Shapes = std::vector<RawShape>; template<class RawShape> - static RawShape create(const TContour<RawShape>& contour, + inline RawShape create(const TContour<RawShape>& contour, const THolesContainer<RawShape>& holes) { return RawShape(contour, holes); } template<class RawShape> - static RawShape create(TContour<RawShape>&& contour, + inline RawShape create(TContour<RawShape>&& contour, THolesContainer<RawShape>&& holes) { return RawShape(contour, holes); } template<class RawShape> - static RawShape create(const TContour<RawShape>& contour) + inline RawShape create(const TContour<RawShape>& contour) { return create<RawShape>(contour, {}); } template<class RawShape> - static RawShape create(TContour<RawShape>&& contour) + inline RawShape create(TContour<RawShape>&& contour) { return create<RawShape>(contour, {}); } template<class RawShape> - static THolesContainer<RawShape>& holes(RawShape& /*sh*/) + inline THolesContainer<RawShape>& holes(RawShape& /*sh*/) { static THolesContainer<RawShape> empty; return empty; } template<class RawShape> - static const THolesContainer<RawShape>& holes(const RawShape& /*sh*/) + inline const THolesContainer<RawShape>& holes(const RawShape& /*sh*/) { static THolesContainer<RawShape> empty; return empty; } template<class RawShape> - static TContour<RawShape>& getHole(RawShape& sh, unsigned long idx) + inline TContour<RawShape>& getHole(RawShape& sh, unsigned long idx) { return holes(sh)[idx]; } template<class RawShape> - static const TContour<RawShape>& getHole(const RawShape& sh, + inline const TContour<RawShape>& getHole(const RawShape& sh, unsigned long idx) { return holes(sh)[idx]; } template<class RawShape> - static size_t holeCount(const RawShape& sh) + inline size_t holeCount(const RawShape& sh) { return holes(sh).size(); } template<class RawShape> - static TContour<RawShape>& getContour(RawShape& sh) + inline TContour<RawShape>& getContour(RawShape& sh) { return sh; } template<class RawShape> - static const TContour<RawShape>& getContour(const RawShape& sh) + inline const TContour<RawShape>& getContour(const RawShape& sh) { return sh; } // Optional, does nothing by default template<class RawShape> - static void reserve(RawShape& /*sh*/, size_t /*vertex_capacity*/) {} + inline void reserve(RawShape& /*sh*/, size_t /*vertex_capacity*/) {} template<class RawShape, class...Args> - static void addVertex(RawShape& sh, Args...args) + inline void addVertex(RawShape& sh, Args...args) { return getContour(sh).emplace_back(std::forward<Args>(args)...); } template<class RawShape> - static TVertexIterator<RawShape> begin(RawShape& sh) + inline TVertexIterator<RawShape> begin(RawShape& sh) { return sh.begin(); } template<class RawShape> - static TVertexIterator<RawShape> end(RawShape& sh) + inline TVertexIterator<RawShape> end(RawShape& sh) { return sh.end(); } template<class RawShape> - static TVertexConstIterator<RawShape> cbegin(const RawShape& sh) + inline TVertexConstIterator<RawShape> cbegin(const RawShape& sh) { return sh.cbegin(); } template<class RawShape> - static TVertexConstIterator<RawShape> cend(const RawShape& sh) + inline TVertexConstIterator<RawShape> cend(const RawShape& sh) { return sh.cend(); } template<class RawShape> - static std::string toString(const RawShape& /*sh*/) + inline std::string toString(const RawShape& /*sh*/) { return ""; } template<Formats, class RawShape> - static std::string serialize(const RawShape& /*sh*/, double /*scale*/=1) + inline std::string serialize(const RawShape& /*sh*/, double /*scale*/=1) { static_assert(always_false<RawShape>::value, "ShapeLike::serialize() unimplemented!"); @@ -481,14 +493,14 @@ struct ShapeLike { } template<Formats, class RawShape> - static void unserialize(RawShape& /*sh*/, const std::string& /*str*/) + inline void unserialize(RawShape& /*sh*/, const std::string& /*str*/) { static_assert(always_false<RawShape>::value, "ShapeLike::unserialize() unimplemented!"); } template<class RawShape> - static double area(const RawShape& /*sh*/) + inline double area(const RawShape& /*sh*/, const PolygonTag&) { static_assert(always_false<RawShape>::value, "ShapeLike::area() unimplemented!"); @@ -496,7 +508,7 @@ struct ShapeLike { } template<class RawShape> - static bool intersects(const RawShape& /*sh*/, const RawShape& /*sh*/) + inline bool intersects(const RawShape& /*sh*/, const RawShape& /*sh*/) { static_assert(always_false<RawShape>::value, "ShapeLike::intersects() unimplemented!"); @@ -504,7 +516,7 @@ struct ShapeLike { } template<class RawShape> - static bool isInside(const TPoint<RawShape>& /*point*/, + inline bool isInside(const TPoint<RawShape>& /*point*/, const RawShape& /*shape*/) { static_assert(always_false<RawShape>::value, @@ -513,7 +525,7 @@ struct ShapeLike { } template<class RawShape> - static bool isInside(const RawShape& /*shape*/, + inline bool isInside(const RawShape& /*shape*/, const RawShape& /*shape*/) { static_assert(always_false<RawShape>::value, @@ -522,7 +534,7 @@ struct ShapeLike { } template<class RawShape> - static bool touches( const RawShape& /*shape*/, + inline bool touches( const RawShape& /*shape*/, const RawShape& /*shape*/) { static_assert(always_false<RawShape>::value, @@ -531,7 +543,7 @@ struct ShapeLike { } template<class RawShape> - static bool touches( const TPoint<RawShape>& /*point*/, + inline bool touches( const TPoint<RawShape>& /*point*/, const RawShape& /*shape*/) { static_assert(always_false<RawShape>::value, @@ -540,21 +552,22 @@ struct ShapeLike { } template<class RawShape> - static _Box<TPoint<RawShape>> boundingBox(const RawShape& /*sh*/) + inline _Box<TPoint<RawShape>> boundingBox(const RawShape& /*sh*/, + const PolygonTag&) { static_assert(always_false<RawShape>::value, "ShapeLike::boundingBox(shape) unimplemented!"); } template<class RawShape> - static _Box<TPoint<RawShape>> boundingBox(const Shapes<RawShape>& /*sh*/) + inline _Box<TPoint<RawShape>> boundingBox(const Shapes<RawShape>& /*sh*/) { static_assert(always_false<RawShape>::value, "ShapeLike::boundingBox(shapes) unimplemented!"); } template<class RawShape> - static RawShape convexHull(const RawShape& /*sh*/) + inline RawShape convexHull(const RawShape& /*sh*/) { static_assert(always_false<RawShape>::value, "ShapeLike::convexHull(shape) unimplemented!"); @@ -562,7 +575,7 @@ struct ShapeLike { } template<class RawShape> - static RawShape convexHull(const Shapes<RawShape>& /*sh*/) + inline RawShape convexHull(const Shapes<RawShape>& /*sh*/) { static_assert(always_false<RawShape>::value, "ShapeLike::convexHull(shapes) unimplemented!"); @@ -570,34 +583,34 @@ struct ShapeLike { } template<class RawShape> - static void rotate(RawShape& /*sh*/, const Radians& /*rads*/) + inline void rotate(RawShape& /*sh*/, const Radians& /*rads*/) { static_assert(always_false<RawShape>::value, "ShapeLike::rotate() unimplemented!"); } template<class RawShape, class RawPoint> - static void translate(RawShape& /*sh*/, const RawPoint& /*offs*/) + inline void translate(RawShape& /*sh*/, const RawPoint& /*offs*/) { static_assert(always_false<RawShape>::value, "ShapeLike::translate() unimplemented!"); } template<class RawShape> - static void offset(RawShape& /*sh*/, TCoord<TPoint<RawShape>> /*distance*/) + inline void offset(RawShape& /*sh*/, TCoord<TPoint<RawShape>> /*distance*/) { static_assert(always_false<RawShape>::value, "ShapeLike::offset() unimplemented!"); } template<class RawShape> - static std::pair<bool, std::string> isValid(const RawShape& /*sh*/) + inline std::pair<bool, std::string> isValid(const RawShape& /*sh*/) { return {false, "ShapeLike::isValid() unimplemented!"}; } template<class RawShape> - static inline bool isConvex(const TContour<RawShape>& sh) + inline bool isConvex(const TContour<RawShape>& sh) { using Vertex = TPoint<RawShape>; auto first = sh.begin(); @@ -633,43 +646,55 @@ struct ShapeLike { // No need to implement these // ************************************************************************* - template<class RawShape> - static inline _Box<TPoint<RawShape>> boundingBox( - const _Box<TPoint<RawShape>>& box) + template<class Box> + inline Box boundingBox(const Box& box, const BoxTag& ) { return box; } - template<class RawShape> - static inline _Box<TPoint<RawShape>> boundingBox( - const _Circle<TPoint<RawShape>>& circ) + template<class Circle> + inline _Box<typename Circle::PointType> boundingBox( + const Circle& circ, const CircleTag&) { - using Coord = TCoord<TPoint<RawShape>>; - TPoint<RawShape> pmin = { + using Point = typename Circle::PointType; + using Coord = TCoord<Point>; + Point pmin = { static_cast<Coord>(getX(circ.center()) - circ.radius()), static_cast<Coord>(getY(circ.center()) - circ.radius()) }; - TPoint<RawShape> pmax = { + Point pmax = { static_cast<Coord>(getX(circ.center()) + circ.radius()), static_cast<Coord>(getY(circ.center()) + circ.radius()) }; return {pmin, pmax}; } - template<class RawShape> - static inline double area(const _Box<TPoint<RawShape>>& box) + template<class S> // Dispatch function + inline _Box<typename S::PointType> boundingBox(const S& sh) { - return static_cast<double>(box.width() * box.height()); + return boundingBox(sh, typename S::Tag()); } - template<class RawShape> - static inline double area(const _Circle<TPoint<RawShape>>& circ) + template<class Box> + inline double area(const Box& box, const BoxTag& ) + { + return box.area(); + } + + template<class Circle> + inline double area(const Circle& circ, const CircleTag& ) { return circ.area(); } + template<class RawShape> // Dispatching function + inline double area(const RawShape& sh) + { + return area(sh, typename RawShape::Tag()); + } + template<class RawShape> - static inline double area(const Shapes<RawShape>& shapes) + inline double area(const Shapes<RawShape>& shapes) { return std::accumulate(shapes.begin(), shapes.end(), 0.0, [](double a, const RawShape& b) { @@ -678,14 +703,14 @@ struct ShapeLike { } template<class RawShape> - static bool isInside(const TPoint<RawShape>& point, + inline bool isInside(const TPoint<RawShape>& point, const _Circle<TPoint<RawShape>>& circ) { - return PointLike::distance(point, circ.center()) < circ.radius(); + return pointlike::distance(point, circ.center()) < circ.radius(); } template<class RawShape> - static bool isInside(const TPoint<RawShape>& point, + inline bool isInside(const TPoint<RawShape>& point, const _Box<TPoint<RawShape>>& box) { auto px = getX(point); @@ -699,7 +724,7 @@ struct ShapeLike { } template<class RawShape> - static bool isInside(const RawShape& sh, + inline bool isInside(const RawShape& sh, const _Circle<TPoint<RawShape>>& circ) { return std::all_of(cbegin(sh), cend(sh), @@ -709,7 +734,7 @@ struct ShapeLike { } template<class RawShape> - static bool isInside(const _Box<TPoint<RawShape>>& box, + inline bool isInside(const _Box<TPoint<RawShape>>& box, const _Circle<TPoint<RawShape>>& circ) { return isInside<RawShape>(box.minCorner(), circ) && @@ -717,7 +742,7 @@ struct ShapeLike { } template<class RawShape> - static bool isInside(const _Box<TPoint<RawShape>>& ibb, + inline bool isInside(const _Box<TPoint<RawShape>>& ibb, const _Box<TPoint<RawShape>>& box) { auto iminX = getX(ibb.minCorner()); @@ -734,31 +759,31 @@ struct ShapeLike { } template<class RawShape> // Potential O(1) implementation may exist - static inline TPoint<RawShape>& vertex(RawShape& sh, unsigned long idx) + inline TPoint<RawShape>& vertex(RawShape& sh, unsigned long idx) { return *(begin(sh) + idx); } template<class RawShape> // Potential O(1) implementation may exist - static inline const TPoint<RawShape>& vertex(const RawShape& sh, + inline const TPoint<RawShape>& vertex(const RawShape& sh, unsigned long idx) { return *(cbegin(sh) + idx); } template<class RawShape> - static inline size_t contourVertexCount(const RawShape& sh) + inline size_t contourVertexCount(const RawShape& sh) { return cend(sh) - cbegin(sh); } template<class RawShape, class Fn> - static inline void foreachContourVertex(RawShape& sh, Fn fn) { + inline void foreachContourVertex(RawShape& sh, Fn fn) { for(auto it = begin(sh); it != end(sh); ++it) fn(*it); } template<class RawShape, class Fn> - static inline void foreachHoleVertex(RawShape& sh, Fn fn) { + inline void foreachHoleVertex(RawShape& sh, Fn fn) { for(int i = 0; i < holeCount(sh); ++i) { auto& h = getHole(sh, i); for(auto it = begin(h); it != end(h); ++it) fn(*it); @@ -766,12 +791,12 @@ struct ShapeLike { } template<class RawShape, class Fn> - static inline void foreachContourVertex(const RawShape& sh, Fn fn) { + inline void foreachContourVertex(const RawShape& sh, Fn fn) { for(auto it = cbegin(sh); it != cend(sh); ++it) fn(*it); } template<class RawShape, class Fn> - static inline void foreachHoleVertex(const RawShape& sh, Fn fn) { + inline void foreachHoleVertex(const RawShape& sh, Fn fn) { for(int i = 0; i < holeCount(sh); ++i) { auto& h = getHole(sh, i); for(auto it = cbegin(h); it != cend(h); ++it) fn(*it); @@ -779,18 +804,17 @@ struct ShapeLike { } template<class RawShape, class Fn> - static inline void foreachVertex(RawShape& sh, Fn fn) { + inline void foreachVertex(RawShape& sh, Fn fn) { foreachContourVertex(sh, fn); foreachHoleVertex(sh, fn); } template<class RawShape, class Fn> - static inline void foreachVertex(const RawShape& sh, Fn fn) { + inline void foreachVertex(const RawShape& sh, Fn fn) { foreachContourVertex(sh, fn); foreachHoleVertex(sh, fn); } - -}; +} } diff --git a/xs/src/libnest2d/libnest2d/geometry_traits_nfp.hpp b/xs/src/libnest2d/libnest2d/geometry_traits_nfp.hpp index 90cf21be5..6cac374ae 100644 --- a/xs/src/libnest2d/libnest2d/geometry_traits_nfp.hpp +++ b/xs/src/libnest2d/libnest2d/geometry_traits_nfp.hpp @@ -9,6 +9,27 @@ namespace libnest2d { +namespace __nfp { +// Do not specialize this... +template<class RawShape> +inline bool _vsort(const TPoint<RawShape>& v1, const TPoint<RawShape>& v2) +{ + using Coord = TCoord<TPoint<RawShape>>; + Coord &&x1 = getX(v1), &&x2 = getX(v2), &&y1 = getY(v1), &&y2 = getY(v2); + auto diff = y1 - y2; + if(std::abs(diff) <= std::numeric_limits<Coord>::epsilon()) + return x1 < x2; + + return diff < 0; +} +} + +/// A collection of static methods for handling the no fit polygon creation. +namespace nfp { + +namespace sl = shapelike; +namespace pl = pointlike; + /// The complexity level of a polygon that an NFP implementation can handle. enum class NfpLevel: unsigned { CONVEX_ONLY, @@ -18,12 +39,17 @@ enum class NfpLevel: unsigned { BOTH_CONCAVE_WITH_HOLES }; -/// A collection of static methods for handling the no fit polygon creation. -struct Nfp { +template<class RawShape> +using NfpResult = std::pair<RawShape, TPoint<RawShape>>; + +template<class RawShape> struct MaxNfpLevel { + static const BP2D_CONSTEXPR NfpLevel value = NfpLevel::CONVEX_ONLY; +}; + // Shorthand for a pile of polygons template<class RawShape> -using Shapes = typename ShapeLike::Shapes<RawShape>; +using Shapes = typename shapelike::Shapes<RawShape>; /** * Merge a bunch of polygons with the specified additional polygon. @@ -37,7 +63,7 @@ using Shapes = typename ShapeLike::Shapes<RawShape>; * polygons are disjuct than the resulting set will contain more polygons. */ template<class RawShape> -static Shapes<RawShape> merge(const Shapes<RawShape>& /*shc*/) +inline Shapes<RawShape> merge(const Shapes<RawShape>& /*shc*/) { static_assert(always_false<RawShape>::value, "Nfp::merge(shapes, shape) unimplemented!"); @@ -55,7 +81,7 @@ static Shapes<RawShape> merge(const Shapes<RawShape>& /*shc*/) * polygons are disjuct than the resulting set will contain more polygons. */ template<class RawShape> -static Shapes<RawShape> merge(const Shapes<RawShape>& shc, +inline Shapes<RawShape> merge(const Shapes<RawShape>& shc, const RawShape& sh) { auto m = merge(shc); @@ -64,30 +90,17 @@ static Shapes<RawShape> merge(const Shapes<RawShape>& shc, } /** - * A method to get a vertex from a polygon that always maintains a relative - * position to the coordinate system: It is always the rightmost top vertex. - * - * This way it does not matter in what order the vertices are stored, the - * reference will be always the same for the same polygon. - */ -template<class RawShape> -inline static TPoint<RawShape> referenceVertex(const RawShape& sh) -{ - return rightmostUpVertex(sh); -} - -/** * Get the vertex of the polygon that is at the lowest values (bottom) in the Y * axis and if there are more than one vertices on the same Y coordinate than * the result will be the leftmost (with the highest X coordinate). */ template<class RawShape> -static TPoint<RawShape> leftmostDownVertex(const RawShape& sh) +inline TPoint<RawShape> leftmostDownVertex(const RawShape& sh) { // find min x and min y vertex - auto it = std::min_element(ShapeLike::cbegin(sh), ShapeLike::cend(sh), - _vsort<RawShape>); + auto it = std::min_element(shapelike::cbegin(sh), shapelike::cend(sh), + __nfp::_vsort<RawShape>); return *it; } @@ -98,26 +111,27 @@ static TPoint<RawShape> leftmostDownVertex(const RawShape& sh) * the result will be the rightmost (with the lowest X coordinate). */ template<class RawShape> -static TPoint<RawShape> rightmostUpVertex(const RawShape& sh) +TPoint<RawShape> rightmostUpVertex(const RawShape& sh) { // find max x and max y vertex - auto it = std::max_element(ShapeLike::cbegin(sh), ShapeLike::cend(sh), - _vsort<RawShape>); + auto it = std::max_element(shapelike::cbegin(sh), shapelike::cend(sh), + __nfp::_vsort<RawShape>); return *it; } +/** + * A method to get a vertex from a polygon that always maintains a relative + * position to the coordinate system: It is always the rightmost top vertex. + * + * This way it does not matter in what order the vertices are stored, the + * reference will be always the same for the same polygon. + */ template<class RawShape> -using NfpResult = std::pair<RawShape, TPoint<RawShape>>; - -/// Helper function to get the NFP -template<NfpLevel nfptype, class RawShape> -static NfpResult<RawShape> noFitPolygon(const RawShape& sh, - const RawShape& other) +inline TPoint<RawShape> referenceVertex(const RawShape& sh) { - NfpImpl<RawShape, nfptype> nfp; - return nfp(sh, other); + return rightmostUpVertex(sh); } /** @@ -139,11 +153,11 @@ static NfpResult<RawShape> noFitPolygon(const RawShape& sh, * */ template<class RawShape> -static NfpResult<RawShape> nfpConvexOnly(const RawShape& sh, +inline NfpResult<RawShape> nfpConvexOnly(const RawShape& sh, const RawShape& other) { using Vertex = TPoint<RawShape>; using Edge = _Segment<Vertex>; - using sl = ShapeLike; + namespace sl = shapelike; RawShape rsh; // Final nfp placeholder Vertex top_nfp; @@ -187,7 +201,7 @@ static NfpResult<RawShape> nfpConvexOnly(const RawShape& sh, sl::addVertex(rsh, edgelist.front().second()); // Sorting function for the nfp reference vertex search - auto& cmp = _vsort<RawShape>; + auto& cmp = __nfp::_vsort<RawShape>; // the reference (rightmost top) vertex so far top_nfp = *std::max_element(sl::cbegin(rsh), sl::cend(rsh), cmp ); @@ -214,7 +228,7 @@ static NfpResult<RawShape> nfpConvexOnly(const RawShape& sh, } template<class RawShape> -static NfpResult<RawShape> nfpSimpleSimple(const RawShape& cstationary, +NfpResult<RawShape> nfpSimpleSimple(const RawShape& cstationary, const RawShape& cother) { @@ -233,7 +247,7 @@ static NfpResult<RawShape> nfpSimpleSimple(const RawShape& cstationary, using Vertex = TPoint<RawShape>; using Coord = TCoord<Vertex>; using Edge = _Segment<Vertex>; - using sl = ShapeLike; + namespace sl = shapelike; using std::signbit; using std::sort; using std::vector; @@ -528,27 +542,16 @@ struct NfpImpl { } }; -template<class RawShape> struct MaxNfpLevel { - static const BP2D_CONSTEXPR NfpLevel value = NfpLevel::CONVEX_ONLY; -}; - -private: - -// Do not specialize this... -template<class RawShape> -static inline bool _vsort(const TPoint<RawShape>& v1, - const TPoint<RawShape>& v2) +/// Helper function to get the NFP +template<NfpLevel nfptype, class RawShape> +inline NfpResult<RawShape> noFitPolygon(const RawShape& sh, + const RawShape& other) { - using Coord = TCoord<TPoint<RawShape>>; - Coord &&x1 = getX(v1), &&x2 = getX(v2), &&y1 = getY(v1), &&y2 = getY(v2); - auto diff = y1 - y2; - if(std::abs(diff) <= std::numeric_limits<Coord>::epsilon()) - return x1 < x2; - - return diff < 0; + NfpImpl<RawShape, nfptype> nfps; + return nfps(sh, other); } -}; +} } diff --git a/xs/src/libnest2d/libnest2d/libnest2d.hpp b/xs/src/libnest2d/libnest2d/libnest2d.hpp index eadd1e110..d2850d4ed 100644 --- a/xs/src/libnest2d/libnest2d/libnest2d.hpp +++ b/xs/src/libnest2d/libnest2d/libnest2d.hpp @@ -9,10 +9,12 @@ #include <functional> #include "geometry_traits.hpp" -#include "optimizer.hpp" namespace libnest2d { +namespace sl = shapelike; +namespace pl = pointlike; + /** * \brief An item to be placed on a bin. * @@ -28,7 +30,6 @@ class _Item { using Coord = TCoord<TPoint<RawShape>>; using Vertex = TPoint<RawShape>; using Box = _Box<Vertex>; - using sl = ShapeLike; // The original shape that gets encapsulated. RawShape sh_; @@ -438,7 +439,7 @@ public: inline _Rectangle(Unit width, Unit height, // disable this ctor if o != CLOCKWISE enable_if_t< o == TO::CLOCKWISE, int> = 0 ): - _Item<RawShape>( ShapeLike::create<RawShape>( { + _Item<RawShape>( sl::create<RawShape>( { {0, 0}, {0, height}, {width, height}, @@ -452,7 +453,7 @@ public: inline _Rectangle(Unit width, Unit height, // disable this ctor if o != COUNTER_CLOCKWISE enable_if_t< o == TO::COUNTER_CLOCKWISE, int> = 0 ): - _Item<RawShape>( ShapeLike::create<RawShape>( { + _Item<RawShape>( sl::create<RawShape>( { {0, 0}, {width, 0}, {width, height}, @@ -473,12 +474,32 @@ public: template<class RawShape> inline bool _Item<RawShape>::isInside(const _Box<TPoint<RawShape>>& box) const { - return ShapeLike::isInside<RawShape>(boundingBox(), box); + return sl::isInside<RawShape>(boundingBox(), box); } template<class RawShape> inline bool _Item<RawShape>::isInside(const _Circle<TPoint<RawShape>>& circ) const { - return ShapeLike::isInside<RawShape>(transformedShape(), circ); + return sl::isInside<RawShape>(transformedShape(), circ); +} + + +template<class I> using _ItemRef = std::reference_wrapper<I>; +template<class I> using _ItemGroup = std::vector<_ItemRef<I>>; + +template<class Iterator> +struct ConstItemRange { + Iterator from; + Iterator to; + bool valid = false; + + ConstItemRange() = default; + ConstItemRange(Iterator f, Iterator t): from(f), to(t), valid(true) {} +}; + +template<class Container> +inline ConstItemRange<typename Container::const_iterator> +rem(typename Container::const_iterator it, const Container& cont) { + return {std::next(it), cont.end()}; } /** @@ -515,8 +536,9 @@ public: */ using PackResult = typename PlacementStrategy::PackResult; - using ItemRef = std::reference_wrapper<Item>; - using ItemGroup = std::vector<ItemRef>; + using ItemRef = _ItemRef<Item>; + using ItemGroup = _ItemGroup<Item>; + using DefaultIterator = typename ItemGroup::const_iterator; /** * @brief Constructor taking the bin and an optional configuration. @@ -544,20 +566,24 @@ public: * Try to pack an item with a result object that contains the packing * information for later accepting it. * - * \param item_store A container of items + * \param item_store A container of items that are intended to be packed + * later. Can be used by the placer to switch tactics. When it's knows that + * many items will come a greedy startegy may not be the best. + * \param from The iterator to the item from which the packing should start, + * including the pointed item + * \param count How many items should be packed. If the value is 1, than + * just the item pointed to by "from" argument should be packed. */ - template<class Container> - inline PackResult trypack(Container& item_store, - typename Container::iterator from, - unsigned count = 1) { - using V = typename Container::value_type; - static_assert(std::is_convertible<V, const Item&>::value, - "Invalid Item container!"); - return impl_.trypack(item_store, from, count); + template<class Iter = DefaultIterator> + inline PackResult trypack( + Item& item, + const ConstItemRange<Iter>& remaining = ConstItemRange<Iter>()) + { + return impl_.trypack(item, remaining); } /** - * @brief A method to accept a previously tried item. + * @brief A method to accept a previously tried item (or items). * * If the pack result is a failure the method should ignore it. * @param r The result of a previous trypack call. @@ -565,10 +591,10 @@ public: inline void accept(PackResult& r) { impl_.accept(r); } /** - * @brief pack Try to pack an item and immediately accept it on success. + * @brief pack Try to pack and immediately accept it on success. * * A default implementation would be to call - * { auto&& r = trypack(item); accept(r); return r; } but we should let the + * { auto&& r = trypack(...); accept(r); return r; } but we should let the * implementor of the placement strategy to harvest any optimizations from * the absence of an intermadiate step. The above version can still be used * in the implementation. @@ -577,15 +603,12 @@ public: * @return Returns true if the item was packed or false if it could not be * packed. */ - template<class Container> - inline bool pack(Container& item_store, - typename Container::iterator from, - unsigned count = 1) + template<class Range = ConstItemRange<DefaultIterator>> + inline bool pack( + Item& item, + const Range& remaining = Range()) { - using V = typename Container::value_type; - static_assert(std::is_convertible<V, const Item&>::value, - "Invalid Item container!"); - return impl_.pack(item_store, from, count); + return impl_.pack(item, remaining); } /// Unpack the last element (remove it from the list of packed items). @@ -736,10 +759,9 @@ using _IndexedPackGroup = std::vector< * inside the provided bin. */ template<class PlacementStrategy, class SelectionStrategy > -class Arranger { +class Nester { using TSel = SelectionStrategyLike<SelectionStrategy>; TSel selector_; - bool use_min_bb_rotation_ = false; public: using Item = typename PlacementStrategy::Item; using ItemRef = std::reference_wrapper<Item>; @@ -777,7 +799,7 @@ public: template<class TBinType = BinType, class PConf = PlacementConfig, class SConf = SelectionConfig> - Arranger( TBinType&& bin, + Nester( TBinType&& bin, Unit min_obj_distance = 0, PConf&& pconfig = PConf(), SConf&& sconfig = SConf()): @@ -810,9 +832,9 @@ public: * the selection algorithm. */ template<class TIterator> - inline PackGroup arrange(TIterator from, TIterator to) + inline PackGroup execute(TIterator from, TIterator to) { - return _arrange(from, to); + return _execute(from, to); } /** @@ -823,20 +845,20 @@ public: * input sequence size. */ template<class TIterator> - inline IndexedPackGroup arrangeIndexed(TIterator from, TIterator to) + inline IndexedPackGroup executeIndexed(TIterator from, TIterator to) { - return _arrangeIndexed(from, to); + return _executeIndexed(from, to); } /// Shorthand to normal arrange method. template<class TIterator> inline PackGroup operator() (TIterator from, TIterator to) { - return _arrange(from, to); + return _execute(from, to); } /// Set a progress indicatior function object for the selector. - inline Arranger& progressIndicator(ProgressFunction func) + inline Nester& progressIndicator(ProgressFunction func) { selector_.progressIndicator(func); return *this; } @@ -850,10 +872,6 @@ public: return ret; } - inline Arranger& useMinimumBoundigBoxRotation(bool s = true) { - use_min_bb_rotation_ = s; return *this; - } - private: template<class TIterator, @@ -865,9 +883,9 @@ private: // have to exist for the lifetime of this call. class T = enable_if_t< std::is_convertible<IT, TPItem>::value, IT> > - inline PackGroup _arrange(TIterator from, TIterator to, bool = false) + inline PackGroup _execute(TIterator from, TIterator to, bool = false) { - __arrange(from, to); + __execute(from, to); return lastResult(); } @@ -875,11 +893,11 @@ private: class IT = remove_cvref_t<typename TIterator::value_type>, class T = enable_if_t<!std::is_convertible<IT, TPItem>::value, IT> > - inline PackGroup _arrange(TIterator from, TIterator to, int = false) + inline PackGroup _execute(TIterator from, TIterator to, int = false) { item_cache_ = {from, to}; - __arrange(item_cache_.begin(), item_cache_.end()); + __execute(item_cache_.begin(), item_cache_.end()); return lastResult(); } @@ -892,11 +910,11 @@ private: // have to exist for the lifetime of this call. class T = enable_if_t< std::is_convertible<IT, TPItem>::value, IT> > - inline IndexedPackGroup _arrangeIndexed(TIterator from, + inline IndexedPackGroup _executeIndexed(TIterator from, TIterator to, bool = false) { - __arrange(from, to); + __execute(from, to); return createIndexedPackGroup(from, to, selector_); } @@ -904,12 +922,12 @@ private: class IT = remove_cvref_t<typename TIterator::value_type>, class T = enable_if_t<!std::is_convertible<IT, TPItem>::value, IT> > - inline IndexedPackGroup _arrangeIndexed(TIterator from, + inline IndexedPackGroup _executeIndexed(TIterator from, TIterator to, int = false) { item_cache_ = {from, to}; - __arrange(item_cache_.begin(), item_cache_.end()); + __execute(item_cache_.begin(), item_cache_.end()); return createIndexedPackGroup(from, to, selector_); } @@ -941,37 +959,12 @@ private: return pg; } - Radians findBestRotation(Item& item) { - opt::StopCriteria stopcr; - stopcr.absolute_score_difference = 0.01; - stopcr.max_iterations = 10000; - opt::TOptimizer<opt::Method::G_GENETIC> solver(stopcr); - - auto orig_rot = item.rotation(); - - auto result = solver.optimize_min([&item, &orig_rot](Radians rot){ - item.rotation(orig_rot + rot); - auto bb = item.boundingBox(); - return std::sqrt(bb.height()*bb.width()); - }, opt::initvals(Radians(0)), opt::bound<Radians>(-Pi/2, Pi/2)); - - item.rotation(orig_rot); - - return std::get<0>(result.optimum); - } - - template<class TIter> inline void __arrange(TIter from, TIter to) + template<class TIter> inline void __execute(TIter from, TIter to) { if(min_obj_distance_ > 0) std::for_each(from, to, [this](Item& item) { item.addOffset(static_cast<Unit>(std::ceil(min_obj_distance_/2.0))); }); - if(use_min_bb_rotation_) - std::for_each(from, to, [this](Item& item){ - Radians rot = findBestRotation(item); - item.rotate(rot); - }); - selector_.template packItems<PlacementStrategy>( from, to, bin_, pconfig_); diff --git a/xs/src/libnest2d/libnest2d/placers/bottomleftplacer.hpp b/xs/src/libnest2d/libnest2d/placers/bottomleftplacer.hpp index 71573e34d..af1678372 100644 --- a/xs/src/libnest2d/libnest2d/placers/bottomleftplacer.hpp +++ b/xs/src/libnest2d/libnest2d/placers/bottomleftplacer.hpp @@ -27,11 +27,10 @@ public: explicit _BottomLeftPlacer(const BinType& bin): Base(bin) {} - template<class Store> - PackResult trypack(Store& /*s*/, typename Store::iterator from, - unsigned /*count*/ = 1) + template<class Range = ConstItemRange<typename Base::DefaultIter>> + PackResult trypack(Item& item, + const Range& = Range()) { - Item& item = *from; auto r = _trypack(item); if(!r && Base::config_.allow_rotations) { @@ -117,10 +116,10 @@ protected: const RawShape& scanpoly) { auto tsh = other.transformedShape(); - return ( ShapeLike::intersects(tsh, scanpoly) || - ShapeLike::isInside(tsh, scanpoly) ) && - ( !ShapeLike::intersects(tsh, item.rawShape()) && - !ShapeLike::isInside(tsh, item.rawShape()) ); + return ( sl::intersects(tsh, scanpoly) || + sl::isInside(tsh, scanpoly) ) && + ( !sl::intersects(tsh, item.rawShape()) && + !sl::isInside(tsh, item.rawShape()) ); } template<class C = Coord> @@ -131,25 +130,25 @@ protected: { auto tsh = other.transformedShape(); - bool inters_scanpoly = ShapeLike::intersects(tsh, scanpoly) && - !ShapeLike::touches(tsh, scanpoly); - bool inters_item = ShapeLike::intersects(tsh, item.rawShape()) && - !ShapeLike::touches(tsh, item.rawShape()); + bool inters_scanpoly = sl::intersects(tsh, scanpoly) && + !sl::touches(tsh, scanpoly); + bool inters_item = sl::intersects(tsh, item.rawShape()) && + !sl::touches(tsh, item.rawShape()); return ( inters_scanpoly || - ShapeLike::isInside(tsh, scanpoly)) && + sl::isInside(tsh, scanpoly)) && ( !inters_item && - !ShapeLike::isInside(tsh, item.rawShape()) + !sl::isInside(tsh, item.rawShape()) ); } - Container itemsInTheWayOf(const Item& item, const Dir dir) { + ItemGroup itemsInTheWayOf(const Item& item, const Dir dir) { // Get the left or down polygon, that has the same area as the shadow // of input item reflected to the left or downwards auto&& scanpoly = dir == Dir::LEFT? leftPoly(item) : downPoly(item); - Container ret; // packed items 'in the way' of item + ItemGroup ret; // packed items 'in the way' of item ret.reserve(items_.size()); // Predicate to find items that are 'in the way' for left (down) move @@ -178,18 +177,18 @@ protected: if(dir == Dir::LEFT) { getCoord = [](const Vertex& v) { return getX(v); }; - availableDistance = PointLike::horizontalDistance<Vertex>; + availableDistance = pointlike::horizontalDistance<Vertex>; availableDistanceSV = [](const Segment& s, const Vertex& v) { - auto ret = PointLike::horizontalDistance<Vertex>(v, s); + auto ret = pointlike::horizontalDistance<Vertex>(v, s); if(ret.second) ret.first = -ret.first; return ret; }; } else { getCoord = [](const Vertex& v) { return getY(v); }; - availableDistance = PointLike::verticalDistance<Vertex>; + availableDistance = pointlike::verticalDistance<Vertex>; availableDistanceSV = [](const Segment& s, const Vertex& v) { - auto ret = PointLike::verticalDistance<Vertex>(v, s); + auto ret = pointlike::verticalDistance<Vertex>(v, s); if(ret.second) ret.first = -ret.first; return ret; }; @@ -219,9 +218,9 @@ protected: assert(pleft.vertexCount() > 0); auto trpleft = pleft.transformedShape(); - auto first = ShapeLike::begin(trpleft); + auto first = sl::begin(trpleft); auto next = first + 1; - auto endit = ShapeLike::end(trpleft); + auto endit = sl::end(trpleft); while(next != endit) { Segment seg(*(first++), *(next++)); @@ -345,16 +344,16 @@ protected: // reserve for all vertices plus 2 for the left horizontal wall, 2 for // the additional vertices for maintaning min object distance - ShapeLike::reserve(rsh, finish-start+4); + sl::reserve(rsh, finish-start+4); /*auto addOthers = [&rsh, finish, start, &item](){ for(size_t i = start+1; i < finish; i++) - ShapeLike::addVertex(rsh, item.vertex(i)); + sl::addVertex(rsh, item.vertex(i)); };*/ auto reverseAddOthers = [&rsh, finish, start, &item](){ for(auto i = finish-1; i > start; i--) - ShapeLike::addVertex(rsh, item.vertex( + sl::addVertex(rsh, item.vertex( static_cast<unsigned long>(i))); }; @@ -366,25 +365,25 @@ protected: // Clockwise polygon construction - ShapeLike::addVertex(rsh, topleft_vertex); + sl::addVertex(rsh, topleft_vertex); if(dir == Dir::LEFT) reverseAddOthers(); else { - ShapeLike::addVertex(rsh, getX(topleft_vertex), 0); - ShapeLike::addVertex(rsh, getX(bottomleft_vertex), 0); + sl::addVertex(rsh, getX(topleft_vertex), 0); + sl::addVertex(rsh, getX(bottomleft_vertex), 0); } - ShapeLike::addVertex(rsh, bottomleft_vertex); + sl::addVertex(rsh, bottomleft_vertex); if(dir == Dir::LEFT) { - ShapeLike::addVertex(rsh, 0, getY(bottomleft_vertex)); - ShapeLike::addVertex(rsh, 0, getY(topleft_vertex)); + sl::addVertex(rsh, 0, getY(bottomleft_vertex)); + sl::addVertex(rsh, 0, getY(topleft_vertex)); } else reverseAddOthers(); // Close the polygon - ShapeLike::addVertex(rsh, topleft_vertex); + sl::addVertex(rsh, topleft_vertex); return rsh; } diff --git a/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp b/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp index d74fe2b1d..638d606e0 100644 --- a/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp +++ b/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp @@ -19,7 +19,7 @@ namespace libnest2d { namespace strategies { template<class RawShape> struct NfpPConfig { - using ItemGroup = std::vector<std::reference_wrapper<_Item<RawShape>>>; + using ItemGroup = _ItemGroup<_Item<RawShape>>; enum class Alignment { CENTER, @@ -58,16 +58,6 @@ struct NfpPConfig { * * \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 (no candidate item there) so you don't have - * to iterate through them if you only need their accumulated area. - * - * \param norm A norming factor for physical dimensions. E.g. if your score - * is the distance between the item and the bin center, you should divide - * that distance with the norming factor. If the score is an area than - * divide it with the square of the norming factor. Imagine it as a unit of - * distance. - * * \param remaining A container with the remaining items waiting to be * placed. You can use some features about the remaining items to alter to * score of the current placement. If you know that you have to leave place @@ -81,8 +71,8 @@ struct NfpPConfig { * decisions (for you or a more intelligent AI). * */ - std::function<double(Nfp::Shapes<RawShape>&, const _Item<RawShape>&, - double, double, const ItemGroup&)> + std::function<double(nfp::Shapes<RawShape>&, const _Item<RawShape>&, + const ItemGroup&)> object_function; /** @@ -134,11 +124,11 @@ template<class RawShape> class EdgeCache { void createCache(const RawShape& sh) { { // For the contour - auto first = ShapeLike::cbegin(sh); + auto first = shapelike::cbegin(sh); auto next = std::next(first); - auto endit = ShapeLike::cend(sh); + auto endit = shapelike::cend(sh); - contour_.distances.reserve(ShapeLike::contourVertexCount(sh)); + contour_.distances.reserve(shapelike::contourVertexCount(sh)); while(next != endit) { contour_.emap.emplace_back(*(first++), *(next++)); @@ -147,7 +137,7 @@ template<class RawShape> class EdgeCache { } } - for(auto& h : ShapeLike::holes(sh)) { // For the holes + for(auto& h : shapelike::holes(sh)) { // For the holes auto first = h.begin(); auto next = std::next(first); auto endit = h.end(); @@ -295,11 +285,11 @@ public: }; -template<NfpLevel lvl> -struct Lvl { static const NfpLevel value = lvl; }; +template<nfp::NfpLevel lvl> +struct Lvl { static const nfp::NfpLevel value = lvl; }; template<class RawShape> -inline void correctNfpPosition(Nfp::NfpResult<RawShape>& nfp, +inline void correctNfpPosition(nfp::NfpResult<RawShape>& nfp, const _Item<RawShape>& stationary, const _Item<RawShape>& orbiter) { @@ -319,46 +309,47 @@ inline void correctNfpPosition(Nfp::NfpResult<RawShape>& nfp, auto dtouch = touch_sh - touch_other; auto top_other = orbiter.rightmostTopVertex() + dtouch; auto dnfp = top_other - nfp.second; // nfp.second is the nfp reference point - ShapeLike::translate(nfp.first, dnfp); + shapelike::translate(nfp.first, dnfp); } template<class RawShape> -inline void correctNfpPosition(Nfp::NfpResult<RawShape>& nfp, +inline void correctNfpPosition(nfp::NfpResult<RawShape>& nfp, const RawShape& stationary, const _Item<RawShape>& orbiter) { - auto touch_sh = Nfp::rightmostUpVertex(stationary); + auto touch_sh = nfp::rightmostUpVertex(stationary); auto touch_other = orbiter.leftmostBottomVertex(); auto dtouch = touch_sh - touch_other; auto top_other = orbiter.rightmostTopVertex() + dtouch; auto dnfp = top_other - nfp.second; - ShapeLike::translate(nfp.first, dnfp); + shapelike::translate(nfp.first, dnfp); } template<class RawShape, class Container> -Nfp::Shapes<RawShape> nfp( const Container& polygons, +nfp::Shapes<RawShape> calcnfp( const Container& polygons, const _Item<RawShape>& trsh, - Lvl<NfpLevel::CONVEX_ONLY>) + Lvl<nfp::NfpLevel::CONVEX_ONLY>) { using Item = _Item<RawShape>; + using namespace nfp; - Nfp::Shapes<RawShape> nfps; + nfp::Shapes<RawShape> nfps; // int pi = 0; for(Item& sh : polygons) { - auto subnfp_r = Nfp::noFitPolygon<NfpLevel::CONVEX_ONLY>( + auto subnfp_r = noFitPolygon<NfpLevel::CONVEX_ONLY>( sh.transformedShape(), trsh.transformedShape()); #ifndef NDEBUG - auto vv = ShapeLike::isValid(sh.transformedShape()); + auto vv = sl::isValid(sh.transformedShape()); assert(vv.first); - auto vnfp = ShapeLike::isValid(subnfp_r.first); + auto vnfp = sl::isValid(subnfp_r.first); assert(vnfp.first); #endif correctNfpPosition(subnfp_r, sh, trsh); - nfps = Nfp::merge(nfps, subnfp_r.first); + nfps = nfp::merge(nfps, subnfp_r.first); // double SCALE = 1000000; // using SVGWriter = svg::SVGWriter<RawShape>; @@ -379,31 +370,32 @@ Nfp::Shapes<RawShape> nfp( const Container& polygons, } template<class RawShape, class Container, class Level> -Nfp::Shapes<RawShape> nfp( const Container& polygons, +nfp::Shapes<RawShape> calcnfp( const Container& polygons, const _Item<RawShape>& trsh, Level) { + using namespace nfp; using Item = _Item<RawShape>; - Nfp::Shapes<RawShape> nfps; + Shapes<RawShape> nfps; auto& orb = trsh.transformedShape(); bool orbconvex = trsh.isContourConvex(); for(Item& sh : polygons) { - Nfp::NfpResult<RawShape> subnfp; + nfp::NfpResult<RawShape> subnfp; auto& stat = sh.transformedShape(); if(sh.isContourConvex() && orbconvex) - subnfp = Nfp::noFitPolygon<NfpLevel::CONVEX_ONLY>(stat, orb); + subnfp = nfp::noFitPolygon<NfpLevel::CONVEX_ONLY>(stat, orb); else if(orbconvex) - subnfp = Nfp::noFitPolygon<NfpLevel::ONE_CONVEX>(stat, orb); + subnfp = nfp::noFitPolygon<NfpLevel::ONE_CONVEX>(stat, orb); else - subnfp = Nfp::noFitPolygon<Level::value>(stat, orb); + subnfp = nfp::noFitPolygon<Level::value>(stat, orb); correctNfpPosition(subnfp, sh, trsh); - nfps = Nfp::merge(nfps, subnfp.first); + nfps = nfp::merge(nfps, subnfp.first); } return nfps; @@ -448,7 +440,6 @@ Nfp::Shapes<RawShape> nfp( const Container& polygons, template<class RawShape> _Circle<TPoint<RawShape>> minimizeCircle(const RawShape& sh) { - using sl = ShapeLike; using pl = PointLike; using Point = TPoint<RawShape>; using Coord = TCoord<Point>; @@ -518,16 +509,14 @@ class _NofitPolyPlacer: public PlacerBoilerplate<_NofitPolyPlacer<RawShape, TBin const double norm_; - using MaxNfpLevel = Nfp::MaxNfpLevel<RawShape>; - using sl = ShapeLike; - + using MaxNfpLevel = nfp::MaxNfpLevel<RawShape>; public: - using Pile = Nfp::Shapes<RawShape>; + using Pile = nfp::Shapes<RawShape>; inline explicit _NofitPolyPlacer(const BinType& bin): Base(bin), - norm_(std::sqrt(sl::area<RawShape>(bin))) {} + norm_(std::sqrt(sl::area(bin))) {} _NofitPolyPlacer(const _NofitPolyPlacer&) = default; _NofitPolyPlacer& operator=(const _NofitPolyPlacer&) = default; @@ -577,20 +566,17 @@ public: return boundingCircle(chull).radius() < bin.radius(); } - template<class Container> - PackResult trypack(Container& items, - typename Container::iterator from, - unsigned /*count*/ = 1) - { - return trypack(*from, {std::next(from), items.end()}); - } - - PackResult trypack(Item& item, ItemGroup remaining) { + template<class Range = ConstItemRange<typename Base::DefaultIter>> + PackResult trypack( + Item& item, + const Range& remaining = Range()) { PackResult ret; bool can_pack = false; + auto remlist = ItemGroup(remaining.from, remaining.to); + if(items_.empty()) { setInitialPosition(item); can_pack = item.isInside(bin_); @@ -602,7 +588,7 @@ public: auto initial_rot = item.rotation(); Vertex final_tr = {0, 0}; Radians final_rot = initial_rot; - Nfp::Shapes<RawShape> nfps; + nfp::Shapes<RawShape> nfps; for(auto rot : config_.rotations) { @@ -615,8 +601,8 @@ public: auto trsh = item.transformedShape(); - nfps = nfp(items_, item, Lvl<MaxNfpLevel::value>()); - auto iv = Nfp::referenceVertex(trsh); + nfps = calcnfp(items_, item, Lvl<MaxNfpLevel::value>()); + auto iv = nfp::referenceVertex(trsh); auto startpos = item.translation(); @@ -644,7 +630,7 @@ public: ecache[opt.nfpidx].coords(opt.hidx, opt.relpos); }; - Nfp::Shapes<RawShape> pile; + nfp::Shapes<RawShape> pile; pile.reserve(items_.size()+1); double pile_area = 0; for(Item& mitem : items_) { @@ -652,17 +638,15 @@ public: pile_area += mitem.area(); } - auto merged_pile = Nfp::merge(pile); + auto merged_pile = nfp::merge(pile); // This is the kernel part of the object function that is // customizable by the library client auto _objfunc = config_.object_function? config_.object_function : - [this, &merged_pile]( - Nfp::Shapes<RawShape>& /*pile*/, + [this, &merged_pile, &pile_area]( + nfp::Shapes<RawShape>& /*pile*/, const Item& item, - double occupied_area, - double norm, const ItemGroup& /*remaining*/) { merged_pile.emplace_back(item.transformedShape()); @@ -670,7 +654,7 @@ public: merged_pile.pop_back(); // The pack ratio -- how much is the convex hull occupied - double pack_rate = occupied_area/sl::area(ch); + double pack_rate = (pile_area + item.area())/sl::area(ch); // ratio of waste double waste = 1.0 - pack_rate; @@ -680,7 +664,7 @@ public: // (larger) values. auto score = std::sqrt(waste); - if(!wouldFit(ch, bin_)) score += norm; + if(!wouldFit(ch, bin_)) score += norm_; return score; }; @@ -692,10 +676,7 @@ public: d += startpos; item.translation(d); - double occupied_area = pile_area + item.area(); - - double score = _objfunc(pile, item, occupied_area, - norm_, remaining); + double score = _objfunc(pile, item, remlist); return score; }; @@ -830,7 +811,7 @@ private: inline void finalAlign(_Circle<TPoint<RawShape>> cbin) { if(items_.empty()) return; - Nfp::Shapes<RawShape> m; + nfp::Shapes<RawShape> m; m.reserve(items_.size()); for(Item& item : items_) m.emplace_back(item.transformedShape()); @@ -842,7 +823,7 @@ private: inline void finalAlign(Box bbin) { if(items_.empty()) return; - Nfp::Shapes<RawShape> m; + nfp::Shapes<RawShape> m; m.reserve(items_.size()); for(Item& item : items_) m.emplace_back(item.transformedShape()); auto&& bb = sl::boundingBox<RawShape>(m); @@ -884,7 +865,7 @@ private: void setInitialPosition(Item& item) { Box&& bb = item.boundingBox(); Vertex ci, cb; - auto bbin = sl::boundingBox<RawShape>(bin_); + auto bbin = sl::boundingBox(bin_); switch(config_.starting_point) { case Config::Alignment::CENTER: { @@ -920,7 +901,7 @@ private: void placeOutsideOfBin(Item& item) { auto&& bb = item.boundingBox(); - Box binbb = sl::boundingBox<RawShape>(bin_); + Box binbb = sl::boundingBox(bin_); Vertex v = { getX(bb.maxCorner()), getY(bb.minCorner()) }; diff --git a/xs/src/libnest2d/libnest2d/placers/placer_boilerplate.hpp b/xs/src/libnest2d/libnest2d/placers/placer_boilerplate.hpp index f31a9343c..1a0730d88 100644 --- a/xs/src/libnest2d/libnest2d/placers/placer_boilerplate.hpp +++ b/xs/src/libnest2d/libnest2d/placers/placer_boilerplate.hpp @@ -7,10 +7,7 @@ namespace libnest2d { namespace strategies { struct EmptyConfig {}; -template<class Subclass, class RawShape, class TBin, - class Cfg = EmptyConfig, - class Store = std::vector<std::reference_wrapper<_Item<RawShape>>> - > +template<class Subclass, class RawShape, class TBin, class Cfg = EmptyConfig> class PlacerBoilerplate { mutable bool farea_valid_ = false; mutable double farea_ = 0.0; @@ -22,7 +19,8 @@ public: using Coord = TCoord<Vertex>; using Unit = Coord; using Config = Cfg; - using Container = Store; + using ItemGroup = _ItemGroup<Item>; + using DefaultIter = typename ItemGroup::const_iterator; class PackResult { Item *item_ptr_; @@ -39,8 +37,6 @@ public: operator bool() { return item_ptr_ != nullptr; } }; - using ItemGroup = const Container&; - inline PlacerBoilerplate(const BinType& bin, unsigned cap = 50): bin_(bin) { items_.reserve(cap); @@ -56,11 +52,10 @@ public: config_ = config; } - template<class Container> - bool pack(Container& items, - typename Container::iterator from, - unsigned count = 1) { - auto&& r = static_cast<Subclass*>(this)->trypack(items, from, count); + template<class Range = ConstItemRange<DefaultIter>> + bool pack(Item& item, + const Range& rem = Range()) { + auto&& r = static_cast<Subclass*>(this)->trypack(item, rem); if(r) { items_.push_back(*(r.item_ptr_)); farea_valid_ = false; @@ -82,7 +77,7 @@ public: farea_valid_ = false; } - inline ItemGroup getItems() const { return items_; } + inline const ItemGroup& getItems() const { return items_; } inline void clearItems() { items_.clear(); @@ -113,7 +108,7 @@ public: protected: BinType bin_; - Container items_; + ItemGroup items_; Cfg config_; }; @@ -124,6 +119,7 @@ using Base::items_; \ using Base::config_; \ public: \ using typename Base::Item; \ +using typename Base::ItemGroup; \ using typename Base::BinType; \ using typename Base::Config; \ using typename Base::Vertex; \ @@ -131,7 +127,6 @@ using typename Base::Segment; \ using typename Base::PackResult; \ using typename Base::Coord; \ using typename Base::Unit; \ -using typename Base::Container; \ private: } diff --git a/xs/src/libnest2d/libnest2d/rotfinder.hpp b/xs/src/libnest2d/libnest2d/rotfinder.hpp new file mode 100644 index 000000000..525fd8759 --- /dev/null +++ b/xs/src/libnest2d/libnest2d/rotfinder.hpp @@ -0,0 +1,41 @@ +#ifndef ROTFINDER_HPP +#define ROTFINDER_HPP + +#include <libnest2d/libnest2d.hpp> +#include <libnest2d/optimizer.hpp> +#include <iterator> + +namespace libnest2d { + +template<class RawShape> +Radians findBestRotation(_Item<RawShape>& item) { + opt::StopCriteria stopcr; + stopcr.absolute_score_difference = 0.01; + stopcr.max_iterations = 10000; + opt::TOptimizer<opt::Method::G_GENETIC> solver(stopcr); + + auto orig_rot = item.rotation(); + + auto result = solver.optimize_min([&item, &orig_rot](Radians rot){ + item.rotation(orig_rot + rot); + auto bb = item.boundingBox(); + return std::sqrt(bb.height()*bb.width()); + }, opt::initvals(Radians(0)), opt::bound<Radians>(-Pi/2, Pi/2)); + + item.rotation(orig_rot); + + return std::get<0>(result.optimum); +} + +template<class Iterator> +void findMinimumBoundingBoxRotations(Iterator from, Iterator to) { + using V = typename std::iterator_traits<Iterator>::value_type; + std::for_each(from, to, [](V& item){ + Radians rot = findBestRotation(item); + item.rotate(rot); + }); +} + +} + +#endif // ROTFINDER_HPP diff --git a/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp b/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp index 34d6d05c5..8c02dc373 100644 --- a/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp +++ b/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp @@ -118,7 +118,7 @@ public: using Placer = PlacementStrategyLike<TPlacer>; using ItemList = std::list<ItemRef>; - const double bin_area = ShapeLike::area<RawShape>(bin); + const double bin_area = sl::area(bin); const double w = bin_area * config_.waste_increment; const double INITIAL_FILL_PROPORTION = config_.initial_fill_proportion; @@ -227,10 +227,14 @@ public: bool ret = false; auto it = not_packed.begin(); + auto pack = [&placer, ¬_packed](ItemListIt it) { + return placer.pack(*it, rem(it, not_packed)); + }; + while(it != not_packed.end() && !ret && free_area - (item_area = it->get().area()) <= waste) { - if(item_area <= free_area && placer.pack(not_packed, it) ) { + if(item_area <= free_area && pack(it) ) { free_area -= item_area; filled_area = bin_area - free_area; ret = true; @@ -270,6 +274,11 @@ public: auto it2 = it; std::vector<TPair> wrong_pairs; + using std::placeholders::_1; + + auto trypack = [&placer, ¬_packed](ItemListIt it) { + return placer.trypack(*it, rem(it, not_packed)); + }; while(it != endit && !ret && free_area - (item_area = it->get().area()) - @@ -278,7 +287,7 @@ public: if(item_area + smallestPiece(it, not_packed)->get().area() > free_area ) { it++; continue; } - auto pr = placer.trypack(not_packed, it); + auto pr = trypack(it); // First would fit it2 = not_packed.begin(); @@ -294,14 +303,14 @@ public: } placer.accept(pr); - auto pr2 = placer.trypack(not_packed, it2); + auto pr2 = trypack(it2); if(!pr2) { placer.unpackLast(); // remove first if(try_reverse) { - pr2 = placer.trypack(not_packed, it2); + pr2 = trypack(it2); if(pr2) { placer.accept(pr2); - auto pr12 = placer.trypack(not_packed, it); + auto pr12 = trypack(it); if(pr12) { placer.accept(pr12); ret = true; @@ -365,6 +374,14 @@ public: return it->get().area(); }; + auto trypack = [&placer, ¬_packed](ItemListIt it) { + return placer.trypack(*it, rem(it, not_packed)); + }; + + auto pack = [&placer, ¬_packed](ItemListIt it) { + return placer.pack(*it, rem(it, not_packed)); + }; + while (it != endit && !ret) { // drill down 1st level // We need to determine in each iteration the largest, second @@ -394,7 +411,7 @@ public: it++; continue; } - auto pr = placer.trypack(not_packed, it); + auto pr = trypack(it); // Check for free area and try to pack the 1st item... if(!pr) { it++; continue; } @@ -420,15 +437,15 @@ public: bool can_pack2 = false; placer.accept(pr); - auto pr2 = placer.trypack(not_packed, it2); + auto pr2 = trypack(it2); auto pr12 = pr; if(!pr2) { placer.unpackLast(); // remove first if(try_reverse) { - pr2 = placer.trypack(not_packed, it2); + pr2 = trypack(it2); if(pr2) { placer.accept(pr2); - pr12 = placer.trypack(not_packed, it); + pr12 = trypack(it); if(pr12) can_pack2 = true; placer.unpackLast(); } @@ -463,7 +480,7 @@ public: if(a3_sum > free_area) { it3++; continue; } placer.accept(pr12); placer.accept(pr2); - bool can_pack3 = placer.pack(not_packed, it3); + bool can_pack3 = pack(it3); if(!can_pack3) { placer.unpackLast(); @@ -476,13 +493,14 @@ public: std::array<typename ItemList::iterator, 3> candidates = {it, it2, it3}; - auto tryPack = [&placer, &candidates, ¬_packed]( + auto tryPack = [&placer, &candidates, ¬_packed, + &pack]( const decltype(indices)& idx) { std::array<bool, 3> packed = {false}; for(auto id : idx) packed.at(id) = - placer.pack(not_packed, candidates[id]); + pack(candidates[id]); bool check = std::all_of(packed.begin(), @@ -536,7 +554,7 @@ public: { auto it = store_.begin(); while (it != store_.end()) { Placer p(bin); p.configure(pconfig); - if(!p.pack(store_, it)) { + if(!p.pack(*it, rem(it, store_))) { it = store_.erase(it); } else it++; } @@ -601,7 +619,7 @@ public: while(it != not_packed.end() && filled_area < INITIAL_FILL_AREA) { - if(placer.pack(not_packed, it)) { + if(placer.pack(*it, rem(it, not_packed))) { filled_area += it->get().area(); free_area = bin_area - filled_area; it = not_packed.erase(it); diff --git a/xs/src/libnest2d/libnest2d/selections/filler.hpp b/xs/src/libnest2d/libnest2d/selections/filler.hpp index ca1281fe6..b20455b0e 100644 --- a/xs/src/libnest2d/libnest2d/selections/filler.hpp +++ b/xs/src/libnest2d/libnest2d/selections/filler.hpp @@ -56,18 +56,13 @@ public: std::sort(store_.begin(), store_.end(), sortfunc); -// Container a = {store_[0], store_[1], store_[4], store_[5] }; -//// a.insert(a.end(), store_.end()-10, store_.end()); -// store_ = a; - PlacementStrategyLike<TPlacer> placer(bin); placer.configure(pconfig); auto it = store_.begin(); while(it != store_.end()) { - if(!placer.pack(store_, it)) { + if(!placer.pack(*it, {std::next(it), store_.end()})) { if(packed_bins_.back().empty()) ++it; -// makeProgress(placer); placer.clearItems(); packed_bins_.emplace_back(); } else { @@ -76,9 +71,6 @@ public: } } -// if(was_packed) { -// packed_bins_.push_back(placer.getItems()); -// } } }; diff --git a/xs/src/libnest2d/libnest2d/selections/firstfit.hpp b/xs/src/libnest2d/libnest2d/selections/firstfit.hpp index 93ca02b1e..1312f9874 100644 --- a/xs/src/libnest2d/libnest2d/selections/firstfit.hpp +++ b/xs/src/libnest2d/libnest2d/selections/firstfit.hpp @@ -61,7 +61,7 @@ public: { auto it = store_.begin(); while (it != store_.end()) { Placer p(bin); p.configure(pconfig); - if(!p.pack(store_, it)) { + if(!p.pack(*it)) { it = store_.erase(it); } else it++; } @@ -73,8 +73,9 @@ public: while(!was_packed) { for(size_t j = 0; j < placers.size() && !was_packed; j++) { - if((was_packed = placers[j].pack(store_, it))) - makeProgress(placers[j], j); + if((was_packed = + placers[j].pack(*it, rem(it, store_) ))) + makeProgress(placers[j], j); } if(!was_packed) { diff --git a/xs/src/libnest2d/tests/test.cpp b/xs/src/libnest2d/tests/test.cpp index 79832b683..197ff6598 100644 --- a/xs/src/libnest2d/tests/test.cpp +++ b/xs/src/libnest2d/tests/test.cpp @@ -110,7 +110,7 @@ TEST(GeometryAlgorithms, boundingCircle) { ASSERT_EQ(c.center().Y, 0); ASSERT_DOUBLE_EQ(c.radius(), 10); - ShapeLike::translate(p, PointImpl{10, 10}); + shapelike::translate(p, PointImpl{10, 10}); c = boundingCircle<PolygonImpl>(p); ASSERT_EQ(c.center().X, 10); @@ -124,8 +124,8 @@ TEST(GeometryAlgorithms, boundingCircle) { c = boundingCircle(part.transformedShape()); if(std::isnan(c.radius())) std::cout << "fail: radius is nan" << std::endl; - else for(auto v : ShapeLike::getContour(part.transformedShape()) ) { - auto d = PointLike::distance(v, c.center()); + else for(auto v : shapelike::getContour(part.transformedShape()) ) { + auto d = pointlike::distance(v, c.center()); if(d > c.radius() ) { auto e = std::abs( 1.0 - d/c.radius()); ASSERT_LE(e, 1e-3); @@ -144,14 +144,14 @@ TEST(GeometryAlgorithms, Distance) { Point p2 = {10, 0}; Point p3 = {10, 10}; - ASSERT_DOUBLE_EQ(PointLike::distance(p1, p2), 10); - ASSERT_DOUBLE_EQ(PointLike::distance(p1, p3), sqrt(200)); + ASSERT_DOUBLE_EQ(pointlike::distance(p1, p2), 10); + ASSERT_DOUBLE_EQ(pointlike::distance(p1, p3), sqrt(200)); Segment seg(p1, p3); - ASSERT_DOUBLE_EQ(PointLike::distance(p2, seg), 7.0710678118654755); + ASSERT_DOUBLE_EQ(pointlike::distance(p2, seg), 7.0710678118654755); - auto result = PointLike::horizontalDistance(p2, seg); + auto result = pointlike::horizontalDistance(p2, seg); auto check = [](Coord val, Coord expected) { if(std::is_floating_point<Coord>::value) @@ -164,11 +164,11 @@ TEST(GeometryAlgorithms, Distance) { ASSERT_TRUE(result.second); check(result.first, 10); - result = PointLike::verticalDistance(p2, seg); + result = pointlike::verticalDistance(p2, seg); ASSERT_TRUE(result.second); check(result.first, -10); - result = PointLike::verticalDistance(Point{10, 20}, seg); + result = pointlike::verticalDistance(Point{10, 20}, seg); ASSERT_TRUE(result.second); check(result.first, 10); @@ -176,12 +176,12 @@ TEST(GeometryAlgorithms, Distance) { Point p4 = {80, 0}; Segment seg2 = { {0, 0}, {0, 40} }; - result = PointLike::horizontalDistance(p4, seg2); + result = pointlike::horizontalDistance(p4, seg2); ASSERT_TRUE(result.second); check(result.first, 80); - result = PointLike::verticalDistance(p4, seg2); + result = pointlike::verticalDistance(p4, seg2); // Point should not be related to the segment ASSERT_FALSE(result.second); @@ -209,7 +209,7 @@ TEST(GeometryAlgorithms, Area) { {61, 97} }; - ASSERT_TRUE(ShapeLike::area(item.transformedShape()) > 0 ); + ASSERT_TRUE(shapelike::area(item.transformedShape()) > 0 ); } TEST(GeometryAlgorithms, IsPointInsidePolygon) { @@ -287,7 +287,7 @@ TEST(GeometryAlgorithms, LeftAndDownPolygon) Item leftp(placer.leftPoly(item)); - ASSERT_TRUE(ShapeLike::isValid(leftp.rawShape()).first); + ASSERT_TRUE(shapelike::isValid(leftp.rawShape()).first); ASSERT_EQ(leftp.vertexCount(), leftControl.vertexCount()); for(unsigned long i = 0; i < leftControl.vertexCount(); i++) { @@ -297,7 +297,7 @@ TEST(GeometryAlgorithms, LeftAndDownPolygon) Item downp(placer.downPoly(item)); - ASSERT_TRUE(ShapeLike::isValid(downp.rawShape()).first); + ASSERT_TRUE(shapelike::isValid(downp.rawShape()).first); ASSERT_EQ(downp.vertexCount(), downControl.vertexCount()); for(unsigned long i = 0; i < downControl.vertexCount(); i++) { @@ -334,7 +334,7 @@ TEST(GeometryAlgorithms, ArrangeRectanglesTight) {20, 20} }; - Arranger<BottomLeftPlacer, DJDHeuristic> arrange(Box(210, 250)); + Nester<BottomLeftPlacer, DJDHeuristic> arrange(Box(210, 250)); auto groups = arrange(rects.begin(), rects.end()); @@ -387,7 +387,7 @@ TEST(GeometryAlgorithms, ArrangeRectanglesLoose) Coord min_obj_distance = 5; - Arranger<BottomLeftPlacer, DJDHeuristic> arrange(Box(210, 250), + Nester<BottomLeftPlacer, DJDHeuristic> arrange(Box(210, 250), min_obj_distance); auto groups = arrange(rects.begin(), rects.end()); @@ -438,7 +438,7 @@ R"raw(<?xml version="1.0" encoding="UTF-8" standalone="yes"?> setX(v, getX(v)/SCALE); rbin.setVertex(i, v); } - out << ShapeLike::serialize<Formats::SVG>(rbin.rawShape()) << std::endl; + out << shapelike::serialize<Formats::SVG>(rbin.rawShape()) << std::endl; for(Item& sh : r) { Item tsh(sh.transformedShape()); for(unsigned i = 0; i < tsh.vertexCount(); i++) { @@ -447,7 +447,7 @@ R"raw(<?xml version="1.0" encoding="UTF-8" standalone="yes"?> setX(v, getX(v)/SCALE); tsh.setVertex(i, v); } - out << ShapeLike::serialize<Formats::SVG>(tsh.rawShape()) << std::endl; + out << shapelike::serialize<Formats::SVG>(tsh.rawShape()) << std::endl; } out << "\n</svg>" << std::endl; } @@ -471,8 +471,8 @@ TEST(GeometryAlgorithms, BottomLeftStressTest) { auto next = it; int i = 0; while(it != input.end() && ++next != input.end()) { - placer.pack(input, it); - placer.pack(input, next); + placer.pack(*it); + placer.pack(*next); auto result = placer.getItems(); bool valid = true; @@ -701,7 +701,7 @@ std::vector<ItemPair> nfp_concave_testdata = { } }; -template<NfpLevel lvl, Coord SCALE> +template<nfp::NfpLevel lvl, Coord SCALE> void testNfp(const std::vector<ItemPair>& testdata) { using namespace libnest2d; @@ -716,12 +716,12 @@ void testNfp(const std::vector<ItemPair>& testdata) { orbiter.translate({210*SCALE, 0}); - auto&& nfp = Nfp::noFitPolygon<lvl>(stationary.rawShape(), + auto&& nfp = nfp::noFitPolygon<lvl>(stationary.rawShape(), orbiter.transformedShape()); strategies::correctNfpPosition(nfp, stationary, orbiter); - auto v = ShapeLike::isValid(nfp.first); + auto v = shapelike::isValid(nfp.first); if(!v.first) { std::cout << v.second << std::endl; @@ -733,7 +733,7 @@ void testNfp(const std::vector<ItemPair>& testdata) { int i = 0; auto rorbiter = orbiter.transformedShape(); - auto vo = Nfp::referenceVertex(rorbiter); + auto vo = nfp::referenceVertex(rorbiter); ASSERT_TRUE(stationary.isInside(infp)); @@ -774,7 +774,7 @@ void testNfp(const std::vector<ItemPair>& testdata) { } TEST(GeometryAlgorithms, nfpConvexConvex) { - testNfp<NfpLevel::CONVEX_ONLY, 1>(nfp_testdata); + testNfp<nfp::NfpLevel::CONVEX_ONLY, 1>(nfp_testdata); } //TEST(GeometryAlgorithms, nfpConcaveConcave) { @@ -807,7 +807,7 @@ TEST(GeometryAlgorithms, pointOnPolygonContour) { for(int i = 0; i <= 100; i++) { auto v = ecache.coords(i*(0.01)); - ASSERT_TRUE(ShapeLike::touches(v, input.transformedShape())); + ASSERT_TRUE(shapelike::touches(v, input.transformedShape())); } } @@ -821,17 +821,17 @@ TEST(GeometryAlgorithms, mergePileWithPolygon) { rect2.translate({10, 0}); rect3.translate({25, 0}); - ShapeLike::Shapes<PolygonImpl> pile; + shapelike::Shapes<PolygonImpl> pile; pile.push_back(rect1.transformedShape()); pile.push_back(rect2.transformedShape()); - auto result = Nfp::merge(pile, rect3.transformedShape()); + auto result = nfp::merge(pile, rect3.transformedShape()); ASSERT_EQ(result.size(), 1); Rectangle ref(45, 15); - ASSERT_EQ(ShapeLike::area(result.front()), ref.area()); + ASSERT_EQ(shapelike::area(result.front()), ref.area()); } int main(int argc, char **argv) { diff --git a/xs/src/libnest2d/tools/svgtools.hpp b/xs/src/libnest2d/tools/svgtools.hpp index 3a83caa70..776dd5a1a 100644 --- a/xs/src/libnest2d/tools/svgtools.hpp +++ b/xs/src/libnest2d/tools/svgtools.hpp @@ -56,14 +56,14 @@ public: auto d = static_cast<Coord>( std::round(conf_.height*conf_.mm_in_coord_units) ); - auto& contour = ShapeLike::getContour(tsh); + auto& contour = shapelike::getContour(tsh); for(auto& v : contour) setY(v, -getY(v) + d); - auto& holes = ShapeLike::holes(tsh); + auto& holes = shapelike::holes(tsh); for(auto& h : holes) for(auto& v : h) setY(v, -getY(v) + d); } - currentLayer() += ShapeLike::serialize<Formats::SVG>(tsh, + currentLayer() += shapelike::serialize<Formats::SVG>(tsh, 1.0/conf_.mm_in_coord_units) + "\n"; } diff --git a/xs/src/libslic3r/ModelArrange.hpp b/xs/src/libslic3r/ModelArrange.hpp index 79371cdb2..cc4bfff0f 100644 --- a/xs/src/libslic3r/ModelArrange.hpp +++ b/xs/src/libslic3r/ModelArrange.hpp @@ -104,8 +104,7 @@ using ItemGroup = std::vector<std::reference_wrapper<Item>>; std::tuple<double /*score*/, Box /*farthest point from bin center*/> objfunc(const PointImpl& bincenter, double bin_area, - ShapeLike::Shapes<PolygonImpl>& pile, // The currently arranged pile - double pile_area, + sl::Shapes<PolygonImpl>& pile, // The currently arranged pile const Item &item, double norm, // A norming factor for physical dimensions std::vector<double>& areacache, // pile item areas will be cached @@ -114,8 +113,6 @@ objfunc(const PointImpl& bincenter, const ItemGroup& remaining ) { - using pl = PointLike; - using sl = ShapeLike; using Coord = TCoord<PointImpl>; static const double BIG_ITEM_TRESHOLD = 0.02; @@ -150,7 +147,7 @@ objfunc(const PointImpl& bincenter, // Calculate the full bounding box of the pile with the candidate item pile.emplace_back(item.transformedShape()); - auto fullbb = ShapeLike::boundingBox(pile); + auto fullbb = sl::boundingBox(pile); pile.pop_back(); // The bounding box of the big items (they will accumulate in the center @@ -283,21 +280,23 @@ class _ArrBase { protected: using Placer = strategies::_NofitPolyPlacer<PolygonImpl, TBin>; using Selector = FirstFitSelection; - using Packer = Arranger<Placer, Selector>; + using Packer = Nester<Placer, Selector>; using PConfig = typename Packer::PlacementConfig; using Distance = TCoord<PointImpl>; - using Pile = ShapeLike::Shapes<PolygonImpl>; + using Pile = sl::Shapes<PolygonImpl>; Packer pck_; PConfig pconf_; // Placement configuration double bin_area_; std::vector<double> areacache_; SpatIndex rtree_; + double norm_; public: _ArrBase(const TBin& bin, Distance dist, std::function<void(unsigned)> progressind): - pck_(bin, dist), bin_area_(ShapeLike::area<PolygonImpl>(bin)) + pck_(bin, dist), bin_area_(sl::area(bin)), + norm_(std::sqrt(sl::area(bin))) { fillConfig(pconf_); pck_.progressIndicator(progressind); @@ -306,7 +305,7 @@ public: template<class...Args> inline IndexedPackGroup operator()(Args&&...args) { areacache_.clear(); rtree_.clear(); - return pck_.arrangeIndexed(std::forward<Args>(args)...); + return pck_.executeIndexed(std::forward<Args>(args)...); } }; @@ -321,21 +320,17 @@ public: pconf_.object_function = [this, bin] ( Pile& pile, const Item &item, - double pile_area, - double norm, const ItemGroup& rem) { auto result = objfunc(bin.center(), bin_area_, pile, - pile_area, item, norm, areacache_, - rtree_, - rem); + item, norm_, areacache_, rtree_, rem); double score = std::get<0>(result); auto& fullbb = std::get<1>(result); auto wdiff = fullbb.width() - bin.width(); auto hdiff = fullbb.height() - bin.height(); - if(wdiff > 0) score += std::pow(wdiff, 2) / norm; - if(hdiff > 0) score += std::pow(hdiff, 2) / norm; + if(wdiff > 0) score += std::pow(wdiff, 2) / norm_; + if(hdiff > 0) score += std::pow(hdiff, 2) / norm_; return score; }; @@ -357,31 +352,28 @@ public: pconf_.object_function = [this, &bin] ( Pile& pile, const Item &item, - double pile_area, - double norm, const ItemGroup& rem) { - auto result = objfunc(bin.center(), bin_area_, pile, - pile_area, item, norm, areacache_, - rtree_, rem); + auto result = objfunc(bin.center(), bin_area_, pile, item, norm_, + areacache_, rtree_, rem); double score = std::get<0>(result); auto& fullbb = std::get<1>(result); - auto d = PointLike::distance(fullbb.minCorner(), + auto d = pl::distance(fullbb.minCorner(), fullbb.maxCorner()); auto diff = d - 2*bin.radius(); if(diff > 0) { if( item.area() > 0.01*bin_area_ && item.vertexCount() < 30) { pile.emplace_back(item.transformedShape()); - auto chull = ShapeLike::convexHull(pile); + auto chull = sl::convexHull(pile); pile.pop_back(); auto C = strategies::boundingCircle(chull); auto rdiff = C.radius() - bin.radius(); if(rdiff > 0) { - score += std::pow(rdiff, 3) / norm; + score += std::pow(rdiff, 3) / norm_; } } } @@ -403,14 +395,11 @@ public: pconf_.object_function = [this, &bin] ( Pile& pile, const Item &item, - double pile_area, - double norm, const ItemGroup& rem) { - auto binbb = ShapeLike::boundingBox(bin); - auto result = objfunc(binbb.center(), bin_area_, pile, - pile_area, item, norm, areacache_, - rtree_, rem); + auto binbb = sl::boundingBox(bin); + auto result = objfunc(binbb.center(), bin_area_, pile, item, norm_, + areacache_, rtree_, rem); double score = std::get<0>(result); return score; @@ -430,13 +419,10 @@ public: this->pconf_.object_function = [this] ( Pile& pile, const Item &item, - double pile_area, - double norm, const ItemGroup& rem) { - auto result = objfunc({0, 0}, 0, pile, pile_area, - item, norm, areacache_, - rtree_, rem); + auto result = objfunc({0, 0}, 0, pile, item, norm_, + areacache_, rtree_, rem); return std::get<0>(result); }; @@ -711,7 +697,7 @@ bool arrange(Model &model, coordf_t min_obj_distance, using P = libnest2d::PolygonImpl; auto ctour = Slic3rMultiPoint_to_ClipperPath(bed); - P irrbed = ShapeLike::create<PolygonImpl>(std::move(ctour)); + P irrbed = sl::create<PolygonImpl>(std::move(ctour)); AutoArranger<P> arrange(irrbed, min_obj_distance, progressind); |