From 34c850fa9da216070e07b7276fb1ba99c8dbe32b Mon Sep 17 00:00:00 2001 From: tamasmeszaros Date: Tue, 5 Jun 2018 12:02:45 +0200 Subject: initial NFP method with convex polygons working. --- xs/src/libnest2d/CMakeLists.txt | 30 +- xs/src/libnest2d/cmake_modules/FindClipper.cmake | 4 + xs/src/libnest2d/libnest2d.h | 1 + xs/src/libnest2d/libnest2d/boost_alg.hpp | 109 +- .../libnest2d/clipper_backend/CMakeLists.txt | 2 +- .../libnest2d/clipper_backend/clipper_backend.cpp | 19 +- .../libnest2d/clipper_backend/clipper_backend.hpp | 115 +- xs/src/libnest2d/libnest2d/geometries_nfp.hpp | 135 +- xs/src/libnest2d/libnest2d/geometry_traits.hpp | 227 +- xs/src/libnest2d/libnest2d/libnest2d.hpp | 73 +- xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp | 172 +- .../libnest2d/placers/placer_boilerplate.hpp | 7 +- .../libnest2d/selections/djd_heuristic.hpp | 35 +- .../libnest2d/selections/selection_boilerplate.hpp | 6 + xs/src/libnest2d/tests/CMakeLists.txt | 27 +- xs/src/libnest2d/tests/main.cpp | 242 +- xs/src/libnest2d/tests/printer_parts.cpp | 2856 +++++++++++++++++--- xs/src/libnest2d/tests/printer_parts.h | 7 +- xs/src/libnest2d/tests/svgtools.hpp | 112 + xs/src/libnest2d/tests/test.cpp | 338 ++- 20 files changed, 3755 insertions(+), 762 deletions(-) create mode 100644 xs/src/libnest2d/tests/svgtools.hpp (limited to 'xs/src/libnest2d') diff --git a/xs/src/libnest2d/CMakeLists.txt b/xs/src/libnest2d/CMakeLists.txt index 568d1a5a9..ac9530a63 100644 --- a/xs/src/libnest2d/CMakeLists.txt +++ b/xs/src/libnest2d/CMakeLists.txt @@ -19,6 +19,9 @@ list(APPEND CMAKE_MODULE_PATH ${CMAKE_CURRENT_SOURCE_DIR}/cmake_modules/) option(LIBNEST2D_UNITTESTS "If enabled, googletest framework will be downloaded and the provided unit tests will be included in the build." OFF) +option(LIBNEST2D_BUILD_EXAMPLES "If enabled, examples will be built." OFF) +option(LIBNEST2D_BUILD_SHARED_LIB "Build shared library." ON) + #set(LIBNEST2D_GEOMETRIES_TARGET "" CACHE STRING # "Build libnest2d with geometry classes implemented by the chosen target.") @@ -46,7 +49,7 @@ if((NOT LIBNEST2D_GEOMETRIES_TARGET) OR (LIBNEST2D_GEOMETRIES_TARGET STREQUAL "" message(STATUS "libnest2D backend is default") if(NOT Boost_INCLUDE_DIRS_FOUND) - find_package(Boost REQUIRED) + find_package(Boost 1.58 REQUIRED) # TODO automatic download of boost geometry headers endif() @@ -65,9 +68,19 @@ else() message(STATUS "Libnest2D backend is: ${LIBNEST2D_GEOMETRIES_TARGET}") endif() -add_library(libnest2d STATIC ${LIBNEST2D_SRCFILES} ) -target_link_libraries(libnest2d ${LIBNEST2D_GEOMETRIES_TARGET}) -target_include_directories(libnest2d PUBLIC ${CMAKE_SOURCE_DIR}) +message(STATUS "clipper lib is: ${LIBNEST2D_GEOMETRIES_TARGET}") + +add_library(libnest2d_static STATIC ${LIBNEST2D_SRCFILES} ) +target_link_libraries(libnest2d_static PRIVATE ${LIBNEST2D_GEOMETRIES_TARGET}) +target_include_directories(libnest2d_static PUBLIC ${CMAKE_SOURCE_DIR}) +set_target_properties(libnest2d_static PROPERTIES PREFIX "") + +if(LIBNEST2D_BUILD_SHARED_LIB) + add_library(libnest2d SHARED ${LIBNEST2D_SRCFILES} ) + target_link_libraries(libnest2d PRIVATE ${LIBNEST2D_GEOMETRIES_TARGET}) + target_include_directories(libnest2d PUBLIC ${CMAKE_SOURCE_DIR}) + set_target_properties(libnest2d PROPERTIES PREFIX "") +endif() set(LIBNEST2D_HEADERS ${CMAKE_CURRENT_SOURCE_DIR}) @@ -79,3 +92,12 @@ endif() if(LIBNEST2D_UNITTESTS) add_subdirectory(tests) endif() + +if(LIBNEST2D_BUILD_EXAMPLES) + add_executable(example tests/main.cpp + tests/svgtools.hpp + tests/printer_parts.cpp + tests/printer_parts.h) + target_link_libraries(example libnest2d_static) + target_include_directories(example PUBLIC ${CMAKE_CURRENT_SOURCE_DIR}) +endif() diff --git a/xs/src/libnest2d/cmake_modules/FindClipper.cmake b/xs/src/libnest2d/cmake_modules/FindClipper.cmake index ad4460c35..f6b973440 100644 --- a/xs/src/libnest2d/cmake_modules/FindClipper.cmake +++ b/xs/src/libnest2d/cmake_modules/FindClipper.cmake @@ -14,6 +14,8 @@ FIND_PATH(CLIPPER_INCLUDE_DIRS clipper.hpp $ENV{CLIPPER_PATH}/include/polyclipping/ ${PROJECT_SOURCE_DIR}/python/pymesh/third_party/include/ ${PROJECT_SOURCE_DIR}/python/pymesh/third_party/include/polyclipping/ + ${CMAKE_PREFIX_PATH}/include/polyclipping + ${CMAKE_PREFIX_PATH}/include/ /opt/local/include/ /opt/local/include/polyclipping/ /usr/local/include/ @@ -29,6 +31,8 @@ FIND_LIBRARY(CLIPPER_LIBRARIES polyclipping $ENV{CLIPPER_PATH}/lib/polyclipping/ ${PROJECT_SOURCE_DIR}/python/pymesh/third_party/lib/ ${PROJECT_SOURCE_DIR}/python/pymesh/third_party/lib/polyclipping/ + ${CMAKE_PREFIX_PATH}/lib/ + ${CMAKE_PREFIX_PATH}/lib/polyclipping/ /opt/local/lib/ /opt/local/lib/polyclipping/ /usr/local/lib/ diff --git a/xs/src/libnest2d/libnest2d.h b/xs/src/libnest2d/libnest2d.h index dcdb812dc..dff7009ee 100644 --- a/xs/src/libnest2d/libnest2d.h +++ b/xs/src/libnest2d/libnest2d.h @@ -29,6 +29,7 @@ using FillerSelection = strategies::_FillerSelection; using FirstFitSelection = strategies::_FirstFitSelection; using DJDHeuristic = strategies::_DJDHeuristic; +using NfpPlacer = strategies::_NofitPolyPlacer; using BottomLeftPlacer = strategies::_BottomLeftPlacer; using NofitPolyPlacer = strategies::_NofitPolyPlacer; diff --git a/xs/src/libnest2d/libnest2d/boost_alg.hpp b/xs/src/libnest2d/libnest2d/boost_alg.hpp index 5f1c2806f..fb43c2125 100644 --- a/xs/src/libnest2d/libnest2d/boost_alg.hpp +++ b/xs/src/libnest2d/libnest2d/boost_alg.hpp @@ -25,12 +25,13 @@ using libnest2d::setX; using libnest2d::setY; using Box = libnest2d::_Box; using Segment = libnest2d::_Segment; +using Shapes = libnest2d::Nfp::Shapes; } /** - * We have to make all the binpack2d geometry types available to boost. The real - * models of the geometries remain the same if a conforming model for binpack2d + * We have to make all the libnest2d geometry types available to boost. The real + * models of the geometries remain the same if a conforming model for libnest2d * was defined by the library client. Boost is used only as an optional * implementer of some algorithms that can be implemented by the model itself * if a faster alternative exists. @@ -184,10 +185,10 @@ template<> struct indexed_access { /* ************************************************************************** */ -/* Polygon concept adaptaion ************************************************ */ +/* Polygon concept adaptation *********************************************** */ /* ************************************************************************** */ -// Connversion between binpack2d::Orientation and order_selector /////////////// +// Connversion between libnest2d::Orientation and order_selector /////////////// template struct ToBoostOrienation {}; @@ -269,17 +270,34 @@ struct interior_rings { } }; +/* ************************************************************************** */ +/* MultiPolygon concept adaptation ****************************************** */ +/* ************************************************************************** */ + +template<> struct tag { + using type = multi_polygon_tag; +}; + } // traits } // geometry -// This is an addition to the ring implementation +// This is an addition to the ring implementation of Polygon concept template<> struct range_value { using type = bp2d::PointImpl; }; +template<> +struct range_value { + using type = bp2d::PolygonImpl; +}; + } // boost +/* ************************************************************************** */ +/* Algorithms *************************************************************** */ +/* ************************************************************************** */ + namespace libnest2d { // Now the algorithms that boost can provide... template<> @@ -296,7 +314,7 @@ inline double PointLike::distance(const PointImpl& p, return boost::geometry::distance(p, seg); } -// Tell binpack2d how to make string out of a ClipperPolygon object +// Tell libnest2d how to make string out of a ClipperPolygon object template<> inline bool ShapeLike::intersects(const PathImpl& sh1, const PathImpl& sh2) @@ -304,14 +322,14 @@ inline bool ShapeLike::intersects(const PathImpl& sh1, return boost::geometry::intersects(sh1, sh2); } -// Tell binpack2d how to make string out of a ClipperPolygon object +// Tell libnest2d how to make string out of a ClipperPolygon object template<> inline bool ShapeLike::intersects(const PolygonImpl& sh1, const PolygonImpl& sh2) { return boost::geometry::intersects(sh1, sh2); } -// Tell binpack2d how to make string out of a ClipperPolygon object +// Tell libnest2d how to make string out of a ClipperPolygon object template<> inline bool ShapeLike::intersects(const bp2d::Segment& s1, const bp2d::Segment& s2) { @@ -346,6 +364,7 @@ inline bool ShapeLike::touches( const PolygonImpl& sh1, return boost::geometry::touches(sh1, sh2); } +#ifndef DISABLE_BOOST_BOUNDING_BOX template<> inline bp2d::Box ShapeLike::boundingBox(const PolygonImpl& sh) { bp2d::Box b; @@ -354,7 +373,34 @@ inline bp2d::Box ShapeLike::boundingBox(const PolygonImpl& sh) { } template<> -inline void ShapeLike::rotate(PolygonImpl& sh, const Radians& rads) { +inline bp2d::Box ShapeLike::boundingBox(const bp2d::Shapes& shapes) { + bp2d::Box b; + boost::geometry::envelope(shapes, b); + return b; +} +#endif + +#ifndef DISABLE_BOOST_CONVEX_HULL +template<> +inline PolygonImpl ShapeLike::convexHull(const PolygonImpl& sh) +{ + PolygonImpl ret; + boost::geometry::convex_hull(sh, ret); + return ret; +} + +template<> +inline PolygonImpl ShapeLike::convexHull(const bp2d::Shapes& shapes) +{ + PolygonImpl ret; + boost::geometry::convex_hull(shapes, ret); + return ret; +} +#endif + +template<> +inline void ShapeLike::rotate(PolygonImpl& sh, const Radians& rads) +{ namespace trans = boost::geometry::strategy::transform; PolygonImpl cpy = sh; @@ -364,8 +410,10 @@ inline void ShapeLike::rotate(PolygonImpl& sh, const Radians& rads) { boost::geometry::transform(cpy, sh, rotate); } +#ifndef DISABLE_BOOST_TRANSLATE template<> -inline void ShapeLike::translate(PolygonImpl& sh, const PointImpl& offs) { +inline void ShapeLike::translate(PolygonImpl& sh, const PointImpl& offs) +{ namespace trans = boost::geometry::strategy::transform; PolygonImpl cpy = sh; @@ -374,19 +422,33 @@ inline void ShapeLike::translate(PolygonImpl& sh, const PointImpl& offs) { boost::geometry::transform(cpy, sh, translate); } +#endif #ifndef DISABLE_BOOST_OFFSET template<> -inline void ShapeLike::offset(PolygonImpl& sh, bp2d::Coord distance) { +inline void ShapeLike::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_MINKOWSKI_ADD template<> inline PolygonImpl& Nfp::minkowskiAdd(PolygonImpl& sh, - const PolygonImpl& /*other*/) { + const PolygonImpl& /*other*/) +{ return sh; } #endif @@ -394,12 +456,26 @@ inline PolygonImpl& Nfp::minkowskiAdd(PolygonImpl& sh, #ifndef DISABLE_BOOST_SERIALIZE template<> inline std::string ShapeLike::serialize( - const PolygonImpl& sh) + const PolygonImpl& sh, double scale) { std::stringstream ss; - std::string style = "fill: orange; stroke: black; stroke-width: 1px;"; - auto svg_data = boost::geometry::svg(sh, style); + std::string style = "fill: none; stroke: black; stroke-width: 1px;"; + + using namespace boost::geometry; + using Pointf = model::point; + using Polygonf = model::polygon; + + Polygonf::ring_type ring; + ring.reserve(ShapeLike::contourVertexCount(sh)); + + for(auto it = ShapeLike::cbegin(sh); it != ShapeLike::cend(sh); it++) { + auto& v = *it; + ring.emplace_back(getX(v)*scale, getY(v)*scale); + }; + Polygonf poly; + poly.outer() = ring; + auto svg_data = boost::geometry::svg(poly, style); ss << svg_data << std::endl; @@ -417,7 +493,8 @@ inline void ShapeLike::unserialize( #endif template<> inline std::pair -ShapeLike::isValid(const PolygonImpl& sh) { +ShapeLike::isValid(const PolygonImpl& sh) +{ std::string message; bool ret = boost::geometry::is_valid(sh, message); diff --git a/xs/src/libnest2d/libnest2d/clipper_backend/CMakeLists.txt b/xs/src/libnest2d/libnest2d/clipper_backend/CMakeLists.txt index 9e6a48cf6..b6f2de439 100644 --- a/xs/src/libnest2d/libnest2d/clipper_backend/CMakeLists.txt +++ b/xs/src/libnest2d/libnest2d/clipper_backend/CMakeLists.txt @@ -1,6 +1,6 @@ if(NOT TARGET clipper) # If there is a clipper target in the parent project we are good to go. - find_package(Clipper QUIET) + find_package(Clipper 6.1) if(NOT CLIPPER_FOUND) find_package(Subversion QUIET) diff --git a/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.cpp b/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.cpp index 08b095087..6bd7bf99f 100644 --- a/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.cpp +++ b/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.cpp @@ -46,10 +46,25 @@ std::string ShapeLike::toString(const PolygonImpl& sh) return ss.str(); } -template<> PolygonImpl ShapeLike::create( std::initializer_list< PointImpl > il) +template<> PolygonImpl ShapeLike::create( const PathImpl& path ) { PolygonImpl p; - p.Contour = il; + p.Contour = path; + + // Expecting that the coordinate system Y axis is positive in upwards + // direction + if(ClipperLib::Orientation(p.Contour)) { + // Not clockwise then reverse the b*tch + ClipperLib::ReversePath(p.Contour); + } + + return p; +} + +template<> PolygonImpl ShapeLike::create( PathImpl&& path ) +{ + PolygonImpl p; + p.Contour.swap(path); // Expecting that the coordinate system Y axis is positive in upwards // direction diff --git a/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.hpp b/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.hpp index 92a806727..6621d7085 100644 --- a/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.hpp +++ b/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.hpp @@ -20,6 +20,7 @@ using PolygonImpl = ClipperLib::PolyNode; using PathImpl = ClipperLib::Path; inline PointImpl& operator +=(PointImpl& p, const PointImpl& pa ) { + // This could be done with SIMD p.X += pa.X; p.Y += pa.Y; return p; @@ -37,6 +38,13 @@ inline PointImpl& operator -=(PointImpl& p, const PointImpl& pa ) { return p; } +inline PointImpl operator -(PointImpl& p ) { + PointImpl ret = p; + ret.X = -ret.X; + ret.Y = -ret.Y; + return ret; +} + inline PointImpl operator-(const PointImpl& p1, const PointImpl& p2) { PointImpl ret = p1; ret -= p2; @@ -100,14 +108,29 @@ inline void ShapeLike::reserve(PolygonImpl& sh, unsigned long vertex_capacity) return sh.Contour.reserve(vertex_capacity); } +#define DISABLE_BOOST_AREA + +namespace _smartarea { +template +inline double area(const PolygonImpl& sh) { + return std::nan(""); +} + +template<> +inline double area(const PolygonImpl& sh) { + return -ClipperLib::Area(sh.Contour); +} + +template<> +inline double area(const PolygonImpl& sh) { + return ClipperLib::Area(sh.Contour); +} +} + // Tell binpack2d how to make string out of a ClipperPolygon object template<> inline double ShapeLike::area(const PolygonImpl& sh) { - #define DISABLE_BOOST_AREA - double ret = ClipperLib::Area(sh.Contour); -// if(OrientationType::Value == Orientation::COUNTER_CLOCKWISE) -// ret = -ret; - return ret; + return _smartarea::area::Value>(sh); } template<> @@ -191,8 +214,9 @@ template<> struct HolesContainer { using Type = ClipperLib::Paths; }; -template<> -PolygonImpl ShapeLike::create( std::initializer_list< PointImpl > il); +template<> PolygonImpl ShapeLike::create( const PathImpl& path); + +template<> PolygonImpl ShapeLike::create( PathImpl&& path); template<> const THolesContainer& ShapeLike::holes( @@ -202,33 +226,94 @@ template<> THolesContainer& ShapeLike::holes(PolygonImpl& sh); template<> -inline TCountour& ShapeLike::getHole(PolygonImpl& sh, +inline TContour& ShapeLike::getHole(PolygonImpl& sh, unsigned long idx) { return sh.Childs[idx]->Contour; } template<> -inline const TCountour& ShapeLike::getHole(const PolygonImpl& sh, - unsigned long idx) { +inline const TContour& ShapeLike::getHole(const PolygonImpl& sh, + unsigned long idx) +{ return sh.Childs[idx]->Contour; } -template<> -inline size_t ShapeLike::holeCount(const PolygonImpl& sh) { +template<> inline size_t ShapeLike::holeCount(const PolygonImpl& sh) +{ return sh.Childs.size(); } -template<> -inline PathImpl& ShapeLike::getContour(PolygonImpl& sh) { +template<> inline PathImpl& ShapeLike::getContour(PolygonImpl& sh) +{ return sh.Contour; } template<> -inline const PathImpl& ShapeLike::getContour(const PolygonImpl& sh) { +inline const PathImpl& ShapeLike::getContour(const PolygonImpl& sh) +{ return sh.Contour; } +#define DISABLE_BOOST_TRANSLATE +template<> +inline void ShapeLike::translate(PolygonImpl& sh, const PointImpl& offs) +{ + for(auto& p : sh.Contour) { p += offs; } + for(auto& hole : sh.Childs) for(auto& p : hole->Contour) { p += offs; } +} + +#define DISABLE_BOOST_NFP_MERGE + +template<> inline +Nfp::Shapes Nfp::merge(const Nfp::Shapes& shapes, + const PolygonImpl& sh) +{ + Nfp::Shapes retv; + + ClipperLib::Clipper clipper; + + bool closed = true; + +#ifndef NDEBUG +#define _valid() valid = + bool valid = false; +#else +#define _valid() +#endif + + _valid() clipper.AddPath(sh.Contour, ClipperLib::ptSubject, closed); + + for(auto& hole : sh.Childs) { + _valid() clipper.AddPath(hole->Contour, ClipperLib::ptSubject, closed); + assert(valid); + } + + for(auto& path : shapes) { + _valid() clipper.AddPath(path.Contour, ClipperLib::ptSubject, closed); + assert(valid); + for(auto& hole : path.Childs) { + _valid() clipper.AddPath(hole->Contour, ClipperLib::ptSubject, closed); + assert(valid); + } + } + + ClipperLib::Paths rret; + clipper.Execute(ClipperLib::ctUnion, rret, ClipperLib::pftNonZero); + retv.reserve(rret.size()); + for(auto& p : rret) { + if(ClipperLib::Orientation(p)) { + // Not clockwise then reverse the b*tch + ClipperLib::ReversePath(p); + } + retv.emplace_back(); + retv.back().Contour = p; + retv.back().Contour.emplace_back(p.front()); + } + + return retv; +} + } //#define DISABLE_BOOST_SERIALIZE diff --git a/xs/src/libnest2d/libnest2d/geometries_nfp.hpp b/xs/src/libnest2d/libnest2d/geometries_nfp.hpp index 219c4b565..9f8bd6031 100644 --- a/xs/src/libnest2d/libnest2d/geometries_nfp.hpp +++ b/xs/src/libnest2d/libnest2d/geometries_nfp.hpp @@ -3,18 +3,56 @@ #include "geometry_traits.hpp" #include +#include namespace libnest2d { struct Nfp { template -static RawShape& minkowskiAdd(RawShape& sh, const RawShape& /*other*/) { +using Shapes = typename ShapeLike::Shapes; + +template +static RawShape& minkowskiAdd(RawShape& sh, const RawShape& /*other*/) +{ static_assert(always_false::value, - "ShapeLike::minkowskiAdd() unimplemented!"); + "Nfp::minkowskiAdd() unimplemented!"); return sh; } +template +static Shapes merge(const Shapes& shc, const RawShape& sh) +{ + static_assert(always_false::value, + "Nfp::merge(shapes, shape) unimplemented!"); +} + +template +inline static TPoint referenceVertex(const RawShape& sh) +{ + return rightmostUpVertex(sh); +} + +template +static TPoint leftmostDownVertex(const RawShape& sh) { + + // find min x and min y vertex + auto it = std::min_element(ShapeLike::cbegin(sh), ShapeLike::cend(sh), + _vsort); + + return *it; +} + +template +static TPoint rightmostUpVertex(const RawShape& sh) { + + // find min x and min y vertex + auto it = std::max_element(ShapeLike::cbegin(sh), ShapeLike::cend(sh), + _vsort); + + return *it; +} + template static RawShape noFitPolygon(const RawShape& sh, const RawShape& other) { auto isConvex = [](const RawShape& sh) { @@ -31,24 +69,20 @@ static RawShape noFitPolygon(const RawShape& sh, const RawShape& other) { { RawShape other = cother; - // Make it counter-clockwise - for(auto shit = ShapeLike::begin(other); - shit != ShapeLike::end(other); ++shit ) { - auto& v = *shit; - setX(v, -getX(v)); - setY(v, -getY(v)); - } + // Make the other polygon counter-clockwise + std::reverse(ShapeLike::begin(other), ShapeLike::end(other)); - RawShape rsh; + RawShape rsh; // Final nfp placeholder std::vector edgelist; size_t cap = ShapeLike::contourVertexCount(sh) + ShapeLike::contourVertexCount(other); + // Reserve the needed memory edgelist.reserve(cap); ShapeLike::reserve(rsh, cap); - { + { // place all edges from sh into edgelist auto first = ShapeLike::cbegin(sh); auto next = first + 1; auto endit = ShapeLike::cend(sh); @@ -56,7 +90,7 @@ static RawShape noFitPolygon(const RawShape& sh, const RawShape& other) { while(next != endit) edgelist.emplace_back(*(first++), *(next++)); } - { + { // place all edges from other into edgelist auto first = ShapeLike::cbegin(other); auto next = first + 1; auto endit = ShapeLike::cend(other); @@ -64,31 +98,64 @@ static RawShape noFitPolygon(const RawShape& sh, const RawShape& other) { while(next != endit) edgelist.emplace_back(*(first++), *(next++)); } + // Sort the edges by angle to X axis. std::sort(edgelist.begin(), edgelist.end(), [](const Edge& e1, const Edge& e2) { return e1.angleToXaxis() > e2.angleToXaxis(); }); + // Add the two vertices from the first edge into the final polygon. ShapeLike::addVertex(rsh, edgelist.front().first()); ShapeLike::addVertex(rsh, edgelist.front().second()); auto tmp = std::next(ShapeLike::begin(rsh)); - // Construct final nfp + // Construct final nfp by placing each edge to the end of the previous for(auto eit = std::next(edgelist.begin()); eit != edgelist.end(); - ++eit) { - - auto dx = getX(*tmp) - getX(eit->first()); - auto dy = getY(*tmp) - getY(eit->first()); + ++eit) + { + auto d = *tmp - eit->first(); + auto p = eit->second() + d; - ShapeLike::addVertex(rsh, getX(eit->second())+dx, - getY(eit->second())+dy ); + ShapeLike::addVertex(rsh, p); tmp = std::next(tmp); } + // Now we have an nfp somewhere in the dark. We need to get it + // to the right position around the stationary shape. + // This is done by choosing the leftmost lowest vertex of the + // orbiting polygon to be touched with the rightmost upper + // vertex of the stationary polygon. In this configuration, the + // reference vertex of the orbiting polygon (which can be dragged around + // the nfp) will be its rightmost upper vertex that coincides with the + // rightmost upper vertex of the nfp. No proof provided other than Jonas + // Lindmark's reasoning about the reference vertex of nfp in his thesis + // ("No fit polygon problem" - section 2.1.9) + + auto csh = sh; // Copy sh, we will sort the verices in the copy + auto& cmp = _vsort; + std::sort(ShapeLike::begin(csh), ShapeLike::end(csh), cmp); + std::sort(ShapeLike::begin(other), ShapeLike::end(other), cmp); + + // leftmost lower vertex of the stationary polygon + auto& touch_sh = *(std::prev(ShapeLike::end(csh))); + // rightmost upper vertex of the orbiting polygon + auto& touch_other = *(ShapeLike::begin(other)); + + // Calculate the difference and move the orbiter to the touch position. + auto dtouch = touch_sh - touch_other; + auto top_other = *(std::prev(ShapeLike::end(other))) + dtouch; + + // Get the righmost upper vertex of the nfp and move it to the RMU of + // the orbiter because they should coincide. + auto&& top_nfp = rightmostUpVertex(rsh); + auto dnfp = top_other - top_nfp; + std::for_each(ShapeLike::begin(rsh), ShapeLike::end(rsh), + [&dnfp](Vertex& v) { v+= dnfp; } ); + return rsh; }; @@ -118,6 +185,36 @@ static RawShape noFitPolygon(const RawShape& sh, const RawShape& other) { return rsh; } +template +static inline Shapes noFitPolygon(const Shapes& shapes, + const RawShape& other) +{ + assert(shapes.size() >= 1); + auto shit = shapes.begin(); + + Shapes ret; + ret.emplace_back(noFitPolygon(*shit, other)); + + while(++shit != shapes.end()) ret = merge(ret, noFitPolygon(*shit, other)); + + return ret; +} + +private: + +// Do not specialize this... +template +static inline bool _vsort(const TPoint& v1, + const TPoint& v2) +{ + using Coord = TCoord>; + auto diff = getY(v1) - getY(v2); + if(std::abs(diff) <= std::numeric_limits::epsilon()) + return getX(v1) < getX(v2); + + return diff < 0; +} + }; } diff --git a/xs/src/libnest2d/libnest2d/geometry_traits.hpp b/xs/src/libnest2d/libnest2d/geometry_traits.hpp index 2ab2d1c49..b1353b457 100644 --- a/xs/src/libnest2d/libnest2d/geometry_traits.hpp +++ b/xs/src/libnest2d/libnest2d/geometry_traits.hpp @@ -5,6 +5,7 @@ #include #include #include +#include #include #include "common.hpp" @@ -81,6 +82,8 @@ public: inline TCoord width() const BP2D_NOEXCEPT; inline TCoord height() const BP2D_NOEXCEPT; + + inline RawPoint center() const BP2D_NOEXCEPT; }; template @@ -102,8 +105,9 @@ public: inline Radians angleToXaxis() const; }; -class PointLike { -public: +// This struct serves as a namespace. The only difference is that is can be +// used in friend declarations. +struct PointLike { template static TCoord x(const RawPoint& p) @@ -133,7 +137,7 @@ public: static double distance(const RawPoint& /*p1*/, const RawPoint& /*p2*/) { static_assert(always_false::value, - "PointLike::distance(point, point) unimplemented"); + "PointLike::distance(point, point) unimplemented!"); return 0; } @@ -142,7 +146,7 @@ public: const _Segment& /*s*/) { static_assert(always_false::value, - "PointLike::distance(point, segment) unimplemented"); + "PointLike::distance(point, segment) unimplemented!"); return 0; } @@ -229,21 +233,38 @@ void setY(RawPoint& p, const TCoord& val) { template inline Radians _Segment::angleToXaxis() const { + static const double Pi_2 = 2*Pi; TCoord dx = getX(second()) - getX(first()); TCoord dy = getY(second()) - getY(first()); - if(dx == 0 && dy >= 0) return Pi/2; - if(dx == 0 && dy < 0) return 3*Pi/2; - if(dy == 0 && dx >= 0) return 0; - if(dy == 0 && dx < 0) return Pi; + double a = std::atan2(dy, dx); +// if(dx == 0 && dy >= 0) return Pi/2; +// if(dx == 0 && dy < 0) return 3*Pi/2; +// if(dy == 0 && dx >= 0) return 0; +// if(dy == 0 && dx < 0) return Pi; - double ddx = static_cast(dx); - auto s = std::signbit(ddx); - double a = std::atan(ddx/dy); - if(s) a += Pi; +// double ddx = static_cast(dx); + auto s = std::signbit(a); +// double a = std::atan(ddx/dy); + if(s) a += Pi_2; return a; } +template +inline RawPoint _Box::center() const BP2D_NOEXCEPT { + auto& minc = minCorner(); + auto& maxc = maxCorner(); + + using Coord = TCoord; + + RawPoint ret = { + static_cast( std::round((getX(minc) + getX(maxc))/2.0) ), + static_cast( std::round((getY(minc) + getY(maxc))/2.0) ) + }; + + return ret; +} + template struct HolesContainer { using Type = std::vector; @@ -258,7 +279,7 @@ struct CountourType { }; template -using TCountour = typename CountourType>::Type; +using TContour = typename CountourType>::Type; enum class Orientation { CLOCKWISE, @@ -277,12 +298,23 @@ enum class Formats { SVG }; +// This struct serves as a namespace. The only difference is that is can be +// used in friend declarations. struct ShapeLike { template - static RawShape create( std::initializer_list< TPoint > il) + using Shapes = std::vector; + + template + static RawShape create(const TContour& contour) + { + return RawShape(contour); + } + + template + static RawShape create(TContour&& contour) { - return RawShape(il); + return RawShape(contour); } // Optional, does nothing by default @@ -319,25 +351,6 @@ struct ShapeLike { return sh.cend(); } - template - static TPoint& vertex(RawShape& sh, unsigned long idx) - { - return *(begin(sh) + idx); - } - - template - static const TPoint& vertex(const RawShape& sh, - unsigned long idx) - { - return *(cbegin(sh) + idx); - } - - template - static size_t contourVertexCount(const RawShape& sh) - { - return cend(sh) - cbegin(sh); - } - template static std::string toString(const RawShape& /*sh*/) { @@ -345,10 +358,10 @@ struct ShapeLike { } template - static std::string serialize(const RawShape& /*sh*/) + static std::string serialize(const RawShape& /*sh*/, double scale=1) { static_assert(always_false::value, - "ShapeLike::serialize() unimplemented"); + "ShapeLike::serialize() unimplemented!"); return ""; } @@ -356,21 +369,14 @@ struct ShapeLike { static void unserialize(RawShape& /*sh*/, const std::string& /*str*/) { static_assert(always_false::value, - "ShapeLike::unserialize() unimplemented"); + "ShapeLike::unserialize() unimplemented!"); } template static double area(const RawShape& /*sh*/) { static_assert(always_false::value, - "ShapeLike::area() unimplemented"); - return 0; - } - - template - static double area(const _Box>& box) - { - return box.width() * box.height(); + "ShapeLike::area() unimplemented!"); return 0; } @@ -378,7 +384,7 @@ struct ShapeLike { static bool intersects(const RawShape& /*sh*/, const RawShape& /*sh*/) { static_assert(always_false::value, - "ShapeLike::intersects() unimplemented"); + "ShapeLike::intersects() unimplemented!"); return false; } @@ -387,7 +393,7 @@ struct ShapeLike { const RawShape& /*shape*/) { static_assert(always_false::value, - "ShapeLike::isInside(point, shape) unimplemented"); + "ShapeLike::isInside(point, shape) unimplemented!"); return false; } @@ -396,7 +402,7 @@ struct ShapeLike { const RawShape& /*shape*/) { static_assert(always_false::value, - "ShapeLike::isInside(shape, shape) unimplemented"); + "ShapeLike::isInside(shape, shape) unimplemented!"); return false; } @@ -405,7 +411,7 @@ struct ShapeLike { const RawShape& /*shape*/) { static_assert(always_false::value, - "ShapeLike::touches(shape, shape) unimplemented"); + "ShapeLike::touches(shape, shape) unimplemented!"); return false; } @@ -413,13 +419,30 @@ struct ShapeLike { static _Box> boundingBox(const RawShape& /*sh*/) { static_assert(always_false::value, - "ShapeLike::boundingBox(shape) unimplemented"); + "ShapeLike::boundingBox(shape) unimplemented!"); } template - static _Box> boundingBox(const _Box>& box) + static _Box> boundingBox(const Shapes& /*sh*/) { - return box; + static_assert(always_false::value, + "ShapeLike::boundingBox(shapes) unimplemented!"); + } + + template + static RawShape convexHull(const RawShape& /*sh*/) + { + static_assert(always_false::value, + "ShapeLike::convexHull(shape) unimplemented!"); + return RawShape(); + } + + template + static RawShape convexHull(const Shapes& /*sh*/) + { + static_assert(always_false::value, + "ShapeLike::convexHull(shapes) unimplemented!"); + return RawShape(); } template @@ -437,13 +460,13 @@ struct ShapeLike { } template - static TCountour& getHole(RawShape& sh, unsigned long idx) + static TContour& getHole(RawShape& sh, unsigned long idx) { return holes(sh)[idx]; } template - static const TCountour& getHole(const RawShape& sh, + static const TContour& getHole(const RawShape& sh, unsigned long idx) { return holes(sh)[idx]; @@ -456,13 +479,13 @@ struct ShapeLike { } template - static TCountour& getContour(RawShape& sh) + static TContour& getContour(RawShape& sh) { return sh; } template - static const TCountour& getContour(const RawShape& sh) + static const TContour& getContour(const RawShape& sh) { return sh; } @@ -471,14 +494,14 @@ struct ShapeLike { static void rotate(RawShape& /*sh*/, const Radians& /*rads*/) { static_assert(always_false::value, - "ShapeLike::rotate() unimplemented"); + "ShapeLike::rotate() unimplemented!"); } template static void translate(RawShape& /*sh*/, const RawPoint& /*offs*/) { static_assert(always_false::value, - "ShapeLike::translate() unimplemented"); + "ShapeLike::translate() unimplemented!"); } template @@ -490,11 +513,95 @@ struct ShapeLike { template static std::pair isValid(const RawShape& /*sh*/) { - return {false, "ShapeLike::isValid() unimplemented"}; + return {false, "ShapeLike::isValid() unimplemented!"}; } -}; + // ************************************************************************* + // No need to implement these + // ************************************************************************* + + template + static inline _Box> boundingBox( + const _Box>& box) + { + return box; + } + + template + static inline double area(const _Box>& box) + { + return static_cast(box.width() * box.height()); + } + + template + static double area(const Shapes& shapes) + { + double ret = 0; + std::accumulate(shapes.first(), shapes.end(), + [](const RawShape& a, const RawShape& b) { + return area(a) + area(b); + }); + return ret; + } + + template // Potential O(1) implementation may exist + static inline TPoint& vertex(RawShape& sh, unsigned long idx) + { + return *(begin(sh) + idx); + } + + template // Potential O(1) implementation may exist + static inline const TPoint& vertex(const RawShape& sh, + unsigned long idx) + { + return *(cbegin(sh) + idx); + } + + template + static inline size_t contourVertexCount(const RawShape& sh) + { + return cend(sh) - cbegin(sh); + } + + template + static inline void foreachContourVertex(RawShape& sh, Fn fn) { + for(auto it = begin(sh); it != end(sh); ++it) fn(*it); + } + template + static 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); + } + } + + template + static inline void foreachContourVertex(const RawShape& sh, Fn fn) { + for(auto it = cbegin(sh); it != cend(sh); ++it) fn(*it); + } + + template + static 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); + } + } + + template + static inline void foreachVertex(RawShape& sh, Fn fn) { + foreachContourVertex(sh, fn); + foreachHoleVertex(sh, fn); + } + + template + static inline void foreachVertex(const RawShape& sh, Fn fn) { + foreachContourVertex(sh, fn); + foreachHoleVertex(sh, fn); + } + +}; } diff --git a/xs/src/libnest2d/libnest2d/libnest2d.hpp b/xs/src/libnest2d/libnest2d/libnest2d.hpp index e57e49779..76df1829b 100644 --- a/xs/src/libnest2d/libnest2d/libnest2d.hpp +++ b/xs/src/libnest2d/libnest2d/libnest2d.hpp @@ -97,6 +97,12 @@ public: inline _Item(const std::initializer_list< Vertex >& il): sh_(ShapeLike::create(il)) {} + inline _Item(const TContour& contour): + sh_(ShapeLike::create(contour)) {} + + inline _Item(TContour&& contour): + sh_(ShapeLike::create(std::move(contour))) {} + /** * @brief Convert the polygon to string representation. The format depends * on the implementation of the polygon. @@ -174,7 +180,7 @@ public: double ret ; if(area_cache_valid_) ret = area_cache_; else { - ret = std::abs(ShapeLike::area(offsettedShape())); + ret = ShapeLike::area(offsettedShape()); area_cache_ = ret; area_cache_valid_ = true; } @@ -201,6 +207,8 @@ public: return ShapeLike::isInside(transformedShape(), sh.transformedShape()); } + inline bool isInside(const _Box>& box); + inline void translate(const Vertex& d) BP2D_NOEXCEPT { translation_ += d; has_translation_ = true; @@ -328,7 +336,7 @@ class _Rectangle: public _Item { using TO = Orientation; public: - using Unit = TCoord; + using Unit = TCoord>; template::Value> inline _Rectangle(Unit width, Unit height, @@ -367,6 +375,12 @@ public: } }; +template +inline bool _Item::isInside(const _Box>& box) { + _Rectangle rect(box.width(), box.height()); + return _Item::isInside(rect); +} + /** * \brief A wrapper interface (trait) class for any placement strategy provider. * @@ -481,8 +495,18 @@ public: /// Clear the packed items so a new session can be started. inline void clearItems() { impl_.clearItems(); } +#ifndef NDEBUG + inline auto getDebugItems() -> decltype(impl_.debug_items_)& + { + return impl_.debug_items_; + } +#endif + }; +// The progress function will be called with the number of placed items +using ProgressFunction = std::function; + /** * A wrapper interface (trait) class for any selections strategy provider. */ @@ -508,6 +532,14 @@ public: impl_.configure(config); } + /** + * @brief A function callback which should be called whenewer an item or + * a group of items where succesfully packed. + * @param fn A function callback object taking one unsigned integer as the + * number of the remaining items to pack. + */ + void progressIndicator(ProgressFunction fn) { impl_.progressIndicator(fn); } + /** * \brief A method to start the calculation on the input sequence. * @@ -614,7 +646,7 @@ public: private: BinType bin_; PlacementConfig pconfig_; - TCoord min_obj_distance_; + Unit min_obj_distance_; using SItem = typename SelectionStrategy::Item; using TPItem = remove_cvref_t; @@ -680,6 +712,21 @@ public: return _arrange(from, to); } + /// Set a progress indicatior function object for the selector. + inline void progressIndicator(ProgressFunction func) + { + selector_.progressIndicator(func); + } + + inline PackGroup lastResult() { + PackGroup ret; + for(size_t i = 0; i < selector_.binCount(); i++) { + auto items = selector_.itemsForBin(i); + ret.push_back(items); + } + return ret; + } + private: template inline void __arrange(TIter from, TIter to) { if(min_obj_distance_ > 0) std::for_each(from, to, [this](Item& item) { - item.addOffset(std::ceil(min_obj_distance_/2.0)); + item.addOffset(static_cast(std::ceil(min_obj_distance_/2.0))); }); selector_.template packItems( diff --git a/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp b/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp index b9d6741d0..f5701b904 100644 --- a/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp +++ b/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp @@ -2,29 +2,195 @@ #define NOFITPOLY_HPP #include "placer_boilerplate.hpp" +#include "../geometries_nfp.hpp" namespace libnest2d { namespace strategies { +template +struct NfpPConfig { + + enum class Alignment { + CENTER, + BOTTOM_LEFT, + BOTTOM_RIGHT, + TOP_LEFT, + TOP_RIGHT, + }; + + bool allow_rotations = false; + Alignment alignment; +}; + template class _NofitPolyPlacer: public PlacerBoilerplate<_NofitPolyPlacer, - RawShape, _Box>> { + RawShape, _Box>, NfpPConfig> { using Base = PlacerBoilerplate<_NofitPolyPlacer, - RawShape, _Box>>; + RawShape, _Box>, NfpPConfig>; DECLARE_PLACER(Base) + using Box = _Box>; + public: inline explicit _NofitPolyPlacer(const BinType& bin): Base(bin) {} PackResult trypack(Item& item) { - return PackResult(); + PackResult ret; + + bool can_pack = false; + + if(items_.empty()) { + setInitialPosition(item); + can_pack = item.isInside(bin_); + } else { + + // place the new item outside of the print bed to make sure it is + // disjuct from the current merged pile + placeOutsideOfBin(item); + + auto trsh = item.transformedShape(); + Nfp::Shapes nfps; + +#ifndef NDEBUG +#ifdef DEBUG_EXPORT_NFP + Base::debug_items_.clear(); +#endif + auto v = ShapeLike::isValid(trsh); + assert(v.first); +#endif + for(Item& sh : items_) { + auto subnfp = Nfp::noFitPolygon(sh.transformedShape(), + trsh); +#ifndef NDEBUG +#ifdef DEBUG_EXPORT_NFP + Base::debug_items_.emplace_back(subnfp); +#endif + auto vv = ShapeLike::isValid(sh.transformedShape()); + assert(vv.first); + + auto vnfp = ShapeLike::isValid(subnfp); + assert(vnfp.first); +#endif + nfps = Nfp::merge(nfps, subnfp); + } + + double min_area = std::numeric_limits::max(); + Vertex tr = {0, 0}; + + auto iv = Nfp::referenceVertex(trsh); + + // place item on each the edge of this nfp + for(auto& nfp : nfps) + ShapeLike::foreachContourVertex(nfp, [&] + (Vertex& v) + { + Coord dx = getX(v) - getX(iv); + Coord dy = getY(v) - getY(iv); + + Item placeditem(trsh); + placeditem.translate(Vertex(dx, dy)); + + if( placeditem.isInside(bin_) ) { + Nfp::Shapes m; + m.reserve(items_.size()); + + for(Item& pi : items_) + m.emplace_back(pi.transformedShape()); + + m.emplace_back(placeditem.transformedShape()); + +// auto b = ShapeLike::boundingBox(m); + +// auto a = static_cast(std::max(b.height(), +// b.width())); + + auto b = ShapeLike::convexHull(m); + auto a = ShapeLike::area(b); + + if(a < min_area) { + can_pack = true; + min_area = a; + tr = {dx, dy}; + } + } + }); + +#ifndef NDEBUG + for(auto&nfp : nfps) { + auto val = ShapeLike::isValid(nfp); + if(!val.first) std::cout << val.second << std::endl; +#ifdef DEBUG_EXPORT_NFP + Base::debug_items_.emplace_back(nfp); +#endif + } +#endif + + item.translate(tr); + } + + if(can_pack) { + ret = PackResult(item); + } + + return ret; + } + +private: + + void setInitialPosition(Item& item) { + Box&& bb = item.boundingBox(); + Vertex ci, cb; + + switch(config_.alignment) { + case Config::Alignment::CENTER: { + ci = bb.center(); + cb = bin_.center(); + break; + } + case Config::Alignment::BOTTOM_LEFT: { + ci = bb.minCorner(); + cb = bin_.minCorner(); + break; + } + case Config::Alignment::BOTTOM_RIGHT: { + ci = {getX(bb.maxCorner()), getY(bb.minCorner())}; + cb = {getX(bin_.maxCorner()), getY(bin_.minCorner())}; + break; + } + case Config::Alignment::TOP_LEFT: { + ci = {getX(bb.minCorner()), getY(bb.maxCorner())}; + cb = {getX(bin_.minCorner()), getY(bin_.maxCorner())}; + break; + } + case Config::Alignment::TOP_RIGHT: { + ci = bb.maxCorner(); + cb = bin_.maxCorner(); + break; + } + } + + auto d = cb - ci; + item.translate(d); + } + + void placeOutsideOfBin(Item& item) { + auto bb = item.boundingBox(); + Box binbb = ShapeLike::boundingBox(bin_); + + Vertex v = { getX(bb.maxCorner()), getY(bb.minCorner()) }; + + Coord dx = getX(binbb.maxCorner()) - getX(v); + Coord dy = getY(binbb.maxCorner()) - getY(v); + + item.translate({dx, dy}); } }; + } } diff --git a/xs/src/libnest2d/libnest2d/placers/placer_boilerplate.hpp b/xs/src/libnest2d/libnest2d/placers/placer_boilerplate.hpp index 1d82a5e66..338667432 100644 --- a/xs/src/libnest2d/libnest2d/placers/placer_boilerplate.hpp +++ b/xs/src/libnest2d/libnest2d/placers/placer_boilerplate.hpp @@ -67,16 +67,19 @@ public: void unpackLast() { items_.pop_back(); } - inline ItemGroup getItems() { return items_; } + inline ItemGroup getItems() const { return items_; } inline void clearItems() { items_.clear(); } +#ifndef NDEBUG + std::vector debug_items_; +#endif + protected: BinType bin_; Container items_; Cfg config_; - }; diff --git a/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp b/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp index 8ae77bbb3..305b3403a 100644 --- a/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp +++ b/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp @@ -84,9 +84,11 @@ public: bool try_reverse = config_.try_reverse_order; // Will use a subroutine to add a new bin - auto addBin = [&placers, &free_area, &filled_area, &bin, &pconfig]() + auto addBin = [this, &placers, &free_area, + &filled_area, &bin, &pconfig]() { placers.emplace_back(bin); + packed_bins_.emplace_back(); placers.back().configure(pconfig); free_area = ShapeLike::area(bin); filled_area = 0; @@ -457,6 +459,16 @@ public: } } + auto makeProgress = [this, ¬_packed](Placer& placer) { + packed_bins_.back() = placer.getItems(); +#ifndef NDEBUG + packed_bins_.back().insert(packed_bins_.back().end(), + placer.getDebugItems().begin(), + placer.getDebugItems().end()); +#endif + this->progress_(not_packed.size()); + }; + while(!not_packed.empty()) { auto& placer = placers.back(); @@ -472,30 +484,37 @@ public: free_area = bin_area - filled_area; auto itmp = it++; not_packed.erase(itmp); + makeProgress(placer); } else it++; } } // try pieses one by one - while(tryOneByOne(placer, waste)) + while(tryOneByOne(placer, waste)) { waste = 0; + makeProgress(placer); + } // try groups of 2 pieses - while(tryGroupsOfTwo(placer, waste)) + while(tryGroupsOfTwo(placer, waste)) { waste = 0; + makeProgress(placer); + } // try groups of 3 pieses - while(tryGroupsOfThree(placer, waste)) + while(tryGroupsOfThree(placer, waste)) { waste = 0; + makeProgress(placer); + } if(waste < free_area) waste += w; else if(!not_packed.empty()) addBin(); } - std::for_each(placers.begin(), placers.end(), - [this](Placer& placer){ - packed_bins_.push_back(placer.getItems()); - }); +// std::for_each(placers.begin(), placers.end(), +// [this](Placer& placer){ +// packed_bins_.push_back(placer.getItems()); +// }); } }; diff --git a/xs/src/libnest2d/libnest2d/selections/selection_boilerplate.hpp b/xs/src/libnest2d/libnest2d/selections/selection_boilerplate.hpp index 8af489a30..59ef5cb23 100644 --- a/xs/src/libnest2d/libnest2d/selections/selection_boilerplate.hpp +++ b/xs/src/libnest2d/libnest2d/selections/selection_boilerplate.hpp @@ -26,8 +26,14 @@ public: return packed_bins_[binIndex]; } + inline void progressIndicator(ProgressFunction fn) { + progress_ = fn; + } + protected: + PackGroup packed_bins_; + ProgressFunction progress_ = [](unsigned){}; }; } diff --git a/xs/src/libnest2d/tests/CMakeLists.txt b/xs/src/libnest2d/tests/CMakeLists.txt index bfe32bfeb..3af5e6f70 100644 --- a/xs/src/libnest2d/tests/CMakeLists.txt +++ b/xs/src/libnest2d/tests/CMakeLists.txt @@ -1,10 +1,11 @@ # Try to find existing GTest installation -find_package(GTest QUIET) +find_package(GTest 1.7) if(NOT GTEST_FOUND) + message(STATUS "GTest not found so downloading...") # Go and download google test framework, integrate it with the build - set(GTEST_LIBRARIES gtest gmock) + set(GTEST_LIBS_TO_LINK gtest gtest_main) if (CMAKE_VERSION VERSION_LESS 3.2) set(UPDATE_DISCONNECTED_IF_AVAILABLE "") @@ -15,7 +16,7 @@ if(NOT GTEST_FOUND) include(DownloadProject) download_project(PROJ googletest GIT_REPOSITORY https://github.com/google/googletest.git - GIT_TAG release-1.8.0 + GIT_TAG release-1.7.0 ${UPDATE_DISCONNECTED_IF_AVAILABLE} ) @@ -27,22 +28,20 @@ if(NOT GTEST_FOUND) ${googletest_BINARY_DIR} ) + set(GTEST_INCLUDE_DIRS ${googletest_SOURCE_DIR}/include) + else() - include_directories(${GTEST_INCLUDE_DIRS} ) + find_package(Threads REQUIRED) + set(GTEST_LIBS_TO_LINK ${GTEST_BOTH_LIBRARIES} Threads::Threads) endif() -include_directories(BEFORE ${LIBNEST2D_HEADERS}) -add_executable(bp2d_tests test.cpp printer_parts.h printer_parts.cpp) -target_link_libraries(bp2d_tests libnest2d - ${GTEST_LIBRARIES} -) +add_executable(bp2d_tests test.cpp svgtools.hpp printer_parts.h printer_parts.cpp) +target_link_libraries(bp2d_tests libnest2d_static ${GTEST_LIBS_TO_LINK} ) +target_include_directories(bp2d_tests PRIVATE BEFORE ${LIBNEST2D_HEADERS} + ${GTEST_INCLUDE_DIRS}) if(DEFINED LIBNEST2D_TEST_LIBRARIES) target_link_libraries(bp2d_tests ${LIBNEST2D_TEST_LIBRARIES}) endif() -add_test(gtests bp2d_tests) - -add_executable(main EXCLUDE_FROM_ALL main.cpp printer_parts.cpp printer_parts.h) -target_link_libraries(main libnest2d) -target_include_directories(main PUBLIC ${CMAKE_SOURCE_DIR}) +add_test(libnest2d_tests bp2d_tests) diff --git a/xs/src/libnest2d/tests/main.cpp b/xs/src/libnest2d/tests/main.cpp index 3d5baca76..633fe0c97 100644 --- a/xs/src/libnest2d/tests/main.cpp +++ b/xs/src/libnest2d/tests/main.cpp @@ -7,232 +7,56 @@ #include "printer_parts.h" #include "benchmark.h" +#include "svgtools.hpp" -namespace { using namespace libnest2d; using ItemGroup = std::vector>; -//using PackGroup = std::vector; -template -void exportSVG(PackGroup& result, const Bin& bin) { - - std::string loc = "out"; - - static std::string svg_header = -R"raw( - - -)raw"; - - int i = 0; - for(auto r : result) { - std::fstream out(loc + std::to_string(i) + ".svg", std::fstream::out); - if(out.is_open()) { - out << svg_header; - Item rbin( Rectangle(bin.width(), bin.height()) ); - for(unsigned i = 0; i < rbin.vertexCount(); i++) { - auto v = rbin.vertex(i); - setY(v, -getY(v)/SCALE + 500 ); - setX(v, getX(v)/SCALE); - rbin.setVertex(i, v); - } - out << ShapeLike::serialize(rbin.rawShape()) << std::endl; - for(Item& sh : r) { - Item tsh(sh.transformedShape()); - for(unsigned i = 0; i < tsh.vertexCount(); i++) { - auto v = tsh.vertex(i); - setY(v, -getY(v)/SCALE + 500); - setX(v, getX(v)/SCALE); - tsh.setVertex(i, v); - } - out << ShapeLike::serialize(tsh.rawShape()) << std::endl; - } - out << "\n" << std::endl; - } - out.close(); - - i++; +std::vector& _parts(std::vector& ret, const TestData& data) +{ + if(ret.empty()) { + ret.reserve(data.size()); + for(auto& inp : data) + ret.emplace_back(inp); } -} - -template< int SCALE, class Bin> -void exportSVG(ItemGroup& result, const Bin& bin, int idx) { - - std::string loc = "out"; - static std::string svg_header = -R"raw( - - -)raw"; - - int i = idx; - auto r = result; -// for(auto r : result) { - std::fstream out(loc + std::to_string(i) + ".svg", std::fstream::out); - if(out.is_open()) { - out << svg_header; - Item rbin( Rectangle(bin.width(), bin.height()) ); - for(unsigned i = 0; i < rbin.vertexCount(); i++) { - auto v = rbin.vertex(i); - setY(v, -getY(v)/SCALE + 500 ); - setX(v, getX(v)/SCALE); - rbin.setVertex(i, v); - } - out << ShapeLike::serialize(rbin.rawShape()) << std::endl; - for(Item& sh : r) { - Item tsh(sh.transformedShape()); - for(unsigned i = 0; i < tsh.vertexCount(); i++) { - auto v = tsh.vertex(i); - setY(v, -getY(v)/SCALE + 500); - setX(v, getX(v)/SCALE); - tsh.setVertex(i, v); - } - out << ShapeLike::serialize(tsh.rawShape()) << std::endl; - } - out << "\n" << std::endl; - } - out.close(); - -// i++; -// } + return ret; } -} - - -void findDegenerateCase() { - using namespace libnest2d; - - auto input = PRINTER_PART_POLYGONS; - - auto scaler = [](Item& item) { - for(unsigned i = 0; i < item.vertexCount(); i++) { - auto v = item.vertex(i); - setX(v, 100*getX(v)); setY(v, 100*getY(v)); - item.setVertex(i, v); - } - }; - - auto cmp = [](const Item& t1, const Item& t2) { - return t1.area() > t2.area(); - }; - - std::for_each(input.begin(), input.end(), scaler); - - std::sort(input.begin(), input.end(), cmp); - - Box bin(210*100, 250*100); - BottomLeftPlacer placer(bin); - - auto it = input.begin(); - auto next = it; - int i = 0; - while(it != input.end() && ++next != input.end()) { - placer.pack(*it); - placer.pack(*next); - - auto result = placer.getItems(); - bool valid = true; - - if(result.size() == 2) { - Item& r1 = result[0]; - Item& r2 = result[1]; - valid = !Item::intersects(r1, r2) || Item::touches(r1, r2); - valid = (valid && !r1.isInside(r2) && !r2.isInside(r1)); - if(!valid) { - std::cout << "error index: " << i << std::endl; - exportSVG<100>(result, bin, i); - } - } else { - std::cout << "something went terribly wrong!" << std::endl; - } +std::vector& prusaParts() { + static std::vector ret; + return _parts(ret, PRINTER_PART_POLYGONS); +} - placer.clearItems(); - it++; - i++; - } +std::vector& stegoParts() { + static std::vector ret; + return _parts(ret, STEGOSAUR_POLYGONS); } void arrangeRectangles() { using namespace libnest2d; - -// std::vector input = { -// {80, 80}, -// {110, 10}, -// {200, 5}, -// {80, 30}, -// {60, 90}, -// {70, 30}, -// {80, 60}, -// {60, 60}, -// {60, 40}, -// {40, 40}, -// {10, 10}, -// {10, 10}, -// {10, 10}, -// {10, 10}, -// {10, 10}, -// {5, 5}, -// {5, 5}, -// {5, 5}, -// {5, 5}, -// {5, 5}, -// {5, 5}, -// {5, 5}, -// {20, 20}, -// {80, 80}, -// {110, 10}, -// {200, 5}, -// {80, 30}, -// {60, 90}, -// {70, 30}, -// {80, 60}, -// {60, 60}, -// {60, 40}, -// {40, 40}, -// {10, 10}, -// {10, 10}, -// {10, 10}, -// {10, 10}, -// {10, 10}, -// {5, 5}, -// {5, 5}, -// {5, 5}, -// {5, 5}, -// {5, 5}, -// {5, 5}, -// {5, 5}, -// {20, 20} -// }; - - auto input = PRINTER_PART_POLYGONS; + auto input = stegoParts(); const int SCALE = 1000000; -// const int SCALE = 1; Box bin(210*SCALE, 250*SCALE); - auto scaler = [&SCALE, &bin](Item& item) { -// double max_area = 0; - for(unsigned i = 0; i < item.vertexCount(); i++) { - auto v = item.vertex(i); - setX(v, SCALE*getX(v)); setY(v, SCALE*getY(v)); - item.setVertex(i, v); -// double area = item.area(); -// if(max_area < area) { -// max_area = area; -// bin = item.boundingBox(); -// } - } - }; - - Coord min_obj_distance = 2*SCALE; + Coord min_obj_distance = 0; //6*SCALE; - std::for_each(input.begin(), input.end(), scaler); + NfpPlacer::Config pconf; + pconf.alignment = NfpPlacer::Config::Alignment::TOP_LEFT; + Arranger arrange(bin, min_obj_distance, pconf); - Arranger arrange(bin, min_obj_distance); +// arrange.progressIndicator([&arrange, &bin](unsigned r){ +// svg::SVGWriter::Config conf; +// conf.mm_in_coord_units = SCALE; +// svg::SVGWriter svgw(conf); +// svgw.setSize(bin); +// svgw.writePackGroup(arrange.lastResult()); +// svgw.save("out"); +// std::cout << "Remaining items: " << r << std::endl; +// }); Benchmark bench; @@ -249,8 +73,12 @@ void arrangeRectangles() { std::cout << ret.second << std::endl; } - exportSVG(result, bin); - + svg::SVGWriter::Config conf; + conf.mm_in_coord_units = SCALE; + svg::SVGWriter svgw(conf); + svgw.setSize(bin); + svgw.writePackGroup(result); + svgw.save("out"); } int main(void /*int argc, char **argv*/) { diff --git a/xs/src/libnest2d/tests/printer_parts.cpp b/xs/src/libnest2d/tests/printer_parts.cpp index 02ea6bb7f..13bc627ad 100644 --- a/xs/src/libnest2d/tests/printer_parts.cpp +++ b/xs/src/libnest2d/tests/printer_parts.cpp @@ -1,339 +1,2527 @@ #include "printer_parts.h" -const std::vector PRINTER_PART_POLYGONS = { +const TestData PRINTER_PART_POLYGONS = { - {120, 114}, - {130, 114}, - {130, 103}, - {128, 96}, - {122, 96}, - {120, 103}, - {120, 114} -}, -{ - {61, 97}, - {70, 151}, - {176, 151}, - {189, 138}, - {189, 59}, - {70, 59}, - {61, 77}, - {61, 97} -}, -{ - {72, 147}, - {94, 151}, - {178, 151}, - {178, 59}, - {72, 59}, - {72, 147} -}, -{ - {121, 119}, - {123, 119}, - {129, 109}, - {129, 107}, - {128, 100}, - {127, 98}, - {123, 91}, - {121, 91}, - {121, 119}, -}, -{ - {93, 104}, - {100, 146}, - {107, 152}, - {136, 152}, - {142, 146}, - {157, 68}, - {157, 61}, - {154, 58}, - {104, 58}, - {93, 101}, - {93, 104}, -}, -{ - {90, 91}, - {114, 130}, - {158, 130}, - {163, 126}, - {163, 123}, - {152, 80}, - {116, 80}, - {90, 81}, - {87, 86}, - {90, 91}, -}, -{ - {111, 114}, - {114, 122}, - {139, 122}, - {139, 88}, - {114, 88}, - {111, 97}, - {111, 114}, -}, -{ - {120, 107}, - {125, 110}, - {130, 110}, - {130, 100}, - {120, 100}, - {120, 107}, -}, -{ - {113, 123}, - {137, 123}, - {137, 87}, - {113, 87}, - {113, 123}, -}, -{ - {107, 104}, - {110, 127}, - {114, 131}, - {136, 131}, - {140, 127}, - {143, 104}, - {143, 79}, - {107, 79}, - {107, 104}, -}, -{ - {48, 135}, - {50, 138}, - {52, 140}, - {198, 140}, - {202, 135}, - {202, 72}, - {200, 70}, - {50, 70}, - {48, 72}, - {48, 135}, -}, -{ - {115, 104}, - {116, 106}, - {123, 119}, - {127, 119}, - {134, 106}, - {135, 104}, - {135, 98}, - {134, 96}, - {132, 93}, - {128, 91}, - {122, 91}, - {118, 93}, - {116, 96}, - {115, 98}, - {115, 104}, -}, -{ - {91, 100}, - {94, 144}, - {117, 153}, - {118, 153}, - {159, 112}, - {159, 110}, - {156, 66}, - {133, 57}, - {132, 57}, - {91, 98}, - {91, 100}, -}, -{ - {101, 90}, - {103, 98}, - {107, 113}, - {114, 125}, - {115, 126}, - {135, 126}, - {136, 125}, - {144, 114}, - {149, 90}, - {149, 89}, - {148, 87}, - {145, 84}, - {105, 84}, - {102, 87}, - {101, 89}, - {101, 90}, -}, -{ - {93, 116}, - {94, 118}, - {141, 121}, - {151, 121}, - {156, 118}, - {157, 116}, - {157, 91}, - {156, 89}, - {94, 89}, - {93, 91}, - {93, 116}, -}, -{ - {89, 60}, - {91, 66}, - {134, 185}, - {139, 198}, - {140, 200}, - {141, 201}, - {159, 201}, - {161, 199}, - {161, 195}, - {157, 179}, - {114, 26}, - {110, 12}, - {108, 10}, - {106, 9}, - {92, 9}, - {89, 50}, - {89, 60}, -}, -{ - {99, 130}, - {101, 133}, - {118, 150}, - {142, 150}, - {145, 148}, - {151, 142}, - {151, 80}, - {142, 62}, - {139, 60}, - {111, 60}, - {108, 62}, - {102, 80}, - {99, 95}, - {99, 130}, -}, -{ - {99, 122}, - {108, 140}, - {110, 142}, - {139, 142}, - {151, 122}, - {151, 102}, - {142, 70}, - {139, 68}, - {111, 68}, - {108, 70}, - {99, 102}, - {99, 122}, -}, -{ - {107, 124}, - {128, 125}, - {133, 125}, - {136, 124}, - {140, 121}, - {142, 119}, - {143, 116}, - {143, 109}, - {141, 93}, - {139, 89}, - {136, 86}, - {134, 85}, - {108, 85}, - {107, 86}, - {107, 124}, -}, -{ - {107, 146}, - {124, 146}, - {141, 96}, - {143, 79}, - {143, 73}, - {142, 70}, - {140, 68}, - {136, 65}, - {134, 64}, - {127, 64}, - {107, 65}, - {107, 146}, -}, -{ - {113, 118}, - {115, 120}, - {129, 129}, - {137, 129}, - {137, 81}, - {129, 81}, - {115, 90}, - {113, 92}, - {113, 118}, -}, -{ - {112, 122}, - {138, 122}, - {138, 88}, - {112, 88}, - {112, 122}, -}, -{ - {102, 116}, - {111, 126}, - {114, 126}, - {144, 106}, - {148, 100}, - {148, 85}, - {147, 84}, - {102, 84}, - {102, 116}, -}, -{ - {112, 110}, - {121, 112}, - {129, 112}, - {138, 110}, - {138, 106}, - {134, 98}, - {117, 98}, - {114, 102}, - {112, 106}, - {112, 110}, -}, -{ - {100, 156}, - {102, 158}, - {104, 159}, - {143, 159}, - {150, 152}, - {150, 58}, - {143, 51}, - {104, 51}, - {102, 52}, - {100, 54}, - {100, 156} -}, -{ - {106, 151}, - {108, 151}, - {139, 139}, - {144, 134}, - {144, 76}, - {139, 71}, - {108, 59}, - {106, 59}, - {106, 151} -}, + { + {120000000, 113954048}, + {130000000, 113954048}, + {130000000, 104954048}, + {129972610, 104431449}, + {128500000, 96045951}, + {121500000, 96045951}, + {120027389, 104431449}, + {120000000, 104954048}, + {120000000, 113954048}, + }, + { + {61250000, 97000000}, + {70250000, 151000000}, + {175750000, 151000000}, + {188750000, 138000000}, + {188750000, 59000000}, + {70250000, 59000000}, + {61250000, 77000000}, + {61250000, 97000000}, + }, + { + {72250000, 146512344}, + {93750000, 150987655}, + {177750000, 150987655}, + {177750000, 59012348}, + {72250000, 59012348}, + {72250000, 146512344}, + }, + { + {121099998, 119000000}, + {122832046, 119000000}, + {126016967, 113483596}, + {126721450, 112263397}, + {128828536, 108613792}, + {128838806, 108582153}, + {128871566, 108270568}, + {128899993, 108000000}, + {128500000, 102000000}, + {128447555, 101501014}, + {128292510, 101023834}, + {128100006, 100487052}, + {126030128, 96901916}, + {122622650, 91000000}, + {121099998, 91000000}, + {121099998, 119000000}, + }, + { + {93250000, 104000000}, + {99750000, 145500000}, + {106750000, 152500000}, + {135750000, 152500000}, + {141750000, 146500000}, + {156750000, 68000000}, + {156750000, 61142101}, + {156659606, 61051700}, + {153107894, 57500000}, + {143392105, 57500000}, + {104250000, 58500000}, + {93250000, 101000000}, + {93250000, 104000000}, + }, + { + {90375000, 90734603}, + {114074996, 129875000}, + {158324996, 129875000}, + {162574996, 125625000}, + {162574996, 122625000}, + {151574996, 80125000}, + {116074996, 80125000}, + {90375000, 80515396}, + {87425003, 85625000}, + {90375000, 90734603}, + }, + { + {111000000, 114000000}, + {114000000, 122000000}, + {139000000, 122000000}, + {139000000, 88000000}, + {114000000, 88000000}, + {111000000, 97000000}, + {111000000, 114000000}, + }, + { + {119699996, 107227401}, + {124762199, 110150001}, + {130300003, 110150001}, + {130300003, 105650001}, + {129699996, 99850006}, + {119699996, 99850006}, + {119699996, 107227401}, + }, + { + {113000000, 123000000}, + {137000000, 123000000}, + {137000000, 87000000}, + {113000000, 87000000}, + {113000000, 123000000}, + }, + { + {107000000, 104000000}, + {110000000, 127000000}, + {114000000, 131000000}, + {136000000, 131000000}, + {140000000, 127000000}, + {143000000, 104000000}, + {143000000, 79000000}, + {107000000, 79000000}, + {107000000, 104000000}, + }, + { + {47500000, 135000000}, + {52500000, 140000000}, + {197500000, 140000000}, + {202500000, 135000000}, + {202500000, 72071098}, + {200428894, 70000000}, + {49571098, 70000000}, + {48570396, 71000701}, + {47500000, 72071098}, + {47500000, 135000000}, + }, + { + {115054779, 101934379}, + {115218521, 102968223}, + {115489440, 103979270}, + {115864547, 104956466}, + {122900001, 119110900}, + {127099998, 119110900}, + {134135452, 104956466}, + {134510559, 103979270}, + {134781478, 102968223}, + {134945220, 101934379}, + {135000000, 100889099}, + {134945220, 99843818}, + {134781478, 98809982}, + {134510559, 97798927}, + {134135452, 96821731}, + {133660247, 95889099}, + {133090164, 95011245}, + {132431457, 94197792}, + {131691314, 93457649}, + {130877853, 92798927}, + {130000000, 92228851}, + {129067367, 91753646}, + {128090164, 91378540}, + {127079116, 91107620}, + {126045280, 90943878}, + {125000000, 90889099}, + {123954719, 90943878}, + {122920883, 91107620}, + {121909828, 91378540}, + {120932632, 91753646}, + {120000000, 92228851}, + {119122146, 92798927}, + {118308692, 93457649}, + {117568550, 94197792}, + {116909828, 95011245}, + {116339752, 95889099}, + {115864547, 96821731}, + {115489440, 97798927}, + {115218521, 98809982}, + {115054779, 99843818}, + {115000000, 100889099}, + {115054779, 101934379}, + }, + { + {90807601, 99807609}, + {93500000, 144000000}, + {116816207, 152669006}, + {118230407, 152669006}, + {120351806, 150547698}, + {159192398, 111707107}, + {159192398, 110192390}, + {156500000, 66000000}, + {133183807, 57331001}, + {131769607, 57331001}, + {129648208, 59452301}, + {92525100, 96575378}, + {90807601, 98292892}, + {90807601, 99807609}, + }, + { + {101524497, 93089904}, + {107000000, 113217697}, + {113860298, 125099998}, + {114728599, 125900001}, + {134532012, 125900001}, + {136199996, 125099998}, + {143500000, 113599998}, + {148475494, 93089904}, + {148800003, 90099998}, + {148706604, 89211097}, + {148668899, 88852500}, + {148281295, 87659599}, + {147654098, 86573303}, + {146814804, 85641098}, + {145800003, 84903800}, + {144654098, 84393699}, + {143427200, 84132904}, + {142800003, 84099998}, + {107199996, 84099998}, + {106572799, 84132904}, + {105345901, 84393699}, + {104199996, 84903800}, + {103185195, 85641098}, + {102345901, 86573303}, + {101718704, 87659599}, + {101331100, 88852500}, + {101199996, 90099998}, + {101524497, 93089904}, + }, + { + {93000000, 115000000}, + {93065559, 115623733}, + {93259361, 116220207}, + {93572952, 116763359}, + {93992614, 117229431}, + {94500000, 117598083}, + {95072952, 117853172}, + {95686416, 117983566}, + {141000000, 121000000}, + {151000000, 121000000}, + {156007400, 117229431}, + {156427093, 116763359}, + {156740600, 116220207}, + {156934402, 115623733}, + {157000000, 115000000}, + {157000000, 92000000}, + {156934402, 91376296}, + {156740600, 90779800}, + {156427093, 90236602}, + {156007400, 89770599}, + {155500000, 89401901}, + {154927093, 89146797}, + {154313598, 89016403}, + {154000000, 89000000}, + {97000000, 89000000}, + {95686416, 89016403}, + {95072952, 89146797}, + {94500000, 89401901}, + {93992614, 89770599}, + {93572952, 90236602}, + {93259361, 90779800}, + {93065559, 91376296}, + {93000000, 92000000}, + {93000000, 115000000}, + }, + { + {88866210, 58568977}, + {88959899, 58828182}, + {89147277, 59346588}, + {127200073, 164616485}, + {137112792, 192039184}, + {139274505, 198019332}, + {139382049, 198291641}, + {139508483, 198563430}, + {139573425, 198688369}, + {139654052, 198832443}, + {139818634, 199096328}, + {139982757, 199327621}, + {140001708, 199352630}, + {140202392, 199598999}, + {140419342, 199833160}, + {140497497, 199910552}, + {140650848, 200053039}, + {140894866, 200256866}, + {141104309, 200412185}, + {141149047, 200443206}, + {141410888, 200611038}, + {141677795, 200759750}, + {141782348, 200812332}, + {141947143, 200889144}, + {142216400, 200999465}, + {142483123, 201091293}, + {142505554, 201098251}, + {142745178, 201165542}, + {143000671, 201223373}, + {143245880, 201265884}, + {143484039, 201295257}, + {143976715, 201319580}, + {156135131, 201319580}, + {156697082, 201287902}, + {156746368, 201282104}, + {157263000, 201190719}, + {157338623, 201172576}, + {157821411, 201026641}, + {157906188, 200995391}, + {158360565, 200797012}, + {158443420, 200754882}, + {158869171, 200505874}, + {158900756, 200485122}, + {159136413, 200318618}, + {159337127, 200159790}, + {159377288, 200125930}, + {159619628, 199905410}, + {159756286, 199767364}, + {159859008, 199656143}, + {160090606, 199378067}, + {160120849, 199338546}, + {160309295, 199072113}, + {160434875, 198871475}, + {160510070, 198740310}, + {160688232, 198385772}, + {160699096, 198361679}, + {160839782, 198012557}, + {160905487, 197817459}, + {160961578, 197625488}, + {161048004, 197249023}, + {161051574, 197229934}, + {161108856, 196831405}, + {161122985, 196667816}, + {161133789, 196435317}, + {161129669, 196085830}, + {161127685, 196046661}, + {161092742, 195669830}, + {161069946, 195514739}, + {161031829, 195308425}, + {160948211, 194965225}, + {159482635, 189756820}, + {152911407, 166403976}, + {145631286, 140531890}, + {119127441, 46342559}, + {110756378, 16593490}, + {110423187, 15409400}, + {109578002, 12405799}, + {109342315, 11568267}, + {108961059, 11279479}, + {108579803, 10990692}, + {107817291, 10413124}, + {106165161, 9161727}, + {105529724, 8680419}, + {103631866, 8680419}, + {102236145, 8680465}, + {95257537, 8680725}, + {92466064, 8680831}, + {88866210, 50380981}, + {88866210, 58568977}, + }, + { + {99000000, 130500000}, + {101070701, 132570709}, + {118500000, 150000000}, + {142500000, 150000000}, + {151000000, 141500000}, + {151000000, 86000000}, + {150949996, 80500000}, + {142000000, 62785301}, + {139300003, 60000000}, + {110699996, 60000000}, + {107500000, 63285301}, + {101599998, 80500000}, + {99000000, 94535995}, + {99000000, 130500000}, + }, + { + {99000000, 121636100}, + {99927795, 123777801}, + {108500000, 140300003}, + {109949996, 141750000}, + {138550003, 141750000}, + {140000000, 140300003}, + {151000000, 121045196}, + {151000000, 102250000}, + {141500000, 70492095}, + {139257904, 68250000}, + {110742095, 68250000}, + {108500000, 70492095}, + {99000000, 102250000}, + {99000000, 121636100}, + }, + { + {106937652, 123950103}, + {129644943, 125049896}, + {131230361, 125049896}, + {132803283, 124851196}, + {134338897, 124456901}, + {135812988, 123873298}, + {137202316, 123109497}, + {138484954, 122177597}, + {139640670, 121092300}, + {140651245, 119870697}, + {141500747, 118532104}, + {142175842, 117097595}, + {142665756, 115589698}, + {142962844, 114032402}, + {143062347, 112450103}, + {142962844, 110867797}, + {140810745, 93992263}, + {140683746, 93272232}, + {140506851, 92562797}, + {140280929, 91867439}, + {140007034, 91189529}, + {139686523, 90532394}, + {139320953, 89899200}, + {138912094, 89293052}, + {138461959, 88716903}, + {137972732, 88173553}, + {137446792, 87665664}, + {136886703, 87195693}, + {136295196, 86765930}, + {135675155, 86378479}, + {135029586, 86035232}, + {134361648, 85737854}, + {133674606, 85487777}, + {132971786, 85286300}, + {132256607, 85134201}, + {131532592, 85032501}, + {130803222, 84981498}, + {130437652, 84975097}, + {123937652, 84950103}, + {108437652, 84950103}, + {106937652, 86450103}, + {106937652, 123950103}, + }, + { + {106937652, 146299896}, + {123937652, 146299896}, + {140280929, 96882560}, + {140506851, 96187202}, + {140683746, 95477767}, + {140810745, 94757736}, + {142962844, 77882202}, + {143062347, 76299896}, + {142962844, 74717597}, + {142665756, 73160301}, + {142175842, 71652404}, + {141500747, 70217895}, + {140651245, 68879302}, + {139640670, 67657699}, + {138484954, 66572402}, + {137202316, 65640502}, + {135812988, 64876701}, + {134338897, 64293098}, + {132803283, 63898799}, + {131230361, 63700099}, + {129644943, 63700099}, + {106937652, 64799896}, + {106937652, 146299896}, + }, + { + {113250000, 118057899}, + {115192138, 120000000}, + {129392135, 129000000}, + {136750000, 129000000}, + {136750000, 81000000}, + {129392135, 81000000}, + {115192138, 90000000}, + {113250000, 91942100}, + {113250000, 118057899}, + }, + { + {112500000, 122500000}, + {137500000, 122500000}, + {137500000, 87500000}, + {112500000, 87500000}, + {112500000, 122500000}, + }, + { + {101500000, 116500000}, + {111142143, 126000000}, + {114000000, 126000000}, + {143500000, 105500000}, + {148500000, 100500000}, + {148500000, 85500000}, + {147000000, 84000000}, + {101500000, 84000000}, + {101500000, 116500000}, + }, + { + {112000000, 110250000}, + {121000000, 111750000}, + {129000000, 111750000}, + {138000000, 110250000}, + {138000000, 105838462}, + {136376296, 103026062}, + {135350906, 101250000}, + {133618804, 98250000}, + {116501708, 98250000}, + {112000000, 106047180}, + {112000000, 110250000}, + }, + { + {100000000, 155500000}, + {103500000, 159000000}, + {143286804, 159000000}, + {150000000, 152286804}, + {150000000, 57713199}, + {143397705, 51110900}, + {143286804, 51000000}, + {103500000, 51000000}, + {100000000, 54500000}, + {100000000, 155500000}, + }, + { + {106000000, 151000000}, + {108199996, 151000000}, + {139000000, 139000000}, + {144000000, 134000000}, + {144000000, 76000000}, + {139000000, 71000000}, + {108199996, 59000000}, + {106000000, 59000000}, + {106000000, 151000000}, + }, + { + {117043830, 105836227}, + {117174819, 106663291}, + {117232467, 106914527}, + {117391548, 107472137}, + {117691642, 108253890}, + {117916351, 108717781}, + {118071800, 109000000}, + {118527862, 109702278}, + {119011909, 110304977}, + {119054840, 110353042}, + {119646957, 110945159}, + {120297721, 111472137}, + {120455482, 111583869}, + {121000000, 111928199}, + {121746109, 112308357}, + {122163162, 112480133}, + {122527862, 112608451}, + {123336708, 112825180}, + {124035705, 112941673}, + {124163772, 112956169}, + {125000000, 113000000}, + {125836227, 112956169}, + {125964294, 112941673}, + {126663291, 112825180}, + {127472137, 112608451}, + {127836837, 112480133}, + {128253890, 112308357}, + {129000000, 111928199}, + {129544525, 111583869}, + {129702285, 111472137}, + {130353042, 110945159}, + {130945159, 110353042}, + {130988082, 110304977}, + {131472137, 109702278}, + {131928192, 109000000}, + {132083648, 108717781}, + {132308364, 108253890}, + {132608444, 107472137}, + {132767532, 106914527}, + {132825180, 106663291}, + {132956176, 105836227}, + {133000000, 105000000}, + {132956176, 104163772}, + {132825180, 103336708}, + {132767532, 103085472}, + {132608444, 102527862}, + {132308364, 101746109}, + {132083648, 101282218}, + {131928192, 101000000}, + {131472137, 100297721}, + {130988082, 99695022}, + {130945159, 99646957}, + {130353042, 99054840}, + {129702285, 98527862}, + {129544525, 98416130}, + {129000000, 98071800}, + {128253890, 97691642}, + {127836837, 97519866}, + {127472137, 97391548}, + {126663291, 97174819}, + {125964294, 97058326}, + {125836227, 97043830}, + {125000000, 97000000}, + {124163772, 97043830}, + {124035705, 97058326}, + {123336708, 97174819}, + {122527862, 97391548}, + {122163162, 97519866}, + {121746109, 97691642}, + {121000000, 98071800}, + {120455482, 98416130}, + {120297721, 98527862}, + {119646957, 99054840}, + {119054840, 99646957}, + {119011909, 99695022}, + {118527862, 100297721}, + {118071800, 101000000}, + {117916351, 101282218}, + {117691642, 101746109}, + {117391548, 102527862}, + {117232467, 103085472}, + {117174819, 103336708}, + {117043830, 104163772}, + {117000000, 105000000}, + {117043830, 105836227}, + }, +}; + +const TestData STEGOSAUR_POLYGONS = { - {117, 107}, - {118, 109}, - {120, 112}, - {122, 113}, - {128, 113}, - {130, 112}, - {132, 109}, - {133, 107}, - {133, 103}, - {132, 101}, - {130, 98}, - {128, 97}, - {122, 97}, - {120, 98}, - {118, 101}, - {117, 103}, - {117, 107} -} + { + {113210205, 107034095}, + {113561798, 109153793}, + {113750099, 109914001}, + {114396499, 111040199}, + {114599197, 111321998}, + {115570404, 112657096}, + {116920097, 114166595}, + {117630599, 114609390}, + {119703704, 115583900}, + {120559494, 115811996}, + {121045410, 115754493}, + {122698097, 115526496}, + {123373001, 115370193}, + {123482406, 115315689}, + {125664199, 114129798}, + {125920303, 113968193}, + {128551208, 111866195}, + {129075592, 111443199}, + {135044692, 106572608}, + {135254898, 106347694}, + {135415100, 106102897}, + {136121704, 103779891}, + {136325103, 103086303}, + {136690093, 101284896}, + {136798309, 97568496}, + {136798309, 97470397}, + {136787399, 97375297}, + {136753295, 97272102}, + {136687988, 97158699}, + {136539794, 96946899}, + {135526702, 95550994}, + {135388488, 95382293}, + {135272491, 95279098}, + {135214904, 95250595}, + {135122894, 95218002}, + {134966705, 95165191}, + {131753997, 94380798}, + {131226806, 94331001}, + {129603393, 94193893}, + {129224197, 94188003}, + {127874107, 94215103}, + {126812797, 94690200}, + {126558197, 94813896}, + {118361801, 99824195}, + {116550796, 101078796}, + {116189704, 101380493}, + {114634002, 103027999}, + {114118103, 103820297}, + {113399200, 105568000}, + {113201705, 106093597}, + {113210205, 107034095}, + }, + { + {77917999, 130563003}, + {77926300, 131300903}, + {77990196, 132392700}, + {78144195, 133328002}, + {78170593, 133427093}, + {78235900, 133657592}, + {78799598, 135466705}, + {78933296, 135832397}, + {79112899, 136247604}, + {79336303, 136670898}, + {79585197, 137080596}, + {79726303, 137309005}, + {79820297, 137431900}, + {79942199, 137549407}, + {90329193, 145990203}, + {90460197, 146094390}, + {90606399, 146184509}, + {90715194, 146230010}, + {90919601, 146267211}, + {142335296, 153077697}, + {143460296, 153153594}, + {143976593, 153182189}, + {145403991, 153148605}, + {145562301, 153131195}, + {145705993, 153102905}, + {145938796, 153053192}, + {146134094, 153010101}, + {146483184, 152920196}, + {146904693, 152806396}, + {147180099, 152670196}, + {147357788, 152581695}, + {147615295, 152423095}, + {147782287, 152294708}, + {149281799, 150908386}, + {149405303, 150784912}, + {166569305, 126952499}, + {166784301, 126638099}, + {166938491, 126393699}, + {167030899, 126245101}, + {167173004, 126015899}, + {167415298, 125607200}, + {167468292, 125504699}, + {167553100, 125320899}, + {167584594, 125250694}, + {167684997, 125004394}, + {167807098, 124672401}, + {167938995, 124255203}, + {168052307, 123694000}, + {170094100, 112846900}, + {170118408, 112684204}, + {172079101, 88437797}, + {172082000, 88294403}, + {171916290, 82827606}, + {171911590, 82705703}, + {171874893, 82641906}, + {169867004, 79529907}, + {155996795, 58147998}, + {155904998, 58066299}, + {155864791, 58054199}, + {134315704, 56830902}, + {134086486, 56817901}, + {98200096, 56817798}, + {97838195, 56818599}, + {79401695, 56865097}, + {79291297, 56865501}, + {79180694, 56869499}, + {79058799, 56885097}, + {78937301, 56965301}, + {78324691, 57374599}, + {77932998, 57638401}, + {77917999, 57764297}, + {77917999, 130563003}, + }, + { + {75566848, 109289947}, + {75592651, 109421951}, + {75644248, 109534446}, + {95210548, 141223846}, + {95262649, 141307449}, + {95487854, 141401443}, + {95910850, 141511642}, + {96105651, 141550338}, + {106015045, 142803451}, + {106142852, 142815155}, + {166897460, 139500244}, + {167019348, 139484741}, + {168008239, 138823043}, + {168137542, 138735153}, + {168156250, 138616851}, + {173160751, 98882049}, + {174381546, 87916046}, + {174412246, 87579048}, + {174429443, 86988746}, + {174436141, 86297348}, + {174438949, 84912048}, + {174262939, 80999145}, + {174172546, 80477546}, + {173847549, 79140846}, + {173623840, 78294349}, + {173120239, 76485046}, + {173067138, 76300544}, + {173017852, 76137542}, + {172941543, 75903045}, + {172892547, 75753143}, + {172813537, 75533348}, + {172758453, 75387046}, + {172307556, 74196746}, + {171926544, 73192848}, + {171891448, 73100448}, + {171672546, 72524147}, + {171502441, 72085144}, + {171414459, 71859146}, + {171294250, 71552352}, + {171080139, 71019744}, + {171039245, 70928146}, + {170970550, 70813346}, + {170904235, 70704040}, + {170786254, 70524353}, + {168063247, 67259048}, + {167989547, 67184844}, + {83427947, 67184844}, + {78360847, 67201248}, + {78238845, 67220550}, + {78151550, 67350547}, + {77574554, 68220550}, + {77494949, 68342651}, + {77479949, 68464546}, + {75648345, 106513351}, + {75561050, 109165740}, + {75566848, 109289947}, + }, + { + {75619415, 108041595}, + {83609863, 134885772}, + {83806945, 135450820}, + {83943908, 135727371}, + {84799934, 137289794}, + {86547897, 140033782}, + {86674118, 140192962}, + {86810661, 140364715}, + {87045211, 140619918}, + {88187042, 141853240}, + {93924575, 147393783}, + {94058013, 147454803}, + {111640083, 153754562}, + {111762550, 153787933}, + {111975250, 153835311}, + {112127426, 153842803}, + {116797996, 154005157}, + {116969688, 154010681}, + {117141731, 154005935}, + {117333145, 153988037}, + {118007507, 153919952}, + {118159675, 153902130}, + {118931480, 153771942}, + {120878150, 153379089}, + {121172164, 153319259}, + {122074508, 153034362}, + {122260681, 152970367}, + {122313438, 152949584}, + {130755096, 149423736}, + {130996063, 149316818}, + {138893524, 144469665}, + {138896423, 144466918}, + {169883666, 97686134}, + {170115036, 96518981}, + {170144317, 96365257}, + {174395645, 67672065}, + {174396560, 67664222}, + {174288452, 66839241}, + {174170364, 66096923}, + {174112731, 65952033}, + {174021377, 65823486}, + {173948608, 65743225}, + {173863830, 65654769}, + {170408340, 63627494}, + {170004867, 63394714}, + {169585632, 63194389}, + {169441162, 63137046}, + {168944274, 62952133}, + {160605072, 60214218}, + {160331573, 60126396}, + {159674743, 59916877}, + {150337249, 56943778}, + {150267730, 56922073}, + {150080139, 56864868}, + {149435333, 56676422}, + {149310241, 56640579}, + {148055419, 56285041}, + {147828796, 56230949}, + {147598205, 56181800}, + {147149963, 56093917}, + {146834457, 56044700}, + {146727966, 56028717}, + {146519729, 56004882}, + {146328521, 55989326}, + {146170684, 55990036}, + {146151321, 55990745}, + {145800170, 56003616}, + {145639526, 56017753}, + {145599426, 56022491}, + {145481338, 56039184}, + {145389556, 56052757}, + {145325134, 56062591}, + {145176574, 56086135}, + {145017272, 56113922}, + {107163085, 63504539}, + {101013870, 65454101}, + {100921798, 65535285}, + {95362182, 74174079}, + {75652366, 107803443}, + {75635391, 107834983}, + {75628814, 107853294}, + {75603431, 107933692}, + {75619415, 108041595}, + }, + { + {83617141, 120264900}, + {84617370, 126416427}, + {84648635, 126601341}, + {84693695, 126816085}, + {84762496, 127082641}, + {84772140, 127117034}, + {84860748, 127391693}, + {84927398, 127550239}, + {85072967, 127789642}, + {85155151, 127908851}, + {86745422, 130042907}, + {86982666, 130317489}, + {89975143, 133230743}, + {90091384, 133338500}, + {96260833, 138719818}, + {96713928, 139103668}, + {98139297, 140307388}, + {102104766, 143511505}, + {102142089, 143536468}, + {102457626, 143735107}, + {103386764, 144312988}, + {103845001, 144579177}, + {104139175, 144737136}, + {104551254, 144932250}, + {104690155, 144985778}, + {104844238, 145010009}, + {105020034, 145010375}, + {128999633, 144082305}, + {129096542, 144076141}, + {133932327, 143370178}, + {134130615, 143326751}, + {134281250, 143289520}, + {135247116, 142993438}, + {150774948, 137828704}, + {150893478, 137786178}, + {151350921, 137608901}, + {159797760, 134318115}, + {159979827, 134244384}, + {159988128, 134240997}, + {160035186, 134221633}, + {160054962, 134211486}, + {160168762, 134132736}, + {160181228, 134121047}, + {160336425, 133961502}, + {160689147, 133564331}, + {161446258, 132710739}, + {163306427, 130611648}, + {164845474, 128873855}, + {165270233, 128393600}, + {165281478, 128380706}, + {165300598, 128358673}, + {165303497, 128355194}, + {166411590, 122772674}, + {166423767, 122708648}, + {164745605, 66237312}, + {164740341, 66193061}, + {164721755, 66082092}, + {164721160, 66078750}, + {164688476, 65914146}, + {164668426, 65859436}, + {164563110, 65765937}, + {164431152, 65715034}, + {163997619, 65550788}, + {163946426, 65531440}, + {162998107, 65173629}, + {162664978, 65049140}, + {162482696, 64991668}, + {162464660, 64989639}, + {148029083, 66896141}, + {147862396, 66932853}, + {130087829, 73341102}, + {129791564, 73469726}, + {100590927, 90307685}, + {100483535, 90373847}, + {100364990, 90458930}, + {96447448, 93276664}, + {95179656, 94189010}, + {93692718, 95260208}, + {87904327, 99430885}, + {87663711, 99606147}, + {87576202, 99683990}, + {87498199, 99801719}, + {85740264, 104173728}, + {85538925, 104710494}, + {84786132, 107265830}, + {84635955, 107801383}, + {84619506, 107868064}, + {84518463, 108287200}, + {84456848, 108613471}, + {84419158, 108826194}, + {84375244, 109093818}, + {84329818, 109435180}, + {84249862, 110179664}, + {84218429, 110572166}, + {83630020, 117995208}, + {83595535, 118787673}, + {83576217, 119290679}, + {83617141, 120264900}, + }, + { + {91735549, 117640846}, + {91748252, 117958145}, + {91823547, 118515449}, + {92088752, 119477249}, + {97995346, 140538452}, + {98031051, 140660446}, + {98154449, 141060241}, + {98179855, 141133758}, + {98217056, 141232849}, + {98217147, 141233047}, + {98269256, 141337051}, + {98298950, 141387954}, + {98337753, 141445755}, + {99455047, 142984451}, + {99656250, 143247344}, + {102567855, 146783752}, + {102685150, 146906845}, + {102828948, 147031250}, + {102972457, 147120452}, + {103676147, 147539642}, + {103758956, 147586151}, + {103956756, 147682144}, + {104479949, 147931457}, + {104744453, 148044143}, + {104994750, 148123443}, + {105375648, 148158645}, + {109266250, 148178253}, + {109447753, 148169052}, + {109693649, 148129150}, + {113729949, 147337448}, + {113884552, 147303054}, + {115155349, 146956146}, + {117637145, 146174346}, + {154694046, 134048049}, + {156979949, 133128555}, + {157076843, 133059356}, + {157125045, 133001449}, + {157561340, 132300750}, + {157865753, 131795959}, + {157923156, 131667358}, + {158007049, 131297653}, + {158112747, 130777053}, + {158116653, 130640853}, + {158268951, 119981643}, + {158260040, 119824752}, + {158229949, 119563751}, + {149914047, 73458648}, + {149877548, 73331748}, + {144460754, 66413558}, + {144230545, 66153152}, + {144128051, 66075057}, + {143974853, 65973152}, + {142812744, 65353149}, + {141810943, 64837249}, + {141683349, 64805152}, + {141505157, 64784652}, + {108214355, 61896251}, + {107826354, 61866352}, + {107072151, 61821750}, + {106938850, 61873550}, + {106584251, 62055152}, + {106419952, 62147548}, + {100459152, 65546951}, + {100343849, 65615150}, + {100198852, 65716949}, + {99825149, 65979751}, + {94619247, 70330352}, + {94492355, 70480850}, + {94445846, 70547355}, + {94425354, 70588752}, + {94379753, 70687652}, + {94110252, 71443450}, + {94095252, 71569053}, + {91737251, 117308746}, + {91731048, 117430946}, + {91735549, 117640846}, + }, + { + {108231399, 111763748}, + {108335403, 111927955}, + {108865203, 112754745}, + {109206703, 113283851}, + {127117500, 125545951}, + {127212097, 125560951}, + {127358497, 125563652}, + {131348007, 125551147}, + {131412002, 125550849}, + {131509506, 125535446}, + {131579391, 125431343}, + {132041000, 124735656}, + {132104690, 124637847}, + {144108505, 100950546}, + {144120605, 100853042}, + {144123291, 100764648}, + {144122695, 100475143}, + {144086898, 85637748}, + {144083602, 85549346}, + {144071105, 85451843}, + {144007003, 85354545}, + {143679595, 84864547}, + {143468597, 84551048}, + {143367889, 84539146}, + {109847702, 84436347}, + {109684700, 84458953}, + {105946502, 89406143}, + {105915901, 91160446}, + {105880905, 93187744}, + {105876701, 93441345}, + {108231399, 111763748}, + }, + { + {102614700, 117684249}, + {102675102, 118074157}, + {102888999, 118743148}, + {103199707, 119517555}, + {103446800, 120099655}, + {103488204, 120193450}, + {104063903, 121373947}, + {104535499, 122192245}, + {104595802, 122295249}, + {104663002, 122402854}, + {104945701, 122854858}, + {105740501, 124038848}, + {106809700, 125479354}, + {107564399, 126380050}, + {108116203, 126975646}, + {123724700, 142516540}, + {124938400, 143705444}, + {127919601, 146599243}, + {128150894, 146821456}, + {128251602, 146917251}, + {128383605, 147041839}, + {128527709, 147176147}, + {128685699, 147321456}, + {128861007, 147481246}, + {132825103, 151046661}, + {133005493, 151205657}, + {133389007, 151488143}, + {133896499, 151858062}, + {134172302, 151991546}, + {134375000, 152063140}, + {135316101, 152300949}, + {136056304, 152220947}, + {136242706, 152186843}, + {136622207, 152016448}, + {136805404, 151908355}, + {147099594, 145766845}, + {147246704, 144900756}, + {147387603, 144048461}, + {144353698, 99345855}, + {144333801, 99232254}, + {144244598, 98812850}, + {144228698, 98757858}, + {144174606, 98616455}, + {133010101, 72396743}, + {132018905, 70280853}, + {130667404, 67536949}, + {129167297, 64854446}, + {128569198, 64098350}, + {124458503, 59135948}, + {124260597, 58946949}, + {123908706, 58658851}, + {123460098, 58327850}, + {122674499, 57840648}, + {122041801, 57712150}, + {121613403, 57699047}, + {121359901, 57749351}, + {121123199, 57826450}, + {120953498, 57882247}, + {120431701, 58198547}, + {120099205, 58599349}, + {119892303, 58903049}, + {102835296, 115179351}, + {102686599, 115817245}, + {102612396, 116540557}, + {102614700, 117684249}, + }, + { + {98163757, 71203430}, + {98212463, 73314544}, + {98326538, 74432693}, + {98402908, 75169799}, + {98524154, 76328353}, + {99088806, 79911361}, + {99304885, 80947769}, + {100106689, 84244186}, + {100358123, 85080337}, + {101715545, 89252807}, + {101969528, 89987213}, + {107989440, 106391418}, + {126299575, 140277343}, + {127061813, 141486663}, + {127405746, 141872253}, + {127846908, 142318450}, + {130818496, 145301574}, + {134366424, 148100921}, + {135308380, 148798828}, + {135745666, 149117523}, + {136033020, 149251800}, + {136500579, 149387725}, + {136662719, 149418395}, + {136973922, 149474822}, + {137184890, 149484375}, + {137623748, 149434356}, + {137830810, 149355072}, + {138681732, 148971343}, + {139374465, 148463409}, + {139589187, 148264312}, + {139809707, 148010711}, + {139985610, 147685028}, + {140196029, 147284973}, + {140355834, 146978668}, + {142079666, 142575622}, + {146702194, 129469726}, + {151285888, 113275238}, + {151543731, 112046264}, + {151701629, 110884704}, + {151837020, 108986206}, + {151837097, 107724029}, + {151760101, 106529205}, + {151581970, 105441925}, + {151577301, 105413757}, + {151495269, 105014709}, + {151393142, 104551513}, + {151058502, 103296112}, + {150705520, 102477264}, + {150137725, 101686370}, + {149427032, 100938537}, + {102979965, 60772064}, + {101930953, 60515609}, + {101276748, 60634414}, + {100717803, 60918136}, + {100125732, 61584625}, + {99618148, 62413436}, + {99457214, 62709442}, + {99368347, 62914794}, + {99166992, 63728332}, + {98313827, 69634780}, + {98176910, 70615707}, + {98162902, 70798233}, + {98163757, 71203430}, + }, + { + {79090698, 116426399}, + {80959800, 137087692}, + {81030303, 137762298}, + {81190704, 138903503}, + {81253700, 139084197}, + {81479301, 139544998}, + {81952003, 140118896}, + {82319900, 140523895}, + {82967803, 140993896}, + {83022903, 141032104}, + {83777900, 141493606}, + {84722099, 141849899}, + {84944396, 141887207}, + {86144699, 141915893}, + {87643997, 141938095}, + {88277503, 141887695}, + {88582099, 141840606}, + {89395401, 141712203}, + {90531204, 141528396}, + {91014801, 141438400}, + {92097595, 141190093}, + {123348297, 132876998}, + {123399505, 132860000}, + {123452804, 132841506}, + {123515502, 132818908}, + {123543800, 132806198}, + {124299598, 132437393}, + {124975502, 132042098}, + {125047500, 131992202}, + {125119506, 131930603}, + {166848800, 86317703}, + {168976409, 83524902}, + {169359603, 82932701}, + {169852600, 81917800}, + {170686904, 79771202}, + {170829406, 79245597}, + {170885498, 78796295}, + {170909301, 78531898}, + {170899703, 78238700}, + {170842803, 77553199}, + {170701293, 76723495}, + {170302307, 75753898}, + {169924301, 75067398}, + {169359802, 74578796}, + {168148605, 73757499}, + {163261596, 71124702}, + {162986007, 70977798}, + {162248703, 70599098}, + {158193405, 68923995}, + {157514297, 68667495}, + {156892700, 68495201}, + {156607299, 68432998}, + {154301895, 68061904}, + {93440299, 68061904}, + {88732002, 68255996}, + {88627304, 68298500}, + {88111396, 68541900}, + {86393898, 69555404}, + {86138298, 69706695}, + {85871704, 69913200}, + {85387199, 70393402}, + {79854499, 76783203}, + {79209701, 77649398}, + {79108505, 78072502}, + {79090698, 78472198}, + {79090698, 116426399}, + }, + { + {90956314, 84639938}, + {91073814, 85141891}, + {91185752, 85505371}, + {109815368, 137196487}, + {110342590, 138349899}, + {110388549, 138447540}, + {110652862, 138971343}, + {110918045, 139341140}, + {114380859, 143159042}, + {114446723, 143220352}, + {114652198, 143392166}, + {114712196, 143437301}, + {114782165, 143476028}, + {114873054, 143514923}, + {115217086, 143660934}, + {115306060, 143695526}, + {115344009, 143707580}, + {115444541, 143737747}, + {115589378, 143779937}, + {115751358, 143823989}, + {115802780, 143825820}, + {116872810, 143753616}, + {116927055, 143744644}, + {154690734, 133504180}, + {155009704, 133371856}, + {155029907, 133360061}, + {155089141, 133323181}, + {155342315, 133163360}, + {155602294, 132941406}, + {155669158, 132880294}, + {155821624, 132737884}, + {155898986, 132656890}, + {155934936, 132608932}, + {155968627, 132562713}, + {156062896, 132431808}, + {156111694, 132363174}, + {156148147, 132297180}, + {158738342, 127281066}, + {159026672, 126378631}, + {159073699, 125806335}, + {159048522, 125299743}, + {159040313, 125192901}, + {158898300, 123934677}, + {149829376, 70241508}, + {149763031, 69910629}, + {149684692, 69628723}, + {149557800, 69206214}, + {149366485, 68864326}, + {149137390, 68578514}, + {148637466, 68048767}, + {147027725, 66632934}, + {146228607, 66257507}, + {146061309, 66184646}, + {146017929, 66174186}, + {145236465, 66269500}, + {144802490, 66345039}, + {144673995, 66376220}, + {93732284, 79649864}, + {93345336, 79785865}, + {93208084, 79840286}, + {92814521, 79997779}, + {92591087, 80098968}, + {92567016, 80110511}, + {92032684, 80860725}, + {91988853, 80930152}, + {91471725, 82210029}, + {91142349, 83076683}, + {90969284, 83653182}, + {90929664, 84043212}, + {90926315, 84325256}, + {90956314, 84639938}, + }, + { + {114758499, 88719909}, + {114771591, 88860549}, + {115515533, 94195907}, + {115559539, 94383651}, + {119882980, 109502059}, + {120660522, 111909683}, + {126147735, 124949630}, + {127127212, 127107215}, + {129976379, 132117279}, + {130754470, 133257080}, + {130820968, 133340835}, + {130889312, 133423858}, + {131094787, 133652832}, + {131257629, 133828247}, + {131678619, 134164276}, + {131791107, 134248901}, + {131969482, 134335189}, + {132054107, 134373718}, + {132927368, 134701141}, + {133077072, 134749313}, + {133196075, 134785705}, + {133345230, 134804351}, + {133498809, 134809051}, + {133611541, 134797607}, + {134621170, 134565322}, + {134741165, 134527511}, + {134892089, 134465240}, + {135071212, 134353820}, + {135252029, 134185821}, + {135384979, 134003631}, + {135615585, 133576675}, + {135793029, 132859008}, + {135890228, 131382904}, + {135880828, 131261657}, + {135837570, 130787963}, + {135380661, 127428909}, + {132830596, 109495368}, + {132815826, 109411666}, + {132765869, 109199302}, + {132724380, 109068161}, + {127490066, 93353515}, + {125330810, 87852828}, + {125248336, 87647026}, + {125002182, 87088424}, + {124894592, 86872482}, + {121007278, 80019584}, + {120962829, 79941261}, + {120886489, 79833923}, + {120154983, 78949615}, + {119366561, 78111709}, + {119014755, 77776794}, + {116728790, 75636238}, + {116660522, 75593933}, + {116428192, 75458541}, + {116355255, 75416870}, + {116264663, 75372528}, + {115952728, 75233367}, + {115865554, 75205482}, + {115756835, 75190956}, + {115564163, 75197830}, + {115481170, 75202087}, + {115417144, 75230400}, + {115226959, 75337806}, + {115203842, 75351448}, + {114722015, 75746932}, + {114672103, 75795661}, + {114594619, 75891891}, + {114565811, 75973831}, + {114478256, 76240814}, + {114178039, 77252197}, + {114137664, 77769668}, + {114109771, 78154464}, + {114758499, 88719909}, + }, + { + {108135070, 109828002}, + {108200347, 110091529}, + {108319419, 110298500}, + {108439025, 110488388}, + {108663574, 110766731}, + {108812957, 110935768}, + {109321914, 111398925}, + {109368087, 111430320}, + {109421295, 111466331}, + {110058998, 111849746}, + {127160308, 120588981}, + {127350692, 120683456}, + {128052749, 120997207}, + {128326919, 121113449}, + {131669586, 122213058}, + {131754745, 122240592}, + {131854583, 122264770}, + {132662048, 122449813}, + {132782669, 122449897}, + {132909118, 122443687}, + {133013442, 122436058}, + {140561035, 121609939}, + {140786346, 121583320}, + {140876144, 121570228}, + {140962356, 121547996}, + {141052612, 121517837}, + {141231292, 121442184}, + {141309371, 121390007}, + {141370132, 121327003}, + {141456008, 121219932}, + {141591598, 121045005}, + {141905761, 120634796}, + {141894607, 120305725}, + {141881881, 120110855}, + {141840881, 119885009}, + {141685043, 119238922}, + {141617416, 118962882}, + {141570434, 118858856}, + {131617462, 100598548}, + {131542846, 100487213}, + {131229385, 100089019}, + {131091476, 99928108}, + {119824127, 90297180}, + {119636337, 90142387}, + {119507492, 90037765}, + {119436744, 89983657}, + {119423942, 89974159}, + {119207366, 89822471}, + {119117149, 89767097}, + {119039489, 89726867}, + {116322929, 88522857}, + {114817031, 87882110}, + {114683975, 87826751}, + {114306411, 87728507}, + {113876434, 87646003}, + {113792106, 87629974}, + {113658988, 87615974}, + {113574333, 87609275}, + {112813575, 87550102}, + {112578567, 87560157}, + {112439880, 87571647}, + {112306922, 87599395}, + {112225082, 87622535}, + {112132568, 87667175}, + {112103477, 87682830}, + {110795242, 88511634}, + {110373565, 88847793}, + {110286537, 88934989}, + {109730873, 89531501}, + {109648735, 89628883}, + {109552581, 89768859}, + {109514228, 89838470}, + {109501640, 89877586}, + {109480964, 89941864}, + {109461761, 90032417}, + {109457778, 90055458}, + {108105194, 109452575}, + {108094238, 109620979}, + {108135070, 109828002}, + }, + { + {108764694, 108910400}, + {108965499, 112306495}, + {109598602, 120388298}, + {110573898, 128289596}, + {110597801, 128427795}, + {113786201, 137983795}, + {113840301, 138134704}, + {113937202, 138326904}, + {114046005, 138520401}, + {114150802, 138696792}, + {114164703, 138717895}, + {114381896, 139021194}, + {114701004, 139425292}, + {114997398, 139747497}, + {115065597, 139805191}, + {115134498, 139850891}, + {115167098, 139871704}, + {115473396, 139992797}, + {115537498, 139995101}, + {116762596, 139832000}, + {116897499, 139808593}, + {118401802, 139225585}, + {118437500, 139209594}, + {118488204, 139182189}, + {118740097, 139033996}, + {118815795, 138967285}, + {134401000, 116395492}, + {134451507, 116309997}, + {135488098, 113593597}, + {137738006, 106775695}, + {140936492, 97033889}, + {140960006, 96948997}, + {141026504, 96660995}, + {141067291, 96467094}, + {141124893, 95771896}, + {141511795, 90171600}, + {141499801, 90026000}, + {141479598, 89907798}, + {141276794, 88844596}, + {141243804, 88707397}, + {140778305, 87031593}, + {140733306, 86871696}, + {140697204, 86789993}, + {140619796, 86708190}, + {140398391, 86487396}, + {125798797, 72806198}, + {125415802, 72454498}, + {123150398, 70566093}, + {123038803, 70503997}, + {122681198, 70305397}, + {121919204, 70104797}, + {121533699, 70008094}, + {121273696, 70004898}, + {121130599, 70020797}, + {121045097, 70033294}, + {120847099, 70082298}, + {120481895, 70278999}, + {120367004, 70379692}, + {120272796, 70475097}, + {119862098, 71004791}, + {119745101, 71167297}, + {119447799, 71726997}, + {119396499, 71825798}, + {119348701, 71944496}, + {109508796, 98298797}, + {109368598, 98700897}, + {109298400, 98926391}, + {108506301, 102750991}, + {108488197, 102879898}, + {108764694, 108910400}, + }, + { + {106666252, 87231246}, + {106673248, 87358055}, + {107734146, 101975646}, + {107762649, 102357955}, + {108702445, 111208351}, + {108749450, 111345153}, + {108848350, 111542648}, + {110270645, 114264358}, + {110389648, 114445144}, + {138794845, 143461151}, + {139048355, 143648956}, + {139376144, 143885345}, + {139594451, 144022644}, + {139754043, 144110046}, + {139923950, 144185852}, + {140058242, 144234451}, + {140185653, 144259552}, + {140427551, 144292648}, + {141130950, 144281448}, + {141157653, 144278152}, + {141214355, 144266555}, + {141347457, 144223449}, + {141625350, 144098953}, + {141755142, 144040145}, + {141878143, 143971557}, + {142011444, 143858154}, + {142076843, 143796356}, + {142160644, 143691055}, + {142224456, 143560852}, + {142925842, 142090850}, + {142935653, 142065353}, + {142995956, 141899154}, + {143042556, 141719757}, + {143102951, 141436157}, + {143129257, 141230453}, + {143316055, 139447250}, + {143342544, 133704650}, + {143307556, 130890960}, + {142461257, 124025558}, + {141916046, 120671051}, + {141890457, 120526153}, + {140002349, 113455749}, + {139909149, 113144149}, + {139853454, 112974456}, + {137303756, 105228057}, + {134700546, 98161254}, + {134617950, 97961547}, + {133823547, 96118057}, + {133688751, 95837356}, + {133481353, 95448059}, + {133205444, 94948150}, + {131178955, 91529853}, + {131144744, 91482055}, + {113942047, 67481246}, + {113837051, 67360549}, + {113048950, 66601745}, + {112305549, 66002746}, + {112030853, 65790351}, + {111970649, 65767547}, + {111912445, 65755249}, + {111854248, 65743453}, + {111657447, 65716354}, + {111576950, 65707351}, + {111509750, 65708549}, + {111443550, 65718551}, + {111397247, 65737449}, + {111338546, 65764648}, + {111129547, 65863349}, + {111112449, 65871551}, + {110995254, 65927856}, + {110968849, 65946151}, + {110941444, 65966751}, + {110836448, 66057853}, + {110490447, 66445449}, + {110404144, 66576751}, + {106802055, 73202148}, + {106741950, 73384948}, + {106715454, 73469650}, + {106678054, 73627151}, + {106657455, 75433448}, + {106666252, 87231246}, + }, + { + {101852752, 106261352}, + {101868949, 106406051}, + {102347549, 108974250}, + {112286750, 152027954}, + {112305648, 152106536}, + {112325752, 152175857}, + {112391448, 152290863}, + {113558250, 154187454}, + {113592048, 154226745}, + {113694351, 154313156}, + {113736549, 154335647}, + {113818145, 154367462}, + {114284454, 154490951}, + {114415847, 154504547}, + {114520751, 154489151}, + {114571350, 154478057}, + {114594551, 154472854}, + {114630546, 154463958}, + {114715148, 154429443}, + {146873657, 136143051}, + {146941741, 136074249}, + {147190155, 135763549}, + {147262649, 135654937}, + {147309951, 135557159}, + {147702255, 133903945}, + {147934143, 131616348}, + {147967041, 131273864}, + {148185852, 127892250}, + {148195648, 127669754}, + {148179656, 126409851}, + {148119552, 126182151}, + {147874053, 125334152}, + {147818954, 125150352}, + {146958557, 122656646}, + {139070251, 101025955}, + {139002655, 100879051}, + {119028450, 63067649}, + {118846649, 62740753}, + {115676048, 57814651}, + {115550453, 57629852}, + {115330352, 57319751}, + {115094749, 56998352}, + {114978347, 56847454}, + {114853050, 56740550}, + {114695053, 56609550}, + {114582252, 56528148}, + {114210449, 56375953}, + {113636245, 56214950}, + {113470352, 56171649}, + {109580749, 55503551}, + {109491645, 55495452}, + {109238754, 55511550}, + {109080352, 55534049}, + {108027748, 55687351}, + {107839950, 55732349}, + {107614456, 55834953}, + {107488143, 55925952}, + {107302551, 56062553}, + {107218353, 56145751}, + {107199447, 56167251}, + {107052749, 56354850}, + {106978652, 56476348}, + {106869644, 56710754}, + {104541351, 62448753}, + {104454551, 62672554}, + {104441253, 62707351}, + {104231750, 63366348}, + {104222648, 63419952}, + {104155746, 63922649}, + {104127349, 64147552}, + {104110847, 64299957}, + {102235450, 92366752}, + {101804351, 102877655}, + {101852752, 106261352}, + }, + { + {106808700, 120885696}, + {106818695, 120923103}, + {106873901, 121057098}, + {115123603, 133614700}, + {115128799, 133619598}, + {115182197, 133661804}, + {115330101, 133740707}, + {115455398, 133799407}, + {115595001, 133836807}, + {115651000, 133851806}, + {116413604, 134055206}, + {116654495, 134097900}, + {116887603, 134075210}, + {117071098, 134040405}, + {117458801, 133904891}, + {118057998, 133572601}, + {118546997, 133261001}, + {118578498, 133239395}, + {118818603, 133011596}, + {121109695, 130501495}, + {122661598, 128760101}, + {142458190, 102765197}, + {142789001, 102099601}, + {143105010, 101386505}, + {143154800, 101239700}, + {143193908, 100825500}, + {143160507, 100282501}, + {143133499, 100083602}, + {143092697, 99880500}, + {143050689, 99766700}, + {142657501, 98974502}, + {142580307, 98855201}, + {122267196, 76269897}, + {122036399, 76105003}, + {121832000, 76028305}, + {121688796, 75983108}, + {121591598, 75955001}, + {121119697, 75902099}, + {120789596, 75953498}, + {120487495, 76041900}, + {120042701, 76365798}, + {119886695, 76507301}, + {119774200, 76635299}, + {119739097, 76686904}, + {119685195, 76798202}, + {119456199, 77320098}, + {106877601, 119561401}, + {106854797, 119645103}, + {106849098, 119668807}, + {106847099, 119699005}, + {106840400, 119801406}, + {106807800, 120719299}, + {106806098, 120862808}, + {106808700, 120885696}, + }, + { + {99663352, 105328948}, + {99690048, 105797050}, + {99714050, 105921447}, + {99867248, 106439949}, + {100111557, 107256546}, + {104924850, 120873649}, + {105106155, 121284049}, + {105519149, 122184753}, + {105586051, 122292655}, + {105665054, 122400154}, + {106064147, 122838455}, + {106755355, 123453453}, + {106929054, 123577651}, + {107230346, 123771949}, + {107760650, 123930648}, + {108875854, 124205154}, + {108978752, 124228050}, + {131962051, 123738754}, + {135636047, 123513954}, + {135837249, 123500747}, + {136357345, 123442749}, + {136577346, 123394454}, + {136686645, 123367752}, + {137399353, 123185050}, + {137733947, 123063156}, + {137895355, 122997154}, + {138275650, 122829154}, + {138394256, 122767753}, + {138516845, 122670150}, + {139987045, 121111251}, + {149171646, 108517349}, + {149274353, 108372848}, + {149314758, 108314247}, + {149428848, 108140846}, + {149648651, 107650550}, + {149779541, 107290252}, + {149833343, 107115249}, + {149891357, 106920051}, + {150246353, 105630249}, + {150285842, 105423454}, + {150320953, 105233749}, + {150336639, 104981552}, + {150298049, 104374053}, + {150287948, 104271850}, + {150026153, 103481147}, + {149945449, 103301651}, + {149888946, 103213455}, + {149800949, 103103851}, + {149781143, 103079650}, + {149714141, 103005447}, + {149589950, 102914146}, + {149206054, 102698951}, + {128843856, 91378150}, + {128641754, 91283050}, + {119699851, 87248046}, + {117503555, 86311950}, + {117145851, 86178054}, + {116323654, 85925048}, + {115982551, 85834045}, + {115853050, 85819252}, + {115222549, 85771949}, + {107169357, 85771949}, + {107122650, 85776451}, + {106637145, 85831550}, + {105095046, 86423950}, + {104507850, 86703750}, + {104384155, 86763153}, + {104332351, 86790145}, + {104198257, 86882644}, + {103913757, 87109451}, + {103592346, 87388450}, + {103272651, 87666748}, + {103198051, 87779052}, + {101698654, 90600952}, + {101523551, 90958450}, + {101360054, 91347450}, + {101295349, 91542144}, + {99774551, 98278152}, + {99746749, 98417755}, + {99704055, 98675453}, + {99663352, 99022949}, + {99663352, 105328948}, + }, + { + {95036499, 101778106}, + {95479103, 102521301}, + {95587295, 102700103}, + {98306503, 106984901}, + {98573303, 107377700}, + {100622406, 110221702}, + {101252304, 111089599}, + {104669502, 115750198}, + {121838500, 131804107}, + {122000503, 131943695}, + {122176803, 132023406}, + {122474105, 132025390}, + {122703804, 132023101}, + {123278808, 131878112}, + {124072998, 131509109}, + {124466506, 131102508}, + {152779296, 101350906}, + {153016510, 101090606}, + {153269699, 100809097}, + {153731994, 100214096}, + {153927902, 99939796}, + {154641098, 98858100}, + {154864303, 98517601}, + {155056594, 97816604}, + {155083511, 97645599}, + {155084899, 97462097}, + {154682601, 94386100}, + {154376007, 92992599}, + {154198593, 92432403}, + {153830505, 91861701}, + {153686904, 91678695}, + {151907104, 90314605}, + {151368896, 89957603}, + {146983306, 87632202}, + {139082397, 84273605}, + {128947692, 80411399}, + {121179000, 78631301}, + {120264701, 78458198}, + {119279510, 78304603}, + {116913101, 77994102}, + {116151504, 77974601}, + {115435104, 78171401}, + {113544105, 78709106}, + {113231002, 78879898}, + {112726303, 79163604}, + {112310501, 79411102}, + {96169998, 97040802}, + {95196304, 98364402}, + {95167800, 98409599}, + {95083503, 98570701}, + {94986999, 99022201}, + {94915100, 100413299}, + {95036499, 101778106}, + }, + { + {82601348, 96004745}, + {83443847, 128861953}, + {84173248, 136147354}, + {104268249, 141388839}, + {104373649, 141395355}, + {105686950, 141389541}, + {149002243, 140435653}, + {159095748, 133388244}, + {159488143, 133112655}, + {159661849, 132894653}, + {163034149, 128290847}, + {164801849, 124684249}, + {167405746, 72553245}, + {167330444, 71960746}, + {167255050, 71791847}, + {167147155, 71572044}, + {166999557, 71341545}, + {166723937, 70961448}, + {166238250, 70611541}, + {165782348, 70359649}, + {165649444, 70286849}, + {165332946, 70122344}, + {165164154, 70062248}, + {164879150, 69967544}, + {164744949, 69928947}, + {164691452, 69915245}, + {164669448, 69910247}, + {159249938, 68738952}, + {158528259, 68704742}, + {147564254, 68604644}, + {116196655, 68982742}, + {115364944, 69005050}, + {115193145, 69013549}, + {101701248, 70984146}, + {93918449, 72233047}, + {93789749, 72285247}, + {93777046, 72292648}, + {93586044, 72444046}, + {93366348, 72662345}, + {93301147, 72745452}, + {93260345, 72816345}, + {83523948, 92593849}, + {83430145, 92810241}, + {82815048, 94665542}, + {82755554, 94858551}, + {82722953, 95014350}, + {82594253, 95682350}, + {82601348, 96004745}, + }, + { + {110371345, 125796493}, + {110411544, 126159599}, + {110445251, 126362899}, + {111201950, 127863800}, + {112030052, 129270492}, + {112367050, 129799301}, + {113088348, 130525604}, + {113418144, 130853698}, + {117363449, 134705505}, + {118131149, 135444793}, + {118307449, 135607299}, + {119102546, 136297195}, + {119385047, 136531906}, + {120080848, 137094390}, + {120794845, 137645401}, + {121150344, 137896392}, + {121528945, 138162506}, + {121644546, 138242095}, + {122142349, 138506408}, + {127540847, 141363006}, + {127933448, 141516204}, + {128728256, 141766799}, + {129877151, 141989898}, + {130626052, 142113891}, + {130912246, 142135192}, + {131246841, 142109100}, + {131496047, 142027404}, + {131596252, 141957794}, + {131696350, 141873504}, + {131741043, 141803405}, + {138788452, 128037704}, + {139628646, 125946197}, + {138319351, 112395401}, + {130035354, 78066703}, + {124174049, 69908798}, + {123970649, 69676895}, + {123874252, 69571899}, + {123246643, 68961303}, + {123193954, 68924400}, + {121952049, 68110000}, + {121787345, 68021896}, + {121661544, 67970306}, + {121313446, 67877502}, + {121010650, 67864799}, + {120995346, 67869705}, + {120583747, 68122207}, + {120509750, 68170600}, + {120485847, 68189102}, + {112160148, 77252403}, + {111128646, 78690704}, + {110969650, 78939407}, + {110512550, 79663406}, + {110397247, 79958206}, + {110371345, 80038299}, + {110371345, 125796493}, + }, + { + {112163948, 137752700}, + {112171150, 137837997}, + {112203048, 137955993}, + {112240150, 138008209}, + {112343246, 138111099}, + {112556243, 138223205}, + {112937149, 138307998}, + {113318748, 138331909}, + {126076446, 138428298}, + {126165245, 138428695}, + {126312446, 138417907}, + {134075546, 136054504}, + {134322753, 135949401}, + {134649948, 135791198}, + {135234954, 135493408}, + {135290145, 135464691}, + {135326248, 135443695}, + {135920043, 135032592}, + {135993850, 134975799}, + {136244247, 134761199}, + {136649444, 134378692}, + {137067153, 133964294}, + {137188156, 133839096}, + {137298049, 133704498}, + {137318954, 133677795}, + {137413543, 133522201}, + {137687347, 133043792}, + {137816055, 132660705}, + {137836044, 131747695}, + {137807144, 131318603}, + {136279342, 119078704}, + {136249053, 118945800}, + {127306152, 81348602}, + {127114852, 81065505}, + {127034248, 80951400}, + {126971649, 80893707}, + {125093551, 79178001}, + {124935745, 79036003}, + {115573745, 71767601}, + {115411148, 71701805}, + {115191947, 71621002}, + {115017051, 71571304}, + {114870147, 71572898}, + {113869552, 71653900}, + {112863349, 72976104}, + {112756347, 73223899}, + {112498947, 73832206}, + {112429351, 73998504}, + {112366050, 74168098}, + {112273246, 74487098}, + {112239250, 74605400}, + {112195549, 74899902}, + {112163948, 75280700}, + {112163948, 137752700}, + }, + { + {78562347, 141451843}, + {79335624, 142828186}, + {79610343, 143188140}, + {79845077, 143445724}, + {81379173, 145126678}, + {81826751, 145577178}, + {82519126, 146209472}, + {83964973, 147280502}, + {85471343, 148377868}, + {86115539, 148760803}, + {88839988, 150281188}, + {89021247, 150382217}, + {90775917, 151320526}, + {91711380, 151767288}, + {92757591, 152134277}, + {93241058, 152201766}, + {113402145, 153091995}, + {122065994, 146802825}, + {164111053, 91685104}, + {164812759, 90470565}, + {165640182, 89037384}, + {171027435, 66211853}, + {171450805, 64406951}, + {171463150, 64349624}, + {171469787, 64317184}, + {171475585, 64282028}, + {171479812, 64253036}, + {171483596, 64210433}, + {171484405, 64153488}, + {171483001, 64140785}, + {171481719, 64132751}, + {171478668, 64115478}, + {171472702, 64092437}, + {171462768, 64075408}, + {171448089, 64061347}, + {171060333, 63854789}, + {169640502, 63197738}, + {169342147, 63086711}, + {166413101, 62215766}, + {151881774, 58826736}, + {146010574, 57613151}, + {141776962, 56908004}, + {140982940, 57030628}, + {139246154, 57540817}, + {139209609, 57566974}, + {127545310, 66015594}, + {127476654, 66104812}, + {105799087, 98784980}, + {85531921, 129338897}, + {79319717, 138704513}, + {78548156, 140188079}, + {78530448, 140530456}, + {78515594, 141299987}, + {78562347, 141451843}, + }, + { + {77755004, 128712387}, + {78073547, 130552612}, + {78433593, 132017822}, + {79752693, 136839645}, + {80479461, 138929260}, + {80903221, 140119674}, + {81789848, 141978454}, + {82447387, 143105575}, + {83288436, 144264328}, + {84593582, 145846542}, + {84971939, 146242813}, + {86905578, 147321304}, + {87874191, 147594131}, + {89249092, 147245132}, + {89541542, 147169052}, + {98759140, 144071609}, + {98894233, 144024261}, + {113607818, 137992843}, + {128324356, 131649307}, + {139610076, 126210189}, + {146999572, 122112884}, + {147119415, 122036041}, + {148717330, 120934616}, + {149114776, 120652725}, + {171640289, 92086624}, + {171677917, 92036224}, + {171721191, 91973869}, + {171851608, 91721557}, + {171927795, 91507644}, + {172398696, 89846351}, + {172436752, 89559959}, + {169361663, 64753852}, + {169349029, 64687164}, + {169115127, 63616458}, + {168965728, 63218254}, + {168911788, 63121219}, + {168901611, 63106807}, + {168896896, 63100486}, + {168890686, 63092460}, + {168876586, 63081058}, + {168855529, 63067909}, + {168808746, 63046024}, + {167251068, 62405864}, + {164291717, 63716899}, + {152661651, 69910156}, + {142312393, 75421356}, + {78778053, 111143295}, + {77887222, 113905914}, + {77591979, 124378433}, + {77563247, 126586669}, + {77755004, 128712387}, + }, + { + {105954101, 131182754}, + {105959197, 131275848}, + {105972801, 131473556}, + {105981498, 131571044}, + {106077903, 132298553}, + {106134094, 132715255}, + {106155700, 132832351}, + {106180099, 132942657}, + {106326797, 133590347}, + {106375099, 133719345}, + {106417602, 133829345}, + {106471000, 133930343}, + {106707901, 134308654}, + {106728401, 134340545}, + {106778198, 134417556}, + {106832397, 134491851}, + {106891296, 134562957}, + {106981300, 134667358}, + {107044204, 134736557}, + {107111000, 134802658}, + {107180999, 134865661}, + {107291099, 134961349}, + {107362998, 135020355}, + {107485397, 135112854}, + {107558998, 135166946}, + {107690399, 135256256}, + {107765098, 135305252}, + {107903594, 135390548}, + {108183898, 135561843}, + {108459503, 135727951}, + {108532501, 135771850}, + {108796096, 135920059}, + {108944099, 135972549}, + {109102401, 136010757}, + {109660598, 136071044}, + {109971595, 136100250}, + {110209594, 136116851}, + {110752799, 136122344}, + {111059906, 136105758}, + {111152900, 136100357}, + {111237197, 136091354}, + {111316101, 136075057}, + {111402000, 136050949}, + {111475296, 136026657}, + {143546600, 123535949}, + {143899002, 122454353}, + {143917404, 122394348}, + {143929199, 122354652}, + {143944793, 122295753}, + {143956207, 122250953}, + {143969497, 122192253}, + {143980102, 122143249}, + {143991302, 122083053}, + {144000396, 122031753}, + {144009796, 121970954}, + {144017303, 121917655}, + {144025405, 121850250}, + {144030609, 121801452}, + {144036804, 121727455}, + {144040008, 121683456}, + {144043502, 121600952}, + {144044708, 121565048}, + {144045700, 121470352}, + {144045898, 121446952}, + {144041503, 121108657}, + {144037506, 121023452}, + {143733795, 118731750}, + {140461395, 95238647}, + {140461105, 95236755}, + {140433807, 95115249}, + {140392608, 95011650}, + {134840805, 84668952}, + {134824996, 84642456}, + {134781494, 84572952}, + {134716796, 84480850}, + {127473899, 74425453}, + {127467002, 74417152}, + {127431701, 74381652}, + {127402603, 74357147}, + {127375503, 74334457}, + {127294906, 74276649}, + {127181900, 74207649}, + {127177597, 74205451}, + {127123901, 74178451}, + {127078903, 74155853}, + {127028999, 74133148}, + {126870803, 74070953}, + {126442901, 73917648}, + {126432403, 73914955}, + {126326004, 73889846}, + {126262405, 73880645}, + {126128097, 73878456}, + {125998199, 73877655}, + {108701095, 74516647}, + {108644599, 74519348}, + {108495201, 74528953}, + {108311302, 74556457}, + {108252799, 74569458}, + {108079002, 74612152}, + {107981399, 74638954}, + {107921295, 74657951}, + {107862197, 74685951}, + {107601303, 74828948}, + {107546997, 74863449}, + {107192794, 75098846}, + {107131202, 75151153}, + {106260002, 76066146}, + {106195098, 76221145}, + {106168502, 76328453}, + {106144699, 76437454}, + {106124496, 76538452}, + {106103698, 76649650}, + {106084197, 76761650}, + {106066299, 76874450}, + {106049903, 76987457}, + {106034797, 77101150}, + {106020904, 77214950}, + {106008201, 77328948}, + {105996902, 77443145}, + {105986099, 77565849}, + {105977005, 77679649}, + {105969299, 77793151}, + {105963096, 77906349}, + {105958297, 78019149}, + {105955299, 78131454}, + {105954101, 78242950}, + {105954101, 131182754}, + }, + { + {91355499, 77889205}, + {114834197, 120804504}, + {114840301, 120815200}, + {124701507, 132324798}, + {124798805, 132436706}, + {124901504, 132548309}, + {125126602, 132788909}, + {125235000, 132901901}, + {125337707, 133005401}, + {125546302, 133184707}, + {125751602, 133358703}, + {126133300, 133673004}, + {126263900, 133775604}, + {126367401, 133855499}, + {126471908, 133935104}, + {126596008, 134027496}, + {127119308, 134397094}, + {127135101, 134408203}, + {127433609, 134614303}, + {127554107, 134695709}, + {128155395, 135070907}, + {128274505, 135141799}, + {129132003, 135573211}, + {129438003, 135713195}, + {129556106, 135767196}, + {131512695, 136648498}, + {132294509, 136966598}, + {132798400, 137158798}, + {133203796, 137294494}, + {133377410, 137350799}, + {133522399, 137396606}, + {133804397, 137480697}, + {134017807, 137542205}, + {134288696, 137618408}, + {134564208, 137680099}, + {134844696, 137740097}, + {135202606, 137807098}, + {135489105, 137849807}, + {135626800, 137864898}, + {135766906, 137878692}, + {135972808, 137895797}, + {136110107, 137905502}, + {136235000, 137913101}, + {136485809, 137907196}, + {139194305, 136979202}, + {140318298, 136536209}, + {140380004, 136505004}, + {140668197, 136340499}, + {140724304, 136298904}, + {140808197, 136228210}, + {140861801, 136180603}, + {140917404, 136129104}, + {140979202, 136045104}, + {141022903, 135984207}, + {147591094, 126486999}, + {147661315, 126356101}, + {147706100, 126261901}, + {147749099, 126166000}, + {147817108, 126007507}, + {147859100, 125908599}, + {153693206, 111901100}, + {153731109, 111807800}, + {153760894, 111698806}, + {158641998, 92419303}, + {158644500, 92263702}, + {158539703, 92013504}, + {158499603, 91918899}, + {158335510, 91626800}, + {158264007, 91516304}, + {158216308, 91449203}, + {158178314, 91397506}, + {158094299, 91283203}, + {157396408, 90368202}, + {157285491, 90224700}, + {157169906, 90079200}, + {157050003, 89931304}, + {156290603, 89006805}, + {156221099, 88922897}, + {156087707, 88771003}, + {155947906, 88620498}, + {155348602, 88004203}, + {155113204, 87772796}, + {154947296, 87609703}, + {154776306, 87448204}, + {154588806, 87284301}, + {153886306, 86716400}, + {153682403, 86560501}, + {152966705, 86032402}, + {152687805, 85828704}, + {152484313, 85683204}, + {152278808, 85539001}, + {150878204, 84561401}, + {150683013, 84426498}, + {150599395, 84372703}, + {150395599, 84243202}, + {149988906, 83989395}, + {149782897, 83864501}, + {149568908, 83739799}, + {148872100, 83365303}, + {148625396, 83242202}, + {128079010, 73079605}, + {127980506, 73031005}, + {126701103, 72407104}, + {126501701, 72312202}, + {126431503, 72280601}, + {126311706, 72230606}, + {126260101, 72210899}, + {126191902, 72187599}, + {126140106, 72170303}, + {126088203, 72155303}, + {126036102, 72142700}, + {125965904, 72126899}, + {125913009, 72116600}, + {125859603, 72108505}, + {125788101, 72100296}, + {125733505, 72094398}, + {125678100, 72090400}, + {125621398, 72088302}, + {125548805, 72087303}, + {125490707, 72086898}, + {125430908, 72088203}, + {125369804, 72091094}, + {125306900, 72095306}, + {125233505, 72100997}, + {125168609, 72106506}, + {125102203, 72113601}, + {125034103, 72122207}, + {124964309, 72132095}, + {124890701, 72143707}, + {124819305, 72155105}, + {91355499, 77889099}, + {91355499, 77889205}, + }, + { + {84531845, 127391708}, + {84916946, 130417510}, + {86133247, 131166900}, + {86338447, 131292892}, + {86748847, 131544799}, + {102193946, 136599502}, + {103090942, 136796798}, + {103247146, 136822509}, + {104083549, 136911499}, + {106119346, 137109802}, + {106265853, 137122207}, + {106480247, 137139205}, + {110257850, 137133605}, + {116917747, 136131408}, + {117054946, 136106704}, + {119043945, 135244293}, + {119249046, 135154708}, + {136220947, 126833007}, + {165896347, 91517105}, + {166032546, 91314697}, + {166055435, 91204902}, + {166056152, 91176803}, + {166047256, 91100006}, + {166039733, 91063705}, + {165814849, 90080802}, + {165736450, 89837707}, + {165677246, 89732101}, + {165676956, 89731803}, + {165560241, 89629302}, + {154419952, 82608505}, + {153822143, 82239700}, + {137942749, 74046104}, + {137095245, 73845504}, + {135751342, 73537704}, + {134225952, 73208602}, + {132484344, 72860801}, + {124730346, 73902000}, + {120736549, 74464401}, + {100401245, 78685401}, + {90574645, 90625701}, + {90475944, 90748809}, + {90430747, 90808700}, + {90321548, 90958305}, + {90254852, 91077903}, + {90165641, 91244003}, + {90134941, 91302398}, + {84474647, 103745697}, + {84328048, 104137901}, + {84288543, 104327606}, + {84038047, 106164604}, + {84013351, 106368698}, + {83943847, 110643203}, + {84531845, 127391708}, + }, }; diff --git a/xs/src/libnest2d/tests/printer_parts.h b/xs/src/libnest2d/tests/printer_parts.h index 3d101810e..41791a189 100644 --- a/xs/src/libnest2d/tests/printer_parts.h +++ b/xs/src/libnest2d/tests/printer_parts.h @@ -2,8 +2,11 @@ #define PRINTER_PARTS_H #include -#include +#include -extern const std::vector PRINTER_PART_POLYGONS; +using TestData = std::vector; + +extern const TestData PRINTER_PART_POLYGONS; +extern const TestData STEGOSAUR_POLYGONS; #endif // PRINTER_PARTS_H diff --git a/xs/src/libnest2d/tests/svgtools.hpp b/xs/src/libnest2d/tests/svgtools.hpp new file mode 100644 index 000000000..5ede726f3 --- /dev/null +++ b/xs/src/libnest2d/tests/svgtools.hpp @@ -0,0 +1,112 @@ +#ifndef SVGTOOLS_HPP +#define SVGTOOLS_HPP + +#include +#include +#include + +#include +#include + +namespace libnest2d { namespace svg { + +class SVGWriter { +public: + + enum OrigoLocation { + TOPLEFT, + BOTTOMLEFT + }; + + struct Config { + OrigoLocation origo_location; + Coord mm_in_coord_units; + double width, height; + Config(): + origo_location(BOTTOMLEFT), mm_in_coord_units(1000000), + width(500), height(500) {} + + }; + +private: + Config conf_; + std::vector svg_layers_; + bool finished_ = false; +public: + + SVGWriter(const Config& conf = Config()): + conf_(conf) {} + + void setSize(const Box& box) { + conf_.height = static_cast(box.height()) / + conf_.mm_in_coord_units; + conf_.width = static_cast(box.width()) / + conf_.mm_in_coord_units; + } + + void writeItem(const Item& item) { + if(svg_layers_.empty()) addLayer(); + Item tsh(item.transformedShape()); + if(conf_.origo_location == BOTTOMLEFT) + for(unsigned i = 0; i < tsh.vertexCount(); i++) { + auto v = tsh.vertex(i); + setY(v, -getY(v) + conf_.height*conf_.mm_in_coord_units); + tsh.setVertex(i, v); + } + currentLayer() += ShapeLike::serialize(tsh.rawShape(), + 1.0/conf_.mm_in_coord_units) + "\n"; + } + + void writePackGroup(const PackGroup& result) { + for(auto r : result) { + addLayer(); + for(Item& sh : r) { + writeItem(sh); + } + finishLayer(); + } + } + + void addLayer() { + svg_layers_.emplace_back(header()); + finished_ = false; + } + + void finishLayer() { + currentLayer() += "\n\n"; + finished_ = true; + } + + void save(const std::string& filepath) { + unsigned lyrc = svg_layers_.size() > 1? 1 : 0; + unsigned last = svg_layers_.size() > 1? svg_layers_.size() : 0; + + for(auto& lyr : svg_layers_) { + std::fstream out(filepath + (lyrc > 0? std::to_string(lyrc) : "") + + ".svg", std::fstream::out); + if(out.is_open()) out << lyr; + if(lyrc == last && !finished_) out << "\n\n"; + out.flush(); out.close(); lyrc++; + }; + } + +private: + + std::string& currentLayer() { return svg_layers_.back(); } + + const std::string header() const { + std::string svg_header = +R"raw( + +)raw"; + return svg_header; + } + +}; + +} +} + +#endif // SVGTOOLS_HPP diff --git a/xs/src/libnest2d/tests/test.cpp b/xs/src/libnest2d/tests/test.cpp index c7fef3246..7ed7aa419 100644 --- a/xs/src/libnest2d/tests/test.cpp +++ b/xs/src/libnest2d/tests/test.cpp @@ -1,5 +1,4 @@ -#include "gtest/gtest.h" -#include "gmock/gmock.h" +#include #include #include @@ -7,6 +6,17 @@ #include #include +std::vector& prusaParts() { + static std::vector ret; + + if(ret.empty()) { + ret.reserve(PRINTER_PART_POLYGONS.size()); + for(auto& inp : PRINTER_PART_POLYGONS) ret.emplace_back(inp); + } + + return ret; +} + TEST(BasicFunctionality, Angles) { @@ -24,6 +34,44 @@ TEST(BasicFunctionality, Angles) ASSERT_TRUE(rad == deg); + Segment seg = {{0, 0}, {12, -10}}; + + ASSERT_TRUE(Degrees(seg.angleToXaxis()) > 270 && + Degrees(seg.angleToXaxis()) < 360); + + seg = {{0, 0}, {12, 10}}; + + ASSERT_TRUE(Degrees(seg.angleToXaxis()) > 0 && + Degrees(seg.angleToXaxis()) < 90); + + seg = {{0, 0}, {-12, 10}}; + + ASSERT_TRUE(Degrees(seg.angleToXaxis()) > 90 && + Degrees(seg.angleToXaxis()) < 180); + + seg = {{0, 0}, {-12, -10}}; + + ASSERT_TRUE(Degrees(seg.angleToXaxis()) > 180 && + Degrees(seg.angleToXaxis()) < 270); + + seg = {{0, 0}, {1, 0}}; + + ASSERT_DOUBLE_EQ(Degrees(seg.angleToXaxis()), 0); + + seg = {{0, 0}, {0, 1}}; + + ASSERT_DOUBLE_EQ(Degrees(seg.angleToXaxis()), 90); + + + seg = {{0, 0}, {-1, 0}}; + + ASSERT_DOUBLE_EQ(Degrees(seg.angleToXaxis()), 180); + + + seg = {{0, 0}, {0, -1}}; + + ASSERT_DOUBLE_EQ(Degrees(seg.angleToXaxis()), 270); + } // Simple test, does not use gmock @@ -33,21 +81,21 @@ TEST(BasicFunctionality, creationAndDestruction) Item sh = { {0, 0}, {1, 0}, {1, 1}, {0, 1} }; - ASSERT_EQ(sh.vertexCount(), 4); + ASSERT_EQ(sh.vertexCount(), 4u); Item sh2 ({ {0, 0}, {1, 0}, {1, 1}, {0, 1} }); - ASSERT_EQ(sh2.vertexCount(), 4); + ASSERT_EQ(sh2.vertexCount(), 4u); // copy Item sh3 = sh2; - ASSERT_EQ(sh3.vertexCount(), 4); + ASSERT_EQ(sh3.vertexCount(), 4u); sh2 = {}; - ASSERT_EQ(sh2.vertexCount(), 0); - ASSERT_EQ(sh3.vertexCount(), 4); + ASSERT_EQ(sh2.vertexCount(), 0u); + ASSERT_EQ(sh3.vertexCount(), 4u); } @@ -70,7 +118,8 @@ TEST(GeometryAlgorithms, Distance) { auto check = [](Coord val, Coord expected) { if(std::is_floating_point::value) - ASSERT_DOUBLE_EQ(static_cast(val), expected); + ASSERT_DOUBLE_EQ(static_cast(val), + static_cast(expected)); else ASSERT_EQ(val, expected); }; @@ -112,6 +161,18 @@ TEST(GeometryAlgorithms, Area) { ASSERT_EQ(rect2.area(), 10000); + Item item = { + {61, 97}, + {70, 151}, + {176, 151}, + {189, 138}, + {189, 59}, + {70, 59}, + {61, 77}, + {61, 97} + }; + + ASSERT_TRUE(ShapeLike::area(item.transformedShape()) > 0 ); } TEST(GeometryAlgorithms, IsPointInsidePolygon) { @@ -240,7 +301,7 @@ TEST(GeometryAlgorithms, ArrangeRectanglesTight) auto groups = arrange(rects.begin(), rects.end()); - ASSERT_EQ(groups.size(), 1); + ASSERT_EQ(groups.size(), 1u); ASSERT_EQ(groups[0].size(), rects.size()); // check for no intersections, no containment: @@ -294,7 +355,7 @@ TEST(GeometryAlgorithms, ArrangeRectanglesLoose) auto groups = arrange(rects.begin(), rects.end()); - ASSERT_EQ(groups.size(), 1); + ASSERT_EQ(groups.size(), 1u); ASSERT_EQ(groups[0].size(), rects.size()); // check for no intersections, no containment: @@ -363,7 +424,7 @@ R"raw( TEST(GeometryAlgorithms, BottomLeftStressTest) { using namespace libnest2d; - auto input = PRINTER_PART_POLYGONS; + auto& input = prusaParts(); Box bin(210, 250); BottomLeftPlacer placer(bin); @@ -399,73 +460,240 @@ TEST(GeometryAlgorithms, BottomLeftStressTest) { } } +namespace { + +struct ItemPair { + Item orbiter; + Item stationary; +}; + +std::vector nfp_testdata = { + { + { + {80, 50}, + {100, 70}, + {120, 50}, + {80, 50} + }, + { + {10, 10}, + {10, 40}, + {40, 40}, + {40, 10}, + {10, 10} + } + }, + { + { + {80, 50}, + {60, 70}, + {80, 90}, + {120, 90}, + {140, 70}, + {120, 50}, + {80, 50} + }, + { + {10, 10}, + {10, 40}, + {40, 40}, + {40, 10}, + {10, 10} + } + }, + { + { + {40, 10}, + {30, 10}, + {20, 20}, + {20, 30}, + {30, 40}, + {40, 40}, + {50, 30}, + {50, 20}, + {40, 10} + }, + { + {80, 0}, + {80, 30}, + {110, 30}, + {110, 0}, + {80, 0} + } + }, + { + { + {117, 107}, + {118, 109}, + {120, 112}, + {122, 113}, + {128, 113}, + {130, 112}, + {132, 109}, + {133, 107}, + {133, 103}, + {132, 101}, + {130, 98}, + {128, 97}, + {122, 97}, + {120, 98}, + {118, 101}, + {117, 103}, + {117, 107} + }, + { + {102, 116}, + {111, 126}, + {114, 126}, + {144, 106}, + {148, 100}, + {148, 85}, + {147, 84}, + {102, 84}, + {102, 116}, + } + }, + { + { + {99, 122}, + {108, 140}, + {110, 142}, + {139, 142}, + {151, 122}, + {151, 102}, + {142, 70}, + {139, 68}, + {111, 68}, + {108, 70}, + {99, 102}, + {99, 122}, + }, + { + {107, 124}, + {128, 125}, + {133, 125}, + {136, 124}, + {140, 121}, + {142, 119}, + {143, 116}, + {143, 109}, + {141, 93}, + {139, 89}, + {136, 86}, + {134, 85}, + {108, 85}, + {107, 86}, + {107, 124}, + } + }, + { + { + {91, 100}, + {94, 144}, + {117, 153}, + {118, 153}, + {159, 112}, + {159, 110}, + {156, 66}, + {133, 57}, + {132, 57}, + {91, 98}, + {91, 100}, + }, + { + {101, 90}, + {103, 98}, + {107, 113}, + {114, 125}, + {115, 126}, + {135, 126}, + {136, 125}, + {144, 114}, + {149, 90}, + {149, 89}, + {148, 87}, + {145, 84}, + {105, 84}, + {102, 87}, + {101, 89}, + {101, 90}, + } + } +}; + +} + TEST(GeometryAlgorithms, nfpConvexConvex) { using namespace libnest2d; - const unsigned long SCALE = 1; + const Coord SCALE = 1000000; Box bin(210*SCALE, 250*SCALE); - Item stationary = { - {120, 114}, - {130, 114}, - {130, 103}, - {128, 96}, - {122, 96}, - {120, 103}, - {120, 114} - }; + int testcase = 0; - Item orbiter = { - {72, 147}, - {94, 151}, - {178, 151}, - {178, 59}, - {72, 59}, - {72, 147} - }; + auto& exportfun = exportSVG<1, Box>; - orbiter.translate({210*SCALE, 0}); + auto onetest = [&](Item& orbiter, Item& stationary){ + testcase++; - auto&& nfp = Nfp::noFitPolygon(stationary.rawShape(), - orbiter.transformedShape()); + orbiter.translate({210*SCALE, 0}); - auto v = ShapeLike::isValid(nfp); + auto&& nfp = Nfp::noFitPolygon(stationary.rawShape(), + orbiter.transformedShape()); - if(!v.first) { - std::cout << v.second << std::endl; - } + auto v = ShapeLike::isValid(nfp); - ASSERT_TRUE(v.first); + if(!v.first) { + std::cout << v.second << std::endl; + } - Item infp(nfp); + ASSERT_TRUE(v.first); - int i = 0; - auto rorbiter = orbiter.transformedShape(); - auto vo = *(ShapeLike::begin(rorbiter)); - for(auto v : infp) { - auto dx = getX(v) - getX(vo); - auto dy = getY(v) - getY(vo); + Item infp(nfp); + + int i = 0; + auto rorbiter = orbiter.transformedShape(); + auto vo = Nfp::referenceVertex(rorbiter); - Item tmp = orbiter; + ASSERT_TRUE(stationary.isInside(infp)); - tmp.translate({dx, dy}); + for(auto v : infp) { + auto dx = getX(v) - getX(vo); + auto dy = getY(v) - getY(vo); - bool notinside = !tmp.isInside(stationary); - bool notintersecting = !Item::intersects(tmp, stationary); + Item tmp = orbiter; - if(!(notinside && notintersecting)) { - std::vector> inp = { - std::ref(stationary), std::ref(tmp), std::ref(infp) - }; + tmp.translate({dx, dy}); - exportSVG(inp, bin, i++); + bool notinside = !tmp.isInside(stationary); + bool notintersecting = !Item::intersects(tmp, stationary) || + Item::touches(tmp, stationary); + + if(!(notinside && notintersecting)) { + std::vector> inp = { + std::ref(stationary), std::ref(tmp), std::ref(infp) + }; + + exportfun(inp, bin, testcase*i++); + } + + ASSERT_TRUE(notintersecting); + ASSERT_TRUE(notinside); } + }; - //ASSERT_TRUE(notintersecting); - ASSERT_TRUE(notinside); + for(auto& td : nfp_testdata) { + auto orbiter = td.orbiter; + auto stationary = td.stationary; + onetest(orbiter, stationary); } + for(auto& td : nfp_testdata) { + auto orbiter = td.stationary; + auto stationary = td.orbiter; + onetest(orbiter, stationary); + } } int main(int argc, char **argv) { -- cgit v1.2.3