diff options
| author | bubnikv <bubnikv@gmail.com> | 2018-09-14 16:03:38 +0300 |
|---|---|---|
| committer | bubnikv <bubnikv@gmail.com> | 2018-09-14 16:03:38 +0300 |
| commit | 7fc0b4375c43ebb8dcb8e198cc1babdd78da866e (patch) | |
| tree | 5fd9da1f0b308ce5440d7a432d169d99bf7a8273 /xs/src/libnest2d | |
| parent | a0e2df5dbb26079e5220fdc6fce02f5200c1421e (diff) | |
| parent | 1acee8900695b7060f2ee136b4da8e3778b407cb (diff) | |
Merge remote-tracking branch 'origin/parallel_arrange'
Diffstat (limited to 'xs/src/libnest2d')
27 files changed, 2896 insertions, 1507 deletions
diff --git a/xs/src/libnest2d/CMakeLists.txt b/xs/src/libnest2d/CMakeLists.txt index 835e8311d..f81355012 100644 --- a/xs/src/libnest2d/CMakeLists.txt +++ b/xs/src/libnest2d/CMakeLists.txt @@ -31,6 +31,7 @@ set(LIBNEST2D_SRCFILES ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/common.hpp ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/optimizer.hpp ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/metaloop.hpp + ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/rotfinder.hpp ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/placers/placer_boilerplate.hpp ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/placers/bottomleftplacer.hpp ${CMAKE_CURRENT_SOURCE_DIR}/libnest2d/placers/nfpplacer.hpp @@ -89,14 +90,39 @@ if(LIBNEST2D_UNITTESTS) endif() if(LIBNEST2D_BUILD_EXAMPLES) + add_executable(example examples/main.cpp # tools/libnfpglue.hpp # tools/libnfpglue.cpp + tools/nfp_svgnest.hpp + tools/nfp_svgnest_glue.hpp tools/svgtools.hpp tests/printer_parts.cpp tests/printer_parts.h - ${LIBNEST2D_SRCFILES}) - + ${LIBNEST2D_SRCFILES} + ) + set(TBB_STATIC ON) + find_package(TBB QUIET) + if(TBB_FOUND) + message(STATUS "Parallelization with Intel TBB") + target_include_directories(example PUBLIC ${TBB_INCLUDE_DIRS}) + target_compile_definitions(example PUBLIC ${TBB_DEFINITIONS} -DUSE_TBB) + if(MSVC) + # Suppress implicit linking of the TBB libraries by the Visual Studio compiler. + target_compile_definitions(example PUBLIC -D__TBB_NO_IMPLICIT_LINKAGE) + endif() + # The Intel TBB library will use the std::exception_ptr feature of C++11. + target_compile_definitions(example PUBLIC -DTBB_USE_CAPTURED_EXCEPTION=1) + + target_link_libraries(example ${TBB_LIBRARIES}) + else() + find_package(OpenMP QUIET) + if(OpenMP_CXX_FOUND) + message(STATUS "Parallelization with OpenMP") + target_include_directories(example PUBLIC OpenMP::OpenMP_CXX) + target_link_libraries(example OpenMP::OpenMP_CXX) + endif() + endif() target_link_libraries(example ${LIBNEST2D_LIBRARIES}) target_include_directories(example PUBLIC ${LIBNEST2D_HEADERS}) diff --git a/xs/src/libnest2d/README.md b/xs/src/libnest2d/README.md index 3508801a8..61a7ac7d0 100644 --- a/xs/src/libnest2d/README.md +++ b/xs/src/libnest2d/README.md @@ -9,18 +9,28 @@ with templated geometry types. These geometries can have custom or already existing implementation to avoid copying or having unnecessary dependencies. A default backend is provided if the user of the library just wants to use it -out of the box without additional integration. The default backend is reasonably +out of the box without additional integration. This backend is reasonably fast and robust, being built on top of boost geometry and the [polyclipping](http://www.angusj.com/delphi/clipper.php) library. Usage of -this default backend implies the dependency on these packages as well as the -compilation of the backend itself (The default backend is not yet header only). +this default backend implies the dependency on these packages but its header +only as well. This software is currently under construction and lacks a throughout documentation and some essential algorithms as well. At this stage it works well for rectangles and convex closed polygons without considering holes and concavities. -Holes and non-convex polygons will be usable in the near future as well. +Holes and non-convex polygons will be usable in the near future as well. The +no fit polygon based placer module combined with the first fit selection +strategy is now used in the [Slic3r](https://github.com/prusa3d/Slic3r) +application's arrangement feature. It uses local optimization techniques to find +the best placement of each new item based on some features of the arrangement. + +In the near future I would like to use machine learning to evaluate the +placements and (or) the order if items in which they are placed and see what +results can be obtained. This is a different approach than that of SVGnest which +uses genetic algorithms to find better and better selection orders. Maybe the +two approaches can be combined as well. # References - [SVGNest](https://github.com/Jack000/SVGnest) diff --git a/xs/src/libnest2d/cmake_modules/FindTBB.cmake b/xs/src/libnest2d/cmake_modules/FindTBB.cmake new file mode 100644 index 000000000..8b498d3ab --- /dev/null +++ b/xs/src/libnest2d/cmake_modules/FindTBB.cmake @@ -0,0 +1,322 @@ +# The MIT License (MIT) +# +# Copyright (c) 2015 Justus Calvin +# +# Permission is hereby granted, free of charge, to any person obtaining a copy +# of this software and associated documentation files (the "Software"), to deal +# in the Software without restriction, including without limitation the rights +# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the Software is +# furnished to do so, subject to the following conditions: +# +# The above copyright notice and this permission notice shall be included in all +# copies or substantial portions of the Software. +# +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +# SOFTWARE. + +# +# FindTBB +# ------- +# +# Find TBB include directories and libraries. +# +# Usage: +# +# find_package(TBB [major[.minor]] [EXACT] +# [QUIET] [REQUIRED] +# [[COMPONENTS] [components...]] +# [OPTIONAL_COMPONENTS components...]) +# +# where the allowed components are tbbmalloc and tbb_preview. Users may modify +# the behavior of this module with the following variables: +# +# * TBB_ROOT_DIR - The base directory the of TBB installation. +# * TBB_INCLUDE_DIR - The directory that contains the TBB headers files. +# * TBB_LIBRARY - The directory that contains the TBB library files. +# * TBB_<library>_LIBRARY - The path of the TBB the corresponding TBB library. +# These libraries, if specified, override the +# corresponding library search results, where <library> +# may be tbb, tbb_debug, tbbmalloc, tbbmalloc_debug, +# tbb_preview, or tbb_preview_debug. +# * TBB_USE_DEBUG_BUILD - The debug version of tbb libraries, if present, will +# be used instead of the release version. +# * TBB_STATIC - Static linking of libraries with a _static suffix. +# For example, on Windows a tbb_static.lib will be searched for +# instead of tbb.lib. +# +# Users may modify the behavior of this module with the following environment +# variables: +# +# * TBB_INSTALL_DIR +# * TBBROOT +# * LIBRARY_PATH +# +# This module will set the following variables: +# +# * TBB_FOUND - Set to false, or undefined, if we haven’t found, or +# don’t want to use TBB. +# * TBB_<component>_FOUND - If False, optional <component> part of TBB sytem is +# not available. +# * TBB_VERSION - The full version string +# * TBB_VERSION_MAJOR - The major version +# * TBB_VERSION_MINOR - The minor version +# * TBB_INTERFACE_VERSION - The interface version number defined in +# tbb/tbb_stddef.h. +# * TBB_<library>_LIBRARY_RELEASE - The path of the TBB release version of +# <library>, where <library> may be tbb, tbb_debug, +# tbbmalloc, tbbmalloc_debug, tbb_preview, or +# tbb_preview_debug. +# * TBB_<library>_LIBRARY_DEGUG - The path of the TBB release version of +# <library>, where <library> may be tbb, tbb_debug, +# tbbmalloc, tbbmalloc_debug, tbb_preview, or +# tbb_preview_debug. +# +# The following varibles should be used to build and link with TBB: +# +# * TBB_INCLUDE_DIRS - The include directory for TBB. +# * TBB_LIBRARIES - The libraries to link against to use TBB. +# * TBB_LIBRARIES_RELEASE - The release libraries to link against to use TBB. +# * TBB_LIBRARIES_DEBUG - The debug libraries to link against to use TBB. +# * TBB_DEFINITIONS - Definitions to use when compiling code that uses +# TBB. +# * TBB_DEFINITIONS_RELEASE - Definitions to use when compiling release code that +# uses TBB. +# * TBB_DEFINITIONS_DEBUG - Definitions to use when compiling debug code that +# uses TBB. +# +# This module will also create the "tbb" target that may be used when building +# executables and libraries. + +include(FindPackageHandleStandardArgs) + +if(NOT TBB_FOUND) + + ################################## + # Check the build type + ################################## + + if(NOT DEFINED TBB_USE_DEBUG_BUILD) + if(CMAKE_BUILD_TYPE MATCHES "(Debug|DEBUG|debug)") + set(TBB_BUILD_TYPE DEBUG) + else() + set(TBB_BUILD_TYPE RELEASE) + endif() + elseif(TBB_USE_DEBUG_BUILD) + set(TBB_BUILD_TYPE DEBUG) + else() + set(TBB_BUILD_TYPE RELEASE) + endif() + + ################################## + # Set the TBB search directories + ################################## + + # Define search paths based on user input and environment variables + set(TBB_SEARCH_DIR ${TBB_ROOT_DIR} $ENV{TBB_INSTALL_DIR} $ENV{TBBROOT}) + + # Define the search directories based on the current platform + if(CMAKE_SYSTEM_NAME STREQUAL "Windows") + set(TBB_DEFAULT_SEARCH_DIR "C:/Program Files/Intel/TBB" + "C:/Program Files (x86)/Intel/TBB") + + # Set the target architecture + if(CMAKE_SIZEOF_VOID_P EQUAL 8) + set(TBB_ARCHITECTURE "intel64") + else() + set(TBB_ARCHITECTURE "ia32") + endif() + + # Set the TBB search library path search suffix based on the version of VC + if(WINDOWS_STORE) + set(TBB_LIB_PATH_SUFFIX "lib/${TBB_ARCHITECTURE}/vc11_ui") + elseif(MSVC14) + set(TBB_LIB_PATH_SUFFIX "lib/${TBB_ARCHITECTURE}/vc14") + elseif(MSVC12) + set(TBB_LIB_PATH_SUFFIX "lib/${TBB_ARCHITECTURE}/vc12") + elseif(MSVC11) + set(TBB_LIB_PATH_SUFFIX "lib/${TBB_ARCHITECTURE}/vc11") + elseif(MSVC10) + set(TBB_LIB_PATH_SUFFIX "lib/${TBB_ARCHITECTURE}/vc10") + endif() + + # Add the library path search suffix for the VC independent version of TBB + list(APPEND TBB_LIB_PATH_SUFFIX "lib/${TBB_ARCHITECTURE}/vc_mt") + + elseif(CMAKE_SYSTEM_NAME STREQUAL "Darwin") + # OS X + set(TBB_DEFAULT_SEARCH_DIR "/opt/intel/tbb") + + # TODO: Check to see which C++ library is being used by the compiler. + if(NOT ${CMAKE_SYSTEM_VERSION} VERSION_LESS 13.0) + # The default C++ library on OS X 10.9 and later is libc++ + set(TBB_LIB_PATH_SUFFIX "lib/libc++" "lib") + else() + set(TBB_LIB_PATH_SUFFIX "lib") + endif() + elseif(CMAKE_SYSTEM_NAME STREQUAL "Linux") + # Linux + set(TBB_DEFAULT_SEARCH_DIR "/opt/intel/tbb") + + # TODO: Check compiler version to see the suffix should be <arch>/gcc4.1 or + # <arch>/gcc4.1. For now, assume that the compiler is more recent than + # gcc 4.4.x or later. + if(CMAKE_SYSTEM_PROCESSOR STREQUAL "x86_64") + set(TBB_LIB_PATH_SUFFIX "lib/intel64/gcc4.4") + elseif(CMAKE_SYSTEM_PROCESSOR MATCHES "^i.86$") + set(TBB_LIB_PATH_SUFFIX "lib/ia32/gcc4.4") + endif() + endif() + + ################################## + # Find the TBB include dir + ################################## + + find_path(TBB_INCLUDE_DIRS tbb/tbb.h + HINTS ${TBB_INCLUDE_DIR} ${TBB_SEARCH_DIR} + PATHS ${TBB_DEFAULT_SEARCH_DIR} + PATH_SUFFIXES include) + + ################################## + # Set version strings + ################################## + + if(TBB_INCLUDE_DIRS) + file(READ "${TBB_INCLUDE_DIRS}/tbb/tbb_stddef.h" _tbb_version_file) + string(REGEX REPLACE ".*#define TBB_VERSION_MAJOR ([0-9]+).*" "\\1" + TBB_VERSION_MAJOR "${_tbb_version_file}") + string(REGEX REPLACE ".*#define TBB_VERSION_MINOR ([0-9]+).*" "\\1" + TBB_VERSION_MINOR "${_tbb_version_file}") + string(REGEX REPLACE ".*#define TBB_INTERFACE_VERSION ([0-9]+).*" "\\1" + TBB_INTERFACE_VERSION "${_tbb_version_file}") + set(TBB_VERSION "${TBB_VERSION_MAJOR}.${TBB_VERSION_MINOR}") + endif() + + ################################## + # Find TBB components + ################################## + + if(TBB_VERSION VERSION_LESS 4.3) + set(TBB_SEARCH_COMPOMPONENTS tbb_preview tbbmalloc tbb) + else() + set(TBB_SEARCH_COMPOMPONENTS tbb_preview tbbmalloc_proxy tbbmalloc tbb) + endif() + + if(TBB_STATIC) + set(TBB_STATIC_SUFFIX "_static") + endif() + + # Find each component + foreach(_comp ${TBB_SEARCH_COMPOMPONENTS}) + if(";${TBB_FIND_COMPONENTS};tbb;" MATCHES ";${_comp};") + + # Search for the libraries + find_library(TBB_${_comp}_LIBRARY_RELEASE ${_comp}${TBB_STATIC_SUFFIX} + HINTS ${TBB_LIBRARY} ${TBB_SEARCH_DIR} + PATHS ${TBB_DEFAULT_SEARCH_DIR} ENV LIBRARY_PATH + PATH_SUFFIXES ${TBB_LIB_PATH_SUFFIX}) + + find_library(TBB_${_comp}_LIBRARY_DEBUG ${_comp}${TBB_STATIC_SUFFIX}_debug + HINTS ${TBB_LIBRARY} ${TBB_SEARCH_DIR} + PATHS ${TBB_DEFAULT_SEARCH_DIR} ENV LIBRARY_PATH + PATH_SUFFIXES ${TBB_LIB_PATH_SUFFIX}) + + if(TBB_${_comp}_LIBRARY_DEBUG) + list(APPEND TBB_LIBRARIES_DEBUG "${TBB_${_comp}_LIBRARY_DEBUG}") + endif() + if(TBB_${_comp}_LIBRARY_RELEASE) + list(APPEND TBB_LIBRARIES_RELEASE "${TBB_${_comp}_LIBRARY_RELEASE}") + endif() + if(TBB_${_comp}_LIBRARY_${TBB_BUILD_TYPE} AND NOT TBB_${_comp}_LIBRARY) + set(TBB_${_comp}_LIBRARY "${TBB_${_comp}_LIBRARY_${TBB_BUILD_TYPE}}") + endif() + + if(TBB_${_comp}_LIBRARY AND EXISTS "${TBB_${_comp}_LIBRARY}") + set(TBB_${_comp}_FOUND TRUE) + else() + set(TBB_${_comp}_FOUND FALSE) + endif() + + # Mark internal variables as advanced + mark_as_advanced(TBB_${_comp}_LIBRARY_RELEASE) + mark_as_advanced(TBB_${_comp}_LIBRARY_DEBUG) + mark_as_advanced(TBB_${_comp}_LIBRARY) + + endif() + endforeach() + + unset(TBB_STATIC_SUFFIX) + + ################################## + # Set compile flags and libraries + ################################## + + set(TBB_DEFINITIONS_RELEASE "") + set(TBB_DEFINITIONS_DEBUG "-DTBB_USE_DEBUG=1") + + if(TBB_LIBRARIES_${TBB_BUILD_TYPE}) + set(TBB_DEFINITIONS "${TBB_DEFINITIONS_${TBB_BUILD_TYPE}}") + set(TBB_LIBRARIES "${TBB_LIBRARIES_${TBB_BUILD_TYPE}}") + elseif(TBB_LIBRARIES_RELEASE) + set(TBB_DEFINITIONS "${TBB_DEFINITIONS_RELEASE}") + set(TBB_LIBRARIES "${TBB_LIBRARIES_RELEASE}") + elseif(TBB_LIBRARIES_DEBUG) + set(TBB_DEFINITIONS "${TBB_DEFINITIONS_DEBUG}") + set(TBB_LIBRARIES "${TBB_LIBRARIES_DEBUG}") + endif() + + find_package_handle_standard_args(TBB + REQUIRED_VARS TBB_INCLUDE_DIRS TBB_LIBRARIES + HANDLE_COMPONENTS + VERSION_VAR TBB_VERSION) + + ################################## + # Create targets + ################################## + + if(NOT CMAKE_VERSION VERSION_LESS 3.0 AND TBB_FOUND) + add_library(tbb SHARED IMPORTED) + set_target_properties(tbb PROPERTIES + INTERFACE_INCLUDE_DIRECTORIES ${TBB_INCLUDE_DIRS} + IMPORTED_LOCATION ${TBB_LIBRARIES}) + if(TBB_LIBRARIES_RELEASE AND TBB_LIBRARIES_DEBUG) + set_target_properties(tbb PROPERTIES + INTERFACE_COMPILE_DEFINITIONS "$<$<OR:$<CONFIG:Debug>,$<CONFIG:RelWithDebInfo>>:TBB_USE_DEBUG=1>" + IMPORTED_LOCATION_DEBUG ${TBB_LIBRARIES_DEBUG} + IMPORTED_LOCATION_RELWITHDEBINFO ${TBB_LIBRARIES_DEBUG} + IMPORTED_LOCATION_RELEASE ${TBB_LIBRARIES_RELEASE} + IMPORTED_LOCATION_MINSIZEREL ${TBB_LIBRARIES_RELEASE} + ) + elseif(TBB_LIBRARIES_RELEASE) + set_target_properties(tbb PROPERTIES IMPORTED_LOCATION ${TBB_LIBRARIES_RELEASE}) + else() + set_target_properties(tbb PROPERTIES + INTERFACE_COMPILE_DEFINITIONS "${TBB_DEFINITIONS_DEBUG}" + IMPORTED_LOCATION ${TBB_LIBRARIES_DEBUG} + ) + endif() + endif() + + mark_as_advanced(TBB_INCLUDE_DIRS TBB_LIBRARIES) + + unset(TBB_ARCHITECTURE) + unset(TBB_BUILD_TYPE) + unset(TBB_LIB_PATH_SUFFIX) + unset(TBB_DEFAULT_SEARCH_DIR) + + if(TBB_DEBUG) + message(STATUS " TBB_INCLUDE_DIRS = ${TBB_INCLUDE_DIRS}") + message(STATUS " TBB_DEFINITIONS = ${TBB_DEFINITIONS}") + message(STATUS " TBB_LIBRARIES = ${TBB_LIBRARIES}") + message(STATUS " TBB_DEFINITIONS_DEBUG = ${TBB_DEFINITIONS_DEBUG}") + message(STATUS " TBB_LIBRARIES_DEBUG = ${TBB_LIBRARIES_DEBUG}") + message(STATUS " TBB_DEFINITIONS_RELEASE = ${TBB_DEFINITIONS_RELEASE}") + message(STATUS " TBB_LIBRARIES_RELEASE = ${TBB_LIBRARIES_RELEASE}") + endif() + +endif() diff --git a/xs/src/libnest2d/examples/main.cpp b/xs/src/libnest2d/examples/main.cpp index d6b2ccc34..ebc3fb15c 100644 --- a/xs/src/libnest2d/examples/main.cpp +++ b/xs/src/libnest2d/examples/main.cpp @@ -1,7 +1,6 @@ #include <iostream> #include <string> #include <fstream> - //#define DEBUG_EXPORT_NFP #include <libnest2d.h> @@ -9,7 +8,11 @@ #include "tests/printer_parts.h" #include "tools/benchmark.h" #include "tools/svgtools.hpp" +#include "libnest2d/rotfinder.hpp" + //#include "tools/libnfpglue.hpp" +//#include "tools/nfp_svgnest_glue.hpp" + using namespace libnest2d; using ItemGroup = std::vector<std::reference_wrapper<Item>>; @@ -50,499 +53,57 @@ void arrangeRectangles() { using namespace libnest2d; const int SCALE = 1000000; -// const int SCALE = 1; - std::vector<Rectangle> rects = { - {80*SCALE, 80*SCALE}, - {60*SCALE, 90*SCALE}, - {70*SCALE, 30*SCALE}, - {80*SCALE, 60*SCALE}, - {60*SCALE, 60*SCALE}, - {60*SCALE, 40*SCALE}, - {40*SCALE, 40*SCALE}, - {10*SCALE, 10*SCALE}, - {10*SCALE, 10*SCALE}, - {10*SCALE, 10*SCALE}, - {10*SCALE, 10*SCALE}, - {10*SCALE, 10*SCALE}, - {5*SCALE, 5*SCALE}, - {5*SCALE, 5*SCALE}, - {5*SCALE, 5*SCALE}, - {5*SCALE, 5*SCALE}, - {5*SCALE, 5*SCALE}, - {5*SCALE, 5*SCALE}, - {5*SCALE, 5*SCALE}, - {20*SCALE, 20*SCALE} - }; - -// std::vector<Rectangle> rects = { -// {20*SCALE, 10*SCALE}, -// {20*SCALE, 10*SCALE}, -// {20*SCALE, 20*SCALE}, -// }; -// std::vector<Item> input { -// {{0, 0}, {0, 20*SCALE}, {10*SCALE, 0}, {0, 0}} -// }; - - std::vector<Item> crasher = - { - { - {-5000000, 8954050}, - {5000000, 8954050}, - {5000000, -45949}, - {4972609, -568549}, - {3500000, -8954050}, - {-3500000, -8954050}, - {-4972609, -568549}, - {-5000000, -45949}, - {-5000000, 8954050}, - }, - { - {-5000000, 8954050}, - {5000000, 8954050}, - {5000000, -45949}, - {4972609, -568549}, - {3500000, -8954050}, - {-3500000, -8954050}, - {-4972609, -568549}, - {-5000000, -45949}, - {-5000000, 8954050}, - }, - { - {-5000000, 8954050}, - {5000000, 8954050}, - {5000000, -45949}, - {4972609, -568549}, - {3500000, -8954050}, - {-3500000, -8954050}, - {-4972609, -568549}, - {-5000000, -45949}, - {-5000000, 8954050}, - }, - { - {-5000000, 8954050}, - {5000000, 8954050}, - {5000000, -45949}, - {4972609, -568549}, - {3500000, -8954050}, - {-3500000, -8954050}, - {-4972609, -568549}, - {-5000000, -45949}, - {-5000000, 8954050}, - }, - { - {-5000000, 8954050}, - {5000000, 8954050}, - {5000000, -45949}, - {4972609, -568549}, - {3500000, -8954050}, - {-3500000, -8954050}, - {-4972609, -568549}, - {-5000000, -45949}, - {-5000000, 8954050}, - }, - { - {-5000000, 8954050}, - {5000000, 8954050}, - {5000000, -45949}, - {4972609, -568549}, - {3500000, -8954050}, - {-3500000, -8954050}, - {-4972609, -568549}, - {-5000000, -45949}, - {-5000000, 8954050}, - }, - { - {-9945219, -3065619}, - {-9781479, -2031780}, - {-9510560, -1020730}, - {-9135450, -43529}, - {-2099999, 14110899}, - {2099999, 14110899}, - {9135450, -43529}, - {9510560, -1020730}, - {9781479, -2031780}, - {9945219, -3065619}, - {10000000, -4110899}, - {9945219, -5156179}, - {9781479, -6190020}, - {9510560, -7201069}, - {9135450, -8178270}, - {8660249, -9110899}, - {8090169, -9988750}, - {7431449, -10802200}, - {6691309, -11542300}, - {5877850, -12201100}, - {5000000, -12771100}, - {4067369, -13246399}, - {3090169, -13621500}, - {2079119, -13892399}, - {1045279, -14056099}, - {0, -14110899}, - {-1045279, -14056099}, - {-2079119, -13892399}, - {-3090169, -13621500}, - {-4067369, -13246399}, - {-5000000, -12771100}, - {-5877850, -12201100}, - {-6691309, -11542300}, - {-7431449, -10802200}, - {-8090169, -9988750}, - {-8660249, -9110899}, - {-9135450, -8178270}, - {-9510560, -7201069}, - {-9781479, -6190020}, - {-9945219, -5156179}, - {-10000000, -4110899}, - {-9945219, -3065619}, - }, - { - {-9945219, -3065619}, - {-9781479, -2031780}, - {-9510560, -1020730}, - {-9135450, -43529}, - {-2099999, 14110899}, - {2099999, 14110899}, - {9135450, -43529}, - {9510560, -1020730}, - {9781479, -2031780}, - {9945219, -3065619}, - {10000000, -4110899}, - {9945219, -5156179}, - {9781479, -6190020}, - {9510560, -7201069}, - {9135450, -8178270}, - {8660249, -9110899}, - {8090169, -9988750}, - {7431449, -10802200}, - {6691309, -11542300}, - {5877850, -12201100}, - {5000000, -12771100}, - {4067369, -13246399}, - {3090169, -13621500}, - {2079119, -13892399}, - {1045279, -14056099}, - {0, -14110899}, - {-1045279, -14056099}, - {-2079119, -13892399}, - {-3090169, -13621500}, - {-4067369, -13246399}, - {-5000000, -12771100}, - {-5877850, -12201100}, - {-6691309, -11542300}, - {-7431449, -10802200}, - {-8090169, -9988750}, - {-8660249, -9110899}, - {-9135450, -8178270}, - {-9510560, -7201069}, - {-9781479, -6190020}, - {-9945219, -5156179}, - {-10000000, -4110899}, - {-9945219, -3065619}, - }, - { - {-9945219, -3065619}, - {-9781479, -2031780}, - {-9510560, -1020730}, - {-9135450, -43529}, - {-2099999, 14110899}, - {2099999, 14110899}, - {9135450, -43529}, - {9510560, -1020730}, - {9781479, -2031780}, - {9945219, -3065619}, - {10000000, -4110899}, - {9945219, -5156179}, - {9781479, -6190020}, - {9510560, -7201069}, - {9135450, -8178270}, - {8660249, -9110899}, - {8090169, -9988750}, - {7431449, -10802200}, - {6691309, -11542300}, - {5877850, -12201100}, - {5000000, -12771100}, - {4067369, -13246399}, - {3090169, -13621500}, - {2079119, -13892399}, - {1045279, -14056099}, - {0, -14110899}, - {-1045279, -14056099}, - {-2079119, -13892399}, - {-3090169, -13621500}, - {-4067369, -13246399}, - {-5000000, -12771100}, - {-5877850, -12201100}, - {-6691309, -11542300}, - {-7431449, -10802200}, - {-8090169, -9988750}, - {-8660249, -9110899}, - {-9135450, -8178270}, - {-9510560, -7201069}, - {-9781479, -6190020}, - {-9945219, -5156179}, - {-10000000, -4110899}, - {-9945219, -3065619}, - }, - { - {-9945219, -3065619}, - {-9781479, -2031780}, - {-9510560, -1020730}, - {-9135450, -43529}, - {-2099999, 14110899}, - {2099999, 14110899}, - {9135450, -43529}, - {9510560, -1020730}, - {9781479, -2031780}, - {9945219, -3065619}, - {10000000, -4110899}, - {9945219, -5156179}, - {9781479, -6190020}, - {9510560, -7201069}, - {9135450, -8178270}, - {8660249, -9110899}, - {8090169, -9988750}, - {7431449, -10802200}, - {6691309, -11542300}, - {5877850, -12201100}, - {5000000, -12771100}, - {4067369, -13246399}, - {3090169, -13621500}, - {2079119, -13892399}, - {1045279, -14056099}, - {0, -14110899}, - {-1045279, -14056099}, - {-2079119, -13892399}, - {-3090169, -13621500}, - {-4067369, -13246399}, - {-5000000, -12771100}, - {-5877850, -12201100}, - {-6691309, -11542300}, - {-7431449, -10802200}, - {-8090169, -9988750}, - {-8660249, -9110899}, - {-9135450, -8178270}, - {-9510560, -7201069}, - {-9781479, -6190020}, - {-9945219, -5156179}, - {-10000000, -4110899}, - {-9945219, -3065619}, - }, - { - {-9945219, -3065619}, - {-9781479, -2031780}, - {-9510560, -1020730}, - {-9135450, -43529}, - {-2099999, 14110899}, - {2099999, 14110899}, - {9135450, -43529}, - {9510560, -1020730}, - {9781479, -2031780}, - {9945219, -3065619}, - {10000000, -4110899}, - {9945219, -5156179}, - {9781479, -6190020}, - {9510560, -7201069}, - {9135450, -8178270}, - {8660249, -9110899}, - {8090169, -9988750}, - {7431449, -10802200}, - {6691309, -11542300}, - {5877850, -12201100}, - {5000000, -12771100}, - {4067369, -13246399}, - {3090169, -13621500}, - {2079119, -13892399}, - {1045279, -14056099}, - {0, -14110899}, - {-1045279, -14056099}, - {-2079119, -13892399}, - {-3090169, -13621500}, - {-4067369, -13246399}, - {-5000000, -12771100}, - {-5877850, -12201100}, - {-6691309, -11542300}, - {-7431449, -10802200}, - {-8090169, -9988750}, - {-8660249, -9110899}, - {-9135450, -8178270}, - {-9510560, -7201069}, - {-9781479, -6190020}, - {-9945219, -5156179}, - {-10000000, -4110899}, - {-9945219, -3065619}, - }, - { - {-9945219, -3065619}, - {-9781479, -2031780}, - {-9510560, -1020730}, - {-9135450, -43529}, - {-2099999, 14110899}, - {2099999, 14110899}, - {9135450, -43529}, - {9510560, -1020730}, - {9781479, -2031780}, - {9945219, -3065619}, - {10000000, -4110899}, - {9945219, -5156179}, - {9781479, -6190020}, - {9510560, -7201069}, - {9135450, -8178270}, - {8660249, -9110899}, - {8090169, -9988750}, - {7431449, -10802200}, - {6691309, -11542300}, - {5877850, -12201100}, - {5000000, -12771100}, - {4067369, -13246399}, - {3090169, -13621500}, - {2079119, -13892399}, - {1045279, -14056099}, - {0, -14110899}, - {-1045279, -14056099}, - {-2079119, -13892399}, - {-3090169, -13621500}, - {-4067369, -13246399}, - {-5000000, -12771100}, - {-5877850, -12201100}, - {-6691309, -11542300}, - {-7431449, -10802200}, - {-8090169, -9988750}, - {-8660249, -9110899}, - {-9135450, -8178270}, - {-9510560, -7201069}, - {-9781479, -6190020}, - {-9945219, -5156179}, - {-10000000, -4110899}, - {-9945219, -3065619}, - }, - { - {-9945219, -3065619}, - {-9781479, -2031780}, - {-9510560, -1020730}, - {-9135450, -43529}, - {-2099999, 14110899}, - {2099999, 14110899}, - {9135450, -43529}, - {9510560, -1020730}, - {9781479, -2031780}, - {9945219, -3065619}, - {10000000, -4110899}, - {9945219, -5156179}, - {9781479, -6190020}, - {9510560, -7201069}, - {9135450, -8178270}, - {8660249, -9110899}, - {8090169, -9988750}, - {7431449, -10802200}, - {6691309, -11542300}, - {5877850, -12201100}, - {5000000, -12771100}, - {4067369, -13246399}, - {3090169, -13621500}, - {2079119, -13892399}, - {1045279, -14056099}, - {0, -14110899}, - {-1045279, -14056099}, - {-2079119, -13892399}, - {-3090169, -13621500}, - {-4067369, -13246399}, - {-5000000, -12771100}, - {-5877850, -12201100}, - {-6691309, -11542300}, - {-7431449, -10802200}, - {-8090169, -9988750}, - {-8660249, -9110899}, - {-9135450, -8178270}, - {-9510560, -7201069}, - {-9781479, -6190020}, - {-9945219, -5156179}, - {-10000000, -4110899}, - {-9945219, -3065619}, - }, - { - {-9945219, -3065619}, - {-9781479, -2031780}, - {-9510560, -1020730}, - {-9135450, -43529}, - {-2099999, 14110899}, - {2099999, 14110899}, - {9135450, -43529}, - {9510560, -1020730}, - {9781479, -2031780}, - {9945219, -3065619}, - {10000000, -4110899}, - {9945219, -5156179}, - {9781479, -6190020}, - {9510560, -7201069}, - {9135450, -8178270}, - {8660249, -9110899}, - {8090169, -9988750}, - {7431449, -10802200}, - {6691309, -11542300}, - {5877850, -12201100}, - {5000000, -12771100}, - {4067369, -13246399}, - {3090169, -13621500}, - {2079119, -13892399}, - {1045279, -14056099}, - {0, -14110899}, - {-1045279, -14056099}, - {-2079119, -13892399}, - {-3090169, -13621500}, - {-4067369, -13246399}, - {-5000000, -12771100}, - {-5877850, -12201100}, - {-6691309, -11542300}, - {-7431449, -10802200}, - {-8090169, -9988750}, - {-8660249, -9110899}, - {-9135450, -8178270}, - {-9510560, -7201069}, - {-9781479, -6190020}, - {-9945219, -5156179}, - {-10000000, -4110899}, - {-9945219, -3065619}, - }, - { - {-18000000, -1000000}, - {-15000000, 22000000}, - {-11000000, 26000000}, - {11000000, 26000000}, - {15000000, 22000000}, - {18000000, -1000000}, - {18000000, -26000000}, - {-18000000, -26000000}, - {-18000000, -1000000}, - }, - }; + std::vector<Item> rects(202, { + {-9945219, -3065619}, + {-9781479, -2031780}, + {-9510560, -1020730}, + {-9135450, -43529}, + {-2099999, 14110899}, + {2099999, 14110899}, + {9135450, -43529}, + {9510560, -1020730}, + {9781479, -2031780}, + {9945219, -3065619}, + {10000000, -4110899}, + {9945219, -5156179}, + {9781479, -6190019}, + {9510560, -7201069}, + {9135450, -8178270}, + {8660249, -9110899}, + {8090169, -9988750}, + {7431449, -10802209}, + {6691309, -11542349}, + {5877850, -12201069}, + {5000000, -12771149}, + {4067369, -13246350}, + {3090169, -13621459}, + {2079119, -13892379}, + {1045279, -14056119}, + {0, -14110899}, + {-1045279, -14056119}, + {-2079119, -13892379}, + {-3090169, -13621459}, + {-4067369, -13246350}, + {-5000000, -12771149}, + {-5877850, -12201069}, + {-6691309, -11542349}, + {-7431449, -10802209}, + {-8090169, -9988750}, + {-8660249, -9110899}, + {-9135450, -8178270}, + {-9510560, -7201069}, + {-9781479, -6190019}, + {-9945219, -5156179}, + {-10000000, -4110899}, + {-9945219, -3065619}, + }); - std::vector<Item> proba = { - { - Rectangle(100, 2) - }, - { - Rectangle(100, 2) - }, - { - Rectangle(100, 2) - }, - { - Rectangle(10, 10) - }, - }; - - proba[0].rotate(Pi/3); - proba[1].rotate(Pi-Pi/3); - -// std::vector<Item> input(25, Rectangle(70*SCALE, 10*SCALE)); std::vector<Item> input; input.insert(input.end(), prusaParts().begin(), prusaParts().end()); // input.insert(input.end(), prusaExParts().begin(), prusaExParts().end()); // input.insert(input.end(), stegoParts().begin(), stegoParts().end()); // input.insert(input.end(), rects.begin(), rects.end()); -// input.insert(input.end(), proba.begin(), proba.end()); -// input.insert(input.end(), crasher.begin(), crasher.end()); Box bin(250*SCALE, 210*SCALE); // PolygonImpl bin = { @@ -560,10 +121,12 @@ void arrangeRectangles() { // {} // }; - auto min_obj_distance = static_cast<Coord>(0*SCALE); +// Circle bin({0, 0}, 125*SCALE); - using Placer = strategies::_NofitPolyPlacer<PolygonImpl, Box>; - using Packer = Arranger<Placer, FirstFitSelection>; + auto min_obj_distance = static_cast<Coord>(6*SCALE); + + using Placer = placers::_NofitPolyPlacer<PolygonImpl, decltype(bin)>; + using Packer = Nester<Placer, FirstFitSelection>; Packer arrange(bin, min_obj_distance); @@ -571,121 +134,23 @@ void arrangeRectangles() { pconf.alignment = Placer::Config::Alignment::CENTER; pconf.starting_point = Placer::Config::Alignment::CENTER; pconf.rotations = {0.0/*, Pi/2.0, Pi, 3*Pi/2*/}; - pconf.accuracy = 0.5f; - -// auto bincenter = ShapeLike::boundingBox(bin).center(); -// pconf.object_function = [&bin, bincenter]( -// Placer::Pile pile, const Item& item, -// double /*area*/, double norm, double penality) { - -// using pl = PointLike; - -// static const double BIG_ITEM_TRESHOLD = 0.2; -// static const double GRAVITY_RATIO = 0.5; -// static const double DENSITY_RATIO = 1.0 - GRAVITY_RATIO; - -// // We will treat big items (compared to the print bed) differently -// NfpPlacer::Pile bigs; -// bigs.reserve(pile.size()); -// for(auto& p : pile) { -// auto pbb = ShapeLike::boundingBox(p); -// auto na = std::sqrt(pbb.width()*pbb.height())/norm; -// if(na > BIG_ITEM_TRESHOLD) bigs.emplace_back(p); -// } - -// // Candidate item bounding box -// auto ibb = item.boundingBox(); - -// // Calculate the full bounding box of the pile with the candidate item -// pile.emplace_back(item.transformedShape()); -// auto fullbb = ShapeLike::boundingBox(pile); -// pile.pop_back(); - -// // The bounding box of the big items (they will accumulate in the center -// // of the pile -// auto bigbb = bigs.empty()? fullbb : ShapeLike::boundingBox(bigs); - -// // The size indicator of the candidate item. This is not the area, -// // but almost... -// auto itemnormarea = std::sqrt(ibb.width()*ibb.height())/norm; - -// // Will hold the resulting score -// double score = 0; - -// if(itemnormarea > BIG_ITEM_TRESHOLD) { -// // This branch is for the bigger items.. -// // Here we will use the closest point of the item bounding box to -// // the already arranged pile. So not the bb center nor the a choosen -// // corner but whichever is the closest to the center. This will -// // prevent unwanted strange arrangements. - -// auto minc = ibb.minCorner(); // bottom left corner -// auto maxc = ibb.maxCorner(); // top right corner - -// // top left and bottom right corners -// auto top_left = PointImpl{getX(minc), getY(maxc)}; -// auto bottom_right = PointImpl{getX(maxc), getY(minc)}; - -// auto cc = fullbb.center(); // The gravity center - -// // Now the distnce of the gravity center will be calculated to the -// // five anchor points and the smallest will be chosen. -// std::array<double, 5> dists; -// dists[0] = pl::distance(minc, cc); -// dists[1] = pl::distance(maxc, cc); -// dists[2] = pl::distance(ibb.center(), cc); -// dists[3] = pl::distance(top_left, cc); -// dists[4] = pl::distance(bottom_right, cc); - -// auto dist = *(std::min_element(dists.begin(), dists.end())) / norm; - -// // Density is the pack density: how big is the arranged pile -// auto density = std::sqrt(fullbb.width()*fullbb.height()) / norm; - -// // The score is a weighted sum of the distance from pile center -// // and the pile size -// score = GRAVITY_RATIO * dist + DENSITY_RATIO * density; - -// } else if(itemnormarea < BIG_ITEM_TRESHOLD && bigs.empty()) { -// // If there are no big items, only small, we should consider the -// // density here as well to not get silly results -// auto bindist = pl::distance(ibb.center(), bincenter) / norm; -// auto density = std::sqrt(fullbb.width()*fullbb.height()) / norm; -// score = GRAVITY_RATIO * bindist + DENSITY_RATIO * density; -// } else { -// // Here there are the small items that should be placed around the -// // already processed bigger items. -// // No need to play around with the anchor points, the center will be -// // just fine for small items -// score = pl::distance(ibb.center(), bigbb.center()) / norm; -// } - -// // If it does not fit into the print bed we will beat it -// // with a large penality. If we would not do this, there would be only -// // one big pile that doesn't care whether it fits onto the print bed. -// if(!NfpPlacer::wouldFit(fullbb, bin)) score = 2*penality - score; - -// return score; -// }; + pconf.accuracy = 0.65f; + pconf.parallel = true; Packer::SelectionConfig sconf; // sconf.allow_parallel = false; // sconf.force_parallel = false; // sconf.try_triplets = true; // sconf.try_reverse_order = true; -// sconf.waste_increment = 0.005; +// sconf.waste_increment = 0.01; arrange.configure(pconf, sconf); arrange.progressIndicator([&](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("debout"); std::cout << "Remaining items: " << r << std::endl; - })/*.useMinimumBoundigBoxRotation()*/; + }); + +// findMinimumBoundingBoxRotations(input.begin(), input.end()); Benchmark bench; @@ -693,7 +158,7 @@ void arrangeRectangles() { Packer::ResultType result; try { - result = arrange.arrange(input.begin(), input.end()); + result = arrange.execute(input.begin(), input.end()); } catch(GeometryException& ge) { std::cerr << "Geometry error: " << ge.what() << std::endl; return ; @@ -707,7 +172,7 @@ void arrangeRectangles() { std::vector<double> eff; eff.reserve(result.size()); - auto bin_area = ShapeLike::area<PolygonImpl>(bin); + auto bin_area = sl::area(bin); for(auto& r : result) { double a = 0; std::for_each(r.begin(), r.end(), [&a] (Item& e ){ a += e.area(); }); @@ -728,10 +193,10 @@ void arrangeRectangles() { for(auto& r : result) { std::cout << r.size() << " "; total += r.size(); } std::cout << ") Total: " << total << std::endl; - for(auto& it : input) { - auto ret = ShapeLike::isValid(it.transformedShape()); - std::cout << ret.second << std::endl; - } +// for(auto& it : input) { +// auto ret = sl::isValid(it.transformedShape()); +// std::cout << ret.second << std::endl; +// } if(total != input.size()) std::cout << "ERROR " << "could not pack " << input.size() - total << " elements!" @@ -744,13 +209,10 @@ void arrangeRectangles() { SVGWriter svgw(conf); svgw.setSize(Box(250*SCALE, 210*SCALE)); svgw.writePackGroup(result); -// std::for_each(input.begin(), input.end(), [&svgw](Item& item){ svgw.writeItem(item);}); svgw.save("out"); } int main(void /*int argc, char **argv*/) { arrangeRectangles(); -// findDegenerateCase(); - return EXIT_SUCCESS; } diff --git a/xs/src/libnest2d/libnest2d.h b/xs/src/libnest2d/libnest2d.h index c9e21ecfb..bfd88f4f5 100644 --- a/xs/src/libnest2d/libnest2d.h +++ b/xs/src/libnest2d/libnest2d.h @@ -22,6 +22,7 @@ using Point = PointImpl; using Coord = TCoord<PointImpl>; using Box = _Box<PointImpl>; using Segment = _Segment<PointImpl>; +using Circle = _Circle<PointImpl>; using Item = _Item<PolygonImpl>; using Rectangle = _Rectangle<PolygonImpl>; @@ -29,15 +30,12 @@ using Rectangle = _Rectangle<PolygonImpl>; using PackGroup = _PackGroup<PolygonImpl>; using IndexedPackGroup = _IndexedPackGroup<PolygonImpl>; -using FillerSelection = strategies::_FillerSelection<PolygonImpl>; -using FirstFitSelection = strategies::_FirstFitSelection<PolygonImpl>; -using DJDHeuristic = strategies::_DJDHeuristic<PolygonImpl>; +using FillerSelection = selections::_FillerSelection<PolygonImpl>; +using FirstFitSelection = selections::_FirstFitSelection<PolygonImpl>; +using DJDHeuristic = selections::_DJDHeuristic<PolygonImpl>; -using NfpPlacer = strategies::_NofitPolyPlacer<PolygonImpl>; -using BottomLeftPlacer = strategies::_BottomLeftPlacer<PolygonImpl>; - -//template<NfpLevel lvl = NfpLevel::BOTH_CONCAVE_WITH_HOLES> -//using NofitPolyPlacer = strategies::_NofitPolyPlacer<PolygonImpl, lvl>; +using NfpPlacer = placers::_NofitPolyPlacer<PolygonImpl>; +using BottomLeftPlacer = placers::_BottomLeftPlacer<PolygonImpl>; } diff --git a/xs/src/libnest2d/libnest2d/boost_alg.hpp b/xs/src/libnest2d/libnest2d/boost_alg.hpp index 67e19fcbd..bb0403b06 100644 --- a/xs/src/libnest2d/libnest2d/boost_alg.hpp +++ b/xs/src/libnest2d/libnest2d/boost_alg.hpp @@ -36,7 +36,7 @@ using libnest2d::setX; using libnest2d::setY; using Box = libnest2d::_Box<PointImpl>; using Segment = libnest2d::_Segment<PointImpl>; -using Shapes = libnest2d::Nfp::Shapes<PolygonImpl>; +using Shapes = libnest2d::nfp::Shapes<PolygonImpl>; } @@ -241,11 +241,11 @@ template<> struct tag<bp2d::PolygonImpl> { template<> struct exterior_ring<bp2d::PolygonImpl> { static inline bp2d::PathImpl& get(bp2d::PolygonImpl& p) { - return libnest2d::ShapeLike::getContour(p); + return libnest2d::shapelike::getContour(p); } static inline bp2d::PathImpl const& get(bp2d::PolygonImpl const& p) { - return libnest2d::ShapeLike::getContour(p); + return libnest2d::shapelike::getContour(p); } }; @@ -271,13 +271,13 @@ struct interior_rings<bp2d::PolygonImpl> { static inline libnest2d::THolesContainer<bp2d::PolygonImpl>& get( bp2d::PolygonImpl& p) { - return libnest2d::ShapeLike::holes(p); + return libnest2d::shapelike::holes(p); } static inline const libnest2d::THolesContainer<bp2d::PolygonImpl>& get( bp2d::PolygonImpl const& p) { - return libnest2d::ShapeLike::holes(p); + return libnest2d::shapelike::holes(p); } }; @@ -311,83 +311,77 @@ struct range_value<bp2d::Shapes> { namespace libnest2d { // Now the algorithms that boost can provide... +namespace pointlike { template<> -inline double PointLike::distance(const PointImpl& p1, - const PointImpl& p2 ) +inline double distance(const PointImpl& p1, const PointImpl& p2 ) { return boost::geometry::distance(p1, p2); } template<> -inline double PointLike::distance(const PointImpl& p, - const bp2d::Segment& seg ) +inline double distance(const PointImpl& p, const bp2d::Segment& seg ) { return boost::geometry::distance(p, seg); } +} +namespace shapelike { // Tell libnest2d how to make string out of a ClipperPolygon object template<> -inline bool ShapeLike::intersects(const PathImpl& sh1, - const PathImpl& sh2) +inline bool intersects(const PathImpl& sh1, const PathImpl& sh2) { return boost::geometry::intersects(sh1, sh2); } // Tell libnest2d how to make string out of a ClipperPolygon object template<> -inline bool ShapeLike::intersects(const PolygonImpl& sh1, - const PolygonImpl& sh2) +inline bool intersects(const PolygonImpl& sh1, const PolygonImpl& sh2) { return boost::geometry::intersects(sh1, sh2); } // Tell libnest2d how to make string out of a ClipperPolygon object template<> -inline bool ShapeLike::intersects(const bp2d::Segment& s1, - const bp2d::Segment& s2) +inline bool intersects(const bp2d::Segment& s1, const bp2d::Segment& s2) { return boost::geometry::intersects(s1, s2); } #ifndef DISABLE_BOOST_AREA template<> -inline double ShapeLike::area(const PolygonImpl& shape) +inline double area(const PolygonImpl& shape, const PolygonTag&) { return boost::geometry::area(shape); } #endif template<> -inline bool ShapeLike::isInside<PolygonImpl>(const PointImpl& point, - const PolygonImpl& shape) +inline bool isInside(const PointImpl& point, const PolygonImpl& shape) { return boost::geometry::within(point, shape); } template<> -inline bool ShapeLike::isInside(const PolygonImpl& sh1, - const PolygonImpl& sh2) +inline bool isInside(const PolygonImpl& sh1, const PolygonImpl& sh2) { return boost::geometry::within(sh1, sh2); } template<> -inline bool ShapeLike::touches( const PolygonImpl& sh1, - const PolygonImpl& sh2) +inline bool touches(const PolygonImpl& sh1, const PolygonImpl& sh2) { return boost::geometry::touches(sh1, sh2); } template<> -inline bool ShapeLike::touches( const PointImpl& point, - const PolygonImpl& shape) +inline bool touches( const PointImpl& point, const PolygonImpl& shape) { return boost::geometry::touches(point, shape); } #ifndef DISABLE_BOOST_BOUNDING_BOX template<> -inline bp2d::Box ShapeLike::boundingBox(const PolygonImpl& sh) +inline bp2d::Box boundingBox(const PolygonImpl& sh, const PolygonTag&) { bp2d::Box b; boost::geometry::envelope(sh, b); @@ -395,7 +389,8 @@ inline bp2d::Box ShapeLike::boundingBox(const PolygonImpl& sh) } template<> -inline bp2d::Box ShapeLike::boundingBox<PolygonImpl>(const bp2d::Shapes& shapes) +inline bp2d::Box boundingBox<bp2d::Shapes>(const bp2d::Shapes& shapes, + const MultiPolygonTag&) { bp2d::Box b; boost::geometry::envelope(shapes, b); @@ -405,7 +400,7 @@ inline bp2d::Box ShapeLike::boundingBox<PolygonImpl>(const bp2d::Shapes& shapes) #ifndef DISABLE_BOOST_CONVEX_HULL template<> -inline PolygonImpl ShapeLike::convexHull(const PolygonImpl& sh) +inline PolygonImpl convexHull(const PolygonImpl& sh, const PolygonTag&) { PolygonImpl ret; boost::geometry::convex_hull(sh, ret); @@ -413,7 +408,8 @@ inline PolygonImpl ShapeLike::convexHull(const PolygonImpl& sh) } template<> -inline PolygonImpl ShapeLike::convexHull(const bp2d::Shapes& shapes) +inline PolygonImpl convexHull(const TMultiShape<PolygonImpl>& shapes, + const MultiPolygonTag&) { PolygonImpl ret; boost::geometry::convex_hull(shapes, ret); @@ -421,56 +417,17 @@ inline PolygonImpl ShapeLike::convexHull(const bp2d::Shapes& shapes) } #endif -#ifndef DISABLE_BOOST_ROTATE -template<> -inline void ShapeLike::rotate(PolygonImpl& sh, const Radians& rads) -{ - namespace trans = boost::geometry::strategy::transform; - - PolygonImpl cpy = sh; - trans::rotate_transformer<boost::geometry::radian, Radians, 2, 2> - rotate(rads); - - boost::geometry::transform(cpy, sh, rotate); -} -#endif - -#ifndef DISABLE_BOOST_TRANSLATE -template<> -inline void ShapeLike::translate(PolygonImpl& sh, const PointImpl& offs) -{ - namespace trans = boost::geometry::strategy::transform; - - PolygonImpl cpy = sh; - trans::translate_transformer<bp2d::Coord, 2, 2> translate( - bp2d::getX(offs), bp2d::getY(offs)); - - boost::geometry::transform(cpy, sh, translate); -} -#endif - #ifndef DISABLE_BOOST_OFFSET template<> -inline void ShapeLike::offset(PolygonImpl& sh, bp2d::Coord distance) +inline void offset(PolygonImpl& sh, bp2d::Coord distance) { PolygonImpl cpy = sh; boost::geometry::buffer(cpy, sh, distance); } #endif -#ifndef DISABLE_BOOST_NFP_MERGE -template<> -inline bp2d::Shapes Nfp::merge(const bp2d::Shapes& shapes, - const PolygonImpl& sh) -{ - bp2d::Shapes retv; - boost::geometry::union_(shapes, sh, retv); - return retv; -} -#endif - #ifndef DISABLE_BOOST_SERIALIZE -template<> inline std::string ShapeLike::serialize<libnest2d::Formats::SVG>( +template<> inline std::string serialize<libnest2d::Formats::SVG>( const PolygonImpl& sh, double scale) { std::stringstream ss; @@ -482,14 +439,14 @@ template<> inline std::string ShapeLike::serialize<libnest2d::Formats::SVG>( Polygonf::ring_type ring; Polygonf::inner_container_type holes; - ring.reserve(ShapeLike::contourVertexCount(sh)); + ring.reserve(shapelike::contourVertexCount(sh)); - for(auto it = ShapeLike::cbegin(sh); it != ShapeLike::cend(sh); it++) { + for(auto it = shapelike::cbegin(sh); it != shapelike::cend(sh); it++) { auto& v = *it; ring.emplace_back(getX(v)*scale, getY(v)*scale); }; - auto H = ShapeLike::holes(sh); + auto H = shapelike::holes(sh); for(PathImpl& h : H ) { Polygonf::ring_type hf; for(auto it = h.begin(); it != h.end(); it++) { @@ -512,21 +469,47 @@ template<> inline std::string ShapeLike::serialize<libnest2d::Formats::SVG>( #ifndef DISABLE_BOOST_UNSERIALIZE template<> -inline void ShapeLike::unserialize<libnest2d::Formats::SVG>( +inline void unserialize<libnest2d::Formats::SVG>( PolygonImpl& sh, const std::string& str) { } #endif -template<> inline std::pair<bool, std::string> -ShapeLike::isValid(const PolygonImpl& sh) +template<> inline std::pair<bool, std::string> isValid(const PolygonImpl& sh) { std::string message; bool ret = boost::geometry::is_valid(sh, message); return {ret, message}; } +} + +namespace nfp { + +#ifndef DISABLE_BOOST_NFP_MERGE + +// Warning: I could not get boost union_ to work. Geometries will overlap. +template<> +inline bp2d::Shapes nfp::merge(const bp2d::Shapes& shapes, + const PolygonImpl& sh) +{ + bp2d::Shapes retv; + boost::geometry::union_(shapes, sh, retv); + return retv; +} + +template<> +inline bp2d::Shapes nfp::merge(const bp2d::Shapes& shapes) +{ + bp2d::Shapes retv; + boost::geometry::union_(shapes, shapes.back(), retv); + return retv; +} +#endif + +} + } diff --git a/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.hpp b/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.hpp index 15ceb1576..745fd2108 100644 --- a/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.hpp +++ b/xs/src/libnest2d/libnest2d/clipper_backend/clipper_backend.hpp @@ -99,49 +99,54 @@ template<> struct PointType<PolygonImpl> { using Type = PointImpl; }; -// Type of vertex iterator used by Clipper -template<> struct VertexIteratorType<PolygonImpl> { - using Type = ClipperLib::Path::iterator; -}; - -// Type of vertex iterator used by Clipper -template<> struct VertexConstIteratorType<PolygonImpl> { - using Type = ClipperLib::Path::const_iterator; +template<> struct PointType<PointImpl> { + using Type = PointImpl; }; template<> struct CountourType<PolygonImpl> { using Type = PathImpl; }; -// Tell binpack2d how to extract the X coord from a ClipperPoint object -template<> inline TCoord<PointImpl> PointLike::x(const PointImpl& p) +template<> struct ShapeTag<PolygonImpl> { using Type = PolygonTag; }; + +template<> struct ShapeTag<TMultiShape<PolygonImpl>> { + using Type = MultiPolygonTag; +}; + +template<> struct PointType<TMultiShape<PolygonImpl>> { + using Type = PointImpl; +}; + +template<> struct HolesContainer<PolygonImpl> { + using Type = ClipperLib::Paths; +}; + +namespace pointlike { + +// Tell libnest2d how to extract the X coord from a ClipperPoint object +template<> inline TCoord<PointImpl> x(const PointImpl& p) { return p.X; } -// Tell binpack2d how to extract the Y coord from a ClipperPoint object -template<> inline TCoord<PointImpl> PointLike::y(const PointImpl& p) +// Tell libnest2d how to extract the Y coord from a ClipperPoint object +template<> inline TCoord<PointImpl> y(const PointImpl& p) { return p.Y; } -// Tell binpack2d how to extract the X coord from a ClipperPoint object -template<> inline TCoord<PointImpl>& PointLike::x(PointImpl& p) +// Tell libnest2d how to extract the X coord from a ClipperPoint object +template<> inline TCoord<PointImpl>& x(PointImpl& p) { return p.X; } -// Tell binpack2d how to extract the Y coord from a ClipperPoint object -template<> -inline TCoord<PointImpl>& PointLike::y(PointImpl& p) +// Tell libnest2d how to extract the Y coord from a ClipperPoint object +template<> inline TCoord<PointImpl>& y(PointImpl& p) { return p.Y; } -template<> -inline void ShapeLike::reserve(PolygonImpl& sh, size_t vertex_capacity) -{ - return sh.Contour.reserve(vertex_capacity); } #define DISABLE_BOOST_AREA @@ -175,16 +180,24 @@ inline double area<Orientation::COUNTER_CLOCKWISE>(const PolygonImpl& sh) { return ClipperLib::Area(sh.Contour) + a; } + } -// Tell binpack2d how to make string out of a ClipperPolygon object -template<> -inline double ShapeLike::area(const PolygonImpl& sh) { +namespace shapelike { + +template<> inline void reserve(PolygonImpl& sh, size_t vertex_capacity) +{ + return sh.Contour.reserve(vertex_capacity); +} + +// Tell libnest2d how to make string out of a ClipperPolygon object +template<> inline double area(const PolygonImpl& sh, const PolygonTag&) +{ return _smartarea::area<OrientationType<PolygonImpl>::Value>(sh); } -template<> -inline void ShapeLike::offset(PolygonImpl& sh, TCoord<PointImpl> distance) { +template<> inline void offset(PolygonImpl& sh, TCoord<PointImpl> distance) +{ #define DISABLE_BOOST_OFFSET using ClipperLib::ClipperOffset; @@ -234,7 +247,8 @@ inline void ShapeLike::offset(PolygonImpl& sh, TCoord<PointImpl> distance) { } // Tell libnest2d how to make string out of a ClipperPolygon object -template<> inline std::string ShapeLike::toString(const PolygonImpl& sh) { +template<> inline std::string toString(const PolygonImpl& sh) +{ std::stringstream ss; ss << "Contour {\n"; @@ -257,37 +271,8 @@ template<> inline std::string ShapeLike::toString(const PolygonImpl& sh) { } template<> -inline TVertexIterator<PolygonImpl> ShapeLike::begin(PolygonImpl& sh) -{ - return sh.Contour.begin(); -} - -template<> -inline TVertexIterator<PolygonImpl> ShapeLike::end(PolygonImpl& sh) -{ - return sh.Contour.end(); -} - -template<> -inline TVertexConstIterator<PolygonImpl> ShapeLike::cbegin( - const PolygonImpl& sh) -{ - return sh.Contour.cbegin(); -} - -template<> -inline TVertexConstIterator<PolygonImpl> ShapeLike::cend( - const PolygonImpl& sh) +inline PolygonImpl create(const PathImpl& path, const HoleStore& holes) { - return sh.Contour.cend(); -} - -template<> struct HolesContainer<PolygonImpl> { - using Type = ClipperLib::Paths; -}; - -template<> inline PolygonImpl ShapeLike::create(const PathImpl& path, - const HoleStore& holes) { PolygonImpl p; p.Contour = path; @@ -308,8 +293,7 @@ template<> inline PolygonImpl ShapeLike::create(const PathImpl& path, return p; } -template<> inline PolygonImpl ShapeLike::create( PathImpl&& path, - HoleStore&& holes) { +template<> inline PolygonImpl create( PathImpl&& path, HoleStore&& holes) { PolygonImpl p; p.Contour.swap(path); @@ -331,49 +315,49 @@ template<> inline PolygonImpl ShapeLike::create( PathImpl&& path, return p; } -template<> inline const THolesContainer<PolygonImpl>& -ShapeLike::holes(const PolygonImpl& sh) +template<> +inline const THolesContainer<PolygonImpl>& holes(const PolygonImpl& sh) { return sh.Holes; } -template<> inline THolesContainer<PolygonImpl>& -ShapeLike::holes(PolygonImpl& sh) +template<> inline THolesContainer<PolygonImpl>& holes(PolygonImpl& sh) { return sh.Holes; } -template<> inline TContour<PolygonImpl>& -ShapeLike::getHole(PolygonImpl& sh, unsigned long idx) +template<> +inline TContour<PolygonImpl>& getHole(PolygonImpl& sh, unsigned long idx) { return sh.Holes[idx]; } -template<> inline const TContour<PolygonImpl>& -ShapeLike::getHole(const PolygonImpl& sh, unsigned long idx) +template<> +inline const TContour<PolygonImpl>& getHole(const PolygonImpl& sh, + unsigned long idx) { return sh.Holes[idx]; } -template<> inline size_t ShapeLike::holeCount(const PolygonImpl& sh) +template<> inline size_t holeCount(const PolygonImpl& sh) { return sh.Holes.size(); } -template<> inline PathImpl& ShapeLike::getContour(PolygonImpl& sh) +template<> inline PathImpl& getContour(PolygonImpl& sh) { return sh.Contour; } template<> -inline const PathImpl& ShapeLike::getContour(const PolygonImpl& sh) +inline const PathImpl& getContour(const PolygonImpl& sh) { return sh.Contour; } #define DISABLE_BOOST_TRANSLATE template<> -inline void ShapeLike::translate(PolygonImpl& sh, const PointImpl& offs) +inline void translate(PolygonImpl& sh, const PointImpl& offs) { for(auto& p : sh.Contour) { p += offs; } for(auto& hole : sh.Holes) for(auto& p : hole) { p += offs; } @@ -381,7 +365,7 @@ inline void ShapeLike::translate(PolygonImpl& sh, const PointImpl& offs) #define DISABLE_BOOST_ROTATE template<> -inline void ShapeLike::rotate(PolygonImpl& sh, const Radians& rads) +inline void rotate(PolygonImpl& sh, const Radians& rads) { using Coord = TCoord<PointImpl>; @@ -402,9 +386,11 @@ inline void ShapeLike::rotate(PolygonImpl& sh, const Radians& rads) } } +} // namespace shapelike + #define DISABLE_BOOST_NFP_MERGE -inline Nfp::Shapes<PolygonImpl> _merge(ClipperLib::Clipper& clipper) { - Nfp::Shapes<PolygonImpl> retv; +inline std::vector<PolygonImpl> _merge(ClipperLib::Clipper& clipper) { + shapelike::Shapes<PolygonImpl> retv; ClipperLib::PolyTree result; clipper.Execute(ClipperLib::ctUnion, result, ClipperLib::pftNegative); @@ -438,8 +424,10 @@ inline Nfp::Shapes<PolygonImpl> _merge(ClipperLib::Clipper& clipper) { return retv; } -template<> inline Nfp::Shapes<PolygonImpl> -Nfp::merge(const Nfp::Shapes<PolygonImpl>& shapes) +namespace nfp { + +template<> inline std::vector<PolygonImpl> +merge(const std::vector<PolygonImpl>& shapes) { ClipperLib::Clipper clipper(ClipperLib::ioReverseSolution); @@ -461,6 +449,8 @@ Nfp::merge(const Nfp::Shapes<PolygonImpl>& shapes) } +} + //#define DISABLE_BOOST_SERIALIZE //#define DISABLE_BOOST_UNSERIALIZE diff --git a/xs/src/libnest2d/libnest2d/geometry_traits.hpp b/xs/src/libnest2d/libnest2d/geometry_traits.hpp index 058c47cd4..d16257731 100644 --- a/xs/src/libnest2d/libnest2d/geometry_traits.hpp +++ b/xs/src/libnest2d/libnest2d/geometry_traits.hpp @@ -22,34 +22,12 @@ template<class GeomType> using TCoord = typename CoordType<remove_cvref_t<GeomType>>::Type; /// Getting the type of point structure used by a shape. -template<class Shape> struct PointType { /*using Type = void;*/ }; +template<class Sh> struct PointType { using Type = typename Sh::PointType; }; /// TPoint<ShapeClass> as shorthand for `typename PointType<ShapeClass>::Type`. template<class Shape> using TPoint = typename PointType<remove_cvref_t<Shape>>::Type; -/// Getting the VertexIterator type of a shape class. -template<class Shape> struct VertexIteratorType { /*using Type = void;*/ }; - -/// Getting the const vertex iterator for a shape class. -template<class Shape> struct VertexConstIteratorType {/* using Type = void;*/ }; - -/** - * TVertexIterator<Shape> as shorthand for - * `typename VertexIteratorType<Shape>::Type` - */ -template<class Shape> -using TVertexIterator = -typename VertexIteratorType<remove_cvref_t<Shape>>::Type; - -/** - * \brief TVertexConstIterator<Shape> as shorthand for - * `typename VertexConstIteratorType<Shape>::Type` - */ -template<class ShapeClass> -using TVertexConstIterator = -typename VertexConstIteratorType<remove_cvref_t<ShapeClass>>::Type; - /** * \brief A point pair base class for other point pairs (segment, box, ...). * \tparam RawPoint The actual point type to use. @@ -60,6 +38,17 @@ struct PointPair { RawPoint p2; }; +struct PolygonTag {}; +struct MultiPolygonTag {}; +struct BoxTag {}; +struct CircleTag {}; + +template<class Shape> struct ShapeTag { using Type = typename Shape::Tag; }; +template<class S> using Tag = typename ShapeTag<S>::Type; + +template<class S> struct MultiShape { using Type = std::vector<S>; }; +template<class S> using TMultiShape = typename MultiShape<S>::Type; + /** * \brief An abstraction of a box; */ @@ -69,6 +58,9 @@ class _Box: PointPair<RawPoint> { using PointPair<RawPoint>::p2; public: + using Tag = BoxTag; + using PointType = RawPoint; + inline _Box() = default; inline _Box(const RawPoint& p, const RawPoint& pp): PointPair<RawPoint>({p, pp}) {} @@ -98,6 +90,9 @@ class _Circle { double radius_ = 0; public: + using Tag = CircleTag; + using PointType = RawPoint; + _Circle() = default; _Circle(const RawPoint& center, double r): center_(center), radius_(r) {} @@ -109,7 +104,7 @@ public: inline void radius(double r) { radius_ = r; } inline double area() const BP2D_NOEXCEPT { - return 2.0*Pi*radius_; + return 2.0*Pi*radius_*radius_; } }; @@ -123,6 +118,8 @@ class _Segment: PointPair<RawPoint> { mutable Radians angletox_ = std::nan(""); public: + using PointType = RawPoint; + inline _Segment() = default; inline _Segment(const RawPoint& p, const RawPoint& pp): @@ -156,36 +153,36 @@ public: inline double length(); }; -// This struct serves as a namespace. The only difference is that is can be +// This struct serves almost as a namespace. The only difference is that is can // used in friend declarations. -struct PointLike { +namespace pointlike { template<class RawPoint> - static TCoord<RawPoint> x(const RawPoint& p) + inline TCoord<RawPoint> x(const RawPoint& p) { return p.x(); } template<class RawPoint> - static TCoord<RawPoint> y(const RawPoint& p) + inline TCoord<RawPoint> y(const RawPoint& p) { return p.y(); } template<class RawPoint> - static TCoord<RawPoint>& x(RawPoint& p) + inline TCoord<RawPoint>& x(RawPoint& p) { return p.x(); } template<class RawPoint> - static TCoord<RawPoint>& y(RawPoint& p) + inline TCoord<RawPoint>& y(RawPoint& p) { return p.y(); } template<class RawPoint> - static double distance(const RawPoint& /*p1*/, const RawPoint& /*p2*/) + inline double distance(const RawPoint& /*p1*/, const RawPoint& /*p2*/) { static_assert(always_false<RawPoint>::value, "PointLike::distance(point, point) unimplemented!"); @@ -193,7 +190,7 @@ struct PointLike { } template<class RawPoint> - static double distance(const RawPoint& /*p1*/, + inline double distance(const RawPoint& /*p1*/, const _Segment<RawPoint>& /*s*/) { static_assert(always_false<RawPoint>::value, @@ -202,13 +199,13 @@ struct PointLike { } template<class RawPoint> - static std::pair<TCoord<RawPoint>, bool> horizontalDistance( + inline std::pair<TCoord<RawPoint>, bool> horizontalDistance( const RawPoint& p, const _Segment<RawPoint>& s) { using Unit = TCoord<RawPoint>; - auto x = PointLike::x(p), y = PointLike::y(p); - auto x1 = PointLike::x(s.first()), y1 = PointLike::y(s.first()); - auto x2 = PointLike::x(s.second()), y2 = PointLike::y(s.second()); + auto x = pointlike::x(p), y = pointlike::y(p); + auto x1 = pointlike::x(s.first()), y1 = pointlike::y(s.first()); + auto x2 = pointlike::x(s.second()), y2 = pointlike::y(s.second()); TCoord<RawPoint> ret; @@ -228,13 +225,13 @@ struct PointLike { } template<class RawPoint> - static std::pair<TCoord<RawPoint>, bool> verticalDistance( + inline std::pair<TCoord<RawPoint>, bool> verticalDistance( const RawPoint& p, const _Segment<RawPoint>& s) { using Unit = TCoord<RawPoint>; - auto x = PointLike::x(p), y = PointLike::y(p); - auto x1 = PointLike::x(s.first()), y1 = PointLike::y(s.first()); - auto x2 = PointLike::x(s.second()), y2 = PointLike::y(s.second()); + auto x = pointlike::x(p), y = pointlike::y(p); + auto x1 = pointlike::x(s.first()), y1 = pointlike::y(s.first()); + auto x2 = pointlike::x(s.second()), y2 = pointlike::y(s.second()); TCoord<RawPoint> ret; @@ -252,36 +249,36 @@ struct PointLike { return {ret, true}; } -}; +} template<class RawPoint> TCoord<RawPoint> _Box<RawPoint>::width() const BP2D_NOEXCEPT { - return PointLike::x(maxCorner()) - PointLike::x(minCorner()); + return pointlike::x(maxCorner()) - pointlike::x(minCorner()); } template<class RawPoint> TCoord<RawPoint> _Box<RawPoint>::height() const BP2D_NOEXCEPT { - return PointLike::y(maxCorner()) - PointLike::y(minCorner()); + return pointlike::y(maxCorner()) - pointlike::y(minCorner()); } template<class RawPoint> -TCoord<RawPoint> getX(const RawPoint& p) { return PointLike::x<RawPoint>(p); } +TCoord<RawPoint> getX(const RawPoint& p) { return pointlike::x<RawPoint>(p); } template<class RawPoint> -TCoord<RawPoint> getY(const RawPoint& p) { return PointLike::y<RawPoint>(p); } +TCoord<RawPoint> getY(const RawPoint& p) { return pointlike::y<RawPoint>(p); } template<class RawPoint> void setX(RawPoint& p, const TCoord<RawPoint>& val) { - PointLike::x<RawPoint>(p) = val; + pointlike::x<RawPoint>(p) = val; } template<class RawPoint> void setY(RawPoint& p, const TCoord<RawPoint>& val) { - PointLike::y<RawPoint>(p) = val; + pointlike::y<RawPoint>(p) = val; } template<class RawPoint> @@ -303,7 +300,7 @@ inline Radians _Segment<RawPoint>::angleToXaxis() const template<class RawPoint> inline double _Segment<RawPoint>::length() { - return PointLike::distance(first(), second()); + return pointlike::distance(first(), second()); } template<class RawPoint> @@ -313,9 +310,9 @@ inline RawPoint _Box<RawPoint>::center() const BP2D_NOEXCEPT { using Coord = TCoord<RawPoint>; - RawPoint ret = { - static_cast<Coord>( std::round((getX(minc) + getX(maxc))/2.0) ), - static_cast<Coord>( std::round((getY(minc) + getY(maxc))/2.0) ) + RawPoint ret = { // No rounding here, we dont know if these are int coords + static_cast<Coord>( (getX(minc) + getX(maxc))/2.0 ), + static_cast<Coord>( (getY(minc) + getY(maxc))/2.0 ) }; return ret; @@ -356,124 +353,125 @@ enum class Formats { // This struct serves as a namespace. The only difference is that it can be // used in friend declarations and can be aliased at class scope. -struct ShapeLike { +namespace shapelike { template<class RawShape> - using Shapes = std::vector<RawShape>; + using Shapes = TMultiShape<RawShape>; template<class RawShape> - static RawShape create(const TContour<RawShape>& contour, + inline RawShape create(const TContour<RawShape>& contour, const THolesContainer<RawShape>& holes) { return RawShape(contour, holes); } template<class RawShape> - static RawShape create(TContour<RawShape>&& contour, + inline RawShape create(TContour<RawShape>&& contour, THolesContainer<RawShape>&& holes) { return RawShape(contour, holes); } template<class RawShape> - static RawShape create(const TContour<RawShape>& contour) + inline RawShape create(const TContour<RawShape>& contour) { return create<RawShape>(contour, {}); } template<class RawShape> - static RawShape create(TContour<RawShape>&& contour) + inline RawShape create(TContour<RawShape>&& contour) { return create<RawShape>(contour, {}); } template<class RawShape> - static THolesContainer<RawShape>& holes(RawShape& /*sh*/) + inline THolesContainer<RawShape>& holes(RawShape& /*sh*/) { static THolesContainer<RawShape> empty; return empty; } template<class RawShape> - static const THolesContainer<RawShape>& holes(const RawShape& /*sh*/) + inline const THolesContainer<RawShape>& holes(const RawShape& /*sh*/) { static THolesContainer<RawShape> empty; return empty; } template<class RawShape> - static TContour<RawShape>& getHole(RawShape& sh, unsigned long idx) + inline TContour<RawShape>& getHole(RawShape& sh, unsigned long idx) { return holes(sh)[idx]; } template<class RawShape> - static const TContour<RawShape>& getHole(const RawShape& sh, + inline const TContour<RawShape>& getHole(const RawShape& sh, unsigned long idx) { return holes(sh)[idx]; } template<class RawShape> - static size_t holeCount(const RawShape& sh) + inline size_t holeCount(const RawShape& sh) { return holes(sh).size(); } template<class RawShape> - static TContour<RawShape>& getContour(RawShape& sh) + inline TContour<RawShape>& getContour(RawShape& sh) { return sh; } template<class RawShape> - static const TContour<RawShape>& getContour(const RawShape& sh) + inline const TContour<RawShape>& getContour(const RawShape& sh) { return sh; } // Optional, does nothing by default template<class RawShape> - static void reserve(RawShape& /*sh*/, size_t /*vertex_capacity*/) {} + inline void reserve(RawShape& /*sh*/, size_t /*vertex_capacity*/) {} template<class RawShape, class...Args> - static void addVertex(RawShape& sh, Args...args) + inline void addVertex(RawShape& sh, Args...args) { return getContour(sh).emplace_back(std::forward<Args>(args)...); } template<class RawShape> - static TVertexIterator<RawShape> begin(RawShape& sh) + inline typename TContour<RawShape>::iterator begin(RawShape& sh) { - return sh.begin(); + return getContour(sh).begin(); } template<class RawShape> - static TVertexIterator<RawShape> end(RawShape& sh) + inline typename TContour<RawShape>::iterator end(RawShape& sh) { - return sh.end(); + return getContour(sh).end(); } template<class RawShape> - static TVertexConstIterator<RawShape> cbegin(const RawShape& sh) + inline typename TContour<RawShape>::const_iterator + cbegin(const RawShape& sh) { - return sh.cbegin(); + return getContour(sh).cbegin(); } template<class RawShape> - static TVertexConstIterator<RawShape> cend(const RawShape& sh) + inline typename TContour<RawShape>::const_iterator cend(const RawShape& sh) { - return sh.cend(); + return getContour(sh).cend(); } template<class RawShape> - static std::string toString(const RawShape& /*sh*/) + inline std::string toString(const RawShape& /*sh*/) { return ""; } template<Formats, class RawShape> - static std::string serialize(const RawShape& /*sh*/, double /*scale*/=1) + inline std::string serialize(const RawShape& /*sh*/, double /*scale*/=1) { static_assert(always_false<RawShape>::value, "ShapeLike::serialize() unimplemented!"); @@ -481,14 +479,14 @@ struct ShapeLike { } template<Formats, class RawShape> - static void unserialize(RawShape& /*sh*/, const std::string& /*str*/) + inline void unserialize(RawShape& /*sh*/, const std::string& /*str*/) { static_assert(always_false<RawShape>::value, "ShapeLike::unserialize() unimplemented!"); } template<class RawShape> - static double area(const RawShape& /*sh*/) + inline double area(const RawShape& /*sh*/, const PolygonTag&) { static_assert(always_false<RawShape>::value, "ShapeLike::area() unimplemented!"); @@ -496,7 +494,7 @@ struct ShapeLike { } template<class RawShape> - static bool intersects(const RawShape& /*sh*/, const RawShape& /*sh*/) + inline bool intersects(const RawShape& /*sh*/, const RawShape& /*sh*/) { static_assert(always_false<RawShape>::value, "ShapeLike::intersects() unimplemented!"); @@ -504,7 +502,7 @@ struct ShapeLike { } template<class RawShape> - static bool isInside(const TPoint<RawShape>& /*point*/, + inline bool isInside(const TPoint<RawShape>& /*point*/, const RawShape& /*shape*/) { static_assert(always_false<RawShape>::value, @@ -513,7 +511,7 @@ struct ShapeLike { } template<class RawShape> - static bool isInside(const RawShape& /*shape*/, + inline bool isInside(const RawShape& /*shape*/, const RawShape& /*shape*/) { static_assert(always_false<RawShape>::value, @@ -522,7 +520,7 @@ struct ShapeLike { } template<class RawShape> - static bool touches( const RawShape& /*shape*/, + inline bool touches( const RawShape& /*shape*/, const RawShape& /*shape*/) { static_assert(always_false<RawShape>::value, @@ -531,7 +529,7 @@ struct ShapeLike { } template<class RawShape> - static bool touches( const TPoint<RawShape>& /*point*/, + inline bool touches( const TPoint<RawShape>& /*point*/, const RawShape& /*shape*/) { static_assert(always_false<RawShape>::value, @@ -540,64 +538,66 @@ struct ShapeLike { } template<class RawShape> - static _Box<TPoint<RawShape>> boundingBox(const RawShape& /*sh*/) + inline _Box<TPoint<RawShape>> boundingBox(const RawShape& /*sh*/, + const PolygonTag&) { static_assert(always_false<RawShape>::value, "ShapeLike::boundingBox(shape) unimplemented!"); } - template<class RawShape> - static _Box<TPoint<RawShape>> boundingBox(const Shapes<RawShape>& /*sh*/) + template<class RawShapes> + inline _Box<TPoint<typename RawShapes::value_type>> + boundingBox(const RawShapes& /*sh*/, const MultiPolygonTag&) { - static_assert(always_false<RawShape>::value, + static_assert(always_false<RawShapes>::value, "ShapeLike::boundingBox(shapes) unimplemented!"); } template<class RawShape> - static RawShape convexHull(const RawShape& /*sh*/) + inline RawShape convexHull(const RawShape& /*sh*/, const PolygonTag&) { static_assert(always_false<RawShape>::value, "ShapeLike::convexHull(shape) unimplemented!"); return RawShape(); } - template<class RawShape> - static RawShape convexHull(const Shapes<RawShape>& /*sh*/) + template<class RawShapes> + inline typename RawShapes::value_type + convexHull(const RawShapes& /*sh*/, const MultiPolygonTag&) { - static_assert(always_false<RawShape>::value, + static_assert(always_false<RawShapes>::value, "ShapeLike::convexHull(shapes) unimplemented!"); - return RawShape(); + return typename RawShapes::value_type(); } template<class RawShape> - static void rotate(RawShape& /*sh*/, const Radians& /*rads*/) + inline void rotate(RawShape& /*sh*/, const Radians& /*rads*/) { static_assert(always_false<RawShape>::value, "ShapeLike::rotate() unimplemented!"); } template<class RawShape, class RawPoint> - static void translate(RawShape& /*sh*/, const RawPoint& /*offs*/) + inline void translate(RawShape& /*sh*/, const RawPoint& /*offs*/) { static_assert(always_false<RawShape>::value, "ShapeLike::translate() unimplemented!"); } template<class RawShape> - static void offset(RawShape& /*sh*/, TCoord<TPoint<RawShape>> /*distance*/) + inline void offset(RawShape& /*sh*/, TCoord<TPoint<RawShape>> /*distance*/) { - static_assert(always_false<RawShape>::value, - "ShapeLike::offset() unimplemented!"); + dout() << "The current geometry backend does not support offsetting!\n"; } template<class RawShape> - static std::pair<bool, std::string> isValid(const RawShape& /*sh*/) + inline std::pair<bool, std::string> isValid(const RawShape& /*sh*/) { return {false, "ShapeLike::isValid() unimplemented!"}; } template<class RawShape> - static inline bool isConvex(const TContour<RawShape>& sh) + inline bool isConvex(const TContour<RawShape>& sh) { using Vertex = TPoint<RawShape>; auto first = sh.begin(); @@ -633,43 +633,55 @@ struct ShapeLike { // No need to implement these // ************************************************************************* - template<class RawShape> - static inline _Box<TPoint<RawShape>> boundingBox( - const _Box<TPoint<RawShape>>& box) + template<class Box> + inline Box boundingBox(const Box& box, const BoxTag& ) { return box; } - template<class RawShape> - static inline _Box<TPoint<RawShape>> boundingBox( - const _Circle<TPoint<RawShape>>& circ) + template<class Circle> + inline _Box<typename Circle::PointType> boundingBox( + const Circle& circ, const CircleTag&) { - using Coord = TCoord<TPoint<RawShape>>; - TPoint<RawShape> pmin = { + using Point = typename Circle::PointType; + using Coord = TCoord<Point>; + Point pmin = { static_cast<Coord>(getX(circ.center()) - circ.radius()), static_cast<Coord>(getY(circ.center()) - circ.radius()) }; - TPoint<RawShape> pmax = { + Point pmax = { static_cast<Coord>(getX(circ.center()) + circ.radius()), static_cast<Coord>(getY(circ.center()) + circ.radius()) }; return {pmin, pmax}; } - template<class RawShape> - static inline double area(const _Box<TPoint<RawShape>>& box) + template<class S> // Dispatch function + inline _Box<TPoint<S>> boundingBox(const S& sh) { - return static_cast<double>(box.width() * box.height()); + return boundingBox(sh, Tag<S>() ); } - template<class RawShape> - static inline double area(const _Circle<TPoint<RawShape>>& circ) + template<class Box> + inline double area(const Box& box, const BoxTag& ) + { + return box.area(); + } + + template<class Circle> + inline double area(const Circle& circ, const CircleTag& ) { return circ.area(); } + template<class RawShape> // Dispatching function + inline double area(const RawShape& sh) + { + return area(sh, Tag<RawShape>()); + } + template<class RawShape> - static inline double area(const Shapes<RawShape>& shapes) + inline double area(const Shapes<RawShape>& shapes) { return std::accumulate(shapes.begin(), shapes.end(), 0.0, [](double a, const RawShape& b) { @@ -678,14 +690,21 @@ struct ShapeLike { } template<class RawShape> - static bool isInside(const TPoint<RawShape>& point, + inline auto convexHull(const RawShape& sh) + -> decltype(convexHull(sh, Tag<RawShape>())) // TODO: C++14 could deduce + { + return convexHull(sh, Tag<RawShape>()); + } + + template<class RawShape> + inline bool isInside(const TPoint<RawShape>& point, const _Circle<TPoint<RawShape>>& circ) { - return PointLike::distance(point, circ.center()) < circ.radius(); + return pointlike::distance(point, circ.center()) < circ.radius(); } template<class RawShape> - static bool isInside(const TPoint<RawShape>& point, + inline bool isInside(const TPoint<RawShape>& point, const _Box<TPoint<RawShape>>& box) { auto px = getX(point); @@ -699,7 +718,7 @@ struct ShapeLike { } template<class RawShape> - static bool isInside(const RawShape& sh, + inline bool isInside(const RawShape& sh, const _Circle<TPoint<RawShape>>& circ) { return std::all_of(cbegin(sh), cend(sh), @@ -709,7 +728,7 @@ struct ShapeLike { } template<class RawShape> - static bool isInside(const _Box<TPoint<RawShape>>& box, + inline bool isInside(const _Box<TPoint<RawShape>>& box, const _Circle<TPoint<RawShape>>& circ) { return isInside<RawShape>(box.minCorner(), circ) && @@ -717,7 +736,7 @@ struct ShapeLike { } template<class RawShape> - static bool isInside(const _Box<TPoint<RawShape>>& ibb, + inline bool isInside(const _Box<TPoint<RawShape>>& ibb, const _Box<TPoint<RawShape>>& box) { auto iminX = getX(ibb.minCorner()); @@ -734,31 +753,31 @@ struct ShapeLike { } template<class RawShape> // Potential O(1) implementation may exist - static inline TPoint<RawShape>& vertex(RawShape& sh, unsigned long idx) + inline TPoint<RawShape>& vertex(RawShape& sh, unsigned long idx) { return *(begin(sh) + idx); } template<class RawShape> // Potential O(1) implementation may exist - static inline const TPoint<RawShape>& vertex(const RawShape& sh, + inline const TPoint<RawShape>& vertex(const RawShape& sh, unsigned long idx) { return *(cbegin(sh) + idx); } template<class RawShape> - static inline size_t contourVertexCount(const RawShape& sh) + inline size_t contourVertexCount(const RawShape& sh) { return cend(sh) - cbegin(sh); } template<class RawShape, class Fn> - static inline void foreachContourVertex(RawShape& sh, Fn fn) { + inline void foreachContourVertex(RawShape& sh, Fn fn) { for(auto it = begin(sh); it != end(sh); ++it) fn(*it); } template<class RawShape, class Fn> - static inline void foreachHoleVertex(RawShape& sh, Fn fn) { + inline void foreachHoleVertex(RawShape& sh, Fn fn) { for(int i = 0; i < holeCount(sh); ++i) { auto& h = getHole(sh, i); for(auto it = begin(h); it != end(h); ++it) fn(*it); @@ -766,12 +785,12 @@ struct ShapeLike { } template<class RawShape, class Fn> - static inline void foreachContourVertex(const RawShape& sh, Fn fn) { + inline void foreachContourVertex(const RawShape& sh, Fn fn) { for(auto it = cbegin(sh); it != cend(sh); ++it) fn(*it); } template<class RawShape, class Fn> - static inline void foreachHoleVertex(const RawShape& sh, Fn fn) { + inline void foreachHoleVertex(const RawShape& sh, Fn fn) { for(int i = 0; i < holeCount(sh); ++i) { auto& h = getHole(sh, i); for(auto it = cbegin(h); it != cend(h); ++it) fn(*it); @@ -779,18 +798,27 @@ struct ShapeLike { } template<class RawShape, class Fn> - static inline void foreachVertex(RawShape& sh, Fn fn) { + inline void foreachVertex(RawShape& sh, Fn fn) { foreachContourVertex(sh, fn); foreachHoleVertex(sh, fn); } template<class RawShape, class Fn> - static inline void foreachVertex(const RawShape& sh, Fn fn) { + inline void foreachVertex(const RawShape& sh, Fn fn) { foreachContourVertex(sh, fn); foreachHoleVertex(sh, fn); } +} -}; +#define DECLARE_MAIN_TYPES(T) \ + using Polygon = T; \ + using Point = TPoint<T>; \ + using Coord = TCoord<Point>; \ + using Contour = TContour<T>; \ + using Box = _Box<Point>; \ + using Circle = _Circle<Point>; \ + using Segment = _Segment<Point>; \ + using Polygons = TMultiShape<T> } diff --git a/xs/src/libnest2d/libnest2d/geometry_traits_nfp.hpp b/xs/src/libnest2d/libnest2d/geometry_traits_nfp.hpp index 90cf21be5..2982454cd 100644 --- a/xs/src/libnest2d/libnest2d/geometry_traits_nfp.hpp +++ b/xs/src/libnest2d/libnest2d/geometry_traits_nfp.hpp @@ -9,6 +9,27 @@ namespace libnest2d { +namespace __nfp { +// Do not specialize this... +template<class RawShape> +inline bool _vsort(const TPoint<RawShape>& v1, const TPoint<RawShape>& v2) +{ + using Coord = TCoord<TPoint<RawShape>>; + Coord &&x1 = getX(v1), &&x2 = getX(v2), &&y1 = getY(v1), &&y2 = getY(v2); + auto diff = y1 - y2; + if(std::abs(diff) <= std::numeric_limits<Coord>::epsilon()) + return x1 < x2; + + return diff < 0; +} +} + +/// A collection of static methods for handling the no fit polygon creation. +namespace nfp { + +//namespace sl = shapelike; +//namespace pl = pointlike; + /// The complexity level of a polygon that an NFP implementation can handle. enum class NfpLevel: unsigned { CONVEX_ONLY, @@ -18,12 +39,17 @@ enum class NfpLevel: unsigned { BOTH_CONCAVE_WITH_HOLES }; -/// A collection of static methods for handling the no fit polygon creation. -struct Nfp { +template<class RawShape> +using NfpResult = std::pair<RawShape, TPoint<RawShape>>; + +template<class RawShape> struct MaxNfpLevel { + static const BP2D_CONSTEXPR NfpLevel value = NfpLevel::CONVEX_ONLY; +}; + // Shorthand for a pile of polygons template<class RawShape> -using Shapes = typename ShapeLike::Shapes<RawShape>; +using Shapes = TMultiShape<RawShape>; /** * Merge a bunch of polygons with the specified additional polygon. @@ -36,10 +62,10 @@ using Shapes = typename ShapeLike::Shapes<RawShape>; * mostly it will be a set containing only one big polygon but if the input * polygons are disjuct than the resulting set will contain more polygons. */ -template<class RawShape> -static Shapes<RawShape> merge(const Shapes<RawShape>& /*shc*/) +template<class RawShapes> +inline RawShapes merge(const RawShapes& /*shc*/) { - static_assert(always_false<RawShape>::value, + static_assert(always_false<RawShapes>::value, "Nfp::merge(shapes, shape) unimplemented!"); } @@ -55,25 +81,12 @@ static Shapes<RawShape> merge(const Shapes<RawShape>& /*shc*/) * polygons are disjuct than the resulting set will contain more polygons. */ template<class RawShape> -static Shapes<RawShape> merge(const Shapes<RawShape>& shc, - const RawShape& sh) +inline TMultiShape<RawShape> merge(const TMultiShape<RawShape>& shc, + const RawShape& sh) { - auto m = merge(shc); + auto m = nfp::merge(shc); m.push_back(sh); - return merge(m); -} - -/** - * A method to get a vertex from a polygon that always maintains a relative - * position to the coordinate system: It is always the rightmost top vertex. - * - * This way it does not matter in what order the vertices are stored, the - * reference will be always the same for the same polygon. - */ -template<class RawShape> -inline static TPoint<RawShape> referenceVertex(const RawShape& sh) -{ - return rightmostUpVertex(sh); + return nfp::merge(m); } /** @@ -82,14 +95,14 @@ inline static TPoint<RawShape> referenceVertex(const RawShape& sh) * the result will be the leftmost (with the highest X coordinate). */ template<class RawShape> -static TPoint<RawShape> leftmostDownVertex(const RawShape& sh) +inline TPoint<RawShape> leftmostDownVertex(const RawShape& sh) { // find min x and min y vertex - auto it = std::min_element(ShapeLike::cbegin(sh), ShapeLike::cend(sh), - _vsort<RawShape>); + auto it = std::min_element(shapelike::cbegin(sh), shapelike::cend(sh), + __nfp::_vsort<RawShape>); - return *it; + return it == shapelike::cend(sh) ? TPoint<RawShape>() : *it;; } /** @@ -98,26 +111,27 @@ static TPoint<RawShape> leftmostDownVertex(const RawShape& sh) * the result will be the rightmost (with the lowest X coordinate). */ template<class RawShape> -static TPoint<RawShape> rightmostUpVertex(const RawShape& sh) +TPoint<RawShape> rightmostUpVertex(const RawShape& sh) { // find max x and max y vertex - auto it = std::max_element(ShapeLike::cbegin(sh), ShapeLike::cend(sh), - _vsort<RawShape>); + auto it = std::max_element(shapelike::cbegin(sh), shapelike::cend(sh), + __nfp::_vsort<RawShape>); - return *it; + return it == shapelike::cend(sh) ? TPoint<RawShape>() : *it; } +/** + * A method to get a vertex from a polygon that always maintains a relative + * position to the coordinate system: It is always the rightmost top vertex. + * + * This way it does not matter in what order the vertices are stored, the + * reference will be always the same for the same polygon. + */ template<class RawShape> -using NfpResult = std::pair<RawShape, TPoint<RawShape>>; - -/// Helper function to get the NFP -template<NfpLevel nfptype, class RawShape> -static NfpResult<RawShape> noFitPolygon(const RawShape& sh, - const RawShape& other) +inline TPoint<RawShape> referenceVertex(const RawShape& sh) { - NfpImpl<RawShape, nfptype> nfp; - return nfp(sh, other); + return rightmostUpVertex(sh); } /** @@ -139,11 +153,11 @@ static NfpResult<RawShape> noFitPolygon(const RawShape& sh, * */ template<class RawShape> -static NfpResult<RawShape> nfpConvexOnly(const RawShape& sh, +inline NfpResult<RawShape> nfpConvexOnly(const RawShape& sh, const RawShape& other) { using Vertex = TPoint<RawShape>; using Edge = _Segment<Vertex>; - using sl = ShapeLike; + namespace sl = shapelike; RawShape rsh; // Final nfp placeholder Vertex top_nfp; @@ -187,7 +201,7 @@ static NfpResult<RawShape> nfpConvexOnly(const RawShape& sh, sl::addVertex(rsh, edgelist.front().second()); // Sorting function for the nfp reference vertex search - auto& cmp = _vsort<RawShape>; + auto& cmp = __nfp::_vsort<RawShape>; // the reference (rightmost top) vertex so far top_nfp = *std::max_element(sl::cbegin(rsh), sl::cend(rsh), cmp ); @@ -214,7 +228,7 @@ static NfpResult<RawShape> nfpConvexOnly(const RawShape& sh, } template<class RawShape> -static NfpResult<RawShape> nfpSimpleSimple(const RawShape& cstationary, +NfpResult<RawShape> nfpSimpleSimple(const RawShape& cstationary, const RawShape& cother) { @@ -233,7 +247,7 @@ static NfpResult<RawShape> nfpSimpleSimple(const RawShape& cstationary, using Vertex = TPoint<RawShape>; using Coord = TCoord<Vertex>; using Edge = _Segment<Vertex>; - using sl = ShapeLike; + namespace sl = shapelike; using std::signbit; using std::sort; using std::vector; @@ -528,27 +542,16 @@ struct NfpImpl { } }; -template<class RawShape> struct MaxNfpLevel { - static const BP2D_CONSTEXPR NfpLevel value = NfpLevel::CONVEX_ONLY; -}; - -private: - -// Do not specialize this... -template<class RawShape> -static inline bool _vsort(const TPoint<RawShape>& v1, - const TPoint<RawShape>& v2) +/// Helper function to get the NFP +template<NfpLevel nfptype, class RawShape> +inline NfpResult<RawShape> noFitPolygon(const RawShape& sh, + const RawShape& other) { - using Coord = TCoord<TPoint<RawShape>>; - Coord &&x1 = getX(v1), &&x2 = getX(v2), &&y1 = getY(v1), &&y2 = getY(v2); - auto diff = y1 - y2; - if(std::abs(diff) <= std::numeric_limits<Coord>::epsilon()) - return x1 < x2; - - return diff < 0; + NfpImpl<RawShape, nfptype> nfps; + return nfps(sh, other); } -}; +} } diff --git a/xs/src/libnest2d/libnest2d/libnest2d.hpp b/xs/src/libnest2d/libnest2d/libnest2d.hpp index 7f23de358..4d1e62f99 100644 --- a/xs/src/libnest2d/libnest2d/libnest2d.hpp +++ b/xs/src/libnest2d/libnest2d/libnest2d.hpp @@ -9,10 +9,12 @@ #include <functional> #include "geometry_traits.hpp" -#include "optimizer.hpp" namespace libnest2d { +namespace sl = shapelike; +namespace pl = pointlike; + /** * \brief An item to be placed on a bin. * @@ -28,7 +30,8 @@ class _Item { using Coord = TCoord<TPoint<RawShape>>; using Vertex = TPoint<RawShape>; using Box = _Box<Vertex>; - using sl = ShapeLike; + + using VertexConstIterator = typename TContour<RawShape>::const_iterator; // The original shape that gets encapsulated. RawShape sh_; @@ -38,7 +41,7 @@ class _Item { Radians rotation_; Coord offset_distance_; - // Info about whether the tranformations will have to take place + // Info about whether the transformations will have to take place // This is needed because if floating point is used, it is hard to say // that a zero angle is not a rotation because of testing for equality. bool has_rotation_ = false, has_translation_ = false, has_offset_ = false; @@ -58,12 +61,12 @@ class _Item { }; mutable Convexity convexity_ = Convexity::UNCHECKED; - mutable TVertexConstIterator<RawShape> rmt_; // rightmost top vertex - mutable TVertexConstIterator<RawShape> lmb_; // leftmost bottom vertex + mutable VertexConstIterator rmt_; // rightmost top vertex + mutable VertexConstIterator lmb_; // leftmost bottom vertex mutable bool rmt_valid_ = false, lmb_valid_ = false; mutable struct BBCache { - Box bb; bool valid; Vertex tr; - BBCache(): valid(false), tr(0, 0) {} + Box bb; bool valid; + BBCache(): valid(false) {} } bb_cache_; public: @@ -80,7 +83,7 @@ public: * supports. Giving out a non const iterator would make it impossible to * perform correct cache invalidation. */ - using Iterator = TVertexConstIterator<RawShape>; + using Iterator = VertexConstIterator; /** * @brief Get the orientation of the polygon. @@ -109,7 +112,7 @@ public: explicit inline _Item(RawShape&& sh): sh_(std::move(sh)) {} /** - * @brief Create an item from an initilizer list. + * @brief Create an item from an initializer list. * @param il The initializer list of vertices. */ inline _Item(const std::initializer_list< Vertex >& il): @@ -159,7 +162,7 @@ public: } /** - * @brief Get a copy of an outer vertex whithin the carried shape. + * @brief Get a copy of an outer vertex within the carried shape. * * Note that the vertex considered here is taken from the original shape * that this item is constructed from. This means that no transformation is @@ -244,7 +247,7 @@ public: * @param p * @return */ - inline bool isPointInside(const Vertex& p) const + inline bool isInside(const Vertex& p) const { return sl::isInside(p, transformedShape()); } @@ -307,7 +310,7 @@ public: { if(translation_ != tr) { translation_ = tr; has_translation_ = true; tr_cache_valid_ = false; - bb_cache_.valid = false; + //bb_cache_.valid = false; } } @@ -342,13 +345,19 @@ public: inline Box boundingBox() const { if(!bb_cache_.valid) { - bb_cache_.bb = sl::boundingBox(transformedShape()); - bb_cache_.tr = {0, 0}; + if(!has_rotation_) + bb_cache_.bb = sl::boundingBox(offsettedShape()); + else { + // TODO make sure this works + auto rotsh = offsettedShape(); + sl::rotate(rotsh, rotation_); + bb_cache_.bb = sl::boundingBox(rotsh); + } bb_cache_.valid = true; } - auto &bb = bb_cache_.bb; auto &tr = bb_cache_.tr; - return {bb.minCorner() + tr, bb.maxCorner() + tr}; + auto &bb = bb_cache_.bb; auto &tr = translation_; + return {bb.minCorner() + tr, bb.maxCorner() + tr }; } inline Vertex referenceVertex() const { @@ -438,7 +447,7 @@ public: inline _Rectangle(Unit width, Unit height, // disable this ctor if o != CLOCKWISE enable_if_t< o == TO::CLOCKWISE, int> = 0 ): - _Item<RawShape>( ShapeLike::create<RawShape>( { + _Item<RawShape>( sl::create<RawShape>( { {0, 0}, {0, height}, {width, height}, @@ -452,7 +461,7 @@ public: inline _Rectangle(Unit width, Unit height, // disable this ctor if o != COUNTER_CLOCKWISE enable_if_t< o == TO::COUNTER_CLOCKWISE, int> = 0 ): - _Item<RawShape>( ShapeLike::create<RawShape>( { + _Item<RawShape>( sl::create<RawShape>( { {0, 0}, {width, 0}, {width, height}, @@ -473,18 +482,38 @@ public: template<class RawShape> inline bool _Item<RawShape>::isInside(const _Box<TPoint<RawShape>>& box) const { - return ShapeLike::isInside<RawShape>(boundingBox(), box); + return sl::isInside<RawShape>(boundingBox(), box); } template<class RawShape> inline bool _Item<RawShape>::isInside(const _Circle<TPoint<RawShape>>& circ) const { - return ShapeLike::isInside<RawShape>(transformedShape(), circ); + return sl::isInside<RawShape>(transformedShape(), circ); +} + + +template<class I> using _ItemRef = std::reference_wrapper<I>; +template<class I> using _ItemGroup = std::vector<_ItemRef<I>>; + +template<class Iterator> +struct ConstItemRange { + Iterator from; + Iterator to; + bool valid = false; + + ConstItemRange() = default; + ConstItemRange(Iterator f, Iterator t): from(f), to(t), valid(true) {} +}; + +template<class Container> +inline ConstItemRange<typename Container::const_iterator> +rem(typename Container::const_iterator it, const Container& cont) { + return {std::next(it), cont.end()}; } /** * \brief A wrapper interface (trait) class for any placement strategy provider. * - * If a client want's to use its own placement algorithm, all it has to do is to + * If a client wants to use its own placement algorithm, all it has to do is to * specialize this class template and define all the ten methods it has. It can * use the strategies::PlacerBoilerplace class for creating a new placement * strategy where only the constructor and the trypack method has to be provided @@ -515,8 +544,9 @@ public: */ using PackResult = typename PlacementStrategy::PackResult; - using ItemRef = std::reference_wrapper<Item>; - using ItemGroup = std::vector<ItemRef>; + using ItemRef = _ItemRef<Item>; + using ItemGroup = _ItemGroup<Item>; + using DefaultIterator = typename ItemGroup::const_iterator; /** * @brief Constructor taking the bin and an optional configuration. @@ -536,29 +566,32 @@ public: * Note that it depends on the particular placer implementation how it * reacts to config changes in the middle of a calculation. * - * @param config The configuration object defined by the placement startegy. + * @param config The configuration object defined by the placement strategy. */ inline void configure(const Config& config) { impl_.configure(config); } /** - * @brief A method that tries to pack an item and returns an object - * describing the pack result. - * - * The result can be casted to bool and used as an argument to the accept - * method to accept a succesfully packed item. This way the next packing - * will consider the accepted item as well. The PackResult should carry the - * transformation info so that if the tried item is later modified or tried - * multiple times, the result object should set it to the originally - * determied position. An implementation can be found in the - * strategies::PlacerBoilerplate::PackResult class. + * Try to pack an item with a result object that contains the packing + * information for later accepting it. * - * @param item Ithe item to be packed. - * @return The PackResult object that can be implicitly casted to bool. + * \param item_store A container of items that are intended to be packed + * later. Can be used by the placer to switch tactics. When it's knows that + * many items will come a greedy strategy may not be the best. + * \param from The iterator to the item from which the packing should start, + * including the pointed item + * \param count How many items should be packed. If the value is 1, than + * just the item pointed to by "from" argument should be packed. */ - inline PackResult trypack(Item& item) { return impl_.trypack(item); } + template<class Iter = DefaultIterator> + inline PackResult trypack( + Item& item, + const ConstItemRange<Iter>& remaining = ConstItemRange<Iter>()) + { + return impl_.trypack(item, remaining); + } /** - * @brief A method to accept a previously tried item. + * @brief A method to accept a previously tried item (or items). * * If the pack result is a failure the method should ignore it. * @param r The result of a previous trypack call. @@ -566,19 +599,25 @@ public: inline void accept(PackResult& r) { impl_.accept(r); } /** - * @brief pack Try to pack an item and immediately accept it on success. + * @brief pack Try to pack and immediately accept it on success. * * A default implementation would be to call - * { auto&& r = trypack(item); accept(r); return r; } but we should let the + * { auto&& r = trypack(...); accept(r); return r; } but we should let the * implementor of the placement strategy to harvest any optimizations from - * the absence of an intermadiate step. The above version can still be used + * the absence of an intermediate step. The above version can still be used * in the implementation. * * @param item The item to pack. * @return Returns true if the item was packed or false if it could not be * packed. */ - inline bool pack(Item& item) { return impl_.pack(item); } + template<class Range = ConstItemRange<DefaultIterator>> + inline bool pack( + Item& item, + const Range& remaining = Range()) + { + return impl_.pack(item, remaining); + } /// Unpack the last element (remove it from the list of packed items). inline void unpackLast() { impl_.unpackLast(); } @@ -597,13 +636,6 @@ public: inline double filledArea() const { return impl_.filledArea(); } -#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 @@ -628,15 +660,15 @@ public: * Note that it depends on the particular placer implementation how it * reacts to config changes in the middle of a calculation. * - * @param config The configuration object defined by the selection startegy. + * @param config The configuration object defined by the selection strategy. */ inline void configure(const Config& config) { impl_.configure(config); } /** - * @brief A function callback which should be called whenewer an item or - * a group of items where succesfully packed. + * @brief A function callback which should be called whenever an item or + * a group of items where successfully packed. * @param fn A function callback object taking one unsigned integer as the * number of the remaining items to pack. */ @@ -649,7 +681,7 @@ public: * placer compatible with the PlacementStrategyLike interface. * * \param first, last The first and last iterator if the input sequence. It - * can be only an iterator of a type converitible to Item. + * can be only an iterator of a type convertible to Item. * \param bin. The shape of the bin. It has to be supported by the placement * strategy. * \param An optional config object for the placer. @@ -681,7 +713,7 @@ public: /** * @brief Get the items for a particular bin. * @param binIndex The index of the requested bin. - * @return Returns a list of allitems packed into the requested bin. + * @return Returns a list of all items packed into the requested bin. */ inline ItemGroup itemsForBin(size_t binIndex) { return impl_.itemsForBin(binIndex); @@ -723,15 +755,14 @@ using _IndexedPackGroup = std::vector< >; /** - * The Arranger is the frontend class for the binpack2d library. It takes the + * The Arranger is the front-end class for the libnest2d library. It takes the * input items and outputs the items with the proper transformations to be * inside the provided bin. */ template<class PlacementStrategy, class SelectionStrategy > -class Arranger { +class Nester { using TSel = SelectionStrategyLike<SelectionStrategy>; TSel selector_; - bool use_min_bb_rotation_ = false; public: using Item = typename PlacementStrategy::Item; using ItemRef = std::reference_wrapper<Item>; @@ -769,7 +800,7 @@ public: template<class TBinType = BinType, class PConf = PlacementConfig, class SConf = SelectionConfig> - Arranger( TBinType&& bin, + Nester( TBinType&& bin, Unit min_obj_distance = 0, PConf&& pconfig = PConf(), SConf&& sconfig = SConf()): @@ -802,9 +833,9 @@ public: * the selection algorithm. */ template<class TIterator> - inline PackGroup arrange(TIterator from, TIterator to) + inline PackGroup execute(TIterator from, TIterator to) { - return _arrange(from, to); + return _execute(from, to); } /** @@ -815,20 +846,20 @@ public: * input sequence size. */ template<class TIterator> - inline IndexedPackGroup arrangeIndexed(TIterator from, TIterator to) + inline IndexedPackGroup executeIndexed(TIterator from, TIterator to) { - return _arrangeIndexed(from, to); + return _executeIndexed(from, to); } /// Shorthand to normal arrange method. template<class TIterator> inline PackGroup operator() (TIterator from, TIterator to) { - return _arrange(from, to); + return _execute(from, to); } - /// Set a progress indicatior function object for the selector. - inline Arranger& progressIndicator(ProgressFunction func) + /// Set a progress indicator function object for the selector. + inline Nester& progressIndicator(ProgressFunction func) { selector_.progressIndicator(func); return *this; } @@ -842,24 +873,20 @@ public: return ret; } - inline Arranger& useMinimumBoundigBoxRotation(bool s = true) { - use_min_bb_rotation_ = s; return *this; - } - private: template<class TIterator, class IT = remove_cvref_t<typename TIterator::value_type>, - // This funtion will be used only if the iterators are pointing to - // a type compatible with the binpack2d::_Item template. + // This function will be used only if the iterators are pointing to + // a type compatible with the libnets2d::_Item template. // This way we can use references to input elements as they will // have to exist for the lifetime of this call. class T = enable_if_t< std::is_convertible<IT, TPItem>::value, IT> > - inline PackGroup _arrange(TIterator from, TIterator to, bool = false) + inline PackGroup _execute(TIterator from, TIterator to, bool = false) { - __arrange(from, to); + __execute(from, to); return lastResult(); } @@ -867,28 +894,28 @@ private: class IT = remove_cvref_t<typename TIterator::value_type>, class T = enable_if_t<!std::is_convertible<IT, TPItem>::value, IT> > - inline PackGroup _arrange(TIterator from, TIterator to, int = false) + inline PackGroup _execute(TIterator from, TIterator to, int = false) { item_cache_ = {from, to}; - __arrange(item_cache_.begin(), item_cache_.end()); + __execute(item_cache_.begin(), item_cache_.end()); return lastResult(); } template<class TIterator, class IT = remove_cvref_t<typename TIterator::value_type>, - // This funtion will be used only if the iterators are pointing to - // a type compatible with the binpack2d::_Item template. + // This function will be used only if the iterators are pointing to + // a type compatible with the libnest2d::_Item template. // This way we can use references to input elements as they will // have to exist for the lifetime of this call. class T = enable_if_t< std::is_convertible<IT, TPItem>::value, IT> > - inline IndexedPackGroup _arrangeIndexed(TIterator from, + inline IndexedPackGroup _executeIndexed(TIterator from, TIterator to, bool = false) { - __arrange(from, to); + __execute(from, to); return createIndexedPackGroup(from, to, selector_); } @@ -896,12 +923,12 @@ private: class IT = remove_cvref_t<typename TIterator::value_type>, class T = enable_if_t<!std::is_convertible<IT, TPItem>::value, IT> > - inline IndexedPackGroup _arrangeIndexed(TIterator from, + inline IndexedPackGroup _executeIndexed(TIterator from, TIterator to, int = false) { item_cache_ = {from, to}; - __arrange(item_cache_.begin(), item_cache_.end()); + __execute(item_cache_.begin(), item_cache_.end()); return createIndexedPackGroup(from, to, selector_); } @@ -933,37 +960,12 @@ private: return pg; } - Radians findBestRotation(Item& item) { - opt::StopCriteria stopcr; - stopcr.absolute_score_difference = 0.01; - stopcr.max_iterations = 10000; - opt::TOptimizer<opt::Method::G_GENETIC> solver(stopcr); - - auto orig_rot = item.rotation(); - - auto result = solver.optimize_min([&item, &orig_rot](Radians rot){ - item.rotation(orig_rot + rot); - auto bb = item.boundingBox(); - return std::sqrt(bb.height()*bb.width()); - }, opt::initvals(Radians(0)), opt::bound<Radians>(-Pi/2, Pi/2)); - - item.rotation(orig_rot); - - return std::get<0>(result.optimum); - } - - template<class TIter> inline void __arrange(TIter from, TIter to) + template<class TIter> inline void __execute(TIter from, TIter to) { if(min_obj_distance_ > 0) std::for_each(from, to, [this](Item& item) { item.addOffset(static_cast<Unit>(std::ceil(min_obj_distance_/2.0))); }); - if(use_min_bb_rotation_) - std::for_each(from, to, [this](Item& item){ - Radians rot = findBestRotation(item); - item.rotate(rot); - }); - selector_.template packItems<PlacementStrategy>( from, to, bin_, pconfig_); diff --git a/xs/src/libnest2d/libnest2d/metaloop.hpp b/xs/src/libnest2d/libnest2d/metaloop.hpp index 18755525c..d88988ba1 100644 --- a/xs/src/libnest2d/libnest2d/metaloop.hpp +++ b/xs/src/libnest2d/libnest2d/metaloop.hpp @@ -67,11 +67,11 @@ class metaloop { // need to wrap that in a type (see metaloop::Int). /* - * A helper alias to create integer values wrapped as a type. It is nessecary + * A helper alias to create integer values wrapped as a type. It is necessary * because a non type template parameter (such as int) would be prohibited in * a partial specialization. Also for the same reason we have to use a class * _Metaloop instead of a simple function as a functor. A function cannot be - * partially specialized in a way that is neccesary for this trick. + * partially specialized in a way that is necessary for this trick. */ template<int N> using Int = std::integral_constant<int, N>; @@ -88,7 +88,7 @@ public: // It takes the real functor that can be specified in-place but only // with C++14 because the second parameter's type will depend on the // type of the parameter pack element that is processed. In C++14 we can - // specify this second parameter type as auto in the lamda parameter list. + // specify this second parameter type as auto in the lambda parameter list. inline MapFn(Fn&& fn): fn_(forward<Fn>(fn)) {} template<class T> void operator ()(T&& pack_element) { @@ -146,7 +146,7 @@ public: * version of run is called which does not call itself anymore. * * If you are utterly annoyed, at least you have learned a super crazy - * functional metaprogramming pattern. + * functional meta-programming pattern. */ template<class...Args> using MetaLoop = _MetaLoop<Int<sizeof...(Args)-1>, Args...>; diff --git a/xs/src/libnest2d/libnest2d/optimizer.hpp b/xs/src/libnest2d/libnest2d/optimizer.hpp index c8ed2e378..90d2f2ff9 100644 --- a/xs/src/libnest2d/libnest2d/optimizer.hpp +++ b/xs/src/libnest2d/libnest2d/optimizer.hpp @@ -102,6 +102,9 @@ struct StopCriteria { /// If the relative value difference between two scores. double relative_score_difference = std::nan(""); + /// Stop if this value or better is found. + double stop_score = std::nan(""); + unsigned max_iterations = 0; }; diff --git a/xs/src/libnest2d/libnest2d/optimizers/nlopt_boilerplate.hpp b/xs/src/libnest2d/libnest2d/optimizers/nlopt_boilerplate.hpp index 737ca6e3c..1a0f06e02 100644 --- a/xs/src/libnest2d/libnest2d/optimizers/nlopt_boilerplate.hpp +++ b/xs/src/libnest2d/libnest2d/optimizers/nlopt_boilerplate.hpp @@ -142,10 +142,12 @@ protected: default: ; } - auto abs_diff = stopcr_.absolute_score_difference; - auto rel_diff = stopcr_.relative_score_difference; + double abs_diff = stopcr_.absolute_score_difference; + double rel_diff = stopcr_.relative_score_difference; + double stopval = stopcr_.stop_score; if(!std::isnan(abs_diff)) opt_.set_ftol_abs(abs_diff); if(!std::isnan(rel_diff)) opt_.set_ftol_rel(rel_diff); + if(!std::isnan(stopval)) opt_.set_stopval(stopval); if(this->stopcr_.max_iterations > 0) opt_.set_maxeval(this->stopcr_.max_iterations ); diff --git a/xs/src/libnest2d/libnest2d/placers/bottomleftplacer.hpp b/xs/src/libnest2d/libnest2d/placers/bottomleftplacer.hpp index 775e44e09..18c27c40c 100644 --- a/xs/src/libnest2d/libnest2d/placers/bottomleftplacer.hpp +++ b/xs/src/libnest2d/libnest2d/placers/bottomleftplacer.hpp @@ -5,11 +5,26 @@ #include "placer_boilerplate.hpp" -namespace libnest2d { namespace strategies { +namespace libnest2d { namespace placers { + +template<class T, class = T> struct Epsilon {}; + +template<class T> +struct Epsilon<T, enable_if_t<std::is_integral<T>::value, T> > { + static const T Value = 1; +}; + +template<class T> +struct Epsilon<T, enable_if_t<std::is_floating_point<T>::value, T> > { + static const T Value = 1e-3; +}; template<class RawShape> struct BLConfig { - TCoord<TPoint<RawShape>> min_obj_distance = 0; + DECLARE_MAIN_TYPES(RawShape); + + Coord min_obj_distance = 0; + Coord epsilon = Epsilon<Coord>::Value; bool allow_rotations = false; }; @@ -27,9 +42,13 @@ public: explicit _BottomLeftPlacer(const BinType& bin): Base(bin) {} - PackResult trypack(Item& item) { + template<class Range = ConstItemRange<typename Base::DefaultIter>> + PackResult trypack(Item& item, + const Range& = Range()) + { auto r = _trypack(item); if(!r && Base::config_.allow_rotations) { + item.rotate(Degrees(90)); r =_trypack(item); } @@ -65,20 +84,21 @@ protected: setInitialPosition(item); Unit d = availableSpaceDown(item); - bool can_move = d > 1 /*std::numeric_limits<Unit>::epsilon()*/; + auto eps = config_.epsilon; + bool can_move = d > eps; bool can_be_packed = can_move; bool left = true; while(can_move) { if(left) { // write previous down move and go down - item.translate({0, -d+1}); + item.translate({0, -d+eps}); d = availableSpaceLeft(item); - can_move = d > 1/*std::numeric_limits<Unit>::epsilon()*/; + can_move = d > eps; left = false; } else { // write previous left move and go down - item.translate({-d+1, 0}); + item.translate({-d+eps, 0}); d = availableSpaceDown(item); - can_move = d > 1/*std::numeric_limits<Unit>::epsilon()*/; + can_move = d > eps; left = true; } } @@ -112,10 +132,10 @@ protected: const RawShape& scanpoly) { auto tsh = other.transformedShape(); - return ( ShapeLike::intersects(tsh, scanpoly) || - ShapeLike::isInside(tsh, scanpoly) ) && - ( !ShapeLike::intersects(tsh, item.rawShape()) && - !ShapeLike::isInside(tsh, item.rawShape()) ); + return ( sl::intersects(tsh, scanpoly) || + sl::isInside(tsh, scanpoly) ) && + ( !sl::intersects(tsh, item.rawShape()) && + !sl::isInside(tsh, item.rawShape()) ); } template<class C = Coord> @@ -126,25 +146,25 @@ protected: { auto tsh = other.transformedShape(); - bool inters_scanpoly = ShapeLike::intersects(tsh, scanpoly) && - !ShapeLike::touches(tsh, scanpoly); - bool inters_item = ShapeLike::intersects(tsh, item.rawShape()) && - !ShapeLike::touches(tsh, item.rawShape()); + bool inters_scanpoly = sl::intersects(tsh, scanpoly) && + !sl::touches(tsh, scanpoly); + bool inters_item = sl::intersects(tsh, item.rawShape()) && + !sl::touches(tsh, item.rawShape()); return ( inters_scanpoly || - ShapeLike::isInside(tsh, scanpoly)) && + sl::isInside(tsh, scanpoly)) && ( !inters_item && - !ShapeLike::isInside(tsh, item.rawShape()) + !sl::isInside(tsh, item.rawShape()) ); } - Container itemsInTheWayOf(const Item& item, const Dir dir) { + ItemGroup itemsInTheWayOf(const Item& item, const Dir dir) { // Get the left or down polygon, that has the same area as the shadow // of input item reflected to the left or downwards auto&& scanpoly = dir == Dir::LEFT? leftPoly(item) : downPoly(item); - Container ret; // packed items 'in the way' of item + ItemGroup ret; // packed items 'in the way' of item ret.reserve(items_.size()); // Predicate to find items that are 'in the way' for left (down) move @@ -173,18 +193,18 @@ protected: if(dir == Dir::LEFT) { getCoord = [](const Vertex& v) { return getX(v); }; - availableDistance = PointLike::horizontalDistance<Vertex>; + availableDistance = pointlike::horizontalDistance<Vertex>; availableDistanceSV = [](const Segment& s, const Vertex& v) { - auto ret = PointLike::horizontalDistance<Vertex>(v, s); + auto ret = pointlike::horizontalDistance<Vertex>(v, s); if(ret.second) ret.first = -ret.first; return ret; }; } else { getCoord = [](const Vertex& v) { return getY(v); }; - availableDistance = PointLike::verticalDistance<Vertex>; + availableDistance = pointlike::verticalDistance<Vertex>; availableDistanceSV = [](const Segment& s, const Vertex& v) { - auto ret = PointLike::verticalDistance<Vertex>(v, s); + auto ret = pointlike::verticalDistance<Vertex>(v, s); if(ret.second) ret.first = -ret.first; return ret; }; @@ -214,9 +234,9 @@ protected: assert(pleft.vertexCount() > 0); auto trpleft = pleft.transformedShape(); - auto first = ShapeLike::begin(trpleft); + auto first = sl::begin(trpleft); auto next = first + 1; - auto endit = ShapeLike::end(trpleft); + auto endit = sl::end(trpleft); while(next != endit) { Segment seg(*(first++), *(next++)); @@ -340,16 +360,16 @@ protected: // reserve for all vertices plus 2 for the left horizontal wall, 2 for // the additional vertices for maintaning min object distance - ShapeLike::reserve(rsh, finish-start+4); + sl::reserve(rsh, finish-start+4); /*auto addOthers = [&rsh, finish, start, &item](){ for(size_t i = start+1; i < finish; i++) - ShapeLike::addVertex(rsh, item.vertex(i)); + sl::addVertex(rsh, item.vertex(i)); };*/ auto reverseAddOthers = [&rsh, finish, start, &item](){ for(auto i = finish-1; i > start; i--) - ShapeLike::addVertex(rsh, item.vertex( + sl::addVertex(rsh, item.vertex( static_cast<unsigned long>(i))); }; @@ -361,25 +381,25 @@ protected: // Clockwise polygon construction - ShapeLike::addVertex(rsh, topleft_vertex); + sl::addVertex(rsh, topleft_vertex); if(dir == Dir::LEFT) reverseAddOthers(); else { - ShapeLike::addVertex(rsh, getX(topleft_vertex), 0); - ShapeLike::addVertex(rsh, getX(bottomleft_vertex), 0); + sl::addVertex(rsh, getX(topleft_vertex), 0); + sl::addVertex(rsh, getX(bottomleft_vertex), 0); } - ShapeLike::addVertex(rsh, bottomleft_vertex); + sl::addVertex(rsh, bottomleft_vertex); if(dir == Dir::LEFT) { - ShapeLike::addVertex(rsh, 0, getY(bottomleft_vertex)); - ShapeLike::addVertex(rsh, 0, getY(topleft_vertex)); + sl::addVertex(rsh, 0, getY(bottomleft_vertex)); + sl::addVertex(rsh, 0, getY(topleft_vertex)); } else reverseAddOthers(); // Close the polygon - ShapeLike::addVertex(rsh, topleft_vertex); + sl::addVertex(rsh, topleft_vertex); return rsh; } diff --git a/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp b/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp index 5d09a61fc..c86fb507e 100644 --- a/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp +++ b/xs/src/libnest2d/libnest2d/placers/nfpplacer.hpp @@ -1,21 +1,148 @@ #ifndef NOFITPOLY_HPP #define NOFITPOLY_HPP +#include <cassert> + +// For caching nfps +#include <unordered_map> + +// For parallel for +#include <functional> +#include <iterator> +#include <future> +#include <atomic> + #ifndef NDEBUG #include <iostream> #endif #include "placer_boilerplate.hpp" #include "../geometry_traits_nfp.hpp" #include "libnest2d/optimizer.hpp" -#include <cassert> #include "tools/svgtools.hpp" -namespace libnest2d { namespace strategies { +#ifdef USE_TBB +#include <tbb/parallel_for.h> +#elif defined(_OPENMP) +#include <omp.h> +#endif + +namespace libnest2d { + +namespace __parallel { + +using std::function; +using std::iterator_traits; +template<class It> +using TIteratorValue = typename iterator_traits<It>::value_type; + +template<class Iterator> +inline void enumerate( + Iterator from, Iterator to, + function<void(TIteratorValue<Iterator>, size_t)> fn, + std::launch policy = std::launch::deferred | std::launch::async) +{ + using TN = size_t; + auto iN = to-from; + TN N = iN < 0? 0 : TN(iN); + +#ifdef USE_TBB + if((policy & std::launch::async) == std::launch::async) { + tbb::parallel_for<TN>(0, N, [from, fn] (TN n) { fn(*(from + n), n); } ); + } else { + for(TN n = 0; n < N; n++) fn(*(from + n), n); + } +#elif defined(_OPENMP) + if((policy & std::launch::async) == std::launch::async) { + #pragma omp parallel for + for(TN n = 0; n < N; n++) fn(*(from + n), n); + } + else { + for(TN n = 0; n < N; n++) fn(*(from + n), n); + } +#else + std::vector<std::future<void>> rets(N); + + auto it = from; + for(TN b = 0; b < N; b++) { + rets[b] = std::async(policy, fn, *it++, unsigned(b)); + } + + for(TN fi = 0; fi < N; ++fi) rets[fi].wait(); +#endif +} + +class SpinLock { + static std::atomic_flag locked; +public: + void lock() { + while (locked.test_and_set(std::memory_order_acquire)) { ; } + } + void unlock() { + locked.clear(std::memory_order_release); + } +}; + +std::atomic_flag SpinLock::locked = ATOMIC_FLAG_INIT ; + +} + +namespace __itemhash { + +using Key = size_t; + +template<class S> +Key hash(const _Item<S>& item) { + using Point = TPoint<S>; + using Segment = _Segment<Point>; + + static const int N = 26; + static const int M = N*N - 1; + + std::string ret; + auto& rhs = item.rawShape(); + auto& ctr = sl::getContour(rhs); + auto it = ctr.begin(); + auto nx = std::next(it); + + double circ = 0; + while(nx != ctr.end()) { + Segment seg(*it++, *nx++); + Radians a = seg.angleToXaxis(); + double deg = Degrees(a); + int ms = 'A', ls = 'A'; + while(deg > N) { ms++; deg -= N; } + ls += int(deg); + ret.push_back(char(ms)); ret.push_back(char(ls)); + circ += seg.length(); + } + + it = ctr.begin(); nx = std::next(it); + + while(nx != ctr.end()) { + Segment seg(*it++, *nx++); + auto l = int(M * seg.length() / circ); + int ms = 'A', ls = 'A'; + while(l > N) { ms++; l -= N; } + ls += l; + ret.push_back(char(ms)); ret.push_back(char(ls)); + } + + return std::hash<std::string>()(ret); +} + +template<class S> +using Hash = std::unordered_map<Key, nfp::NfpResult<S>>; + +} + +namespace placers { template<class RawShape> struct NfpPConfig { + using ItemGroup = _ItemGroup<_Item<RawShape>>; + enum class Alignment { CENTER, BOTTOM_LEFT, @@ -45,47 +172,19 @@ struct NfpPConfig { * that will optimize for the best pack efficiency. With a custom fitting * function you can e.g. influence the shape of the arranged pile. * - * \param shapes The first parameter is a container with all the placed - * polygons excluding the current candidate. You can calculate a bounding - * box or convex hull on this pile of polygons without the candidate item - * or push back the candidate item into the container and then calculate - * some features. - * - * \param item The second parameter is the candidate item. - * - * \param occupied_area The third parameter is the sum of areas of the - * items in the first parameter so you don't have to iterate through them - * if you only need their area. - * - * \param norm A norming factor for physical dimensions. E.g. if your score - * is the distance between the item and the bin center, you should divide - * that distance with the norming factor. If the score is an area than - * divide it with the square of the norming factor. Imagine it as a unit of - * distance. - * - * \param penality The fifth parameter is the amount of minimum penality if - * the arranged pile would't fit into the bin. You can use the wouldFit() - * function to check this. Note that the pile can be outside the bin's - * boundaries while the placement algorithm is running. Your job is only to - * check if the pile could be translated into a position in the bin where - * all the items would be inside. For a box shaped bin you can use the - * pile's bounding box to check whether it's width and height is small - * enough. If the pile would not fit, you have to make sure that the - * resulting score will be higher then the penality value. A good solution - * would be to set score = 2*penality-score in case the pile wouldn't fit - * into the bin. + * \param item The only parameter is the candidate item which has info + * about its current position. Your job is to rate this position compared to + * the already packed items. * */ - std::function<double(Nfp::Shapes<RawShape>&, const _Item<RawShape>&, - double, double, double)> - object_function; + std::function<double(const _Item<RawShape>&)> object_function; /** * @brief The quality of search for an optimal placement. * This is a compromise slider between quality and speed. Zero is the * fast and poor solution while 1.0 is the slowest but most accurate. */ - float accuracy = 1.0; + float accuracy = 0.65f; /** * @brief If you want to see items inside other item's holes, you have to @@ -96,6 +195,39 @@ struct NfpPConfig { */ bool explore_holes = false; + /** + * @brief If true, use all CPUs available. Run on a single core otherwise. + */ + bool parallel = true; + + /** + * @brief before_packing Callback that is called just before a search for + * a new item's position is started. You can use this to create various + * cache structures and update them between subsequent packings. + * + * \param merged pile A polygon that is the union of all items in the bin. + * + * \param pile The items parameter is a container with all the placed + * polygons excluding the current candidate. You can for instance check the + * alignment with the candidate item or do anything else. + * + * \param remaining A container with the remaining items waiting to be + * placed. You can use some features about the remaining items to alter to + * score of the current placement. If you know that you have to leave place + * for other items as well, that might influence your decision about where + * the current candidate should be placed. E.g. imagine three big circles + * which you want to place into a box: you might place them in a triangle + * shape which has the maximum pack density. But if there is a 4th big + * circle than you won't be able to pack it. If you knew apriori that + * there four circles are to be placed, you would have placed the first 3 + * into an L shape. This parameter can be used to make these kind of + * decisions (for you or a more intelligent AI). + */ + std::function<void(const nfp::Shapes<RawShape>&, // merged pile + const ItemGroup&, // packed items + const ItemGroup& // remaining items + )> before_packing; + NfpPConfig(): rotations({0.0, Pi/2.0, Pi, 3*Pi/2}), alignment(Alignment::CENTER), starting_point(Alignment::CENTER) {} }; @@ -129,11 +261,11 @@ template<class RawShape> class EdgeCache { void createCache(const RawShape& sh) { { // For the contour - auto first = ShapeLike::cbegin(sh); + auto first = shapelike::cbegin(sh); auto next = std::next(first); - auto endit = ShapeLike::cend(sh); + auto endit = shapelike::cend(sh); - contour_.distances.reserve(ShapeLike::contourVertexCount(sh)); + contour_.distances.reserve(shapelike::contourVertexCount(sh)); while(next != endit) { contour_.emap.emplace_back(*(first++), *(next++)); @@ -142,7 +274,7 @@ template<class RawShape> class EdgeCache { } } - for(auto& h : ShapeLike::holes(sh)) { // For the holes + for(auto& h : shapelike::holes(sh)) { // For the holes auto first = h.begin(); auto next = std::next(first); auto endit = h.end(); @@ -161,12 +293,11 @@ template<class RawShape> class EdgeCache { } size_t stride(const size_t N) const { - using std::ceil; using std::round; using std::pow; return static_cast<Coord>( - std::round(N/std::pow(N, std::pow(accuracy_, 1.0/3.0))) + round(N/pow(N, pow(accuracy_, 1.0/3.0))) ); } @@ -177,6 +308,7 @@ template<class RawShape> class EdgeCache { const auto S = stride(N); contour_.corners.reserve(N / S + 1); + contour_.corners.emplace_back(0.0); auto N_1 = N-1; contour_.corners.emplace_back(0.0); for(size_t i = 0; i < N_1; i += S) { @@ -190,8 +322,8 @@ template<class RawShape> class EdgeCache { if(!hc.corners.empty()) return; const auto N = hc.distances.size(); - const auto S = stride(N); auto N_1 = N-1; + const auto S = stride(N); hc.corners.reserve(N / S + 1); hc.corners.emplace_back(0.0); for(size_t i = 0; i < N_1; i += S) { @@ -290,11 +422,11 @@ public: }; -template<NfpLevel lvl> -struct Lvl { static const NfpLevel value = lvl; }; +template<nfp::NfpLevel lvl> +struct Lvl { static const nfp::NfpLevel value = lvl; }; template<class RawShape> -inline void correctNfpPosition(Nfp::NfpResult<RawShape>& nfp, +inline void correctNfpPosition(nfp::NfpResult<RawShape>& nfp, const _Item<RawShape>& stationary, const _Item<RawShape>& orbiter) { @@ -314,131 +446,78 @@ inline void correctNfpPosition(Nfp::NfpResult<RawShape>& nfp, auto dtouch = touch_sh - touch_other; auto top_other = orbiter.rightmostTopVertex() + dtouch; auto dnfp = top_other - nfp.second; // nfp.second is the nfp reference point - ShapeLike::translate(nfp.first, dnfp); + shapelike::translate(nfp.first, dnfp); } template<class RawShape> -inline void correctNfpPosition(Nfp::NfpResult<RawShape>& nfp, +inline void correctNfpPosition(nfp::NfpResult<RawShape>& nfp, const RawShape& stationary, const _Item<RawShape>& orbiter) { - auto touch_sh = Nfp::rightmostUpVertex(stationary); + auto touch_sh = nfp::rightmostUpVertex(stationary); auto touch_other = orbiter.leftmostBottomVertex(); auto dtouch = touch_sh - touch_other; auto top_other = orbiter.rightmostTopVertex() + dtouch; auto dnfp = top_other - nfp.second; - ShapeLike::translate(nfp.first, dnfp); -} - -template<class RawShape, class Container> -Nfp::Shapes<RawShape> nfp( const Container& polygons, - const _Item<RawShape>& trsh, - Lvl<NfpLevel::CONVEX_ONLY>) -{ - using Item = _Item<RawShape>; - - Nfp::Shapes<RawShape> nfps; - - //int pi = 0; - for(Item& sh : polygons) { - auto subnfp_r = Nfp::noFitPolygon<NfpLevel::CONVEX_ONLY>( - sh.transformedShape(), trsh.transformedShape()); - #ifndef NDEBUG - auto vv = ShapeLike::isValid(sh.transformedShape()); - assert(vv.first); - - auto vnfp = ShapeLike::isValid(subnfp_r.first); - assert(vnfp.first); - #endif - - correctNfpPosition(subnfp_r, sh, trsh); - - nfps = Nfp::merge(nfps, subnfp_r.first); - -// double SCALE = 1000000; -// using SVGWriter = svg::SVGWriter<RawShape>; -// SVGWriter::Config conf; -// conf.mm_in_coord_units = SCALE; -// SVGWriter svgw(conf); -// Box bin(250*SCALE, 210*SCALE); -// svgw.setSize(bin); -// for(int i = 0; i <= pi; i++) svgw.writeItem(polygons[i]); -// svgw.writeItem(trsh); -//// svgw.writeItem(Item(subnfp_r.first)); -// for(auto& n : nfps) svgw.writeItem(Item(n)); -// svgw.save("nfpout"); -// pi++; - } - - return nfps; + shapelike::translate(nfp.first, dnfp); } -template<class RawShape, class Container, class Level> -Nfp::Shapes<RawShape> nfp( const Container& polygons, - const _Item<RawShape>& trsh, - Level) -{ - using Item = _Item<RawShape>; - - Nfp::Shapes<RawShape> nfps; - - auto& orb = trsh.transformedShape(); - bool orbconvex = trsh.isContourConvex(); +template<class RawShape, class Circle = _Circle<TPoint<RawShape>> > +Circle minimizeCircle(const RawShape& sh) { + using Point = TPoint<RawShape>; + using Coord = TCoord<Point>; - for(Item& sh : polygons) { - Nfp::NfpResult<RawShape> subnfp; - auto& stat = sh.transformedShape(); + auto& ctr = sl::getContour(sh); + if(ctr.empty()) return {{0, 0}, 0}; - if(sh.isContourConvex() && orbconvex) - subnfp = Nfp::noFitPolygon<NfpLevel::CONVEX_ONLY>(stat, orb); - else if(orbconvex) - subnfp = Nfp::noFitPolygon<NfpLevel::ONE_CONVEX>(stat, orb); - else - subnfp = Nfp::noFitPolygon<Level::value>(stat, orb); + auto bb = sl::boundingBox(sh); + auto capprx = bb.center(); + auto rapprx = pl::distance(bb.minCorner(), bb.maxCorner()); - correctNfpPosition(subnfp, sh, trsh); - nfps = Nfp::merge(nfps, subnfp.first); - } + opt::StopCriteria stopcr; + stopcr.max_iterations = 30; + stopcr.relative_score_difference = 1e-3; + opt::TOptimizer<opt::Method::L_SUBPLEX> solver(stopcr); - return nfps; + std::vector<double> dists(ctr.size(), 0); + auto result = solver.optimize_min( + [capprx, rapprx, &ctr, &dists](double xf, double yf) { + auto xt = Coord( std::round(getX(capprx) + rapprx*xf) ); + auto yt = Coord( std::round(getY(capprx) + rapprx*yf) ); -// using Item = _Item<RawShape>; -// using sl = ShapeLike; + Point centr(xt, yt); -// Nfp::Shapes<RawShape> nfps, stationary; + unsigned i = 0; + for(auto v : ctr) { + dists[i++] = pl::distance(v, centr); + } -// for(Item& sh : polygons) { -// stationary = Nfp::merge(stationary, sh.transformedShape()); -// } + auto mit = std::max_element(dists.begin(), dists.end()); -// for(RawShape& sh : stationary) { + assert(mit != dists.end()); -//// auto vv = sl::isValid(sh); -//// std::cout << vv.second << std::endl; + return *mit; + }, + opt::initvals(0.0, 0.0), + opt::bound(-1.0, 1.0), opt::bound(-1.0, 1.0) + ); + double oxf = std::get<0>(result.optimum); + double oyf = std::get<1>(result.optimum); + auto xt = Coord( std::round(getX(capprx) + rapprx*oxf) ); + auto yt = Coord( std::round(getY(capprx) + rapprx*oyf) ); -// Nfp::NfpResult<RawShape> subnfp; -// bool shconvex = sl::isConvex<RawShape>(sl::getContour(sh)); -// if(shconvex && trsh.isContourConvex()) { -// subnfp = Nfp::noFitPolygon<NfpLevel::CONVEX_ONLY>( -// sh, trsh.transformedShape()); -// } else if(trsh.isContourConvex()) { -// subnfp = Nfp::noFitPolygon<NfpLevel::ONE_CONVEX>( -// sh, trsh.transformedShape()); -// } -// else { -// subnfp = Nfp::noFitPolygon<Level::value>( sh, -// trsh.transformedShape()); -// } + Point cc(xt, yt); + auto r = result.score; -// correctNfpPosition(subnfp, sh, trsh); - -// nfps = Nfp::merge(nfps, subnfp.first); -// } + return {cc, r}; +} -// return nfps; +template<class RawShape> +_Circle<TPoint<RawShape>> boundingCircle(const RawShape& sh) { + return minimizeCircle(sh); } template<class RawShape, class TBin = _Box<TPoint<RawShape>>> @@ -452,20 +531,26 @@ class _NofitPolyPlacer: public PlacerBoilerplate<_NofitPolyPlacer<RawShape, TBin using Box = _Box<TPoint<RawShape>>; + using MaxNfpLevel = nfp::MaxNfpLevel<RawShape>; + + using ItemKeys = std::vector<__itemhash::Key>; + + // Norming factor for the optimization function const double norm_; - const double penality_; - using MaxNfpLevel = Nfp::MaxNfpLevel<RawShape>; - using sl = ShapeLike; + // Caching calculated nfps + __itemhash::Hash<RawShape> nfpcache_; + + // Storing item hash keys + ItemKeys item_keys_; public: - using Pile = Nfp::Shapes<RawShape>; + using Pile = nfp::Shapes<RawShape>; inline explicit _NofitPolyPlacer(const BinType& bin): Base(bin), - norm_(std::sqrt(sl::area<RawShape>(bin))), - penality_(1e6*norm_) {} + norm_(std::sqrt(sl::area(bin))) {} _NofitPolyPlacer(const _NofitPolyPlacer&) = default; _NofitPolyPlacer& operator=(const _NofitPolyPlacer&) = default; @@ -475,81 +560,322 @@ public: _NofitPolyPlacer& operator=(_NofitPolyPlacer&&) BP2D_NOEXCEPT = default; #endif - bool static inline wouldFit(const Box& bb, const RawShape& bin) { - auto bbin = sl::boundingBox<RawShape>(bin); + static inline double overfit(const Box& bb, const RawShape& bin) { + auto bbin = sl::boundingBox(bin); auto d = bbin.center() - bb.center(); _Rectangle<RawShape> rect(bb.width(), bb.height()); rect.translate(bb.minCorner() + d); - return sl::isInside<RawShape>(rect.transformedShape(), bin); + return sl::isInside(rect.transformedShape(), bin) ? -1.0 : 1; } - bool static inline wouldFit(const RawShape& chull, const RawShape& bin) { - auto bbch = sl::boundingBox<RawShape>(chull); - auto bbin = sl::boundingBox<RawShape>(bin); + static inline double overfit(const RawShape& chull, const RawShape& bin) { + auto bbch = sl::boundingBox(chull); + auto bbin = sl::boundingBox(bin); auto d = bbch.center() - bbin.center(); auto chullcpy = chull; sl::translate(chullcpy, d); - return sl::isInside<RawShape>(chullcpy, bin); + return sl::isInside(chullcpy, bin) ? -1.0 : 1.0; } - bool static inline wouldFit(const RawShape& chull, const Box& bin) + static inline double overfit(const RawShape& chull, const Box& bin) { - auto bbch = sl::boundingBox<RawShape>(chull); - return wouldFit(bbch, bin); + auto bbch = sl::boundingBox(chull); + return overfit(bbch, bin); } - bool static inline wouldFit(const Box& bb, const Box& bin) + static inline double overfit(const Box& bb, const Box& bin) { - return bb.width() <= bin.width() && bb.height() <= bin.height(); + auto wdiff = double(bb.width() - bin.width()); + auto hdiff = double(bb.height() - bin.height()); + double diff = 0; + if(wdiff > 0) diff += wdiff; + if(hdiff > 0) diff += hdiff; + return diff; } - bool static inline wouldFit(const Box& bb, const _Circle<Vertex>& bin) + static inline double overfit(const Box& bb, const _Circle<Vertex>& bin) { - return sl::isInside<RawShape>(bb, bin); + double boxr = 0.5*pl::distance(bb.minCorner(), bb.maxCorner()); + double diff = boxr - bin.radius(); + return diff; } - bool static inline wouldFit(const RawShape& chull, + static inline double overfit(const RawShape& chull, const _Circle<Vertex>& bin) { - return sl::isInside<RawShape>(chull, bin); + double r = boundingCircle(chull).radius(); + double diff = r - bin.radius(); + return diff; + } + + template<class Range = ConstItemRange<typename Base::DefaultIter>> + PackResult trypack(Item& item, + const Range& remaining = Range()) { + auto result = _trypack(item, remaining); + + // Experimental + // if(!result) repack(item, result); + + return result; + } + + ~_NofitPolyPlacer() { + clearItems(); + } + + inline void clearItems() { + finalAlign(bin_); + Base::clearItems(); + } + +private: + + using Shapes = TMultiShape<RawShape>; + using ItemRef = std::reference_wrapper<Item>; + using ItemWithHash = const std::pair<ItemRef, __itemhash::Key>; + + Shapes calcnfp(const ItemWithHash itsh, Lvl<nfp::NfpLevel::CONVEX_ONLY>) + { + using namespace nfp; + + Shapes nfps(items_.size()); + const Item& trsh = itsh.first; + + __parallel::enumerate(items_.begin(), items_.end(), + [&nfps, &trsh](const Item& sh, size_t n) + { + auto& fixedp = sh.transformedShape(); + auto& orbp = trsh.transformedShape(); + auto subnfp_r = noFitPolygon<NfpLevel::CONVEX_ONLY>(fixedp, orbp); + correctNfpPosition(subnfp_r, sh, trsh); + nfps[n] = subnfp_r.first; + }); + +// for(auto& n : nfps) { +// auto valid = sl::isValid(n); +// if(!valid.first) std::cout << "Warning: " << valid.second << std::endl; +// } + + return nfp::merge(nfps); } - PackResult trypack(Item& item) { + template<class Level> + Shapes calcnfp( const ItemWithHash itsh, Level) + { // Function for arbitrary level of nfp implementation + using namespace nfp; + + Shapes nfps; + const Item& trsh = itsh.first; + + auto& orb = trsh.transformedShape(); + bool orbconvex = trsh.isContourConvex(); + + for(Item& sh : items_) { + nfp::NfpResult<RawShape> subnfp; + auto& stat = sh.transformedShape(); + + if(sh.isContourConvex() && orbconvex) + subnfp = nfp::noFitPolygon<NfpLevel::CONVEX_ONLY>(stat, orb); + else if(orbconvex) + subnfp = nfp::noFitPolygon<NfpLevel::ONE_CONVEX>(stat, orb); + else + subnfp = nfp::noFitPolygon<Level::value>(stat, orb); + + correctNfpPosition(subnfp, sh, trsh); + + nfps = nfp::merge(nfps, subnfp.first); + } + + return nfps; + } + + // Very much experimental + void repack(Item& item, PackResult& result) { + + if((sl::area(bin_) - this->filledArea()) >= item.area()) { + auto prev_func = config_.object_function; + + unsigned iter = 0; + ItemGroup backup_rf = items_; + std::vector<Item> backup_cpy; + for(Item& itm : items_) backup_cpy.emplace_back(itm); + + auto ofn = [this, &item, &result, &iter, &backup_cpy, &backup_rf] + (double ratio) + { + auto& bin = bin_; + iter++; + config_.object_function = [bin, ratio]( + nfp::Shapes<RawShape>& pile, + const Item& item, + const ItemGroup& /*remaining*/) + { + pile.emplace_back(item.transformedShape()); + auto ch = sl::convexHull(pile); + auto pbb = sl::boundingBox(pile); + pile.pop_back(); + + double parea = 0.5*(sl::area(ch) + sl::area(pbb)); + + double pile_area = std::accumulate( + pile.begin(), pile.end(), item.area(), + [](double sum, const RawShape& sh){ + return sum + sl::area(sh); + }); + + // The pack ratio -- how much is the convex hull occupied + double pack_rate = (pile_area)/parea; + + // ratio of waste + double waste = 1.0 - pack_rate; + + // Score is the square root of waste. This will extend the + // range of good (lower) values and shrink the range of bad + // (larger) values. + auto wscore = std::sqrt(waste); + + + auto ibb = item.boundingBox(); + auto bbb = sl::boundingBox(bin); + auto c = ibb.center(); + double norm = 0.5*pl::distance(bbb.minCorner(), + bbb.maxCorner()); + + double dscore = pl::distance(c, pbb.center()) / norm; + + return ratio*wscore + (1.0 - ratio) * dscore; + }; + + auto bb = sl::boundingBox(bin); + double norm = bb.width() + bb.height(); + + auto items = items_; + clearItems(); + auto it = items.begin(); + while(auto pr = _trypack(*it++)) { + this->accept(pr); if(it == items.end()) break; + } + + auto count_diff = items.size() - items_.size(); + double score = count_diff; + + if(count_diff == 0) { + result = _trypack(item); + + if(result) { + std::cout << "Success" << std::endl; + score = 0.0; + } else { + score += result.overfit() / norm; + } + } else { + result = PackResult(); + items_ = backup_rf; + for(unsigned i = 0; i < items_.size(); i++) { + items_[i].get() = backup_cpy[i]; + } + } + + std::cout << iter << " repack result: " << score << " " + << ratio << " " << count_diff << std::endl; + + return score; + }; + + opt::StopCriteria stopcr; + stopcr.max_iterations = 30; + stopcr.stop_score = 1e-20; + opt::TOptimizer<opt::Method::L_SUBPLEX> solver(stopcr); + solver.optimize_min(ofn, opt::initvals(0.5), + opt::bound(0.0, 1.0)); + + // optimize + config_.object_function = prev_func; + } + + } + + struct Optimum { + double relpos; + unsigned nfpidx; + int hidx; + Optimum(double pos, unsigned nidx): + relpos(pos), nfpidx(nidx), hidx(-1) {} + Optimum(double pos, unsigned nidx, int holeidx): + relpos(pos), nfpidx(nidx), hidx(holeidx) {} + }; + + class Optimizer: public opt::TOptimizer<opt::Method::L_SUBPLEX> { + public: + Optimizer() { + opt::StopCriteria stopcr; + stopcr.max_iterations = 200; + stopcr.relative_score_difference = 1e-20; + this->stopcr_ = stopcr; + } + }; + + static Box boundingBox(const Box& pilebb, const Box& ibb ) { + auto& pminc = pilebb.minCorner(); + auto& pmaxc = pilebb.maxCorner(); + auto& iminc = ibb.minCorner(); + auto& imaxc = ibb.maxCorner(); + Vertex minc, maxc; + + setX(minc, std::min(getX(pminc), getX(iminc))); + setY(minc, std::min(getY(pminc), getY(iminc))); + + setX(maxc, std::max(getX(pmaxc), getX(imaxc))); + setY(maxc, std::max(getY(pmaxc), getY(imaxc))); + return Box(minc, maxc); + } + + using Edges = EdgeCache<RawShape>; + + template<class Range = ConstItemRange<typename Base::DefaultIter>> + PackResult _trypack( + Item& item, + const Range& remaining = Range()) { PackResult ret; bool can_pack = false; + double best_overfit = std::numeric_limits<double>::max(); + + auto remlist = ItemGroup(remaining.from, remaining.to); + size_t itemhash = __itemhash::hash(item); if(items_.empty()) { setInitialPosition(item); - can_pack = item.isInside(bin_); + best_overfit = overfit(item.transformedShape(), bin_); + can_pack = best_overfit <= 0; } else { - double global_score = penality_; + double global_score = std::numeric_limits<double>::max(); auto initial_tr = item.translation(); auto initial_rot = item.rotation(); Vertex final_tr = {0, 0}; Radians final_rot = initial_rot; - Nfp::Shapes<RawShape> nfps; + Shapes nfps; for(auto rot : config_.rotations) { item.translation(initial_tr); item.rotation(initial_rot + rot); + item.boundingBox(); // fill the bb cache // place the new item outside of the print bed to make sure - // it is disjuct from the current merged pile + // it is disjunct from the current merged pile placeOutsideOfBin(item); - auto trsh = item.transformedShape(); + nfps = calcnfp({item, itemhash}, Lvl<MaxNfpLevel::value>()); - nfps = nfp(items_, item, Lvl<MaxNfpLevel::value>()); - auto iv = Nfp::referenceVertex(trsh); + auto iv = item.referenceVertex(); auto startpos = item.translation(); - std::vector<EdgeCache<RawShape>> ecache; + std::vector<Edges> ecache; ecache.reserve(nfps.size()); for(auto& nfp : nfps ) { @@ -557,79 +883,59 @@ public: ecache.back().accuracy(config_.accuracy); } - struct Optimum { - double relpos; - unsigned nfpidx; - int hidx; - Optimum(double pos, unsigned nidx): - relpos(pos), nfpidx(nidx), hidx(-1) {} - Optimum(double pos, unsigned nidx, int holeidx): - relpos(pos), nfpidx(nidx), hidx(holeidx) {} - }; - - auto getNfpPoint = [&ecache](const Optimum& opt) - { - return opt.hidx < 0? ecache[opt.nfpidx].coords(opt.relpos) : - ecache[opt.nfpidx].coords(opt.hidx, opt.relpos); - }; - - Nfp::Shapes<RawShape> pile; + Shapes pile; pile.reserve(items_.size()+1); - double pile_area = 0; + // double pile_area = 0; for(Item& mitem : items_) { pile.emplace_back(mitem.transformedShape()); - pile_area += mitem.area(); + // pile_area += mitem.area(); } - auto merged_pile = Nfp::merge(pile); + auto merged_pile = nfp::merge(pile); + auto& bin = bin_; + double norm = norm_; + auto pbb = sl::boundingBox(merged_pile); + auto binbb = sl::boundingBox(bin); // This is the kernel part of the object function that is // customizable by the library client auto _objfunc = config_.object_function? config_.object_function : - [this, &merged_pile]( - Nfp::Shapes<RawShape>& /*pile*/, - const Item& item, - double occupied_area, - double norm, - double /*penality*/) + [norm, bin, binbb, pbb](const Item& item) { - merged_pile.emplace_back(item.transformedShape()); - auto ch = sl::convexHull(merged_pile); - merged_pile.pop_back(); + auto ibb = item.boundingBox(); + auto fullbb = boundingBox(pbb, ibb); - // The pack ratio -- how much is the convex hull occupied - double pack_rate = occupied_area/sl::area(ch); + double score = pl::distance(ibb.center(), binbb.center()); + score /= norm; - // ratio of waste - double waste = 1.0 - pack_rate; - - // Score is the square root of waste. This will extend the - // range of good (lower) values and shring the range of bad - // (larger) values. - auto score = std::sqrt(waste); - - if(!wouldFit(ch, bin_)) score += norm; + double miss = overfit(fullbb, bin); + miss = miss > 0? miss : 0; + score += std::pow(miss, 2); return score; }; // Our object function for placement - auto rawobjfunc = [&] (Vertex v) + auto rawobjfunc = + [_objfunc, iv, startpos] (Vertex v, Item& itm) { auto d = v - iv; d += startpos; - item.translation(d); - - double occupied_area = pile_area + item.area(); - - double score = _objfunc(pile, item, occupied_area, - norm_, penality_); + itm.translation(d); + return _objfunc(itm); + }; - return score; + auto getNfpPoint = [&ecache](const Optimum& opt) + { + return opt.hidx < 0? ecache[opt.nfpidx].coords(opt.relpos) : + ecache[opt.nfpidx].coords(opt.hidx, opt.relpos); }; - auto boundaryCheck = [&](const Optimum& o) { + auto boundaryCheck = + [&merged_pile, &getNfpPoint, &item, &bin, &iv, &startpos] + (const Optimum& o) + { auto v = getNfpPoint(o); auto d = v - iv; d += startpos; @@ -639,84 +945,123 @@ public: auto chull = sl::convexHull(merged_pile); merged_pile.pop_back(); - return wouldFit(chull, bin_); + return overfit(chull, bin); }; - opt::StopCriteria stopcr; - stopcr.max_iterations = 100; - stopcr.relative_score_difference = 1e-6; - opt::TOptimizer<opt::Method::L_SUBPLEX> solver(stopcr); - Optimum optimum(0, 0); - double best_score = penality_; + double best_score = std::numeric_limits<double>::max(); + std::launch policy = std::launch::deferred; + if(config_.parallel) policy |= std::launch::async; + + if(config_.before_packing) + config_.before_packing(merged_pile, items_, remlist); + + using OptResult = opt::Result<double>; + using OptResults = std::vector<OptResult>; // Local optimization with the four polygon corners as // starting points for(unsigned ch = 0; ch < ecache.size(); ch++) { auto& cache = ecache[ch]; - auto contour_ofn = [&rawobjfunc, &getNfpPoint, ch] - (double relpos) - { - return rawobjfunc(getNfpPoint(Optimum(relpos, ch))); - }; + OptResults results(cache.corners().size()); + + auto& rofn = rawobjfunc; + auto& nfpoint = getNfpPoint; - std::for_each(cache.corners().begin(), - cache.corners().end(), - [ch, &contour_ofn, &solver, &best_score, - &optimum, &boundaryCheck] (double pos) + __parallel::enumerate( + cache.corners().begin(), + cache.corners().end(), + [&results, &item, &rofn, &nfpoint, ch] + (double pos, size_t n) { + Optimizer solver; + + Item itemcpy = item; + auto contour_ofn = [&rofn, &nfpoint, ch, &itemcpy] + (double relpos) + { + Optimum op(relpos, ch); + return rofn(nfpoint(op), itemcpy); + }; + try { - auto result = solver.optimize_min(contour_ofn, + results[n] = solver.optimize_min(contour_ofn, opt::initvals<double>(pos), opt::bound<double>(0, 1.0) ); - - if(result.score < best_score) { - Optimum o(std::get<0>(result.optimum), ch, -1); - if(boundaryCheck(o)) { - best_score = result.score; - optimum = o; - } - } } catch(std::exception& e) { derr() << "ERROR: " << e.what() << "\n"; } - }); + }, policy); + + auto resultcomp = + []( const OptResult& r1, const OptResult& r2 ) { + return r1.score < r2.score; + }; + + auto mr = *std::min_element(results.begin(), results.end(), + resultcomp); + + if(mr.score < best_score) { + Optimum o(std::get<0>(mr.optimum), ch, -1); + double miss = boundaryCheck(o); + if(miss <= 0) { + best_score = mr.score; + optimum = o; + } else { + best_overfit = std::min(miss, best_overfit); + } + } for(unsigned hidx = 0; hidx < cache.holeCount(); ++hidx) { - auto hole_ofn = - [&rawobjfunc, &getNfpPoint, ch, hidx] - (double pos) - { - Optimum opt(pos, ch, hidx); - return rawobjfunc(getNfpPoint(opt)); - }; + results.clear(); + results.resize(cache.corners(hidx).size()); - std::for_each(cache.corners(hidx).begin(), + // TODO : use parallel for + __parallel::enumerate(cache.corners(hidx).begin(), cache.corners(hidx).end(), - [&hole_ofn, &solver, &best_score, - &optimum, ch, hidx, &boundaryCheck] - (double pos) + [&results, &item, &nfpoint, + &rofn, ch, hidx] + (double pos, size_t n) { + Optimizer solver; + + Item itmcpy = item; + auto hole_ofn = + [&rofn, &nfpoint, ch, hidx, &itmcpy] + (double pos) + { + Optimum opt(pos, ch, hidx); + return rofn(nfpoint(opt), itmcpy); + }; + try { - auto result = solver.optimize_min(hole_ofn, + results[n] = solver.optimize_min(hole_ofn, opt::initvals<double>(pos), opt::bound<double>(0, 1.0) ); - if(result.score < best_score) { - Optimum o(std::get<0>(result.optimum), - ch, hidx); - if(boundaryCheck(o)) { - best_score = result.score; - optimum = o; - } - } } catch(std::exception& e) { derr() << "ERROR: " << e.what() << "\n"; } - }); + }, policy); + + auto hmr = *std::min_element(results.begin(), + results.end(), + resultcomp); + + if(hmr.score < best_score) { + Optimum o(std::get<0>(hmr.optimum), + ch, hidx); + double miss = boundaryCheck(o); + if(miss <= 0.0) { + best_score = hmr.score; + optimum = o; + } else { + best_overfit = std::min(miss, best_overfit); + } + } } } @@ -736,24 +1081,39 @@ public: if(can_pack) { ret = PackResult(item); + item_keys_.emplace_back(itemhash); + } else { + ret = PackResult(best_overfit); } return ret; } - ~_NofitPolyPlacer() { - clearItems(); + inline void finalAlign(const RawShape& pbin) { + auto bbin = sl::boundingBox(pbin); + finalAlign(bbin); } - inline void clearItems() { - Nfp::Shapes<RawShape> m; + inline void finalAlign(_Circle<TPoint<RawShape>> cbin) { + if(items_.empty()) return; + nfp::Shapes<RawShape> m; m.reserve(items_.size()); + for(Item& item : items_) m.emplace_back(item.transformedShape()); + auto c = boundingCircle(sl::convexHull(m)); + + auto d = cbin.center() - c.center(); + for(Item& item : items_) item.translate(d); + } + + inline void finalAlign(Box bbin) { + if(items_.empty()) return; + nfp::Shapes<RawShape> m; + m.reserve(items_.size()); for(Item& item : items_) m.emplace_back(item.transformedShape()); - auto&& bb = sl::boundingBox<RawShape>(m); + auto&& bb = sl::boundingBox(m); Vertex ci, cb; - auto bbin = sl::boundingBox<RawShape>(bin_); switch(config_.alignment) { case Config::Alignment::CENTER: { @@ -785,16 +1145,12 @@ public: auto d = cb - ci; for(Item& item : items_) item.translate(d); - - Base::clearItems(); } -private: - void setInitialPosition(Item& item) { Box&& bb = item.boundingBox(); Vertex ci, cb; - auto bbin = sl::boundingBox<RawShape>(bin_); + auto bbin = sl::boundingBox(bin_); switch(config_.starting_point) { case Config::Alignment::CENTER: { @@ -830,7 +1186,7 @@ private: void placeOutsideOfBin(Item& item) { auto&& bb = item.boundingBox(); - Box binbb = sl::boundingBox<RawShape>(bin_); + Box binbb = sl::boundingBox(bin_); Vertex v = { getX(bb.maxCorner()), getY(bb.minCorner()) }; diff --git a/xs/src/libnest2d/libnest2d/placers/placer_boilerplate.hpp b/xs/src/libnest2d/libnest2d/placers/placer_boilerplate.hpp index 9d2cb626b..0df1b8c91 100644 --- a/xs/src/libnest2d/libnest2d/placers/placer_boilerplate.hpp +++ b/xs/src/libnest2d/libnest2d/placers/placer_boilerplate.hpp @@ -3,14 +3,11 @@ #include "../libnest2d.hpp" -namespace libnest2d { namespace strategies { +namespace libnest2d { namespace placers { struct EmptyConfig {}; -template<class Subclass, class RawShape, class TBin, - class Cfg = EmptyConfig, - class Store = std::vector<std::reference_wrapper<_Item<RawShape>>> - > +template<class Subclass, class RawShape, class TBin, class Cfg = EmptyConfig> class PlacerBoilerplate { mutable bool farea_valid_ = false; mutable double farea_ = 0.0; @@ -22,25 +19,30 @@ public: using Coord = TCoord<Vertex>; using Unit = Coord; using Config = Cfg; - using Container = Store; + using ItemGroup = _ItemGroup<Item>; + using DefaultIter = typename ItemGroup::const_iterator; class PackResult { Item *item_ptr_; Vertex move_; Radians rot_; + double overfit_; friend class PlacerBoilerplate; friend Subclass; + PackResult(Item& item): item_ptr_(&item), move_(item.translation()), rot_(item.rotation()) {} - PackResult(): item_ptr_(nullptr) {} + + PackResult(double overfit = 1.0): + item_ptr_(nullptr), overfit_(overfit) {} + public: operator bool() { return item_ptr_ != nullptr; } + double overfit() const { return overfit_; } }; - using ItemGroup = const Container&; - inline PlacerBoilerplate(const BinType& bin, unsigned cap = 50): bin_(bin) { items_.reserve(cap); @@ -56,8 +58,10 @@ public: config_ = config; } - bool pack(Item& item) { - auto&& r = static_cast<Subclass*>(this)->trypack(item); + template<class Range = ConstItemRange<DefaultIter>> + bool pack(Item& item, + const Range& rem = Range()) { + auto&& r = static_cast<Subclass*>(this)->trypack(item, rem); if(r) { items_.push_back(*(r.item_ptr_)); farea_valid_ = false; @@ -79,14 +83,11 @@ public: farea_valid_ = false; } - inline ItemGroup getItems() const { return items_; } + inline const ItemGroup& getItems() const { return items_; } inline void clearItems() { items_.clear(); farea_valid_ = false; -#ifndef NDEBUG - debug_items_.clear(); -#endif } inline double filledArea() const { @@ -103,14 +104,10 @@ public: return farea_; } -#ifndef NDEBUG - std::vector<Item> debug_items_; -#endif - protected: BinType bin_; - Container items_; + ItemGroup items_; Cfg config_; }; @@ -121,6 +118,7 @@ using Base::items_; \ using Base::config_; \ public: \ using typename Base::Item; \ +using typename Base::ItemGroup; \ using typename Base::BinType; \ using typename Base::Config; \ using typename Base::Vertex; \ @@ -128,7 +126,6 @@ using typename Base::Segment; \ using typename Base::PackResult; \ using typename Base::Coord; \ using typename Base::Unit; \ -using typename Base::Container; \ private: } diff --git a/xs/src/libnest2d/libnest2d/rotfinder.hpp b/xs/src/libnest2d/libnest2d/rotfinder.hpp new file mode 100644 index 000000000..525fd8759 --- /dev/null +++ b/xs/src/libnest2d/libnest2d/rotfinder.hpp @@ -0,0 +1,41 @@ +#ifndef ROTFINDER_HPP +#define ROTFINDER_HPP + +#include <libnest2d/libnest2d.hpp> +#include <libnest2d/optimizer.hpp> +#include <iterator> + +namespace libnest2d { + +template<class RawShape> +Radians findBestRotation(_Item<RawShape>& item) { + opt::StopCriteria stopcr; + stopcr.absolute_score_difference = 0.01; + stopcr.max_iterations = 10000; + opt::TOptimizer<opt::Method::G_GENETIC> solver(stopcr); + + auto orig_rot = item.rotation(); + + auto result = solver.optimize_min([&item, &orig_rot](Radians rot){ + item.rotation(orig_rot + rot); + auto bb = item.boundingBox(); + return std::sqrt(bb.height()*bb.width()); + }, opt::initvals(Radians(0)), opt::bound<Radians>(-Pi/2, Pi/2)); + + item.rotation(orig_rot); + + return std::get<0>(result.optimum); +} + +template<class Iterator> +void findMinimumBoundingBoxRotations(Iterator from, Iterator to) { + using V = typename std::iterator_traits<Iterator>::value_type; + std::for_each(from, to, [](V& item){ + Radians rot = findBestRotation(item); + item.rotate(rot); + }); +} + +} + +#endif // ROTFINDER_HPP diff --git a/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp b/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp index e3ad97c10..ee93d0592 100644 --- a/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp +++ b/xs/src/libnest2d/libnest2d/selections/djd_heuristic.hpp @@ -8,7 +8,7 @@ #include "selection_boilerplate.hpp" -namespace libnest2d { namespace strategies { +namespace libnest2d { namespace selections { /** * Selection heuristic based on [López-Camacho]\ @@ -118,7 +118,7 @@ public: using Placer = PlacementStrategyLike<TPlacer>; using ItemList = std::list<ItemRef>; - const double bin_area = ShapeLike::area<RawShape>(bin); + const double bin_area = sl::area(bin); const double w = bin_area * config_.waste_increment; const double INITIAL_FILL_PROPORTION = config_.initial_fill_proportion; @@ -227,10 +227,14 @@ public: bool ret = false; auto it = not_packed.begin(); + auto pack = [&placer, ¬_packed](ItemListIt it) { + return placer.pack(*it, rem(it, not_packed)); + }; + while(it != not_packed.end() && !ret && free_area - (item_area = it->get().area()) <= waste) { - if(item_area <= free_area && placer.pack(*it) ) { + if(item_area <= free_area && pack(it) ) { free_area -= item_area; filled_area = bin_area - free_area; ret = true; @@ -270,6 +274,11 @@ public: auto it2 = it; std::vector<TPair> wrong_pairs; + using std::placeholders::_1; + + auto trypack = [&placer, ¬_packed](ItemListIt it) { + return placer.trypack(*it, rem(it, not_packed)); + }; while(it != endit && !ret && free_area - (item_area = it->get().area()) - @@ -278,7 +287,7 @@ public: if(item_area + smallestPiece(it, not_packed)->get().area() > free_area ) { it++; continue; } - auto pr = placer.trypack(*it); + auto pr = trypack(it); // First would fit it2 = not_packed.begin(); @@ -294,14 +303,14 @@ public: } placer.accept(pr); - auto pr2 = placer.trypack(*it2); + auto pr2 = trypack(it2); if(!pr2) { placer.unpackLast(); // remove first if(try_reverse) { - pr2 = placer.trypack(*it2); + pr2 = trypack(it2); if(pr2) { placer.accept(pr2); - auto pr12 = placer.trypack(*it); + auto pr12 = trypack(it); if(pr12) { placer.accept(pr12); ret = true; @@ -365,6 +374,14 @@ public: return it->get().area(); }; + auto trypack = [&placer, ¬_packed](ItemListIt it) { + return placer.trypack(*it, rem(it, not_packed)); + }; + + auto pack = [&placer, ¬_packed](ItemListIt it) { + return placer.pack(*it, rem(it, not_packed)); + }; + while (it != endit && !ret) { // drill down 1st level // We need to determine in each iteration the largest, second @@ -394,7 +411,7 @@ public: it++; continue; } - auto pr = placer.trypack(*it); + auto pr = trypack(it); // Check for free area and try to pack the 1st item... if(!pr) { it++; continue; } @@ -420,15 +437,15 @@ public: bool can_pack2 = false; placer.accept(pr); - auto pr2 = placer.trypack(*it2); + auto pr2 = trypack(it2); auto pr12 = pr; if(!pr2) { placer.unpackLast(); // remove first if(try_reverse) { - pr2 = placer.trypack(*it2); + pr2 = trypack(it2); if(pr2) { placer.accept(pr2); - pr12 = placer.trypack(*it); + pr12 = trypack(it); if(pr12) can_pack2 = true; placer.unpackLast(); } @@ -463,7 +480,7 @@ public: if(a3_sum > free_area) { it3++; continue; } placer.accept(pr12); placer.accept(pr2); - bool can_pack3 = placer.pack(*it3); + bool can_pack3 = pack(it3); if(!can_pack3) { placer.unpackLast(); @@ -473,16 +490,16 @@ public: if(!can_pack3 && try_reverse) { std::array<size_t, 3> indices = {0, 1, 2}; - std::array<ItemRef, 3> - candidates = {*it, *it2, *it3}; + std::array<typename ItemList::iterator, 3> + candidates = {it, it2, it3}; - auto tryPack = [&placer, &candidates]( + auto tryPack = [&placer, &candidates, &pack]( const decltype(indices)& idx) { std::array<bool, 3> packed = {false}; for(auto id : idx) packed.at(id) = - placer.pack(candidates[id]); + pack(candidates[id]); bool check = std::all_of(packed.begin(), @@ -536,7 +553,7 @@ public: { auto it = store_.begin(); while (it != store_.end()) { Placer p(bin); p.configure(pconfig); - if(!p.pack(*it)) { + if(!p.pack(*it, rem(it, store_))) { it = store_.erase(it); } else it++; } @@ -551,11 +568,7 @@ public: { packed_bins_[idx] = placer.getItems(); -#ifndef NDEBUG - packed_bins_[idx].insert(packed_bins_[idx].end(), - placer.getDebugItems().begin(), - placer.getDebugItems().end()); -#endif + // TODO here should be a spinlock slock.lock(); acounter -= packednum; @@ -601,7 +614,7 @@ public: while(it != not_packed.end() && filled_area < INITIAL_FILL_AREA) { - if(placer.pack(*it)) { + if(placer.pack(*it, rem(it, not_packed))) { filled_area += it->get().area(); free_area = bin_area - filled_area; it = not_packed.erase(it); diff --git a/xs/src/libnest2d/libnest2d/selections/filler.hpp b/xs/src/libnest2d/libnest2d/selections/filler.hpp index d0018dc73..0da7220a1 100644 --- a/xs/src/libnest2d/libnest2d/selections/filler.hpp +++ b/xs/src/libnest2d/libnest2d/selections/filler.hpp @@ -3,7 +3,7 @@ #include "selection_boilerplate.hpp" -namespace libnest2d { namespace strategies { +namespace libnest2d { namespace selections { template<class RawShape> class _FillerSelection: public SelectionBoilerplate<RawShape> { @@ -56,18 +56,13 @@ public: std::sort(store_.begin(), store_.end(), sortfunc); -// Container a = {store_[0], store_[1], store_[4], store_[5] }; -//// a.insert(a.end(), store_.end()-10, store_.end()); -// store_ = a; - PlacementStrategyLike<TPlacer> placer(bin); placer.configure(pconfig); auto it = store_.begin(); while(it != store_.end()) { - if(!placer.pack(*it)) { + if(!placer.pack(*it, {std::next(it), store_.end()})) { if(packed_bins_.back().empty()) ++it; -// makeProgress(placer); placer.clearItems(); packed_bins_.emplace_back(); } else { @@ -76,9 +71,6 @@ public: } } -// if(was_packed) { -// packed_bins_.push_back(placer.getItems()); -// } } }; diff --git a/xs/src/libnest2d/libnest2d/selections/firstfit.hpp b/xs/src/libnest2d/libnest2d/selections/firstfit.hpp index 665b9da9f..bca7497db 100644 --- a/xs/src/libnest2d/libnest2d/selections/firstfit.hpp +++ b/xs/src/libnest2d/libnest2d/selections/firstfit.hpp @@ -4,7 +4,7 @@ #include "../libnest2d.hpp" #include "selection_boilerplate.hpp" -namespace libnest2d { namespace strategies { +namespace libnest2d { namespace selections { template<class RawShape> class _FirstFitSelection: public SelectionBoilerplate<RawShape> { @@ -40,6 +40,7 @@ public: packed_bins_.clear(); std::vector<Placer> placers; + placers.reserve(last-first); std::copy(first, last, std::back_inserter(store_)); @@ -66,21 +67,25 @@ public: } } - for(auto& item : store_ ) { + auto it = store_.begin(); + + while(it != store_.end()) { bool was_packed = false; + size_t j = 0; while(!was_packed) { - - for(size_t j = 0; j < placers.size() && !was_packed; j++) { - if((was_packed = placers[j].pack(item))) - makeProgress(placers[j], j); + for(; j < placers.size() && !was_packed; j++) { + if((was_packed = placers[j].pack(*it, rem(it, store_) ))) + makeProgress(placers[j], j); } if(!was_packed) { placers.emplace_back(bin); placers.back().configure(pconfig); packed_bins_.emplace_back(); + j = placers.size() - 1; } } + ++it; } } diff --git a/xs/src/libnest2d/libnest2d/selections/selection_boilerplate.hpp b/xs/src/libnest2d/libnest2d/selections/selection_boilerplate.hpp index 59ef5cb23..05bbae658 100644 --- a/xs/src/libnest2d/libnest2d/selections/selection_boilerplate.hpp +++ b/xs/src/libnest2d/libnest2d/selections/selection_boilerplate.hpp @@ -3,8 +3,7 @@ #include "../libnest2d.hpp" -namespace libnest2d { -namespace strategies { +namespace libnest2d { namespace selections { template<class RawShape> class SelectionBoilerplate { diff --git a/xs/src/libnest2d/tests/test.cpp b/xs/src/libnest2d/tests/test.cpp index 39315ff1a..323fb8d31 100644 --- a/xs/src/libnest2d/tests/test.cpp +++ b/xs/src/libnest2d/tests/test.cpp @@ -5,6 +5,7 @@ #include "printer_parts.h" #include <libnest2d/geometry_traits_nfp.hpp> //#include "../tools/libnfpglue.hpp" +//#include "../tools/nfp_svgnest_glue.hpp" std::vector<libnest2d::Item>& prusaParts() { static std::vector<libnest2d::Item> ret; @@ -99,6 +100,43 @@ TEST(BasicFunctionality, creationAndDestruction) } +TEST(GeometryAlgorithms, boundingCircle) { + using namespace libnest2d; + using placers::boundingCircle; + + PolygonImpl p = {{{0, 10}, {10, 0}, {0, -10}, {0, 10}}, {}}; + Circle c = boundingCircle(p); + + ASSERT_EQ(c.center().X, 0); + ASSERT_EQ(c.center().Y, 0); + ASSERT_DOUBLE_EQ(c.radius(), 10); + + shapelike::translate(p, PointImpl{10, 10}); + c = boundingCircle(p); + + ASSERT_EQ(c.center().X, 10); + ASSERT_EQ(c.center().Y, 10); + ASSERT_DOUBLE_EQ(c.radius(), 10); + + auto parts = prusaParts(); + + int i = 0; + for(auto& part : parts) { + c = boundingCircle(part.transformedShape()); + if(std::isnan(c.radius())) std::cout << "fail: radius is nan" << std::endl; + + else for(auto v : shapelike::getContour(part.transformedShape()) ) { + auto d = pointlike::distance(v, c.center()); + if(d > c.radius() ) { + auto e = std::abs( 1.0 - d/c.radius()); + ASSERT_LE(e, 1e-3); + } + } + i++; + } + +} + TEST(GeometryAlgorithms, Distance) { using namespace libnest2d; @@ -107,14 +145,14 @@ TEST(GeometryAlgorithms, Distance) { Point p2 = {10, 0}; Point p3 = {10, 10}; - ASSERT_DOUBLE_EQ(PointLike::distance(p1, p2), 10); - ASSERT_DOUBLE_EQ(PointLike::distance(p1, p3), sqrt(200)); + ASSERT_DOUBLE_EQ(pointlike::distance(p1, p2), 10); + ASSERT_DOUBLE_EQ(pointlike::distance(p1, p3), sqrt(200)); Segment seg(p1, p3); - ASSERT_DOUBLE_EQ(PointLike::distance(p2, seg), 7.0710678118654755); + ASSERT_DOUBLE_EQ(pointlike::distance(p2, seg), 7.0710678118654755); - auto result = PointLike::horizontalDistance(p2, seg); + auto result = pointlike::horizontalDistance(p2, seg); auto check = [](Coord val, Coord expected) { if(std::is_floating_point<Coord>::value) @@ -127,11 +165,11 @@ TEST(GeometryAlgorithms, Distance) { ASSERT_TRUE(result.second); check(result.first, 10); - result = PointLike::verticalDistance(p2, seg); + result = pointlike::verticalDistance(p2, seg); ASSERT_TRUE(result.second); check(result.first, -10); - result = PointLike::verticalDistance(Point{10, 20}, seg); + result = pointlike::verticalDistance(Point{10, 20}, seg); ASSERT_TRUE(result.second); check(result.first, 10); @@ -139,12 +177,12 @@ TEST(GeometryAlgorithms, Distance) { Point p4 = {80, 0}; Segment seg2 = { {0, 0}, {0, 40} }; - result = PointLike::horizontalDistance(p4, seg2); + result = pointlike::horizontalDistance(p4, seg2); ASSERT_TRUE(result.second); check(result.first, 80); - result = PointLike::verticalDistance(p4, seg2); + result = pointlike::verticalDistance(p4, seg2); // Point should not be related to the segment ASSERT_FALSE(result.second); @@ -172,7 +210,7 @@ TEST(GeometryAlgorithms, Area) { {61, 97} }; - ASSERT_TRUE(ShapeLike::area(item.transformedShape()) > 0 ); + ASSERT_TRUE(shapelike::area(item.transformedShape()) > 0 ); } TEST(GeometryAlgorithms, IsPointInsidePolygon) { @@ -182,21 +220,21 @@ TEST(GeometryAlgorithms, IsPointInsidePolygon) { Point p = {1, 1}; - ASSERT_TRUE(rect.isPointInside(p)); + ASSERT_TRUE(rect.isInside(p)); p = {11, 11}; - ASSERT_FALSE(rect.isPointInside(p)); + ASSERT_FALSE(rect.isInside(p)); p = {11, 12}; - ASSERT_FALSE(rect.isPointInside(p)); + ASSERT_FALSE(rect.isInside(p)); p = {3, 3}; - ASSERT_TRUE(rect.isPointInside(p)); + ASSERT_TRUE(rect.isInside(p)); } @@ -250,7 +288,7 @@ TEST(GeometryAlgorithms, LeftAndDownPolygon) Item leftp(placer.leftPoly(item)); - ASSERT_TRUE(ShapeLike::isValid(leftp.rawShape()).first); + ASSERT_TRUE(shapelike::isValid(leftp.rawShape()).first); ASSERT_EQ(leftp.vertexCount(), leftControl.vertexCount()); for(unsigned long i = 0; i < leftControl.vertexCount(); i++) { @@ -260,7 +298,7 @@ TEST(GeometryAlgorithms, LeftAndDownPolygon) Item downp(placer.downPoly(item)); - ASSERT_TRUE(ShapeLike::isValid(downp.rawShape()).first); + ASSERT_TRUE(shapelike::isValid(downp.rawShape()).first); ASSERT_EQ(downp.vertexCount(), downControl.vertexCount()); for(unsigned long i = 0; i < downControl.vertexCount(); i++) { @@ -297,7 +335,7 @@ TEST(GeometryAlgorithms, ArrangeRectanglesTight) {20, 20} }; - Arranger<BottomLeftPlacer, DJDHeuristic> arrange(Box(210, 250)); + Nester<BottomLeftPlacer, DJDHeuristic> arrange(Box(210, 250)); auto groups = arrange(rects.begin(), rects.end()); @@ -350,7 +388,7 @@ TEST(GeometryAlgorithms, ArrangeRectanglesLoose) Coord min_obj_distance = 5; - Arranger<BottomLeftPlacer, DJDHeuristic> arrange(Box(210, 250), + Nester<BottomLeftPlacer, DJDHeuristic> arrange(Box(210, 250), min_obj_distance); auto groups = arrange(rects.begin(), rects.end()); @@ -401,7 +439,7 @@ R"raw(<?xml version="1.0" encoding="UTF-8" standalone="yes"?> setX(v, getX(v)/SCALE); rbin.setVertex(i, v); } - out << ShapeLike::serialize<Formats::SVG>(rbin.rawShape()) << std::endl; + out << shapelike::serialize<Formats::SVG>(rbin.rawShape()) << std::endl; for(Item& sh : r) { Item tsh(sh.transformedShape()); for(unsigned i = 0; i < tsh.vertexCount(); i++) { @@ -410,7 +448,7 @@ R"raw(<?xml version="1.0" encoding="UTF-8" standalone="yes"?> setX(v, getX(v)/SCALE); tsh.setVertex(i, v); } - out << ShapeLike::serialize<Formats::SVG>(tsh.rawShape()) << std::endl; + out << shapelike::serialize<Formats::SVG>(tsh.rawShape()) << std::endl; } out << "\n</svg>" << std::endl; } @@ -664,7 +702,7 @@ std::vector<ItemPair> nfp_concave_testdata = { } }; -template<NfpLevel lvl, Coord SCALE> +template<nfp::NfpLevel lvl, Coord SCALE> void testNfp(const std::vector<ItemPair>& testdata) { using namespace libnest2d; @@ -674,29 +712,33 @@ void testNfp(const std::vector<ItemPair>& testdata) { auto& exportfun = exportSVG<SCALE, Box>; - auto onetest = [&](Item& orbiter, Item& stationary){ + auto onetest = [&](Item& orbiter, Item& stationary, unsigned testidx){ testcase++; orbiter.translate({210*SCALE, 0}); - auto&& nfp = Nfp::noFitPolygon<lvl>(stationary.rawShape(), + auto&& nfp = nfp::noFitPolygon<lvl>(stationary.rawShape(), orbiter.transformedShape()); - strategies::correctNfpPosition(nfp, stationary, orbiter); + placers::correctNfpPosition(nfp, stationary, orbiter); - auto v = ShapeLike::isValid(nfp.first); + auto valid = shapelike::isValid(nfp.first); - if(!v.first) { - std::cout << v.second << std::endl; - } + /*Item infp(nfp.first); + if(!valid.first) { + std::cout << "test instance: " << testidx << " " + << valid.second << std::endl; + std::vector<std::reference_wrapper<Item>> inp = {std::ref(infp)}; + exportfun(inp, bin, testidx); + }*/ - ASSERT_TRUE(v.first); + ASSERT_TRUE(valid.first); Item infp(nfp.first); int i = 0; auto rorbiter = orbiter.transformedShape(); - auto vo = Nfp::referenceVertex(rorbiter); + auto vo = nfp::referenceVertex(rorbiter); ASSERT_TRUE(stationary.isInside(infp)); @@ -710,7 +752,7 @@ void testNfp(const std::vector<ItemPair>& testdata) { bool touching = Item::touches(tmp, stationary); - if(!touching) { + if(!touching || !valid.first) { std::vector<std::reference_wrapper<Item>> inp = { std::ref(stationary), std::ref(tmp), std::ref(infp) }; @@ -722,22 +764,24 @@ void testNfp(const std::vector<ItemPair>& testdata) { } }; + unsigned tidx = 0; for(auto& td : testdata) { auto orbiter = td.orbiter; auto stationary = td.stationary; - onetest(orbiter, stationary); + onetest(orbiter, stationary, tidx++); } + tidx = 0; for(auto& td : testdata) { auto orbiter = td.stationary; auto stationary = td.orbiter; - onetest(orbiter, stationary); + onetest(orbiter, stationary, tidx++); } } } TEST(GeometryAlgorithms, nfpConvexConvex) { - testNfp<NfpLevel::CONVEX_ONLY, 1>(nfp_testdata); + testNfp<nfp::NfpLevel::CONVEX_ONLY, 1>(nfp_testdata); } //TEST(GeometryAlgorithms, nfpConcaveConcave) { @@ -758,7 +802,7 @@ TEST(GeometryAlgorithms, pointOnPolygonContour) { Rectangle input(10, 10); - strategies::EdgeCache<PolygonImpl> ecache(input); + placers::EdgeCache<PolygonImpl> ecache(input); auto first = *input.begin(); ASSERT_TRUE(getX(first) == getX(ecache.coords(0))); @@ -770,7 +814,7 @@ TEST(GeometryAlgorithms, pointOnPolygonContour) { for(int i = 0; i <= 100; i++) { auto v = ecache.coords(i*(0.01)); - ASSERT_TRUE(ShapeLike::touches(v, input.transformedShape())); + ASSERT_TRUE(shapelike::touches(v, input.transformedShape())); } } @@ -784,17 +828,17 @@ TEST(GeometryAlgorithms, mergePileWithPolygon) { rect2.translate({10, 0}); rect3.translate({25, 0}); - ShapeLike::Shapes<PolygonImpl> pile; + shapelike::Shapes<PolygonImpl> pile; pile.push_back(rect1.transformedShape()); pile.push_back(rect2.transformedShape()); - auto result = Nfp::merge(pile, rect3.transformedShape()); + auto result = nfp::merge(pile, rect3.transformedShape()); ASSERT_EQ(result.size(), 1); Rectangle ref(45, 15); - ASSERT_EQ(ShapeLike::area(result.front()), ref.area()); + ASSERT_EQ(shapelike::area(result.front()), ref.area()); } int main(int argc, char **argv) { diff --git a/xs/src/libnest2d/tools/libnfpglue.cpp b/xs/src/libnest2d/tools/libnfpglue.cpp index 18656fd40..31733acf9 100644 --- a/xs/src/libnest2d/tools/libnfpglue.cpp +++ b/xs/src/libnest2d/tools/libnfpglue.cpp @@ -56,7 +56,7 @@ libnfporb::point_t scale(const libnfporb::point_t& p, long double factor) { NfpR _nfp(const PolygonImpl &sh, const PolygonImpl &cother) { - using Vertex = PointImpl; + namespace sl = shapelike; NfpR ret; @@ -85,7 +85,7 @@ NfpR _nfp(const PolygonImpl &sh, const PolygonImpl &cother) // this can throw auto nfp = libnfporb::generateNFP(pstat, porb, true); - auto &ct = ShapeLike::getContour(ret.first); + auto &ct = sl::getContour(ret.first); ct.reserve(nfp.front().size()+1); for(auto v : nfp.front()) { v = scale(v, refactor); @@ -94,7 +94,7 @@ NfpR _nfp(const PolygonImpl &sh, const PolygonImpl &cother) ct.push_back(ct.front()); std::reverse(ct.begin(), ct.end()); - auto &rholes = ShapeLike::holes(ret.first); + auto &rholes = sl::holes(ret.first); for(size_t hidx = 1; hidx < nfp.size(); ++hidx) { if(nfp[hidx].size() >= 3) { rholes.emplace_back(); @@ -110,31 +110,31 @@ NfpR _nfp(const PolygonImpl &sh, const PolygonImpl &cother) } } - ret.second = Nfp::referenceVertex(ret.first); + ret.second = nfp::referenceVertex(ret.first); } catch(std::exception& e) { std::cout << "Error: " << e.what() << "\nTrying with convex hull..." << std::endl; // auto ch_stat = ShapeLike::convexHull(sh); // auto ch_orb = ShapeLike::convexHull(cother); - ret = Nfp::nfpConvexOnly(sh, cother); + ret = nfp::nfpConvexOnly(sh, cother); } return ret; } -NfpR Nfp::NfpImpl<PolygonImpl, NfpLevel::CONVEX_ONLY>::operator()( +NfpR nfp::NfpImpl<PolygonImpl, nfp::NfpLevel::CONVEX_ONLY>::operator()( const PolygonImpl &sh, const ClipperLib::PolygonImpl &cother) { return _nfp(sh, cother);//nfpConvexOnly(sh, cother); } -NfpR Nfp::NfpImpl<PolygonImpl, NfpLevel::ONE_CONVEX>::operator()( +NfpR nfp::NfpImpl<PolygonImpl, nfp::NfpLevel::ONE_CONVEX>::operator()( const PolygonImpl &sh, const ClipperLib::PolygonImpl &cother) { return _nfp(sh, cother); } -NfpR Nfp::NfpImpl<PolygonImpl, NfpLevel::BOTH_CONCAVE>::operator()( +NfpR nfp::NfpImpl<PolygonImpl, nfp::NfpLevel::BOTH_CONCAVE>::operator()( const PolygonImpl &sh, const ClipperLib::PolygonImpl &cother) { return _nfp(sh, cother); diff --git a/xs/src/libnest2d/tools/libnfpglue.hpp b/xs/src/libnest2d/tools/libnfpglue.hpp index 75f639445..1ff033cb9 100644 --- a/xs/src/libnest2d/tools/libnfpglue.hpp +++ b/xs/src/libnest2d/tools/libnfpglue.hpp @@ -5,22 +5,22 @@ namespace libnest2d { -using NfpR = Nfp::NfpResult<PolygonImpl>; +using NfpR = nfp::NfpResult<PolygonImpl>; NfpR _nfp(const PolygonImpl& sh, const PolygonImpl& cother); template<> -struct Nfp::NfpImpl<PolygonImpl, NfpLevel::CONVEX_ONLY> { +struct nfp::NfpImpl<PolygonImpl, nfp::NfpLevel::CONVEX_ONLY> { NfpR operator()(const PolygonImpl& sh, const PolygonImpl& cother); }; template<> -struct Nfp::NfpImpl<PolygonImpl, NfpLevel::ONE_CONVEX> { +struct nfp::NfpImpl<PolygonImpl, nfp::NfpLevel::ONE_CONVEX> { NfpR operator()(const PolygonImpl& sh, const PolygonImpl& cother); }; template<> -struct Nfp::NfpImpl<PolygonImpl, NfpLevel::BOTH_CONCAVE> { +struct nfp::NfpImpl<PolygonImpl, nfp::NfpLevel::BOTH_CONCAVE> { NfpR operator()(const PolygonImpl& sh, const PolygonImpl& cother); }; @@ -34,7 +34,7 @@ struct Nfp::NfpImpl<PolygonImpl, NfpLevel::BOTH_CONCAVE> { // NfpResult operator()(const PolygonImpl& sh, const PolygonImpl& cother); //}; -template<> struct Nfp::MaxNfpLevel<PolygonImpl> { +template<> struct nfp::MaxNfpLevel<PolygonImpl> { static const BP2D_CONSTEXPR NfpLevel value = // NfpLevel::CONVEX_ONLY; NfpLevel::BOTH_CONCAVE; diff --git a/xs/src/libnest2d/tools/nfp_svgnest.hpp b/xs/src/libnest2d/tools/nfp_svgnest.hpp new file mode 100644 index 000000000..ac5700c10 --- /dev/null +++ b/xs/src/libnest2d/tools/nfp_svgnest.hpp @@ -0,0 +1,1018 @@ +#ifndef NFP_SVGNEST_HPP +#define NFP_SVGNEST_HPP + +#include <limits> +#include <unordered_map> + +#include <libnest2d/geometry_traits_nfp.hpp> + +namespace libnest2d { + +namespace __svgnest { + +using std::sqrt; +using std::min; +using std::max; +using std::abs; +using std::isnan; + +//template<class Coord> struct _Scale { +// static const BP2D_CONSTEXPR long long Value = 1000000; +//}; + +template<class S> struct _alg { + using Contour = TContour<S>; + using Point = TPoint<S>; + using iCoord = TCoord<Point>; + using Coord = double; + using Shapes = nfp::Shapes<S>; + + static const Coord TOL; + +#define dNAN std::nan("") + + struct Vector { + Coord x = 0.0, y = 0.0; + bool marked = false; + Vector() = default; + Vector(Coord X, Coord Y): x(X), y(Y) {} + Vector(const Point& p): x(Coord(getX(p))), y(Coord(getY(p))) {} + operator Point() const { return {iCoord(x), iCoord(y)}; } + Vector& operator=(const Point& p) { + x = getX(p), y = getY(p); return *this; + } + bool operator!=(const Vector& v) const { + return v.x != x || v.y != y; + } + Vector(std::initializer_list<Coord> il): + x(*il.begin()), y(*std::next(il.begin())) {} + }; + + static inline Coord x(const Point& p) { return Coord(getX(p)); } + static inline Coord y(const Point& p) { return Coord(getY(p)); } + + static inline Coord x(const Vector& p) { return p.x; } + static inline Coord y(const Vector& p) { return p.y; } + + class Cntr { + std::vector<Vector> v_; + public: + Cntr(const Contour& c) { + v_.reserve(c.size()); + std::transform(c.begin(), c.end(), std::back_inserter(v_), + [](const Point& p) { + return Vector(double(x(p)) / 1e6, double(y(p)) / 1e6); + }); + std::reverse(v_.begin(), v_.end()); + v_.pop_back(); + } + Cntr() = default; + + Coord offsetx = 0; + Coord offsety = 0; + size_t size() const { return v_.size(); } + bool empty() const { return v_.empty(); } + typename std::vector<Vector>::const_iterator cbegin() const { return v_.cbegin(); } + typename std::vector<Vector>::const_iterator cend() const { return v_.cend(); } + typename std::vector<Vector>::iterator begin() { return v_.begin(); } + typename std::vector<Vector>::iterator end() { return v_.end(); } + Vector& operator[](size_t idx) { return v_[idx]; } + const Vector& operator[](size_t idx) const { return v_[idx]; } + template<class...Args> + void emplace_back(Args&&...args) { + v_.emplace_back(std::forward<Args>(args)...); + } + template<class...Args> + void push(Args&&...args) { + v_.emplace_back(std::forward<Args>(args)...); + } + void clear() { v_.clear(); } + + operator Contour() const { + Contour cnt; + cnt.reserve(v_.size() + 1); + std::transform(v_.begin(), v_.end(), std::back_inserter(cnt), + [](const Vector& vertex) { + return Point(iCoord(vertex.x) * 1000000, iCoord(vertex.y) * 1000000); + }); + if(!cnt.empty()) cnt.emplace_back(cnt.front()); + S sh = shapelike::create<S>(cnt); + +// std::reverse(cnt.begin(), cnt.end()); + return shapelike::getContour(sh); + } + }; + + inline static bool _almostEqual(Coord a, Coord b, + Coord tolerance = TOL) + { + return std::abs(a - b) < tolerance; + } + + // returns true if p lies on the line segment defined by AB, + // but not at any endpoints may need work! + static bool _onSegment(const Vector& A, const Vector& B, const Vector& p) { + + // vertical line + if(_almostEqual(A.x, B.x) && _almostEqual(p.x, A.x)) { + if(!_almostEqual(p.y, B.y) && !_almostEqual(p.y, A.y) && + p.y < max(B.y, A.y) && p.y > min(B.y, A.y)){ + return true; + } + else{ + return false; + } + } + + // horizontal line + if(_almostEqual(A.y, B.y) && _almostEqual(p.y, A.y)){ + if(!_almostEqual(p.x, B.x) && !_almostEqual(p.x, A.x) && + p.x < max(B.x, A.x) && p.x > min(B.x, A.x)){ + return true; + } + else{ + return false; + } + } + + //range check + if((p.x < A.x && p.x < B.x) || (p.x > A.x && p.x > B.x) || + (p.y < A.y && p.y < B.y) || (p.y > A.y && p.y > B.y)) + return false; + + // exclude end points + if((_almostEqual(p.x, A.x) && _almostEqual(p.y, A.y)) || + (_almostEqual(p.x, B.x) && _almostEqual(p.y, B.y))) + return false; + + + double cross = (p.y - A.y) * (B.x - A.x) - (p.x - A.x) * (B.y - A.y); + + if(abs(cross) > TOL) return false; + + double dot = (p.x - A.x) * (B.x - A.x) + (p.y - A.y)*(B.y - A.y); + + if(dot < 0 || _almostEqual(dot, 0)) return false; + + double len2 = (B.x - A.x)*(B.x - A.x) + (B.y - A.y)*(B.y - A.y); + + if(dot > len2 || _almostEqual(dot, len2)) return false; + + return true; + } + + // return true if point is in the polygon, false if outside, and null if exactly on a point or edge + static int pointInPolygon(const Vector& point, const Cntr& polygon) { + if(polygon.size() < 3){ + return 0; + } + + bool inside = false; + Coord offsetx = polygon.offsetx; + Coord offsety = polygon.offsety; + + for (size_t i = 0, j = polygon.size() - 1; i < polygon.size(); j=i++) { + auto xi = polygon[i].x + offsetx; + auto yi = polygon[i].y + offsety; + auto xj = polygon[j].x + offsetx; + auto yj = polygon[j].y + offsety; + + if(_almostEqual(xi, point.x) && _almostEqual(yi, point.y)){ + return 0; // no result + } + + if(_onSegment({xi, yi}, {xj, yj}, point)){ + return 0; // exactly on the segment + } + + if(_almostEqual(xi, xj) && _almostEqual(yi, yj)){ // ignore very small lines + continue; + } + + bool intersect = ((yi > point.y) != (yj > point.y)) && + (point.x < (xj - xi) * (point.y - yi) / (yj - yi) + xi); + if (intersect) inside = !inside; + } + + return inside? 1 : -1; + } + + static bool intersect(const Cntr& A, const Cntr& B){ + Contour a = A, b = B; + return shapelike::intersects(shapelike::create<S>(a), shapelike::create<S>(b)); + } + + static Vector _normalizeVector(const Vector& v) { + if(_almostEqual(v.x*v.x + v.y*v.y, Coord(1))){ + return Point(v); // given vector was already a unit vector + } + auto len = sqrt(v.x*v.x + v.y*v.y); + auto inverse = 1/len; + + return { Coord(v.x*inverse), Coord(v.y*inverse) }; + } + + static double pointDistance( const Vector& p, + const Vector& s1, + const Vector& s2, + Vector normal, + bool infinite = false) + { + normal = _normalizeVector(normal); + + Vector dir = { + normal.y, + -normal.x + }; + + auto pdot = p.x*dir.x + p.y*dir.y; + auto s1dot = s1.x*dir.x + s1.y*dir.y; + auto s2dot = s2.x*dir.x + s2.y*dir.y; + + auto pdotnorm = p.x*normal.x + p.y*normal.y; + auto s1dotnorm = s1.x*normal.x + s1.y*normal.y; + auto s2dotnorm = s2.x*normal.x + s2.y*normal.y; + + if(!infinite){ + if (((pdot<s1dot || _almostEqual(pdot, s1dot)) && + (pdot<s2dot || _almostEqual(pdot, s2dot))) || + ((pdot>s1dot || _almostEqual(pdot, s1dot)) && + (pdot>s2dot || _almostEqual(pdot, s2dot)))) + { + // dot doesn't collide with segment, + // or lies directly on the vertex + return dNAN; + } + if ((_almostEqual(pdot, s1dot) && _almostEqual(pdot, s2dot)) && + (pdotnorm>s1dotnorm && pdotnorm>s2dotnorm)) + { + return min(pdotnorm - s1dotnorm, pdotnorm - s2dotnorm); + } + if ((_almostEqual(pdot, s1dot) && _almostEqual(pdot, s2dot)) && + (pdotnorm<s1dotnorm && pdotnorm<s2dotnorm)){ + return -min(s1dotnorm-pdotnorm, s2dotnorm-pdotnorm); + } + } + + return -(pdotnorm - s1dotnorm + (s1dotnorm - s2dotnorm)*(s1dot - pdot) + / double(s1dot - s2dot)); + } + + static double segmentDistance( const Vector& A, + const Vector& B, + const Vector& E, + const Vector& F, + Vector direction) + { + Vector normal = { + direction.y, + -direction.x + }; + + Vector reverse = { + -direction.x, + -direction.y + }; + + auto dotA = A.x*normal.x + A.y*normal.y; + auto dotB = B.x*normal.x + B.y*normal.y; + auto dotE = E.x*normal.x + E.y*normal.y; + auto dotF = F.x*normal.x + F.y*normal.y; + + auto crossA = A.x*direction.x + A.y*direction.y; + auto crossB = B.x*direction.x + B.y*direction.y; + auto crossE = E.x*direction.x + E.y*direction.y; + auto crossF = F.x*direction.x + F.y*direction.y; + +// auto crossABmin = min(crossA, crossB); +// auto crossABmax = max(crossA, crossB); + +// auto crossEFmax = max(crossE, crossF); +// auto crossEFmin = min(crossE, crossF); + + auto ABmin = min(dotA, dotB); + auto ABmax = max(dotA, dotB); + + auto EFmax = max(dotE, dotF); + auto EFmin = min(dotE, dotF); + + // segments that will merely touch at one point + if(_almostEqual(ABmax, EFmin, TOL) || _almostEqual(ABmin, EFmax,TOL)) { + return dNAN; + } + // segments miss eachother completely + if(ABmax < EFmin || ABmin > EFmax){ + return dNAN; + } + + double overlap = 0; + + if((ABmax > EFmax && ABmin < EFmin) || (EFmax > ABmax && EFmin < ABmin)) + { + overlap = 1; + } + else{ + auto minMax = min(ABmax, EFmax); + auto maxMin = max(ABmin, EFmin); + + auto maxMax = max(ABmax, EFmax); + auto minMin = min(ABmin, EFmin); + + overlap = (minMax-maxMin)/(maxMax-minMin); + } + + auto crossABE = (E.y - A.y) * (B.x - A.x) - (E.x - A.x) * (B.y - A.y); + auto crossABF = (F.y - A.y) * (B.x - A.x) - (F.x - A.x) * (B.y - A.y); + + // lines are colinear + if(_almostEqual(crossABE,0) && _almostEqual(crossABF,0)){ + + Vector ABnorm = {B.y-A.y, A.x-B.x}; + Vector EFnorm = {F.y-E.y, E.x-F.x}; + + auto ABnormlength = sqrt(ABnorm.x*ABnorm.x + ABnorm.y*ABnorm.y); + ABnorm.x /= ABnormlength; + ABnorm.y /= ABnormlength; + + auto EFnormlength = sqrt(EFnorm.x*EFnorm.x + EFnorm.y*EFnorm.y); + EFnorm.x /= EFnormlength; + EFnorm.y /= EFnormlength; + + // segment normals must point in opposite directions + if(abs(ABnorm.y * EFnorm.x - ABnorm.x * EFnorm.y) < TOL && + ABnorm.y * EFnorm.y + ABnorm.x * EFnorm.x < 0){ + // normal of AB segment must point in same direction as + // given direction vector + auto normdot = ABnorm.y * direction.y + ABnorm.x * direction.x; + // the segments merely slide along eachother + if(_almostEqual(normdot,0, TOL)){ + return dNAN; + } + if(normdot < 0){ + return 0.0; + } + } + return dNAN; + } + + std::vector<double> distances; distances.reserve(10); + + // coincident points + if(_almostEqual(dotA, dotE)){ + distances.emplace_back(crossA-crossE); + } + else if(_almostEqual(dotA, dotF)){ + distances.emplace_back(crossA-crossF); + } + else if(dotA > EFmin && dotA < EFmax){ + auto d = pointDistance(A,E,F,reverse); + if(!isnan(d) && _almostEqual(d, 0)) + { // A currently touches EF, but AB is moving away from EF + auto dB = pointDistance(B,E,F,reverse,true); + if(dB < 0 || _almostEqual(dB*overlap,0)){ + d = dNAN; + } + } + if(!isnan(d)){ + distances.emplace_back(d); + } + } + + if(_almostEqual(dotB, dotE)){ + distances.emplace_back(crossB-crossE); + } + else if(_almostEqual(dotB, dotF)){ + distances.emplace_back(crossB-crossF); + } + else if(dotB > EFmin && dotB < EFmax){ + auto d = pointDistance(B,E,F,reverse); + + if(!isnan(d) && _almostEqual(d, 0)) + { // crossA>crossB A currently touches EF, but AB is moving away from EF + double dA = pointDistance(A,E,F,reverse,true); + if(dA < 0 || _almostEqual(dA*overlap,0)){ + d = dNAN; + } + } + if(!isnan(d)){ + distances.emplace_back(d); + } + } + + if(dotE > ABmin && dotE < ABmax){ + auto d = pointDistance(E,A,B,direction); + if(!isnan(d) && _almostEqual(d, 0)) + { // crossF<crossE A currently touches EF, but AB is moving away from EF + double dF = pointDistance(F,A,B,direction, true); + if(dF < 0 || _almostEqual(dF*overlap,0)){ + d = dNAN; + } + } + if(!isnan(d)){ + distances.emplace_back(d); + } + } + + if(dotF > ABmin && dotF < ABmax){ + auto d = pointDistance(F,A,B,direction); + if(!isnan(d) && _almostEqual(d, 0)) + { // && crossE<crossF A currently touches EF, + // but AB is moving away from EF + double dE = pointDistance(E,A,B,direction, true); + if(dE < 0 || _almostEqual(dE*overlap,0)){ + d = dNAN; + } + } + if(!isnan(d)){ + distances.emplace_back(d); + } + } + + if(distances.empty()){ + return dNAN; + } + + return *std::min_element(distances.begin(), distances.end()); + } + + static double polygonSlideDistance( const Cntr& AA, + const Cntr& BB, + Vector direction, + bool ignoreNegative) + { +// Vector A1, A2, B1, B2; + Cntr A = AA; + Cntr B = BB; + + Coord Aoffsetx = A.offsetx; + Coord Boffsetx = B.offsetx; + Coord Aoffsety = A.offsety; + Coord Boffsety = B.offsety; + + // close the loop for polygons + if(A[0] != A[A.size()-1]){ + A.emplace_back(AA[0]); + } + + if(B[0] != B[B.size()-1]){ + B.emplace_back(BB[0]); + } + + auto& edgeA = A; + auto& edgeB = B; + + double distance = dNAN, d = dNAN; + + Vector dir = _normalizeVector(direction); + +// Vector normal = { +// dir.y, +// -dir.x +// }; + +// Vector reverse = { +// -dir.x, +// -dir.y, +// }; + + for(size_t i = 0; i < edgeB.size() - 1; i++){ + for(size_t j = 0; j < edgeA.size() - 1; j++){ + Vector A1 = {x(edgeA[j]) + Aoffsetx, y(edgeA[j]) + Aoffsety }; + Vector A2 = {x(edgeA[j+1]) + Aoffsetx, y(edgeA[j+1]) + Aoffsety}; + Vector B1 = {x(edgeB[i]) + Boffsetx, y(edgeB[i]) + Boffsety }; + Vector B2 = {x(edgeB[i+1]) + Boffsetx, y(edgeB[i+1]) + Boffsety}; + + if((_almostEqual(A1.x, A2.x) && _almostEqual(A1.y, A2.y)) || + (_almostEqual(B1.x, B2.x) && _almostEqual(B1.y, B2.y))){ + continue; // ignore extremely small lines + } + + d = segmentDistance(A1, A2, B1, B2, dir); + + if(!isnan(d) && (isnan(distance) || d < distance)){ + if(!ignoreNegative || d > 0 || _almostEqual(d, 0)){ + distance = d; + } + } + } + } + return distance; + } + + static double polygonProjectionDistance(const Cntr& AA, + const Cntr& BB, + Vector direction) + { + Cntr A = AA; + Cntr B = BB; + + auto Boffsetx = B.offsetx; + auto Boffsety = B.offsety; + auto Aoffsetx = A.offsetx; + auto Aoffsety = A.offsety; + + // close the loop for polygons + if(A[0] != A[A.size()-1]){ + A.push(A[0]); + } + + if(B[0] != B[B.size()-1]){ + B.push(B[0]); + } + + auto& edgeA = A; + auto& edgeB = B; + + double distance = dNAN, d; +// Vector p, s1, s2; + + for(size_t i = 0; i < edgeB.size(); i++) { + // the shortest/most negative projection of B onto A + double minprojection = dNAN; + Vector minp; + for(size_t j = 0; j < edgeA.size() - 1; j++){ + Vector p = {x(edgeB[i]) + Boffsetx, y(edgeB[i]) + Boffsety }; + Vector s1 = {x(edgeA[j]) + Aoffsetx, y(edgeA[j]) + Aoffsety }; + Vector s2 = {x(edgeA[j+1]) + Aoffsetx, y(edgeA[j+1]) + Aoffsety }; + + if(abs((s2.y-s1.y) * direction.x - + (s2.x-s1.x) * direction.y) < TOL) continue; + + // project point, ignore edge boundaries + d = pointDistance(p, s1, s2, direction); + + if(!isnan(d) && (isnan(minprojection) || d < minprojection)) { + minprojection = d; + minp = p; + } + } + + if(!isnan(minprojection) && (isnan(distance) || + minprojection > distance)){ + distance = minprojection; + } + } + + return distance; + } + + static std::pair<bool, Vector> searchStartPoint( + const Cntr& AA, const Cntr& BB, bool inside, const std::vector<Cntr>& NFP = {}) + { + // clone arrays + auto A = AA; + auto B = BB; + +// // close the loop for polygons +// if(A[0] != A[A.size()-1]){ +// A.push(A[0]); +// } + +// if(B[0] != B[B.size()-1]){ +// B.push(B[0]); +// } + + // returns true if point already exists in the given nfp + auto inNfp = [](const Vector& p, const std::vector<Cntr>& nfp){ + if(nfp.empty()){ + return false; + } + + for(size_t i=0; i < nfp.size(); i++){ + for(size_t j = 0; j< nfp[i].size(); j++){ + if(_almostEqual(p.x, nfp[i][j].x) && + _almostEqual(p.y, nfp[i][j].y)){ + return true; + } + } + } + + return false; + }; + + for(size_t i = 0; i < A.size() - 1; i++){ + if(!A[i].marked) { + A[i].marked = true; + for(size_t j = 0; j < B.size(); j++){ + B.offsetx = A[i].x - B[j].x; + B.offsety = A[i].y - B[j].y; + + int Binside = 0; + for(size_t k = 0; k < B.size(); k++){ + int inpoly = pointInPolygon({B[k].x + B.offsetx, B[k].y + B.offsety}, A); + if(inpoly != 0){ + Binside = inpoly; + break; + } + } + + if(Binside == 0){ // A and B are the same + return {false, {}}; + } + + auto startPoint = std::make_pair(true, Vector(B.offsetx, B.offsety)); + if(((Binside && inside) || (!Binside && !inside)) && + !intersect(A,B) && !inNfp(startPoint.second, NFP)){ + return startPoint; + } + + // slide B along vector + auto vx = A[i+1].x - A[i].x; + auto vy = A[i+1].y - A[i].y; + + double d1 = polygonProjectionDistance(A,B,{vx, vy}); + double d2 = polygonProjectionDistance(B,A,{-vx, -vy}); + + double d = dNAN; + + // todo: clean this up + if(isnan(d1) && isnan(d2)){ + // nothin + } + else if(isnan(d1)){ + d = d2; + } + else if(isnan(d2)){ + d = d1; + } + else{ + d = min(d1,d2); + } + + // only slide until no longer negative + // todo: clean this up + if(!isnan(d) && !_almostEqual(d,0) && d > 0){ + + } + else{ + continue; + } + + auto vd2 = vx*vx + vy*vy; + + if(d*d < vd2 && !_almostEqual(d*d, vd2)){ + auto vd = sqrt(vx*vx + vy*vy); + vx *= d/vd; + vy *= d/vd; + } + + B.offsetx += vx; + B.offsety += vy; + + for(size_t k = 0; k < B.size(); k++){ + int inpoly = pointInPolygon({B[k].x + B.offsetx, B[k].y + B.offsety}, A); + if(inpoly != 0){ + Binside = inpoly; + break; + } + } + startPoint = std::make_pair(true, Vector{B.offsetx, B.offsety}); + if(((Binside && inside) || (!Binside && !inside)) && + !intersect(A,B) && !inNfp(startPoint.second, NFP)){ + return startPoint; + } + } + } + } + + return {false, Vector(0, 0)}; + } + + static std::vector<Cntr> noFitPolygon(Cntr A, + Cntr B, + bool inside, + bool searchEdges) + { + if(A.size() < 3 || B.size() < 3) { + throw GeometryException(GeomErr::NFP); + return {}; + } + + A.offsetx = 0; + A.offsety = 0; + + long i = 0, j = 0; + + auto minA = y(A[0]); + long minAindex = 0; + + auto maxB = y(B[0]); + long maxBindex = 0; + + for(i = 1; i < A.size(); i++){ + A[i].marked = false; + if(y(A[i]) < minA){ + minA = y(A[i]); + minAindex = i; + } + } + + for(i = 1; i < B.size(); i++){ + B[i].marked = false; + if(y(B[i]) > maxB){ + maxB = y(B[i]); + maxBindex = i; + } + } + + std::pair<bool, Vector> startpoint; + + if(!inside){ + // shift B such that the bottom-most point of B is at the top-most + // point of A. This guarantees an initial placement with no + // intersections + startpoint = { true, + { x(A[minAindex]) - x(B[maxBindex]), + y(A[minAindex]) - y(B[maxBindex]) } + }; + } + else { + // no reliable heuristic for inside + startpoint = searchStartPoint(A, B, true); + } + + std::vector<Cntr> NFPlist; + + struct Touch { + int type; + long A; + long B; + Touch(int t, long a, long b): type(t), A(a), B(b) {} + }; + + while(startpoint.first) { + + B.offsetx = startpoint.second.x; + B.offsety = startpoint.second.y; + + // maintain a list of touching points/edges + std::vector<Touch> touching; + + struct V { + Coord x, y; + Vector *start, *end; + operator bool() { + return start != nullptr && end != nullptr; + } + operator Vector() const { return {x, y}; } + } prevvector = {0, 0, nullptr, nullptr}; + + Cntr NFP; + NFP.emplace_back(x(B[0]) + B.offsetx, y(B[0]) + B.offsety); + + auto referencex = x(B[0]) + B.offsetx; + auto referencey = y(B[0]) + B.offsety; + auto startx = referencex; + auto starty = referencey; + unsigned counter = 0; + + // sanity check, prevent infinite loop + while(counter < 10*(A.size() + B.size())){ + touching.clear(); + + // find touching vertices/edges + for(i = 0; i < A.size(); i++){ + long nexti = (i == A.size() - 1) ? 0 : i + 1; + for(j = 0; j < B.size(); j++){ + + long nextj = (j == B.size() - 1) ? 0 : j + 1; + + if( _almostEqual(A[i].x, B[j].x+B.offsetx) && + _almostEqual(A[i].y, B[j].y+B.offsety)) + { + touching.emplace_back(0, i, j); + } + else if( _onSegment( + A[i], A[nexti], + { B[j].x+B.offsetx, B[j].y + B.offsety}) ) + { + touching.emplace_back(1, nexti, j); + } + else if( _onSegment( + {B[j].x+B.offsetx, B[j].y + B.offsety}, + {B[nextj].x+B.offsetx, B[nextj].y + B.offsety}, + A[i]) ) + { + touching.emplace_back(2, i, nextj); + } + } + } + + // generate translation vectors from touching vertices/edges + std::vector<V> vectors; + for(i=0; i < touching.size(); i++){ + auto& vertexA = A[touching[i].A]; + vertexA.marked = true; + + // adjacent A vertices + auto prevAindex = touching[i].A - 1; + auto nextAindex = touching[i].A + 1; + + prevAindex = (prevAindex < 0) ? A.size() - 1 : prevAindex; // loop + nextAindex = (nextAindex >= A.size()) ? 0 : nextAindex; // loop + + auto& prevA = A[prevAindex]; + auto& nextA = A[nextAindex]; + + // adjacent B vertices + auto& vertexB = B[touching[i].B]; + + auto prevBindex = touching[i].B-1; + auto nextBindex = touching[i].B+1; + + prevBindex = (prevBindex < 0) ? B.size() - 1 : prevBindex; // loop + nextBindex = (nextBindex >= B.size()) ? 0 : nextBindex; // loop + + auto& prevB = B[prevBindex]; + auto& nextB = B[nextBindex]; + + if(touching[i].type == 0){ + + V vA1 = { + prevA.x - vertexA.x, + prevA.y - vertexA.y, + &vertexA, + &prevA + }; + + V vA2 = { + nextA.x - vertexA.x, + nextA.y - vertexA.y, + &vertexA, + &nextA + }; + + // B vectors need to be inverted + V vB1 = { + vertexB.x - prevB.x, + vertexB.y - prevB.y, + &prevB, + &vertexB + }; + + V vB2 = { + vertexB.x - nextB.x, + vertexB.y - nextB.y, + &nextB, + &vertexB + }; + + vectors.emplace_back(vA1); + vectors.emplace_back(vA2); + vectors.emplace_back(vB1); + vectors.emplace_back(vB2); + } + else if(touching[i].type == 1){ + vectors.emplace_back(V{ + vertexA.x-(vertexB.x+B.offsetx), + vertexA.y-(vertexB.y+B.offsety), + &prevA, + &vertexA + }); + + vectors.emplace_back(V{ + prevA.x-(vertexB.x+B.offsetx), + prevA.y-(vertexB.y+B.offsety), + &vertexA, + &prevA + }); + } + else if(touching[i].type == 2){ + vectors.emplace_back(V{ + vertexA.x-(vertexB.x+B.offsetx), + vertexA.y-(vertexB.y+B.offsety), + &prevB, + &vertexB + }); + + vectors.emplace_back(V{ + vertexA.x-(prevB.x+B.offsetx), + vertexA.y-(prevB.y+B.offsety), + &vertexB, + &prevB + }); + } + } + + // TODO: there should be a faster way to reject vectors that + // will cause immediate intersection. For now just check them all + + V translate = {0, 0, nullptr, nullptr}; + double maxd = 0; + + for(i = 0; i < vectors.size(); i++) { + if(vectors[i].x == 0 && vectors[i].y == 0){ + continue; + } + + // if this vector points us back to where we came from, ignore it. + // ie cross product = 0, dot product < 0 + if(prevvector && vectors[i].y * prevvector.y + vectors[i].x * prevvector.x < 0){ + + // compare magnitude with unit vectors + double vectorlength = sqrt(vectors[i].x*vectors[i].x+vectors[i].y*vectors[i].y); + Vector unitv = {Coord(vectors[i].x/vectorlength), + Coord(vectors[i].y/vectorlength)}; + + double prevlength = sqrt(prevvector.x*prevvector.x+prevvector.y*prevvector.y); + Vector prevunit = { prevvector.x/prevlength, prevvector.y/prevlength}; + + // we need to scale down to unit vectors to normalize vector length. Could also just do a tan here + if(abs(unitv.y * prevunit.x - unitv.x * prevunit.y) < 0.0001){ + continue; + } + } + + V vi = vectors[i]; + double d = polygonSlideDistance(A, B, vi, true); + double vecd2 = vectors[i].x*vectors[i].x + vectors[i].y*vectors[i].y; + + if(isnan(d) || d*d > vecd2){ + double vecd = sqrt(vectors[i].x*vectors[i].x + vectors[i].y*vectors[i].y); + d = vecd; + } + + if(!isnan(d) && d > maxd){ + maxd = d; + translate = vectors[i]; + } + } + + if(!translate || _almostEqual(maxd, 0)) + { + // didn't close the loop, something went wrong here + NFP.clear(); + break; + } + + translate.start->marked = true; + translate.end->marked = true; + + prevvector = translate; + + // trim + double vlength2 = translate.x*translate.x + translate.y*translate.y; + if(maxd*maxd < vlength2 && !_almostEqual(maxd*maxd, vlength2)){ + double scale = sqrt((maxd*maxd)/vlength2); + translate.x *= scale; + translate.y *= scale; + } + + referencex += translate.x; + referencey += translate.y; + + if(_almostEqual(referencex, startx) && + _almostEqual(referencey, starty)) { + // we've made a full loop + break; + } + + // if A and B start on a touching horizontal line, + // the end point may not be the start point + bool looped = false; + if(NFP.size() > 0) { + for(i = 0; i < NFP.size() - 1; i++) { + if(_almostEqual(referencex, NFP[i].x) && + _almostEqual(referencey, NFP[i].y)){ + looped = true; + } + } + } + + if(looped){ + // we've made a full loop + break; + } + + NFP.emplace_back(referencex, referencey); + + B.offsetx += translate.x; + B.offsety += translate.y; + + counter++; + } + + if(NFP.size() > 0){ + NFPlist.emplace_back(NFP); + } + + if(!searchEdges){ + // only get outer NFP or first inner NFP + break; + } + + startpoint = + searchStartPoint(A, B, inside, NFPlist); + + } + + return NFPlist; + } +}; + +template<class S> const double _alg<S>::TOL = std::pow(10, -9); + +} +} + +#endif // NFP_SVGNEST_HPP diff --git a/xs/src/libnest2d/tools/nfp_svgnest_glue.hpp b/xs/src/libnest2d/tools/nfp_svgnest_glue.hpp new file mode 100644 index 000000000..ea1fb4d07 --- /dev/null +++ b/xs/src/libnest2d/tools/nfp_svgnest_glue.hpp @@ -0,0 +1,75 @@ +#ifndef NFP_SVGNEST_GLUE_HPP +#define NFP_SVGNEST_GLUE_HPP + +#include "nfp_svgnest.hpp" + +#include <libnest2d/clipper_backend/clipper_backend.hpp> + +namespace libnest2d { + +namespace __svgnest { + +//template<> struct _Tol<double> { +// static const BP2D_CONSTEXPR TCoord<PointImpl> Value = 1000000; +//}; + +} + +namespace nfp { + +using NfpR = NfpResult<PolygonImpl>; + +template<> struct NfpImpl<PolygonImpl, NfpLevel::CONVEX_ONLY> { + NfpR operator()(const PolygonImpl& sh, const PolygonImpl& cother) { +// return nfpConvexOnly(sh, cother); + namespace sl = shapelike; + using alg = __svgnest::_alg<PolygonImpl>; + + auto nfp_p = alg::noFitPolygon(sl::getContour(sh), + sl::getContour(cother), false, false); + + PolygonImpl nfp_cntr; + if(!nfp_p.empty()) nfp_cntr.Contour = nfp_p.front(); + return {nfp_cntr, referenceVertex(nfp_cntr)}; + } +}; + +template<> struct NfpImpl<PolygonImpl, NfpLevel::ONE_CONVEX> { + NfpR operator()(const PolygonImpl& sh, const PolygonImpl& cother) { +// return nfpConvexOnly(sh, cother); + namespace sl = shapelike; + using alg = __svgnest::_alg<PolygonImpl>; + + std::cout << "Itt vagyok" << std::endl; + auto nfp_p = alg::noFitPolygon(sl::getContour(sh), + sl::getContour(cother), false, false); + + PolygonImpl nfp_cntr; + nfp_cntr.Contour = nfp_p.front(); + return {nfp_cntr, referenceVertex(nfp_cntr)}; + } +}; + +template<> +struct NfpImpl<PolygonImpl, NfpLevel::BOTH_CONCAVE> { + NfpR operator()(const PolygonImpl& sh, const PolygonImpl& cother) { + namespace sl = shapelike; + using alg = __svgnest::_alg<PolygonImpl>; + + auto nfp_p = alg::noFitPolygon(sl::getContour(sh), + sl::getContour(cother), true, false); + + PolygonImpl nfp_cntr; + nfp_cntr.Contour = nfp_p.front(); + return {nfp_cntr, referenceVertex(nfp_cntr)}; + } +}; + +template<> struct MaxNfpLevel<PolygonImpl> { +// static const BP2D_CONSTEXPR NfpLevel value = NfpLevel::BOTH_CONCAVE; + static const BP2D_CONSTEXPR NfpLevel value = NfpLevel::CONVEX_ONLY; +}; + +}} + +#endif // NFP_SVGNEST_GLUE_HPP diff --git a/xs/src/libnest2d/tools/svgtools.hpp b/xs/src/libnest2d/tools/svgtools.hpp index 3a83caa70..776dd5a1a 100644 --- a/xs/src/libnest2d/tools/svgtools.hpp +++ b/xs/src/libnest2d/tools/svgtools.hpp @@ -56,14 +56,14 @@ public: auto d = static_cast<Coord>( std::round(conf_.height*conf_.mm_in_coord_units) ); - auto& contour = ShapeLike::getContour(tsh); + auto& contour = shapelike::getContour(tsh); for(auto& v : contour) setY(v, -getY(v) + d); - auto& holes = ShapeLike::holes(tsh); + auto& holes = shapelike::holes(tsh); for(auto& h : holes) for(auto& v : h) setY(v, -getY(v) + d); } - currentLayer() += ShapeLike::serialize<Formats::SVG>(tsh, + currentLayer() += shapelike::serialize<Formats::SVG>(tsh, 1.0/conf_.mm_in_coord_units) + "\n"; } |