aboutsummarylogtreecommitdiffstats
diff options
context:
space:
mode:
authorAlexander Jacocks2023-06-18 23:50:34 -0400
committerAlexander Jacocks2023-06-18 23:50:34 -0400
commit6b066b93253afd2416ef098ee43e062db0c532e6 (patch)
treeb8d36d1309bfb5a904134270639abda1736d52eb
parent420a024ba32fb2bb90d6801c49b1fd196d6bd817 (diff)
downloadaur-6b066b93253afd2416ef098ee43e062db0c532e6.tar.gz
start fixing GCC13 issues
Diffstat
-rw-r--r--.SRCINFO12
-rw-r--r--0001-Boost-fix.patch125
-rw-r--r--0001-OpenEXR-GCC13.patch31
-rw-r--r--0001-TBB-GCC13.patch11
-rw-r--r--OpenEXR.cmake18
-rw-r--r--PKGBUILD23
-rw-r--r--TBB.cmake18
-rw-r--r--clipper.engine.cpp3594
-rw-r--r--clipper.engine.h588
9 files changed, 4417 insertions, 3 deletions
diff --git a/.SRCINFO b/.SRCINFO
index 4af8cd0f1650..87639bfc7062 100644
--- a/.SRCINFO
+++ b/.SRCINFO
@@ -29,10 +29,22 @@ pkgbase = bambustudio
source = BambuStudio.cpp.patch
source = TreeSupport.cpp.patch
source = bambu-studio.sh
+ source = clipper.engine.h
+ source = TBB.cmake
+ source = 0001-TBB-GCC13.patch
+ source = OpenEXR.cmake
+ source = 0001-OpenEXR-GCC13.patch
+ source = clipper.engine.cpp
sha512sums = 6c0d34f9ad8dbc74352b912268afc04f30d4e6d9eb21baabdd26c986625ae5e6d1e53c06f412d8315086abc29db54104ace32d17c1bd971b0b7cbd207f3dbd6e
sha512sums = fd0c5df8bd82ad8fb96204921a407a4497406bc0d0b13ab11d241d28b6b924baf1d9557974506a8135f6c58ba0b183c6828a63b8b625edc1654484b3630af775
sha512sums = 419e7ffb8044531a1c78cd191a96c11f719b439afce674f7e31d1d2e0dc57ecc03cea27ab4ad5ee6522606630fd59ac1745b9a1b787db14893561a4495806117
sha512sums = 674fc00a73b2e5997e5f3dcf74299a2ab5dfac5114247f8b6b0c87bf14f289413ec668a39063ef10a557cc2c45ca08e52a7b1714a1f9f69763edf3a7faa1d01c
sha512sums = e3cb1b072754ae6443fa136fffa263761b5e4e3da5dca1e91b7c4d577daaf01afa0affde04f1355fc404fcd336852db4ce8dc57938833f864346a0b17c12d6d6
+ sha512sums = 183dcf3298432904b4fc0098bb356be6b87f703fd189eb66e7da8c39eacd4e7620ec153b2ab3746a777c887dffbd4440bc1cd1977f397044ed330598ce98e0e9
+ sha512sums = 208a24cd44521907a261a5fa0a646eb469099bbe1b96805070e09cc1f288d7b8ff7d79dfd153e08f1ce5894030f87e5d89f33cfadfab8f2454f07d5495d360f1
+ sha512sums = 929fec4b32e05cf88f335adc74dff0cb7e353054674d22f67b5dbe6e1a741de758c53ddeb746a2c2f2ffe7351eb0985f66c15d562069e6fedc7443163eee2171
+ sha512sums = fcc49f8364b9446b34e0b96c72e5e4ff0288d2ebbdef8f38f8a488f97558133d0c826de1b7181e1484135e6a9e3b549b6c5fd66d37d8f3b13751b03a675d4e41
+ sha512sums = b32b2b1d7320ddac22eb081a7d96f75b37cb8fc84d716433ab9e08143390c3f074cfecdaf81f74621bcd9e15def2451d673e7b1600c75fa7edf62736aaf9e315
+ sha512sums = bb206ceefb7da698db8ce52531a865b2b1b2478431fc21307fa40300dda5c081b396f9667392fa677e8a7681682cd82812e6fa2c3f25f9ba5dc758b055d38900
pkgname = bambustudio
diff --git a/0001-Boost-fix.patch b/0001-Boost-fix.patch
new file mode 100644
index 000000000000..f1aad38d62ed
--- /dev/null
+++ b/0001-Boost-fix.patch
@@ -0,0 +1,125 @@
+From 1d6cd7c2f8640db3cda194c1b9b82f1e4b321395 Mon Sep 17 00:00:00 2001
+From: "chunmao.guo" <chunmao.guo@bambulab.com>
+Date: Thu, 5 Jan 2023 15:55:57 +0800
+Subject: [PATCH] FIX: limit_handles
+
+---
+ boost/process/detail/posix/executor.hpp | 4 +++-
+ boost/process/detail/posix/pipe_out.hpp | 13 +++++++++++--
+ boost/process/detail/used_handles.hpp | 3 +++
+ boost/process/detail/windows/handles.hpp | 10 +++++++---
+ 4 files changed, 24 insertions(+), 6 deletions(-)
+
+diff --git a/boost/process/detail/posix/executor.hpp b/boost/process/detail/posix/executor.hpp
+index ca7713c..5521720 100644
+--- a/boost/process/detail/posix/executor.hpp
++++ b/boost/process/detail/posix/executor.hpp
+@@ -325,6 +325,7 @@ public:
+ }
+ void set_error(const std::error_code &ec, const std::string &msg) {set_error(ec, msg.c_str());};
+
++ int error_sink() const { return _pipe_sink; }
+ };
+
+ template<typename Sequence>
+@@ -388,6 +389,8 @@ child executor<Sequence>::invoke(boost::mpl::false_, boost::mpl::false_)
+ set_error(err, "fcntl(2) failed");//this might throw, so we need to be sure our pipe is safe.
+ return child();
+ }
++ _pipe_sink = p.p[1];
++
+ _ec.clear();
+ boost::fusion::for_each(seq, call_on_setup(*this));
+
+@@ -411,7 +414,6 @@ child executor<Sequence>::invoke(boost::mpl::false_, boost::mpl::false_)
+ }
+ else if (pid == 0)
+ {
+- _pipe_sink = p.p[1];
+ ::close(p.p[0]);
+
+ boost::fusion::for_each(seq, call_on_exec_setup(*this));
+diff --git a/boost/process/detail/posix/pipe_out.hpp b/boost/process/detail/posix/pipe_out.hpp
+index d54cca4..a081d78 100644
+--- a/boost/process/detail/posix/pipe_out.hpp
++++ b/boost/process/detail/posix/pipe_out.hpp
+@@ -18,7 +18,7 @@
+ namespace boost { namespace process { namespace detail { namespace posix {
+
+ template<int p1, int p2>
+-struct pipe_out : handler_base_ext
++struct pipe_out : handler_base_ext, ::boost::process::detail::uses_handles
+ {
+ int sink;
+ int source; //opposite end
+@@ -30,6 +30,14 @@ struct pipe_out : handler_base_ext
+ {
+ p.assign_sink(-1);
+ }
++
++ std::array<int, 4> get_used_handles()
++ {
++ const auto pp1 = p1 != -1 ? p1 : p2;
++ const auto pp2 = p2 != -1 ? p2 : p1;
++
++ return {sink, source, pp1, pp2};
++ }
+
+ template<typename Executor>
+ void on_error(Executor &, const std::error_code &) const
+@@ -66,7 +74,7 @@ void pipe_out<2,-1>::on_exec_setup(Executor &e) const
+ if (::dup2(sink, STDERR_FILENO) == -1)
+ e.set_error(::boost::process::detail::get_last_error(), "dup2() failed");
+
+- if (sink != STDOUT_FILENO)
++ if (sink != STDERR_FILENO)
+ ::close(sink);
+ ::close(source);
+ }
+@@ -81,6 +89,7 @@ void pipe_out<1,2>::on_exec_setup(Executor &e) const
+ e.set_error(::boost::process::detail::get_last_error(), "dup2() failed");
+ if ((sink != STDOUT_FILENO) && (sink != STDERR_FILENO))
+ ::close(sink);
++ ::close(source);
+ }
+
+ class async_pipe;
+diff --git a/boost/process/detail/used_handles.hpp b/boost/process/detail/used_handles.hpp
+index 4d56af3..5d71dc3 100644
+--- a/boost/process/detail/used_handles.hpp
++++ b/boost/process/detail/used_handles.hpp
+@@ -61,6 +61,9 @@ struct foreach_handle_invocator
+ template<typename Executor, typename Function>
+ void foreach_used_handle(Executor &exec, Function &&func)
+ {
++#if defined(BOOST_POSIX_API)
++ func(exec.error_sink());
++#endif
+ boost::fusion::for_each(boost::fusion::filter_if<does_use_handle<boost::mpl::_>>(exec.seq),
+ foreach_handle_invocator<Function>(func));
+ }
+diff --git a/boost/process/detail/windows/handles.hpp b/boost/process/detail/windows/handles.hpp
+index 7a93ac2..f120ef7 100644
+--- a/boost/process/detail/windows/handles.hpp
++++ b/boost/process/detail/windows/handles.hpp
+@@ -139,10 +139,14 @@ struct limit_handles_ : handler_base_ext
+ ::boost::winapi::DWORD_ flags = 0u;
+ if (itr != all_handles.end())
+ *itr = ::boost::winapi::INVALID_HANDLE_VALUE_;
+- else if ((::boost::winapi::GetHandleInformation(*itr, &flags) != 0)
+- &&((flags & ::boost::winapi::HANDLE_FLAG_INHERIT_) == 0)) //it is NOT inherited anyhow, so ignore too
+- *itr = ::boost::winapi::INVALID_HANDLE_VALUE_;
+ });
++ for (auto& h : all_handles) {
++ ::boost::winapi::DWORD_ flags = 0u;
++ if ((h != ::boost::winapi::INVALID_HANDLE_VALUE_)
++ && (::boost::winapi::GetHandleInformation(h, &flags) != 0)
++ && ((flags & ::boost::winapi::HANDLE_FLAG_INHERIT_) == 0)) //it is NOT inherited anyhow, so ignore too
++ h = ::boost::winapi::INVALID_HANDLE_VALUE_;
++ }
+
+ auto part_itr = std::partition(all_handles.begin(), all_handles.end(),
+ [](::boost::winapi::HANDLE_ handle) {return handle != ::boost::winapi::INVALID_HANDLE_VALUE_;});
+--
+2.36.1.windows.1
+
diff --git a/0001-OpenEXR-GCC13.patch b/0001-OpenEXR-GCC13.patch
new file mode 100644
index 000000000000..bf7d6ae82b76
--- /dev/null
+++ b/0001-OpenEXR-GCC13.patch
@@ -0,0 +1,31 @@
+--- a/OpenEXR/IlmImf/ImfDwaCompressor.cpp
++++ b/OpenEXR/IlmImf/ImfDwaCompressor.cpp
+@@ -159,6 +159,7 @@
+ #include <limits>
+
+ #include <cstddef>
++#include <cstdint>
+
+
+ // Windows specific addition to prevent the indirect import of the redefined min/max macros
+--- a/OpenEXR/IlmImf/ImfHuf.h
++++ b/OpenEXR/IlmImf/ImfHuf.h
+@@ -40,6 +40,8 @@
+ #include "ImfExport.h"
+ #include "ImfNamespace.h"
+
++#include <cstdint>
++
+ //-----------------------------------------------------------------------------
+ //
+ // 16-bit Huffman compression and decompression:
+--- a/OpenEXR/IlmImf/ImfMisc.h
++++ b/OpenEXR/IlmImf/ImfMisc.h
+@@ -51,6 +51,7 @@
+ #include "ImfForward.h"
+
+ #include <cstddef>
++#include <cstdint>
+ #include <vector>
+
+
diff --git a/0001-TBB-GCC13.patch b/0001-TBB-GCC13.patch
new file mode 100644
index 000000000000..047daa4497b6
--- /dev/null
+++ b/0001-TBB-GCC13.patch
@@ -0,0 +1,11 @@
+--- a/include/tbb/task.h
++++ b/include/tbb/task.h
+@@ -219,7 +219,7 @@
+ #if __TBB_TASK_PRIORITY
+ //! Pointer to the next offloaded lower priority task.
+ /** Used to maintain a list of offloaded tasks inside the scheduler. **/
+- task* next_offloaded;
++ tbb::task* next_offloaded;
+ };
+ #endif /* __TBB_TASK_PRIORITY */
+
diff --git a/OpenEXR.cmake b/OpenEXR.cmake
new file mode 100644
index 000000000000..12272cbd0917
--- /dev/null
+++ b/OpenEXR.cmake
@@ -0,0 +1,18 @@
+bambustudio_add_cmake_project(OpenEXR
+ # GIT_REPOSITORY https://github.com/openexr/openexr.git
+ URL https://github.com/AcademySoftwareFoundation/openexr/archive/refs/tags/v2.5.5.zip
+ URL_HASH SHA256=0307a3d7e1fa1e77e9d84d7e9a8694583fbbbfd50bdc6884e2c96b8ef6b902de
+ PATCH_COMMAND ${PATCH_CMD} ${CMAKE_CURRENT_LIST_DIR}/0001-OpenEXR-GCC13.patch
+ DEPENDS ${ZLIB_PKG}
+ GIT_TAG v2.5.5
+ CMAKE_ARGS
+ -DCMAKE_POSITION_INDEPENDENT_CODE=ON
+ -DBUILD_TESTING=OFF
+ -DPYILMBASE_ENABLE:BOOL=OFF
+ -DOPENEXR_VIEWERS_ENABLE:BOOL=OFF
+ -DOPENEXR_BUILD_UTILS:BOOL=OFF
+)
+
+if (MSVC)
+ add_debug_dep(dep_OpenEXR)
+endif () \ No newline at end of file
diff --git a/PKGBUILD b/PKGBUILD
index ad4c38213f68..2d1dd1b77a7c 100644
--- a/PKGBUILD
+++ b/PKGBUILD
@@ -17,20 +17,37 @@ source=(
'BambuStudio.cpp.patch'
'TreeSupport.cpp.patch'
'bambu-studio.sh'
+ 'clipper.engine.h'
+ 'TBB.cmake'
+ '0001-TBB-GCC13.patch'
+ 'OpenEXR.cmake'
+ '0001-OpenEXR-GCC13.patch'
+ 'clipper.engine.cpp'
)
sha512sums=('6c0d34f9ad8dbc74352b912268afc04f30d4e6d9eb21baabdd26c986625ae5e6d1e53c06f412d8315086abc29db54104ace32d17c1bd971b0b7cbd207f3dbd6e'
'fd0c5df8bd82ad8fb96204921a407a4497406bc0d0b13ab11d241d28b6b924baf1d9557974506a8135f6c58ba0b183c6828a63b8b625edc1654484b3630af775'
'419e7ffb8044531a1c78cd191a96c11f719b439afce674f7e31d1d2e0dc57ecc03cea27ab4ad5ee6522606630fd59ac1745b9a1b787db14893561a4495806117'
'674fc00a73b2e5997e5f3dcf74299a2ab5dfac5114247f8b6b0c87bf14f289413ec668a39063ef10a557cc2c45ca08e52a7b1714a1f9f69763edf3a7faa1d01c'
- 'e3cb1b072754ae6443fa136fffa263761b5e4e3da5dca1e91b7c4d577daaf01afa0affde04f1355fc404fcd336852db4ce8dc57938833f864346a0b17c12d6d6')
+ 'e3cb1b072754ae6443fa136fffa263761b5e4e3da5dca1e91b7c4d577daaf01afa0affde04f1355fc404fcd336852db4ce8dc57938833f864346a0b17c12d6d6'
+ '183dcf3298432904b4fc0098bb356be6b87f703fd189eb66e7da8c39eacd4e7620ec153b2ab3746a777c887dffbd4440bc1cd1977f397044ed330598ce98e0e9'
+ '208a24cd44521907a261a5fa0a646eb469099bbe1b96805070e09cc1f288d7b8ff7d79dfd153e08f1ce5894030f87e5d89f33cfadfab8f2454f07d5495d360f1'
+ '929fec4b32e05cf88f335adc74dff0cb7e353054674d22f67b5dbe6e1a741de758c53ddeb746a2c2f2ffe7351eb0985f66c15d562069e6fedc7443163eee2171'
+ 'fcc49f8364b9446b34e0b96c72e5e4ff0288d2ebbdef8f38f8a488f97558133d0c826de1b7181e1484135e6a9e3b549b6c5fd66d37d8f3b13751b03a675d4e41'
+ 'b32b2b1d7320ddac22eb081a7d96f75b37cb8fc84d716433ab9e08143390c3f074cfecdaf81f74621bcd9e15def2451d673e7b1600c75fa7edf62736aaf9e315'
+ 'bb206ceefb7da698db8ce52531a865b2b1b2478431fc21307fa40300dda5c081b396f9667392fa677e8a7681682cd82812e6fa2c3f25f9ba5dc758b055d38900')
prepare() {
# link up directory
ln -sf BambuStudio-${pkgver} BambuStudio
# add missing 0001-Boost-fix.patch
cp 0001-Boost-fix.patch BambuStudio/deps/Boost
- # remove invalid UTF-8 chars
-# patch -p0 < "$srcdir/TreeSupport.cpp.patch"
+ # deal with GCC13 issues
+ cp 0001-OpenEXR-GCC13.patch BambuStudio/deps/OpenEXR/0001-OpenEXR-GCC13.patch
+ cp OpenEXR.cmake BambuStudio/deps/OpenEXR/OpenEXR.cmake
+ cp 0001-TBB-GCC13.patch BambuStudio/deps/TBB/0001-TBB-GCC13.patch
+ cp TBB.cmake BambuStudio/deps/TBB/TBB.cmake
+ cp clipper.engine.h BambuStudio/src/clipper2/Clipper2Lib/include/clipper2/clipper.engine.h
+ cp clipper.engine.cpp BambuStudio/src/clipper2/Clipper2Lib/src/clipper.engine.cpp
}
build() {
diff --git a/TBB.cmake b/TBB.cmake
new file mode 100644
index 000000000000..304b3ffb1b23
--- /dev/null
+++ b/TBB.cmake
@@ -0,0 +1,18 @@
+bambustudio_add_cmake_project(
+ TBB
+ URL "https://github.com/wjakob/tbb/archive/a0dc9bf76d0120f917b641ed095360448cabc85b.tar.gz"
+ URL_HASH SHA256=0545cb6033bd1873fcae3ea304def720a380a88292726943ae3b9b207f322efe
+ PATCH_COMMAND ${PATCH_CMD} ${CMAKE_CURRENT_LIST_DIR}/0001-TBB-GCC13.patch
+ CMAKE_ARGS
+ -DTBB_BUILD_SHARED=OFF
+ -DTBB_BUILD_TESTS=OFF
+ -DTBB_BUILD_TESTS=OFF
+ -DCMAKE_POSITION_INDEPENDENT_CODE=ON
+ -DCMAKE_DEBUG_POSTFIX=_debug
+)
+
+if (MSVC)
+ add_debug_dep(dep_TBB)
+endif ()
+
+
diff --git a/clipper.engine.cpp b/clipper.engine.cpp
new file mode 100644
index 000000000000..069b52392cac
--- /dev/null
+++ b/clipper.engine.cpp
@@ -0,0 +1,3594 @@
+/*******************************************************************************
+* Author : Angus Johnson *
+* Date : 4 November 2022 *
+* Website : http://www.angusj.com *
+* Copyright : Angus Johnson 2010-2022 *
+* Purpose : This is the main polygon clipping module *
+* License : http://www.boost.org/LICENSE_1_0.txt *
+*******************************************************************************/
+
+#include <stdlib.h>
+#include <cmath>
+#include <stdexcept>
+#include <vector>
+#include <numeric>
+#include <algorithm>
+#include "clipper2/clipper.engine.h"
+
+#include <cstddef>
+#include <cstdint>
+
+namespace Clipper2Lib {
+
+ static const double FloatingPointTolerance = 1.0e-12;
+ static const Rect64 invalid_rect = Rect64(
+ std::numeric_limits<int64_t>::max(),
+ std::numeric_limits<int64_t>::max(),
+ -std::numeric_limits<int64_t>::max(),
+ -std::numeric_limits<int64_t>::max()
+ );
+
+ //Every closed path (or polygon) is made up of a series of vertices forming
+ //edges that alternate between going up (relative to the Y-axis) and going
+ //down. Edges consecutively going up or consecutively going down are called
+ //'bounds' (or sides if they're simple polygons). 'Local Minima' refer to
+ //vertices where descending bounds become ascending ones.
+
+ struct Scanline {
+ int64_t y = 0;
+ Scanline* next = nullptr;
+
+ explicit Scanline(int64_t y_) : y(y_) {}
+ };
+
+ struct Joiner {
+ int idx;
+ OutPt* op1;
+ OutPt* op2;
+ Joiner* next1;
+ Joiner* next2;
+ Joiner* nextH;
+
+ explicit Joiner(OutPt* op1_, OutPt* op2_, Joiner* nexth) :
+ op1(op1_), op2(op2_), nextH(nexth)
+ {
+ idx = -1;
+ next1 = op1->joiner;
+ op1->joiner = this;
+
+ if (op2)
+ {
+ next2 = op2->joiner;
+ op2->joiner = this;
+ }
+ else
+ next2 = nullptr;
+ }
+
+ };
+
+ struct LocMinSorter {
+ inline bool operator()(const LocalMinima* locMin1, const LocalMinima* locMin2)
+ {
+ if (locMin2->vertex->pt.y != locMin1->vertex->pt.y)
+ return locMin2->vertex->pt.y < locMin1->vertex->pt.y;
+ else
+ return locMin2->vertex->pt.x < locMin1->vertex->pt.x;
+ }
+ };
+
+ inline bool IsOdd(int val)
+ {
+ return (val & 1) ? true : false;
+ }
+
+
+ inline bool IsHotEdge(const Active& e)
+ {
+ return (e.outrec);
+ }
+
+
+ inline bool IsOpen(const Active& e)
+ {
+ return (e.local_min->is_open);
+ }
+
+
+ inline bool IsOpenEnd(const Vertex& v)
+ {
+ return (v.flags & (VertexFlags::OpenStart | VertexFlags::OpenEnd)) !=
+ VertexFlags::None;
+ }
+
+
+ inline bool IsOpenEnd(const Active& ae)
+ {
+ return IsOpenEnd(*ae.vertex_top);
+ }
+
+
+ inline Active* GetPrevHotEdge(const Active& e)
+ {
+ Active* prev = e.prev_in_ael;
+ while (prev && (IsOpen(*prev) || !IsHotEdge(*prev)))
+ prev = prev->prev_in_ael;
+ return prev;
+ }
+
+ inline bool IsFront(const Active& e)
+ {
+ return (&e == e.outrec->front_edge);
+ }
+
+ inline bool IsInvalidPath(OutPt* op)
+ {
+ return (!op || op->next == op);
+ }
+
+ /*******************************************************************************
+ * Dx: 0(90deg) *
+ * | *
+ * +inf (180deg) <--- o ---> -inf (0deg) *
+ *******************************************************************************/
+
+ inline double GetDx(const Point64& pt1, const Point64& pt2)
+ {
+ double dy = double(pt2.y - pt1.y);
+ if (dy != 0)
+ return double(pt2.x - pt1.x) / dy;
+ else if (pt2.x > pt1.x)
+ return -std::numeric_limits<double>::max();
+ else
+ return std::numeric_limits<double>::max();
+ }
+
+
+ inline int64_t TopX(const Active& ae, const int64_t currentY)
+ {
+ if ((currentY == ae.top.y) || (ae.top.x == ae.bot.x)) return ae.top.x;
+ else if (currentY == ae.bot.y) return ae.bot.x;
+ else return ae.bot.x + static_cast<int64_t>(std::nearbyint(ae.dx * (currentY - ae.bot.y)));
+ // nb: std::nearbyint (or std::round) substantially *improves* performance here
+ // as it greatly improves the likelihood of edge adjacency in ProcessIntersectList().
+ }
+
+
+ inline bool IsHorizontal(const Active& e)
+ {
+ return (e.top.y == e.bot.y);
+ }
+
+
+ inline bool IsHeadingRightHorz(const Active& e)
+ {
+ return e.dx == -std::numeric_limits<double>::max();
+ }
+
+
+ inline bool IsHeadingLeftHorz(const Active& e)
+ {
+ return e.dx == std::numeric_limits<double>::max();
+ }
+
+
+ inline void SwapActives(Active*& e1, Active*& e2)
+ {
+ Active* e = e1;
+ e1 = e2;
+ e2 = e;
+ }
+
+
+ inline PathType GetPolyType(const Active& e)
+ {
+ return e.local_min->polytype;
+ }
+
+
+ inline bool IsSamePolyType(const Active& e1, const Active& e2)
+ {
+ return e1.local_min->polytype == e2.local_min->polytype;
+ }
+
+ inline Point64 GetEndE1ClosestToEndE2(
+ const Active& e1, const Active& e2)
+ {
+ double d[] = {
+ DistanceSqr(e1.bot, e2.bot),
+ DistanceSqr(e1.top, e2.top),
+ DistanceSqr(e1.top, e2.bot),
+ DistanceSqr(e1.bot, e2.top)
+ };
+ if (d[0] == 0) return e1.bot;
+ int idx = 0;
+ for (int i = 1; i < 4; ++i)
+ {
+ if (d[i] < d[idx]) idx = i;
+ if (d[i] == 0) break;
+ }
+ switch (idx)
+ {
+ case 1: case 2: return e1.top;
+ default: return e1.bot;
+ }
+ }
+
+ Point64 GetIntersectPoint(const Active& e1, const Active& e2)
+ {
+ double b1, b2, q = (e1.dx - e2.dx);
+ if (std::abs(q) < 1e-5) // 1e-5 is a rough empirical limit
+ return GetEndE1ClosestToEndE2(e1, e2); // ie almost parallel
+
+ if (e1.dx == 0)
+ {
+ if (IsHorizontal(e2)) return Point64(e1.bot.x, e2.bot.y);
+ b2 = e2.bot.y - (e2.bot.x / e2.dx);
+ return Point64(e1.bot.x,
+ static_cast<int64_t>(std::round(e1.bot.x / e2.dx + b2)));
+ }
+ else if (e2.dx == 0)
+ {
+ if (IsHorizontal(e1)) return Point64(e2.bot.x, e1.bot.y);
+ b1 = e1.bot.y - (e1.bot.x / e1.dx);
+ return Point64(e2.bot.x,
+ static_cast<int64_t>(std::round(e2.bot.x / e1.dx + b1)));
+ }
+ else
+ {
+ b1 = e1.bot.x - e1.bot.y * e1.dx;
+ b2 = e2.bot.x - e2.bot.y * e2.dx;
+
+ q = (b2 - b1) / q;
+ return (abs(e1.dx) < abs(e2.dx)) ?
+ Point64(static_cast<int64_t>(e1.dx * q + b1),
+ static_cast<int64_t>((q))) :
+ Point64(static_cast<int64_t>(e2.dx * q + b2),
+ static_cast<int64_t>((q)));
+ }
+ }
+
+ bool GetIntersectPoint(const Point64& ln1a, const Point64& ln1b,
+ const Point64& ln2a, const Point64& ln2b, PointD& ip)
+ {
+ ip = PointD(0, 0);
+ double m1, b1, m2, b2;
+ if (ln1b.x == ln1a.x)
+ {
+ if (ln2b.x == ln2a.x) return false;
+ m2 = static_cast<double>(ln2b.y - ln2a.y) /
+ static_cast<double>(ln2b.x - ln2a.x);
+ b2 = ln2a.y - m2 * ln2a.x;
+ ip.x = static_cast<double>(ln1a.x);
+ ip.y = m2 * ln1a.x + b2;
+ }
+ else if (ln2b.x == ln2a.x)
+ {
+ m1 = static_cast<double>(ln1b.y - ln1a.y) /
+ static_cast<double>(ln1b.x - ln1a.x);
+ b1 = ln1a.y - m1 * ln1a.x;
+ ip.x = static_cast<double>(ln2a.x);
+ ip.y = m1 * ln2a.x + b1;
+ }
+ else
+ {
+ m1 = static_cast<double>(ln1b.y - ln1a.y) /
+ static_cast<double>(ln1b.x - ln1a.x);
+ b1 = ln1a.y - m1 * ln1a.x;
+ m2 = static_cast<double>(ln2b.y - ln2a.y) /
+ static_cast<double>(ln2b.x - ln2a.x);
+ b2 = ln2a.y - m2 * ln2a.x;
+ if (std::abs(m1 - m2) > FloatingPointTolerance)
+ {
+ ip.x = (b2 - b1) / (m1 - m2);
+ ip.y = m1 * ip.x + b1;
+ }
+ else
+ {
+ ip.x = static_cast<double>(ln1a.x + ln1b.x) / 2;
+ ip.y = static_cast<double>(ln1a.y + ln1b.y) / 2;
+ }
+ }
+ return true;
+ }
+
+
+ inline void SetDx(Active& e)
+ {
+ e.dx = GetDx(e.bot, e.top);
+ }
+
+
+ inline Vertex* NextVertex(const Active& e)
+ {
+ if (e.wind_dx > 0)
+ return e.vertex_top->next;
+ else
+ return e.vertex_top->prev;
+ }
+
+
+ //PrevPrevVertex: useful to get the (inverted Y-axis) top of the
+ //alternate edge (ie left or right bound) during edge insertion.
+ inline Vertex* PrevPrevVertex(const Active& ae)
+ {
+ if (ae.wind_dx > 0)
+ return ae.vertex_top->prev->prev;
+ else
+ return ae.vertex_top->next->next;
+ }
+
+
+ inline Active* ExtractFromSEL(Active* ae)
+ {
+ Active* res = ae->next_in_sel;
+ if (res)
+ res->prev_in_sel = ae->prev_in_sel;
+ ae->prev_in_sel->next_in_sel = res;
+ return res;
+ }
+
+
+ inline void Insert1Before2InSEL(Active* ae1, Active* ae2)
+ {
+ ae1->prev_in_sel = ae2->prev_in_sel;
+ if (ae1->prev_in_sel)
+ ae1->prev_in_sel->next_in_sel = ae1;
+ ae1->next_in_sel = ae2;
+ ae2->prev_in_sel = ae1;
+ }
+
+ inline bool IsMaxima(const Vertex& v)
+ {
+ return ((v.flags & VertexFlags::LocalMax) != VertexFlags::None);
+ }
+
+
+ inline bool IsMaxima(const Active& e)
+ {
+ return IsMaxima(*e.vertex_top);
+ }
+
+ Vertex* GetCurrYMaximaVertex(const Active& e)
+ {
+ Vertex* result = e.vertex_top;
+ if (e.wind_dx > 0)
+ while (result->next->pt.y == result->pt.y) result = result->next;
+ else
+ while (result->prev->pt.y == result->pt.y) result = result->prev;
+ if (!IsMaxima(*result)) result = nullptr; // not a maxima
+ return result;
+ }
+
+ Active* GetMaximaPair(const Active& e)
+ {
+ Active* e2;
+ e2 = e.next_in_ael;
+ while (e2)
+ {
+ if (e2->vertex_top == e.vertex_top) return e2; // Found!
+ e2 = e2->next_in_ael;
+ }
+ return nullptr;
+ }
+
+ Active* GetHorzMaximaPair(const Active& horz, const Vertex* vert_max)
+ {
+ //we can't be sure whether the MaximaPair is on the left or right, so ...
+ Active* result = horz.prev_in_ael;
+ while (result && result->curr_x >= vert_max->pt.x)
+ {
+ if (result->vertex_top == vert_max) return result; // Found!
+ result = result->prev_in_ael;
+ }
+ result = horz.next_in_ael;
+ while (result && TopX(*result, horz.top.y) <= vert_max->pt.x)
+ {
+ if (result->vertex_top == vert_max) return result; // Found!
+ result = result->next_in_ael;
+ }
+ return nullptr;
+ }
+
+ inline int PointCount(OutPt* op)
+ {
+ OutPt* op2 = op;
+ int cnt = 0;
+ do
+ {
+ op2 = op2->next;
+ ++cnt;
+ } while (op2 != op);
+ return cnt;
+ }
+
+
+ inline OutPt* InsertOp(const Point64& pt, OutPt* insertAfter)
+ {
+ OutPt* result = new OutPt(pt, insertAfter->outrec);
+ result->next = insertAfter->next;
+ insertAfter->next->prev = result;
+ insertAfter->next = result;
+ result->prev = insertAfter;
+ return result;
+ }
+
+
+ inline OutPt* DisposeOutPt(OutPt* op)
+ {
+ OutPt* result = op->next;
+ op->prev->next = op->next;
+ op->next->prev = op->prev;
+ delete op;
+ return result;
+ }
+
+
+ inline void DisposeOutPts(OutRec& outrec)
+ {
+ if (!outrec.pts) return;
+ OutPt* op2 = outrec.pts->next;
+ while (op2 != outrec.pts)
+ {
+ OutPt* tmp = op2->next;
+ delete op2;
+ op2 = tmp;
+ }
+ delete outrec.pts;
+ outrec.pts = nullptr;
+ }
+
+
+ bool IntersectListSort(const IntersectNode& a, const IntersectNode& b)
+ {
+ //note different inequality tests ...
+ return (a.pt.y == b.pt.y) ? (a.pt.x < b.pt.x) : (a.pt.y > b.pt.y);
+ }
+
+
+ inline void SetSides(OutRec& outrec, Active& start_edge, Active& end_edge)
+ {
+ outrec.front_edge = &start_edge;
+ outrec.back_edge = &end_edge;
+ }
+
+
+ void SwapOutrecs(Active& e1, Active& e2)
+ {
+ OutRec* or1 = e1.outrec;
+ OutRec* or2 = e2.outrec;
+ if (or1 == or2)
+ {
+ Active* e = or1->front_edge;
+ or1->front_edge = or1->back_edge;
+ or1->back_edge = e;
+ return;
+ }
+ if (or1)
+ {
+ if (&e1 == or1->front_edge)
+ or1->front_edge = &e2;
+ else
+ or1->back_edge = &e2;
+ }
+ if (or2)
+ {
+ if (&e2 == or2->front_edge)
+ or2->front_edge = &e1;
+ else
+ or2->back_edge = &e1;
+ }
+ e1.outrec = or2;
+ e2.outrec = or1;
+ }
+
+
+ double Area(OutPt* op)
+ {
+ //https://en.wikipedia.org/wiki/Shoelace_formula
+ double result = 0.0;
+ OutPt* op2 = op;
+ do
+ {
+ result += static_cast<double>(op2->prev->pt.y + op2->pt.y) *
+ static_cast<double>(op2->prev->pt.x - op2->pt.x);
+ op2 = op2->next;
+ } while (op2 != op);
+ return result * 0.5;
+ }
+
+ inline double AreaTriangle(const Point64& pt1,
+ const Point64& pt2, const Point64& pt3)
+ {
+ return (static_cast<double>(pt3.y + pt1.y) * static_cast<double>(pt3.x - pt1.x) +
+ static_cast<double>(pt1.y + pt2.y) * static_cast<double>(pt1.x - pt2.x) +
+ static_cast<double>(pt2.y + pt3.y) * static_cast<double>(pt2.x - pt3.x));
+ }
+
+ void ReverseOutPts(OutPt* op)
+ {
+ if (!op) return;
+
+ OutPt* op1 = op;
+ OutPt* op2;
+
+ do
+ {
+ op2 = op1->next;
+ op1->next = op1->prev;
+ op1->prev = op2;
+ op1 = op2;
+ } while (op1 != op);
+ }
+
+
+ inline void SwapSides(OutRec& outrec)
+ {
+ Active* e2 = outrec.front_edge;
+ outrec.front_edge = outrec.back_edge;
+ outrec.back_edge = e2;
+ outrec.pts = outrec.pts->next;
+ }
+
+
+ inline OutRec* GetRealOutRec(OutRec* outrec)
+ {
+ while (outrec && !outrec->pts) outrec = outrec->owner;
+ return outrec;
+ }
+
+
+ inline void UncoupleOutRec(Active ae)
+ {
+ OutRec* outrec = ae.outrec;
+ if (!outrec) return;
+ outrec->front_edge->outrec = nullptr;
+ outrec->back_edge->outrec = nullptr;
+ outrec->front_edge = nullptr;
+ outrec->back_edge = nullptr;
+ }
+
+
+ inline bool PtsReallyClose(const Point64& pt1, const Point64& pt2)
+ {
+ return (std::llabs(pt1.x - pt2.x) < 2) && (std::llabs(pt1.y - pt2.y) < 2);
+ }
+
+ inline bool IsVerySmallTriangle(const OutPt& op)
+ {
+ return op.next->next == op.prev &&
+ (PtsReallyClose(op.prev->pt, op.next->pt) ||
+ PtsReallyClose(op.pt, op.next->pt) ||
+ PtsReallyClose(op.pt, op.prev->pt));
+ }
+
+ inline bool IsValidClosedPath(const OutPt* op)
+ {
+ return op && (op->next != op) && (op->next != op->prev) &&
+ !IsVerySmallTriangle(*op);
+ }
+
+ inline bool OutrecIsAscending(const Active* hotEdge)
+ {
+ return (hotEdge == hotEdge->outrec->front_edge);
+ }
+
+ inline void SwapFrontBackSides(OutRec& outrec)
+ {
+ Active* tmp = outrec.front_edge;
+ outrec.front_edge = outrec.back_edge;
+ outrec.back_edge = tmp;
+ outrec.pts = outrec.pts->next;
+ }
+
+ inline bool EdgesAdjacentInAEL(const IntersectNode& inode)
+ {
+ return (inode.edge1->next_in_ael == inode.edge2) || (inode.edge1->prev_in_ael == inode.edge2);
+ }
+
+ inline bool TestJoinWithPrev1(const Active& e)
+ {
+ //this is marginally quicker than TestJoinWithPrev2
+ //but can only be used when e.PrevInAEL.currX is accurate
+ return IsHotEdge(e) && !IsOpen(e) &&
+ e.prev_in_ael && e.prev_in_ael->curr_x == e.curr_x &&
+ IsHotEdge(*e.prev_in_ael) && !IsOpen(*e.prev_in_ael) &&
+ (CrossProduct(e.prev_in_ael->top, e.bot, e.top) == 0);
+ }
+
+ inline bool TestJoinWithPrev2(const Active& e, const Point64& curr_pt)
+ {
+ return IsHotEdge(e) && !IsOpen(e) &&
+ e.prev_in_ael && !IsOpen(*e.prev_in_ael) &&
+ IsHotEdge(*e.prev_in_ael) && (e.prev_in_ael->top.y < e.bot.y) &&
+ (std::llabs(TopX(*e.prev_in_ael, curr_pt.y) - curr_pt.x) < 2) &&
+ (CrossProduct(e.prev_in_ael->top, curr_pt, e.top) == 0);
+ }
+
+ inline bool TestJoinWithNext1(const Active& e)
+ {
+ //this is marginally quicker than TestJoinWithNext2
+ //but can only be used when e.NextInAEL.currX is accurate
+ return IsHotEdge(e) && !IsOpen(e) &&
+ e.next_in_ael && (e.next_in_ael->curr_x == e.curr_x) &&
+ IsHotEdge(*e.next_in_ael) && !IsOpen(*e.next_in_ael) &&
+ (CrossProduct(e.next_in_ael->top, e.bot, e.top) == 0);
+ }
+
+ inline bool TestJoinWithNext2(const Active& e, const Point64& curr_pt)
+ {
+ return IsHotEdge(e) && !IsOpen(e) &&
+ e.next_in_ael && !IsOpen(*e.next_in_ael) &&
+ IsHotEdge(*e.next_in_ael) && (e.next_in_ael->top.y < e.bot.y) &&
+ (std::llabs(TopX(*e.next_in_ael, curr_pt.y) - curr_pt.x) < 2) &&
+ (CrossProduct(e.next_in_ael->top, curr_pt, e.top) == 0);
+ }
+
+ //------------------------------------------------------------------------------
+ // ClipperBase methods ...
+ //------------------------------------------------------------------------------
+
+ ClipperBase::~ClipperBase()
+ {
+ Clear();
+ }
+
+ void ClipperBase::DeleteEdges(Active*& e)
+ {
+ while (e)
+ {
+ Active* e2 = e;
+ e = e->next_in_ael;
+ delete e2;
+ }
+ }
+
+ void ClipperBase::CleanUp()
+ {
+ DeleteEdges(actives_);
+ scanline_list_ = std::priority_queue<int64_t>();
+ intersect_nodes_.clear();
+ DisposeAllOutRecs();
+ }
+
+
+ void ClipperBase::Clear()
+ {
+ CleanUp();
+ DisposeVerticesAndLocalMinima();
+ current_locmin_iter_ = minima_list_.begin();
+ minima_list_sorted_ = false;
+ has_open_paths_ = false;
+ }
+
+
+ void ClipperBase::Reset()
+ {
+ if (!minima_list_sorted_)
+ {
+ std::sort(minima_list_.begin(), minima_list_.end(), LocMinSorter());
+ minima_list_sorted_ = true;
+ }
+ std::vector<LocalMinima*>::const_reverse_iterator i;
+ for (i = minima_list_.rbegin(); i != minima_list_.rend(); ++i)
+ InsertScanline((*i)->vertex->pt.y);
+
+ current_locmin_iter_ = minima_list_.begin();
+ actives_ = nullptr;
+ sel_ = nullptr;
+ succeeded_ = true;
+ }
+
+
+#ifdef USINGZ
+ void ClipperBase::SetZ(const Active& e1, const Active& e2, Point64& ip)
+ {
+ if (!zCallback_) return;
+ // prioritize subject over clip vertices by passing
+ // subject vertices before clip vertices in the callback
+ if (GetPolyType(e1) == PathType::Subject)
+ {
+ if (ip == e1.bot) ip.z = e1.bot.z;
+ else if (ip == e1.top) ip.z = e1.top.z;
+ else if (ip == e2.bot) ip.z = e2.bot.z;
+ else if (ip == e2.top) ip.z = e2.top.z;
+ zCallback_(e1.bot, e1.top, e2.bot, e2.top, ip);
+ }
+ else
+ {
+ if (ip == e2.bot) ip.z = e2.bot.z;
+ else if (ip == e2.top) ip.z = e2.top.z;
+ else if (ip == e1.bot) ip.z = e1.bot.z;
+ else if (ip == e1.top) ip.z = e1.top.z;
+ zCallback_(e2.bot, e2.top, e1.bot, e1.top, ip);
+ }
+ }
+#endif
+
+ void ClipperBase::AddPath(const Path64& path, PathType polytype, bool is_open)
+ {
+ Paths64 tmp;
+ tmp.push_back(path);
+ AddPaths(tmp, polytype, is_open);
+ }
+
+
+ void ClipperBase::AddPaths(const Paths64& paths, PathType polytype, bool is_open)
+ {
+ if (is_open) has_open_paths_ = true;
+ minima_list_sorted_ = false;
+
+ Path64::size_type total_vertex_count = 0;
+ for (const Path64& path : paths) total_vertex_count += path.size();
+ if (total_vertex_count == 0) return;
+ Vertex* vertices = new Vertex[total_vertex_count], *v = vertices;
+ for (const Path64& path : paths)
+ {
+ //for each path create a circular double linked list of vertices
+ Vertex *v0 = v, *curr_v = v, *prev_v = nullptr;
+
+ v->prev = nullptr;
+ int cnt = 0;
+ for (const Point64& pt : path)
+ {
+ if (prev_v)
+ {
+ if (prev_v->pt == pt) continue; // ie skips duplicates
+ prev_v->next = curr_v;
+ }
+ curr_v->prev = prev_v;
+ curr_v->pt = pt;
+ curr_v->flags = VertexFlags::None;
+ prev_v = curr_v++;
+ cnt++;
+ }
+ if (!prev_v || !prev_v->prev) continue;
+ if (!is_open && prev_v->pt == v0->pt)
+ prev_v = prev_v->prev;
+ prev_v->next = v0;
+ v0->prev = prev_v;
+ v = curr_v; // ie get ready for next path
+ if (cnt < 2 || (cnt == 2 && !is_open)) continue;
+
+ //now find and assign local minima
+ bool going_up, going_up0;
+ if (is_open)
+ {
+ curr_v = v0->next;
+ while (curr_v != v0 && curr_v->pt.y == v0->pt.y)
+ curr_v = curr_v->next;
+ going_up = curr_v->pt.y <= v0->pt.y;
+ if (going_up)
+ {
+ v0->flags = VertexFlags::OpenStart;
+ AddLocMin(*v0, polytype, true);
+ }
+ else
+ v0->flags = VertexFlags::OpenStart | VertexFlags::LocalMax;
+ }
+ else // closed path
+ {
+ prev_v = v0->prev;
+ while (prev_v != v0 && prev_v->pt.y == v0->pt.y)
+ prev_v = prev_v->prev;
+ if (prev_v == v0)
+ continue; // only open paths can be completely flat
+ going_up = prev_v->pt.y > v0->pt.y;
+ }
+
+ going_up0 = going_up;
+ prev_v = v0;
+ curr_v = v0->next;
+ while (curr_v != v0)
+ {
+ if (curr_v->pt.y > prev_v->pt.y && going_up)
+ {
+ prev_v->flags = (prev_v->flags | VertexFlags::LocalMax);
+ going_up = false;
+ }
+ else if (curr_v->pt.y < prev_v->pt.y && !going_up)
+ {
+ going_up = true;
+ AddLocMin(*prev_v, polytype, is_open);
+ }
+ prev_v = curr_v;
+ curr_v = curr_v->next;
+ }
+
+ if (is_open)
+ {
+ prev_v->flags = prev_v->flags | VertexFlags::OpenEnd;
+ if (going_up)
+ prev_v->flags = prev_v->flags | VertexFlags::LocalMax;
+ else
+ AddLocMin(*prev_v, polytype, is_open);
+ }
+ else if (going_up != going_up0)
+ {
+ if (going_up0) AddLocMin(*prev_v, polytype, false);
+ else prev_v->flags = prev_v->flags | VertexFlags::LocalMax;
+ }
+ } // end processing current path
+
+ vertex_lists_.emplace_back(vertices);
+ } // end AddPaths
+
+
+ inline void ClipperBase::InsertScanline(int64_t y)
+ {
+ scanline_list_.push(y);
+ }
+
+
+ bool ClipperBase::PopScanline(int64_t& y)
+ {
+ if (scanline_list_.empty()) return false;
+ y = scanline_list_.top();
+ scanline_list_.pop();
+ while (!scanline_list_.empty() && y == scanline_list_.top())
+ scanline_list_.pop(); // Pop duplicates.
+ return true;
+ }
+
+
+ bool ClipperBase::PopLocalMinima(int64_t y, LocalMinima*& local_minima)
+ {
+ if (current_locmin_iter_ == minima_list_.end() || (*current_locmin_iter_)->vertex->pt.y != y) return false;
+ local_minima = (*current_locmin_iter_++);
+ return true;
+ }
+
+
+ void ClipperBase::DisposeAllOutRecs()
+ {
+ for (auto outrec : outrec_list_)
+ {
+ if (outrec->pts) DisposeOutPts(*outrec);
+ delete outrec;
+ }
+ outrec_list_.resize(0);
+ }
+
+
+ void ClipperBase::DisposeVerticesAndLocalMinima()
+ {
+ for (auto lm : minima_list_) delete lm;
+ minima_list_.clear();
+ for (auto v : vertex_lists_) delete[] v;
+ vertex_lists_.clear();
+ }
+
+
+ void ClipperBase::AddLocMin(Vertex& vert, PathType polytype, bool is_open)
+ {
+ //make sure the vertex is added only once ...
+ if ((VertexFlags::LocalMin & vert.flags) != VertexFlags::None) return;
+
+ vert.flags = (vert.flags | VertexFlags::LocalMin);
+ minima_list_.push_back(new LocalMinima(&vert, polytype, is_open));
+ }
+
+ bool ClipperBase::IsContributingClosed(const Active & e) const
+ {
+ switch (fillrule_)
+ {
+ case FillRule::EvenOdd:
+ break;
+ case FillRule::NonZero:
+ if (abs(e.wind_cnt) != 1) return false;
+ break;
+ case FillRule::Positive:
+ if (e.wind_cnt != 1) return false;
+ break;
+ case FillRule::Negative:
+ if (e.wind_cnt != -1) return false;
+ break;
+ }
+
+ switch (cliptype_)
+ {
+ case ClipType::None:
+ return false;
+ case ClipType::Intersection:
+ switch (fillrule_)
+ {
+ case FillRule::Positive:
+ return (e.wind_cnt2 > 0);
+ case FillRule::Negative:
+ return (e.wind_cnt2 < 0);
+ default:
+ return (e.wind_cnt2 != 0);
+ }
+ break;
+
+ case ClipType::Union:
+ switch (fillrule_)
+ {
+ case FillRule::Positive:
+ return (e.wind_cnt2 <= 0);
+ case FillRule::Negative:
+ return (e.wind_cnt2 >= 0);
+ default:
+ return (e.wind_cnt2 == 0);
+ }
+ break;
+
+ case ClipType::Difference:
+ bool result;
+ switch (fillrule_)
+ {
+ case FillRule::Positive:
+ result = (e.wind_cnt2 <= 0);
+ break;
+ case FillRule::Negative:
+ result = (e.wind_cnt2 >= 0);
+ break;
+ default:
+ result = (e.wind_cnt2 == 0);
+ }
+ if (GetPolyType(e) == PathType::Subject)
+ return result;
+ else
+ return !result;
+ break;
+
+ case ClipType::Xor: return true; break;
+ }
+ return false; // we should never get here
+ }
+
+
+ inline bool ClipperBase::IsContributingOpen(const Active& e) const
+ {
+ bool is_in_clip, is_in_subj;
+ switch (fillrule_)
+ {
+ case FillRule::Positive:
+ is_in_clip = e.wind_cnt2 > 0;
+ is_in_subj = e.wind_cnt > 0;
+ break;
+ case FillRule::Negative:
+ is_in_clip = e.wind_cnt2 < 0;
+ is_in_subj = e.wind_cnt < 0;
+ break;
+ default:
+ is_in_clip = e.wind_cnt2 != 0;
+ is_in_subj = e.wind_cnt != 0;
+ }
+
+ switch (cliptype_)
+ {
+ case ClipType::Intersection: return is_in_clip;
+ case ClipType::Union: return (!is_in_subj && !is_in_clip);
+ default: return !is_in_clip;
+ }
+ }
+
+
+ void ClipperBase::SetWindCountForClosedPathEdge(Active& e)
+ {
+ //Wind counts refer to polygon regions not edges, so here an edge's WindCnt
+ //indicates the higher of the wind counts for the two regions touching the
+ //edge. (NB Adjacent regions can only ever have their wind counts differ by
+ //one. Also, open paths have no meaningful wind directions or counts.)
+
+ Active* e2 = e.prev_in_ael;
+ //find the nearest closed path edge of the same PolyType in AEL (heading left)
+ PathType pt = GetPolyType(e);
+ while (e2 && (GetPolyType(*e2) != pt || IsOpen(*e2))) e2 = e2->prev_in_ael;
+
+ if (!e2)
+ {
+ e.wind_cnt = e.wind_dx;
+ e2 = actives_;
+ }
+ else if (fillrule_ == FillRule::EvenOdd)
+ {
+ e.wind_cnt = e.wind_dx;
+ e.wind_cnt2 = e2->wind_cnt2;
+ e2 = e2->next_in_ael;
+ }
+ else
+ {
+ //NonZero, positive, or negative filling here ...
+ //if e's WindCnt is in the SAME direction as its WindDx, then polygon
+ //filling will be on the right of 'e'.
+ //NB neither e2.WindCnt nor e2.WindDx should ever be 0.
+ if (e2->wind_cnt * e2->wind_dx < 0)
+ {
+ //opposite directions so 'e' is outside 'e2' ...
+ if (abs(e2->wind_cnt) > 1)
+ {
+ //outside prev poly but still inside another.
+ if (e2->wind_dx * e.wind_dx < 0)
+ //reversing direction so use the same WC
+ e.wind_cnt = e2->wind_cnt;
+ else
+ //otherwise keep 'reducing' the WC by 1 (ie towards 0) ...
+ e.wind_cnt = e2->wind_cnt + e.wind_dx;
+ }
+ else
+ //now outside all polys of same polytype so set own WC ...
+ e.wind_cnt = (IsOpen(e) ? 1 : e.wind_dx);
+ }
+ else
+ {
+ //'e' must be inside 'e2'
+ if (e2->wind_dx * e.wind_dx < 0)
+ //reversing direction so use the same WC
+ e.wind_cnt = e2->wind_cnt;
+ else
+ //otherwise keep 'increasing' the WC by 1 (ie away from 0) ...
+ e.wind_cnt = e2->wind_cnt + e.wind_dx;
+ }
+ e.wind_cnt2 = e2->wind_cnt2;
+ e2 = e2->next_in_ael; // ie get ready to calc WindCnt2
+ }
+
+ //update wind_cnt2 ...
+ if (fillrule_ == FillRule::EvenOdd)
+ while (e2 != &e)
+ {
+ if (GetPolyType(*e2) != pt && !IsOpen(*e2))
+ e.wind_cnt2 = (e.wind_cnt2 == 0 ? 1 : 0);
+ e2 = e2->next_in_ael;
+ }
+ else
+ while (e2 != &e)
+ {
+ if (GetPolyType(*e2) != pt && !IsOpen(*e2))
+ e.wind_cnt2 += e2->wind_dx;
+ e2 = e2->next_in_ael;
+ }
+ }
+
+
+ void ClipperBase::SetWindCountForOpenPathEdge(Active& e)
+ {
+ Active* e2 = actives_;
+ if (fillrule_ == FillRule::EvenOdd)
+ {
+ int cnt1 = 0, cnt2 = 0;
+ while (e2 != &e)
+ {
+ if (GetPolyType(*e2) == PathType::Clip)
+ cnt2++;
+ else if (!IsOpen(*e2))
+ cnt1++;
+ e2 = e2->next_in_ael;
+ }
+ e.wind_cnt = (IsOdd(cnt1) ? 1 : 0);
+ e.wind_cnt2 = (IsOdd(cnt2) ? 1 : 0);
+ }
+ else
+ {
+ while (e2 != &e)
+ {
+ if (GetPolyType(*e2) == PathType::Clip)
+ e.wind_cnt2 += e2->wind_dx;
+ else if (!IsOpen(*e2))
+ e.wind_cnt += e2->wind_dx;
+ e2 = e2->next_in_ael;
+ }
+ }
+ }
+
+
+ bool IsValidAelOrder(const Active& resident, const Active& newcomer)
+ {
+ if (newcomer.curr_x != resident.curr_x)
+ return newcomer.curr_x > resident.curr_x;
+
+ //get the turning direction a1.top, a2.bot, a2.top
+ double d = CrossProduct(resident.top, newcomer.bot, newcomer.top);
+ if (d != 0) return d < 0;
+
+ //edges must be collinear to get here
+ //for starting open paths, place them according to
+ //the direction they're about to turn
+ if (!IsMaxima(resident) && (resident.top.y > newcomer.top.y))
+ {
+ return CrossProduct(newcomer.bot,
+ resident.top, NextVertex(resident)->pt) <= 0;
+ }
+ else if (!IsMaxima(newcomer) && (newcomer.top.y > resident.top.y))
+ {
+ return CrossProduct(newcomer.bot,
+ newcomer.top, NextVertex(newcomer)->pt) >= 0;
+ }
+
+ int64_t y = newcomer.bot.y;
+ bool newcomerIsLeft = newcomer.is_left_bound;
+
+ if (resident.bot.y != y || resident.local_min->vertex->pt.y != y)
+ return newcomer.is_left_bound;
+ //resident must also have just been inserted
+ else if (resident.is_left_bound != newcomerIsLeft)
+ return newcomerIsLeft;
+ else if (CrossProduct(PrevPrevVertex(resident)->pt,
+ resident.bot, resident.top) == 0) return true;
+ else
+ //compare turning direction of the alternate bound
+ return (CrossProduct(PrevPrevVertex(resident)->pt,
+ newcomer.bot, PrevPrevVertex(newcomer)->pt) > 0) == newcomerIsLeft;
+ }
+
+
+ void ClipperBase::InsertLeftEdge(Active& e)
+ {
+ Active* e2;
+ if (!actives_)
+ {
+ e.prev_in_ael = nullptr;
+ e.next_in_ael = nullptr;
+ actives_ = &e;
+ }
+ else if (!IsValidAelOrder(*actives_, e))
+ {
+ e.prev_in_ael = nullptr;
+ e.next_in_ael = actives_;
+ actives_->prev_in_ael = &e;
+ actives_ = &e;
+ }
+ else
+ {
+ e2 = actives_;
+ while (e2->next_in_ael && IsValidAelOrder(*e2->next_in_ael, e))
+ e2 = e2->next_in_ael;
+ e.next_in_ael = e2->next_in_ael;
+ if (e2->next_in_ael) e2->next_in_ael->prev_in_ael = &e;
+ e.prev_in_ael = e2;
+ e2->next_in_ael = &e;
+ }
+ }
+
+
+ void InsertRightEdge(Active& e, Active& e2)
+ {
+ e2.next_in_ael = e.next_in_ael;
+ if (e.next_in_ael) e.next_in_ael->prev_in_ael = &e2;
+ e2.prev_in_ael = &e;
+ e.next_in_ael = &e2;
+ }
+
+
+ void ClipperBase::InsertLocalMinimaIntoAEL(int64_t bot_y)
+ {
+ LocalMinima* local_minima;
+ Active* left_bound, * right_bound;
+ //Add any local minima (if any) at BotY ...
+ //nb: horizontal local minima edges should contain locMin.vertex.prev
+
+ while (PopLocalMinima(bot_y, local_minima))
+ {
+ if ((local_minima->vertex->flags & VertexFlags::OpenStart) != VertexFlags::None)
+ {
+ left_bound = nullptr;
+ }
+ else
+ {
+ left_bound = new Active();
+ left_bound->bot = local_minima->vertex->pt;
+ left_bound->curr_x = left_bound->bot.x;
+ left_bound->wind_cnt = 0,
+ left_bound->wind_cnt2 = 0,
+ left_bound->wind_dx = -1,
+ left_bound->vertex_top = local_minima->vertex->prev; // ie descending
+ left_bound->top = left_bound->vertex_top->pt;
+ left_bound->outrec = nullptr;
+ left_bound->local_min = local_minima;
+ SetDx(*left_bound);
+ }
+
+ if ((local_minima->vertex->flags & VertexFlags::OpenEnd) != VertexFlags::None)
+ {
+ right_bound = nullptr;
+ }
+ else
+ {
+ right_bound = new Active();
+ right_bound->bot = local_minima->vertex->pt;
+ right_bound->curr_x = right_bound->bot.x;
+ right_bound->wind_cnt = 0,
+ right_bound->wind_cnt2 = 0,
+ right_bound->wind_dx = 1,
+ right_bound->vertex_top = local_minima->vertex->next; // ie ascending
+ right_bound->top = right_bound->vertex_top->pt;
+ right_bound->outrec = nullptr;
+ right_bound->local_min = local_minima;
+ SetDx(*right_bound);
+ }
+
+ //Currently LeftB is just the descending bound and RightB is the ascending.
+ //Now if the LeftB isn't on the left of RightB then we need swap them.
+ if (left_bound && right_bound)
+ {
+ if (IsHorizontal(*left_bound))
+ {
+ if (IsHeadingRightHorz(*left_bound)) SwapActives(left_bound, right_bound);
+ }
+ else if (IsHorizontal(*right_bound))
+ {
+ if (IsHeadingLeftHorz(*right_bound)) SwapActives(left_bound, right_bound);
+ }
+ else if (left_bound->dx < right_bound->dx)
+ SwapActives(left_bound, right_bound);
+ }
+ else if (!left_bound)
+ {
+ left_bound = right_bound;
+ right_bound = nullptr;
+ }
+
+ bool contributing;
+ left_bound->is_left_bound = true;
+ InsertLeftEdge(*left_bound);
+
+ if (IsOpen(*left_bound))
+ {
+ SetWindCountForOpenPathEdge(*left_bound);
+ contributing = IsContributingOpen(*left_bound);
+ }
+ else
+ {
+ SetWindCountForClosedPathEdge(*left_bound);
+ contributing = IsContributingClosed(*left_bound);
+ }
+
+ if (right_bound)
+ {
+ right_bound->is_left_bound = false;
+ right_bound->wind_cnt = left_bound->wind_cnt;
+ right_bound->wind_cnt2 = left_bound->wind_cnt2;
+ InsertRightEdge(*left_bound, *right_bound); ///////
+ if (contributing)
+ {
+ AddLocalMinPoly(*left_bound, *right_bound, left_bound->bot, true);
+ if (!IsHorizontal(*left_bound) && TestJoinWithPrev1(*left_bound))
+ {
+ OutPt* op = AddOutPt(*left_bound->prev_in_ael, left_bound->bot);
+ AddJoin(op, left_bound->outrec->pts);
+ }
+ }
+
+ while (right_bound->next_in_ael &&
+ IsValidAelOrder(*right_bound->next_in_ael, *right_bound))
+ {
+ IntersectEdges(*right_bound, *right_bound->next_in_ael, right_bound->bot);
+ SwapPositionsInAEL(*right_bound, *right_bound->next_in_ael);
+ }
+
+ if (!IsHorizontal(*right_bound) &&
+ TestJoinWithNext1(*right_bound))
+ {
+ OutPt* op = AddOutPt(*right_bound->next_in_ael, right_bound->bot);
+ AddJoin(right_bound->outrec->pts, op);
+ }
+
+ if (IsHorizontal(*right_bound))
+ PushHorz(*right_bound);
+ else
+ InsertScanline(right_bound->top.y);
+ }
+ else if (contributing)
+ {
+ StartOpenPath(*left_bound, left_bound->bot);
+ }
+
+ if (IsHorizontal(*left_bound))
+ PushHorz(*left_bound);
+ else
+ InsertScanline(left_bound->top.y);
+ } // while (PopLocalMinima())
+ }
+
+
+ inline void ClipperBase::PushHorz(Active& e)
+ {
+ e.next_in_sel = (sel_ ? sel_ : nullptr);
+ sel_ = &e;
+ }
+
+
+ inline bool ClipperBase::PopHorz(Active*& e)
+ {
+ e = sel_;
+ if (!e) return false;
+ sel_ = sel_->next_in_sel;
+ return true;
+ }
+
+
+ OutPt* ClipperBase::AddLocalMinPoly(Active& e1, Active& e2,
+ const Point64& pt, bool is_new)
+ {
+ OutRec* outrec = new OutRec();
+ outrec->idx = (unsigned)outrec_list_.size();
+ outrec_list_.push_back(outrec);
+ outrec->pts = nullptr;
+ outrec->polypath = nullptr;
+ e1.outrec = outrec;
+ e2.outrec = outrec;
+
+ //Setting the owner and inner/outer states (above) is an essential
+ //precursor to setting edge 'sides' (ie left and right sides of output
+ //polygons) and hence the orientation of output paths ...
+
+ if (IsOpen(e1))
+ {
+ outrec->owner = nullptr;
+ outrec->is_open = true;
+ if (e1.wind_dx > 0)
+ SetSides(*outrec, e1, e2);
+ else
+ SetSides(*outrec, e2, e1);
+ }
+ else
+ {
+ Active* prevHotEdge = GetPrevHotEdge(e1);
+ //e.windDx is the winding direction of the **input** paths
+ //and unrelated to the winding direction of output polygons.
+ //Output orientation is determined by e.outrec.frontE which is
+ //the ascending edge (see AddLocalMinPoly).
+ if (prevHotEdge)
+ {
+ outrec->owner = prevHotEdge->outrec;
+ if (OutrecIsAscending(prevHotEdge) == is_new)
+ SetSides(*outrec, e2, e1);
+ else
+ SetSides(*outrec, e1, e2);
+ }
+ else
+ {
+ outrec->owner = nullptr;
+ if (is_new)
+ SetSides(*outrec, e1, e2);
+ else
+ SetSides(*outrec, e2, e1);
+ }
+ }
+
+ OutPt* op = new OutPt(pt, outrec);
+ outrec->pts = op;
+ return op;
+ }
+
+
+ OutPt* ClipperBase::AddLocalMaxPoly(Active& e1, Active& e2, const Point64& pt)
+ {
+ if (IsFront(e1) == IsFront(e2))
+ {
+ if (IsOpenEnd(e1))
+ SwapFrontBackSides(*e1.outrec);
+ else if (IsOpenEnd(e2))
+ SwapFrontBackSides(*e2.outrec);
+ else
+ {
+ succeeded_ = false;
+ return nullptr;
+ }
+ }
+
+ OutPt* result = AddOutPt(e1, pt);
+ if (e1.outrec == e2.outrec)
+ {
+ OutRec& outrec = *e1.outrec;
+ outrec.pts = result;
+
+ UncoupleOutRec(e1);
+ if (!IsOpen(e1)) CleanCollinear(&outrec);
+ result = outrec.pts;
+ if (using_polytree_ && outrec.owner && !outrec.owner->front_edge)
+ outrec.owner = GetRealOutRec(outrec.owner->owner);
+ }
+ //and to preserve the winding orientation of outrec ...
+ else if (IsOpen(e1))
+ {
+ if (e1.wind_dx < 0)
+ JoinOutrecPaths(e1, e2);
+ else
+ JoinOutrecPaths(e2, e1);
+ }
+ else if (e1.outrec->idx < e2.outrec->idx)
+ JoinOutrecPaths(e1, e2);
+ else
+ JoinOutrecPaths(e2, e1);
+
+ return result;
+ }
+
+ void ClipperBase::JoinOutrecPaths(Active& e1, Active& e2)
+ {
+ //join e2 outrec path onto e1 outrec path and then delete e2 outrec path
+ //pointers. (NB Only very rarely do the joining ends share the same coords.)
+ OutPt* p1_st = e1.outrec->pts;
+ OutPt* p2_st = e2.outrec->pts;
+ OutPt* p1_end = p1_st->next;
+ OutPt* p2_end = p2_st->next;
+ if (IsFront(e1))
+ {
+ p2_end->prev = p1_st;
+ p1_st->next = p2_end;
+ p2_st->next = p1_end;
+ p1_end->prev = p2_st;
+ e1.outrec->pts = p2_st;
+ e1.outrec->front_edge = e2.outrec->front_edge;
+ if (e1.outrec->front_edge)
+ e1.outrec->front_edge->outrec = e1.outrec;
+ }
+ else
+ {
+ p1_end->prev = p2_st;
+ p2_st->next = p1_end;
+ p1_st->next = p2_end;
+ p2_end->prev = p1_st;
+ e1.outrec->back_edge = e2.outrec->back_edge;
+ if (e1.outrec->back_edge)
+ e1.outrec->back_edge->outrec = e1.outrec;
+ }
+
+ //an owner must have a lower idx otherwise
+ //it can't be a valid owner
+ if (e2.outrec->owner && e2.outrec->owner->idx < e1.outrec->idx)
+ {
+ if (!e1.outrec->owner || e2.outrec->owner->idx < e1.outrec->owner->idx)
+ e1.outrec->owner = e2.outrec->owner;
+ }
+
+ //after joining, the e2.OutRec must contains no vertices ...
+ e2.outrec->front_edge = nullptr;
+ e2.outrec->back_edge = nullptr;
+ e2.outrec->pts = nullptr;
+ e2.outrec->owner = e1.outrec;
+
+ if (IsOpenEnd(e1))
+ {
+ e2.outrec->pts = e1.outrec->pts;
+ e1.outrec->pts = nullptr;
+ }
+
+ //and e1 and e2 are maxima and are about to be dropped from the Actives list.
+ e1.outrec = nullptr;
+ e2.outrec = nullptr;
+ }
+
+
+ OutPt* ClipperBase::AddOutPt(const Active& e, const Point64& pt)
+ {
+ OutPt* new_op = nullptr;
+
+ //Outrec.OutPts: a circular doubly-linked-list of POutPt where ...
+ //op_front[.Prev]* ~~~> op_back & op_back == op_front.Next
+ OutRec* outrec = e.outrec;
+ bool to_front = IsFront(e);
+ OutPt* op_front = outrec->pts;
+ OutPt* op_back = op_front->next;
+
+ if (to_front && (pt == op_front->pt))
+ new_op = op_front;
+ else if (!to_front && (pt == op_back->pt))
+ new_op = op_back;
+ else
+ {
+ new_op = new OutPt(pt, outrec);
+ op_back->prev = new_op;
+ new_op->prev = op_front;
+ new_op->next = op_back;
+ op_front->next = new_op;
+ if (to_front) outrec->pts = new_op;
+ }
+ return new_op;
+ }
+
+
+ bool ClipperBase::ValidateClosedPathEx(OutPt*& outpt)
+ {
+ if (IsValidClosedPath(outpt)) return true;
+ if (outpt) SafeDisposeOutPts(outpt);
+ return false;
+ }
+
+
+ void ClipperBase::CleanCollinear(OutRec* outrec)
+ {
+ outrec = GetRealOutRec(outrec);
+ if (!outrec || outrec->is_open ||
+ outrec->front_edge || !ValidateClosedPathEx(outrec->pts)) return;
+
+ OutPt* startOp = outrec->pts, * op2 = startOp;
+ for (; ; )
+ {
+ if (op2->joiner) return;
+
+ //NB if preserveCollinear == true, then only remove 180 deg. spikes
+ if ((CrossProduct(op2->prev->pt, op2->pt, op2->next->pt) == 0) &&
+ (op2->pt == op2->prev->pt ||
+ op2->pt == op2->next->pt || !PreserveCollinear ||
+ DotProduct(op2->prev->pt, op2->pt, op2->next->pt) < 0))
+ {
+
+ if (op2 == outrec->pts) outrec->pts = op2->prev;
+
+ op2 = DisposeOutPt(op2);
+ if (!ValidateClosedPathEx(op2))
+ {
+ outrec->pts = nullptr;
+ return;
+ }
+ startOp = op2;
+ continue;
+ }
+ op2 = op2->next;
+ if (op2 == startOp) break;
+ }
+ FixSelfIntersects(outrec);
+ }
+
+ void ClipperBase::DoSplitOp(OutRec* outrec, OutPt* splitOp)
+ {
+ // splitOp.prev -> splitOp &&
+ // splitOp.next -> splitOp.next.next are intersecting
+ OutPt* prevOp = splitOp->prev;
+ OutPt* nextNextOp = splitOp->next->next;
+ outrec->pts = prevOp;
+ PointD ipD;
+ GetIntersectPoint(prevOp->pt,
+ splitOp->pt, splitOp->next->pt, nextNextOp->pt, ipD);
+ Point64 ip = Point64(ipD);
+#ifdef USINGZ
+ if (zCallback_)
+ zCallback_(prevOp->pt, splitOp->pt, splitOp->next->pt, nextNextOp->pt, ip);
+#endif
+ double area1 = Area(outrec->pts);
+ double absArea1 = std::fabs(area1);
+ if (absArea1 < 2)
+ {
+ SafeDisposeOutPts(outrec->pts);
+ // outrec.pts == nil; :)
+ return;
+ }
+
+ // nb: area1 is the path's area *before* splitting, whereas area2 is
+ // the area of the triangle containing splitOp & splitOp.next.
+ // So the only way for these areas to have the same sign is if
+ // the split triangle is larger than the path containing prevOp or
+ // if there's more than one self=intersection.
+ double area2 = AreaTriangle(ip, splitOp->pt, splitOp->next->pt);
+ double absArea2 = std::fabs(area2);
+
+ // de-link splitOp and splitOp.next from the path
+ // while inserting the intersection point
+ if (ip == prevOp->pt || ip == nextNextOp->pt)
+ {
+ nextNextOp->prev = prevOp;
+ prevOp->next = nextNextOp;
+ }
+ else
+ {
+ OutPt* newOp2 = new OutPt(ip, prevOp->outrec);
+ newOp2->prev = prevOp;
+ newOp2->next = nextNextOp;
+ nextNextOp->prev = newOp2;
+ prevOp->next = newOp2;
+ }
+
+ SafeDeleteOutPtJoiners(splitOp->next);
+ SafeDeleteOutPtJoiners(splitOp);
+
+ if (absArea2 >= 1 &&
+ (absArea2 > absArea1 || (area2 > 0) == (area1 > 0)))
+ {
+ OutRec* newOutRec = new OutRec();
+ newOutRec->idx = outrec_list_.size();
+ outrec_list_.push_back(newOutRec);
+ newOutRec->owner = prevOp->outrec->owner;
+ newOutRec->polypath = nullptr;
+ splitOp->outrec = newOutRec;
+ splitOp->next->outrec = newOutRec;
+
+ OutPt* newOp = new OutPt(ip, newOutRec);
+ newOp->prev = splitOp->next;
+ newOp->next = splitOp;
+ newOutRec->pts = newOp;
+ splitOp->prev = newOp;
+ splitOp->next->next = newOp;
+ }
+ else
+ {
+ delete splitOp->next;
+ delete splitOp;
+ }
+ }
+
+ void ClipperBase::FixSelfIntersects(OutRec* outrec)
+ {
+ OutPt* op2 = outrec->pts;
+ for (; ; )
+ {
+ // triangles can't self-intersect
+ if (op2->prev == op2->next->next) break;
+ if (SegmentsIntersect(op2->prev->pt,
+ op2->pt, op2->next->pt, op2->next->next->pt))
+ {
+ if (op2 == outrec->pts || op2->next == outrec->pts)
+ outrec->pts = outrec->pts->prev;
+ DoSplitOp(outrec, op2);
+ if (!outrec->pts) break;
+ op2 = outrec->pts;
+ continue;
+ }
+ else
+ op2 = op2->next;
+
+ if (op2 == outrec->pts) break;
+ }
+ }
+
+
+ inline void UpdateOutrecOwner(OutRec* outrec)
+ {
+ OutPt* opCurr = outrec->pts;
+ for (; ; )
+ {
+ opCurr->outrec = outrec;
+ opCurr = opCurr->next;
+ if (opCurr == outrec->pts) return;
+ }
+ }
+
+
+ void ClipperBase::SafeDisposeOutPts(OutPt*& op)
+ {
+ OutRec* outrec = GetRealOutRec(op->outrec);
+ if (outrec->front_edge)
+ outrec->front_edge->outrec = nullptr;
+ if (outrec->back_edge)
+ outrec->back_edge->outrec = nullptr;
+
+ op->prev->next = nullptr;
+ while (op)
+ {
+ SafeDeleteOutPtJoiners(op);
+ OutPt* tmp = op->next;
+ delete op;
+ op = tmp;
+ }
+ outrec->pts = nullptr;
+ }
+
+
+ void ClipperBase::CompleteSplit(OutPt* op1, OutPt* op2, OutRec& outrec)
+ {
+ double area1 = Area(op1);
+ double area2 = Area(op2);
+ bool signs_change = (area1 > 0) == (area2 < 0);
+
+ if (area1 == 0 || (signs_change && std::abs(area1) < 2))
+ {
+ SafeDisposeOutPts(op1);
+ outrec.pts = op2;
+ }
+ else if (area2 == 0 || (signs_change && std::abs(area2) < 2))
+ {
+ SafeDisposeOutPts(op2);
+ outrec.pts = op1;
+ }
+ else
+ {
+ OutRec* newOr = new OutRec();
+ newOr->idx = outrec_list_.size();
+ outrec_list_.push_back(newOr);
+ newOr->polypath = nullptr;
+
+ if (using_polytree_)
+ {
+ if (!outrec.splits) outrec.splits = new OutRecList();
+ outrec.splits->push_back(newOr);
+ }
+
+ if (std::abs(area1) >= std::abs(area2))
+ {
+ outrec.pts = op1;
+ newOr->pts = op2;
+ }
+ else
+ {
+ outrec.pts = op2;
+ newOr->pts = op1;
+ }
+
+ if ((area1 > 0) == (area2 > 0))
+ newOr->owner = outrec.owner;
+ else
+ newOr->owner = &outrec;
+
+ UpdateOutrecOwner(newOr);
+ CleanCollinear(newOr);
+ }
+ }
+
+
+ OutPt* ClipperBase::StartOpenPath(Active& e, const Point64& pt)
+ {
+ OutRec* outrec = new OutRec();
+ outrec->idx = outrec_list_.size();
+ outrec_list_.push_back(outrec);
+ outrec->owner = nullptr;
+ outrec->is_open = true;
+ outrec->pts = nullptr;
+ outrec->polypath = nullptr;
+
+ if (e.wind_dx > 0)
+ {
+ outrec->front_edge = &e;
+ outrec->back_edge = nullptr;
+ }
+ else
+ {
+ outrec->front_edge = nullptr;
+ outrec->back_edge =& e;
+ }
+
+ e.outrec = outrec;
+
+ OutPt* op = new OutPt(pt, outrec);
+ outrec->pts = op;
+ return op;
+ }
+
+
+ inline void ClipperBase::UpdateEdgeIntoAEL(Active* e)
+ {
+ e->bot = e->top;
+ e->vertex_top = NextVertex(*e);
+ e->top = e->vertex_top->pt;
+ e->curr_x = e->bot.x;
+ SetDx(*e);
+ if (IsHorizontal(*e)) return;
+ InsertScanline(e->top.y);
+ if (TestJoinWithPrev1(*e))
+ {
+ OutPt* op1 = AddOutPt(*e->prev_in_ael, e->bot);
+ OutPt* op2 = AddOutPt(*e, e->bot);
+ AddJoin(op1, op2);
+ }
+ }
+
+
+ Active* FindEdgeWithMatchingLocMin(Active* e)
+ {
+ Active* result = e->next_in_ael;
+ while (result)
+ {
+ if (result->local_min == e->local_min) return result;
+ else if (!IsHorizontal(*result) && e->bot != result->bot) result = nullptr;
+ else result = result->next_in_ael;
+ }
+ result = e->prev_in_ael;
+ while (result)
+ {
+ if (result->local_min == e->local_min) return result;
+ else if (!IsHorizontal(*result) && e->bot != result->bot) return nullptr;
+ else result = result->prev_in_ael;
+ }
+ return result;
+ }
+
+
+ OutPt* ClipperBase::IntersectEdges(Active& e1, Active& e2, const Point64& pt)
+ {
+ //MANAGE OPEN PATH INTERSECTIONS SEPARATELY ...
+ if (has_open_paths_ && (IsOpen(e1) || IsOpen(e2)))
+ {
+ if (IsOpen(e1) && IsOpen(e2)) return nullptr;
+
+ Active* edge_o, * edge_c;
+ if (IsOpen(e1))
+ {
+ edge_o = &e1;
+ edge_c = &e2;
+ }
+ else
+ {
+ edge_o = &e2;
+ edge_c = &e1;
+ }
+
+ if (abs(edge_c->wind_cnt) != 1) return nullptr;
+ switch (cliptype_)
+ {
+ case ClipType::Union:
+ if (!IsHotEdge(*edge_c)) return nullptr;
+ break;
+ default:
+ if (edge_c->local_min->polytype == PathType::Subject)
+ return nullptr;
+ }
+
+ switch (fillrule_)
+ {
+ case FillRule::Positive: if (edge_c->wind_cnt != 1) return nullptr; break;
+ case FillRule::Negative: if (edge_c->wind_cnt != -1) return nullptr; break;
+ default: if (std::abs(edge_c->wind_cnt) != 1) return nullptr; break;
+ }
+
+ //toggle contribution ...
+ if (IsHotEdge(*edge_o))
+ {
+ OutPt* resultOp = AddOutPt(*edge_o, pt);
+#ifdef USINGZ
+ if (zCallback_) SetZ(e1, e2, resultOp->pt);
+#endif
+ if (IsFront(*edge_o)) edge_o->outrec->front_edge = nullptr;
+ else edge_o->outrec->back_edge = nullptr;
+ edge_o->outrec = nullptr;
+ return resultOp;
+ }
+
+ //horizontal edges can pass under open paths at a LocMins
+ else if (pt == edge_o->local_min->vertex->pt &&
+ !IsOpenEnd(*edge_o->local_min->vertex))
+ {
+ //find the other side of the LocMin and
+ //if it's 'hot' join up with it ...
+ Active* e3 = FindEdgeWithMatchingLocMin(edge_o);
+ if (e3 && IsHotEdge(*e3))
+ {
+ edge_o->outrec = e3->outrec;
+ if (edge_o->wind_dx > 0)
+ SetSides(*e3->outrec, *edge_o, *e3);
+ else
+ SetSides(*e3->outrec, *e3, *edge_o);
+ return e3->outrec->pts;
+ }
+ else
+ return StartOpenPath(*edge_o, pt);
+ }
+ else
+ return StartOpenPath(*edge_o, pt);
+ }
+
+
+ //MANAGING CLOSED PATHS FROM HERE ON
+
+ //UPDATE WINDING COUNTS...
+
+ int old_e1_windcnt, old_e2_windcnt;
+ if (e1.local_min->polytype == e2.local_min->polytype)
+ {
+ if (fillrule_ == FillRule::EvenOdd)
+ {
+ old_e1_windcnt = e1.wind_cnt;
+ e1.wind_cnt = e2.wind_cnt;
+ e2.wind_cnt = old_e1_windcnt;
+ }
+ else
+ {
+ if (e1.wind_cnt + e2.wind_dx == 0)
+ e1.wind_cnt = -e1.wind_cnt;
+ else
+ e1.wind_cnt += e2.wind_dx;
+ if (e2.wind_cnt - e1.wind_dx == 0)
+ e2.wind_cnt = -e2.wind_cnt;
+ else
+ e2.wind_cnt -= e1.wind_dx;
+ }
+ }
+ else
+ {
+ if (fillrule_ != FillRule::EvenOdd)
+ {
+ e1.wind_cnt2 += e2.wind_dx;
+ e2.wind_cnt2 -= e1.wind_dx;
+ }
+ else
+ {
+ e1.wind_cnt2 = (e1.wind_cnt2 == 0 ? 1 : 0);
+ e2.wind_cnt2 = (e2.wind_cnt2 == 0 ? 1 : 0);
+ }
+ }
+
+ switch (fillrule_)
+ {
+ case FillRule::EvenOdd:
+ case FillRule::NonZero:
+ old_e1_windcnt = abs(e1.wind_cnt);
+ old_e2_windcnt = abs(e2.wind_cnt);
+ break;
+ default:
+ if (fillrule_ == fillpos)
+ {
+ old_e1_windcnt = e1.wind_cnt;
+ old_e2_windcnt = e2.wind_cnt;
+ }
+ else
+ {
+ old_e1_windcnt = -e1.wind_cnt;
+ old_e2_windcnt = -e2.wind_cnt;
+ }
+ break;
+ }
+
+ const bool e1_windcnt_in_01 = old_e1_windcnt == 0 || old_e1_windcnt == 1;
+ const bool e2_windcnt_in_01 = old_e2_windcnt == 0 || old_e2_windcnt == 1;
+
+ if ((!IsHotEdge(e1) && !e1_windcnt_in_01) || (!IsHotEdge(e2) && !e2_windcnt_in_01))
+ {
+ return nullptr;
+ }
+
+ //NOW PROCESS THE INTERSECTION ...
+ OutPt* resultOp = nullptr;
+ //if both edges are 'hot' ...
+ if (IsHotEdge(e1) && IsHotEdge(e2))
+ {
+ if ((old_e1_windcnt != 0 && old_e1_windcnt != 1) || (old_e2_windcnt != 0 && old_e2_windcnt != 1) ||
+ (e1.local_min->polytype != e2.local_min->polytype && cliptype_ != ClipType::Xor))
+ {
+ resultOp = AddLocalMaxPoly(e1, e2, pt);
+#ifdef USINGZ
+ if (zCallback_ && resultOp) SetZ(e1, e2, resultOp->pt);
+#endif
+ }
+ else if (IsFront(e1) || (e1.outrec == e2.outrec))
+ {
+ //this 'else if' condition isn't strictly needed but
+ //it's sensible to split polygons that ony touch at
+ //a common vertex (not at common edges).
+
+ resultOp = AddLocalMaxPoly(e1, e2, pt);
+ OutPt* op2 = AddLocalMinPoly(e1, e2, pt);
+#ifdef USINGZ
+ if (zCallback_ && resultOp) SetZ(e1, e2, resultOp->pt);
+ if (zCallback_) SetZ(e1, e2, op2->pt);
+#endif
+ if (resultOp && resultOp->pt == op2->pt &&
+ !IsHorizontal(e1) && !IsHorizontal(e2) &&
+ (CrossProduct(e1.bot, resultOp->pt, e2.bot) == 0))
+ AddJoin(resultOp, op2);
+ }
+ else
+ {
+ resultOp = AddOutPt(e1, pt);
+#ifdef USINGZ
+ OutPt* op2 = AddOutPt(e2, pt);
+ if (zCallback_)
+ {
+ SetZ(e1, e2, resultOp->pt);
+ SetZ(e1, e2, op2->pt);
+ }
+#else
+ AddOutPt(e2, pt);
+#endif
+ SwapOutrecs(e1, e2);
+ }
+ }
+ else if (IsHotEdge(e1))
+ {
+ resultOp = AddOutPt(e1, pt);
+#ifdef USINGZ
+ if (zCallback_) SetZ(e1, e2, resultOp->pt);
+#endif
+ SwapOutrecs(e1, e2);
+ }
+ else if (IsHotEdge(e2))
+ {
+ resultOp = AddOutPt(e2, pt);
+#ifdef USINGZ
+ if (zCallback_) SetZ(e1, e2, resultOp->pt);
+#endif
+ SwapOutrecs(e1, e2);
+ }
+ else
+ {
+ int64_t e1Wc2, e2Wc2;
+ switch (fillrule_)
+ {
+ case FillRule::EvenOdd:
+ case FillRule::NonZero:
+ e1Wc2 = abs(e1.wind_cnt2);
+ e2Wc2 = abs(e2.wind_cnt2);
+ break;
+ default:
+ if (fillrule_ == fillpos)
+ {
+ e1Wc2 = e1.wind_cnt2;
+ e2Wc2 = e2.wind_cnt2;
+ }
+ else
+ {
+ e1Wc2 = -e1.wind_cnt2;
+ e2Wc2 = -e2.wind_cnt2;
+ }
+ break;
+ }
+
+ if (!IsSamePolyType(e1, e2))
+ {
+ resultOp = AddLocalMinPoly(e1, e2, pt, false);
+#ifdef USINGZ
+ if (zCallback_) SetZ(e1, e2, resultOp->pt);
+#endif
+ }
+ else if (old_e1_windcnt == 1 && old_e2_windcnt == 1)
+ {
+ resultOp = nullptr;
+ switch (cliptype_)
+ {
+ case ClipType::Union:
+ if (e1Wc2 <= 0 && e2Wc2 <= 0)
+ resultOp = AddLocalMinPoly(e1, e2, pt, false);
+ break;
+ case ClipType::Difference:
+ if (((GetPolyType(e1) == PathType::Clip) && (e1Wc2 > 0) && (e2Wc2 > 0)) ||
+ ((GetPolyType(e1) == PathType::Subject) && (e1Wc2 <= 0) && (e2Wc2 <= 0)))
+ {
+ resultOp = AddLocalMinPoly(e1, e2, pt, false);
+ }
+ break;
+ case ClipType::Xor:
+ resultOp = AddLocalMinPoly(e1, e2, pt, false);
+ break;
+ default:
+ if (e1Wc2 > 0 && e2Wc2 > 0)
+ resultOp = AddLocalMinPoly(e1, e2, pt, false);
+ break;
+ }
+#ifdef USINGZ
+ if (resultOp && zCallback_) SetZ(e1, e2, resultOp->pt);
+#endif
+ }
+ }
+ return resultOp;
+ }
+
+
+ inline void ClipperBase::DeleteFromAEL(Active& e)
+ {
+ Active* prev = e.prev_in_ael;
+ Active* next = e.next_in_ael;
+ if (!prev && !next && (&e != actives_)) return; // already deleted
+ if (prev)
+ prev->next_in_ael = next;
+ else
+ actives_ = next;
+ if (next) next->prev_in_ael = prev;
+ delete& e;
+ }
+
+
+ inline void ClipperBase::AdjustCurrXAndCopyToSEL(const int64_t top_y)
+ {
+ Active* e = actives_;
+ sel_ = e;
+ while (e)
+ {
+ e->prev_in_sel = e->prev_in_ael;
+ e->next_in_sel = e->next_in_ael;
+ e->jump = e->next_in_sel;
+ e->curr_x = TopX(*e, top_y);
+ e = e->next_in_ael;
+ }
+ }
+
+
+ bool ClipperBase::ExecuteInternal(ClipType ct, FillRule fillrule, bool use_polytrees)
+ {
+ cliptype_ = ct;
+ fillrule_ = fillrule;
+ using_polytree_ = use_polytrees;
+ Reset();
+ int64_t y;
+ if (ct == ClipType::None || !PopScanline(y)) return true;
+
+ while (succeeded_)
+ {
+ InsertLocalMinimaIntoAEL(y);
+ Active* e;
+ while (PopHorz(e)) DoHorizontal(*e);
+ if (horz_joiners_) ConvertHorzTrialsToJoins();
+ bot_y_ = y; // bot_y_ == bottom of scanbeam
+ if (!PopScanline(y)) break; // y new top of scanbeam
+ DoIntersections(y);
+ DoTopOfScanbeam(y);
+ while (PopHorz(e)) DoHorizontal(*e);
+ }
+ ProcessJoinerList();
+ return succeeded_;
+ }
+
+ void ClipperBase::DoIntersections(const int64_t top_y)
+ {
+ if (BuildIntersectList(top_y))
+ {
+ ProcessIntersectList();
+ intersect_nodes_.clear();
+ }
+ }
+
+ void ClipperBase::AddNewIntersectNode(Active& e1, Active& e2, int64_t top_y)
+ {
+ Point64 pt = GetIntersectPoint(e1, e2);
+
+ //rounding errors can occasionally place the calculated intersection
+ //point either below or above the scanbeam, so check and correct ...
+ if (pt.y > bot_y_)
+ {
+ //e.curr.y is still the bottom of scanbeam
+ pt.y = bot_y_;
+ //use the more vertical of the 2 edges to derive pt.x ...
+ if (abs(e1.dx) < abs(e2.dx))
+ pt.x = TopX(e1, bot_y_);
+ else
+ pt.x = TopX(e2, bot_y_);
+ }
+ else if (pt.y < top_y)
+ {
+ //top_y is at the top of the scanbeam
+ pt.y = top_y;
+ if (e1.top.y == top_y)
+ pt.x = e1.top.x;
+ else if (e2.top.y == top_y)
+ pt.x = e2.top.x;
+ else if (abs(e1.dx) < abs(e2.dx))
+ pt.x = e1.curr_x;
+ else
+ pt.x = e2.curr_x;
+ }
+
+ intersect_nodes_.push_back(IntersectNode(&e1, &e2, pt));
+ }
+
+
+ bool ClipperBase::BuildIntersectList(const int64_t top_y)
+ {
+ if (!actives_ || !actives_->next_in_ael) return false;
+
+ //Calculate edge positions at the top of the current scanbeam, and from this
+ //we will determine the intersections required to reach these new positions.
+ AdjustCurrXAndCopyToSEL(top_y);
+ //Find all edge intersections in the current scanbeam using a stable merge
+ //sort that ensures only adjacent edges are intersecting. Intersect info is
+ //stored in FIntersectList ready to be processed in ProcessIntersectList.
+ //Re merge sorts see https://stackoverflow.com/a/46319131/359538
+
+ Active* left = sel_, * right, * l_end, * r_end, * curr_base, * tmp;
+
+ while (left && left->jump)
+ {
+ Active* prev_base = nullptr;
+ while (left && left->jump)
+ {
+ curr_base = left;
+ right = left->jump;
+ l_end = right;
+ r_end = right->jump;
+ left->jump = r_end;
+ while (left != l_end && right != r_end)
+ {
+ if (right->curr_x < left->curr_x)
+ {
+ tmp = right->prev_in_sel;
+ for (; ; )
+ {
+ AddNewIntersectNode(*tmp, *right, top_y);
+ if (tmp == left) break;
+ tmp = tmp->prev_in_sel;
+ }
+
+ tmp = right;
+ right = ExtractFromSEL(tmp);
+ l_end = right;
+ Insert1Before2InSEL(tmp, left);
+ if (left == curr_base)
+ {
+ curr_base = tmp;
+ curr_base->jump = r_end;
+ if (!prev_base) sel_ = curr_base;
+ else prev_base->jump = curr_base;
+ }
+ }
+ else left = left->next_in_sel;
+ }
+ prev_base = curr_base;
+ left = r_end;
+ }
+ left = sel_;
+ }
+ return intersect_nodes_.size() > 0;
+ }
+
+ void ClipperBase::ProcessIntersectList()
+ {
+ //We now have a list of intersections required so that edges will be
+ //correctly positioned at the top of the scanbeam. However, it's important
+ //that edge intersections are processed from the bottom up, but it's also
+ //crucial that intersections only occur between adjacent edges.
+
+ //First we do a quicksort so intersections proceed in a bottom up order ...
+ std::sort(intersect_nodes_.begin(), intersect_nodes_.end(), IntersectListSort);
+ //Now as we process these intersections, we must sometimes adjust the order
+ //to ensure that intersecting edges are always adjacent ...
+
+ std::vector<IntersectNode>::iterator node_iter, node_iter2;
+ for (node_iter = intersect_nodes_.begin();
+ node_iter != intersect_nodes_.end(); ++node_iter)
+ {
+ if (!EdgesAdjacentInAEL(*node_iter))
+ {
+ node_iter2 = node_iter + 1;
+ while (!EdgesAdjacentInAEL(*node_iter2)) ++node_iter2;
+ std::swap(*node_iter, *node_iter2);
+ }
+
+ IntersectNode& node = *node_iter;
+ IntersectEdges(*node.edge1, *node.edge2, node.pt);
+ SwapPositionsInAEL(*node.edge1, *node.edge2);
+
+ if (TestJoinWithPrev2(*node.edge2, node.pt))
+ {
+ OutPt* op1 = AddOutPt(*node.edge2->prev_in_ael, node.pt);
+ OutPt* op2 = AddOutPt(*node.edge2, node.pt);
+ if (op1 != op2) AddJoin(op1, op2);
+ }
+ else if (TestJoinWithNext2(*node.edge1, node.pt))
+ {
+ OutPt* op1 = AddOutPt(*node.edge1, node.pt);
+ OutPt* op2 = AddOutPt(*node.edge1->next_in_ael, node.pt);
+ if (op1 != op2) AddJoin(op1, op2);
+ }
+ }
+ }
+
+
+ void ClipperBase::SwapPositionsInAEL(Active& e1, Active& e2)
+ {
+ //preconditon: e1 must be immediately to the left of e2
+ Active* next = e2.next_in_ael;
+ if (next) next->prev_in_ael = &e1;
+ Active* prev = e1.prev_in_ael;
+ if (prev) prev->next_in_ael = &e2;
+ e2.prev_in_ael = prev;
+ e2.next_in_ael = &e1;
+ e1.prev_in_ael = &e2;
+ e1.next_in_ael = next;
+ if (!e2.prev_in_ael) actives_ = &e2;
+ }
+
+
+ bool ClipperBase::ResetHorzDirection(const Active& horz,
+ const Active* max_pair, int64_t& horz_left, int64_t& horz_right)
+ {
+ if (horz.bot.x == horz.top.x)
+ {
+ //the horizontal edge is going nowhere ...
+ horz_left = horz.curr_x;
+ horz_right = horz.curr_x;
+ Active* e = horz.next_in_ael;
+ while (e && e != max_pair) e = e->next_in_ael;
+ return e != nullptr;
+ }
+ else if (horz.curr_x < horz.top.x)
+ {
+ horz_left = horz.curr_x;
+ horz_right = horz.top.x;
+ return true;
+ }
+ else
+ {
+ horz_left = horz.top.x;
+ horz_right = horz.curr_x;
+ return false; // right to left
+ }
+ }
+
+ inline bool HorzIsSpike(const Active& horzEdge)
+ {
+ Point64 nextPt = NextVertex(horzEdge)->pt;
+ return (nextPt.y == horzEdge.bot.y) &&
+ (horzEdge.bot.x < horzEdge.top.x) != (horzEdge.top.x < nextPt.x);
+ }
+
+ inline void TrimHorz(Active& horzEdge, bool preserveCollinear)
+ {
+ bool wasTrimmed = false;
+ Point64 pt = NextVertex(horzEdge)->pt;
+ while (pt.y == horzEdge.top.y)
+ {
+ //always trim 180 deg. spikes (in closed paths)
+ //but otherwise break if preserveCollinear = true
+ if (preserveCollinear &&
+ ((pt.x < horzEdge.top.x) != (horzEdge.bot.x < horzEdge.top.x)))
+ break;
+
+ horzEdge.vertex_top = NextVertex(horzEdge);
+ horzEdge.top = pt;
+ wasTrimmed = true;
+ if (IsMaxima(horzEdge)) break;
+ pt = NextVertex(horzEdge)->pt;
+ }
+
+ if (wasTrimmed) SetDx(horzEdge); // +/-infinity
+ }
+
+
+ void ClipperBase::DoHorizontal(Active& horz)
+ /*******************************************************************************
+ * Notes: Horizontal edges (HEs) at scanline intersections (ie at the top or *
+ * bottom of a scanbeam) are processed as if layered.The order in which HEs *
+ * are processed doesn't matter. HEs intersect with the bottom vertices of *
+ * other HEs[#] and with non-horizontal edges [*]. Once these intersections *
+ * are completed, intermediate HEs are 'promoted' to the next edge in their *
+ * bounds, and they in turn may be intersected[%] by other HEs. *
+ * *
+ * eg: 3 horizontals at a scanline: / | / / *
+ * | / | (HE3)o ========%========== o *
+ * o ======= o(HE2) / | / / *
+ * o ============#=========*======*========#=========o (HE1) *
+ * / | / | / *
+ *******************************************************************************/
+ {
+ Point64 pt;
+ bool horzIsOpen = IsOpen(horz);
+ int64_t y = horz.bot.y;
+ Vertex* vertex_max = nullptr;
+ Active* max_pair = nullptr;
+
+ if (!horzIsOpen)
+ {
+ vertex_max = GetCurrYMaximaVertex(horz);
+ if (vertex_max)
+ {
+ max_pair = GetHorzMaximaPair(horz, vertex_max);
+ //remove 180 deg.spikes and also simplify
+ //consecutive horizontals when PreserveCollinear = true
+ if (vertex_max != horz.vertex_top)
+ TrimHorz(horz, PreserveCollinear);
+ }
+ }
+
+ int64_t horz_left, horz_right;
+ bool is_left_to_right =
+ ResetHorzDirection(horz, max_pair, horz_left, horz_right);
+
+ if (IsHotEdge(horz))
+ AddOutPt(horz, Point64(horz.curr_x, y));
+
+ OutPt* op;
+ while (true) // loop through consec. horizontal edges
+ {
+ if (horzIsOpen && IsMaxima(horz) && !IsOpenEnd(horz))
+ {
+ vertex_max = GetCurrYMaximaVertex(horz);
+ if (vertex_max)
+ max_pair = GetHorzMaximaPair(horz, vertex_max);
+ }
+
+ Active* e;
+ if (is_left_to_right) e = horz.next_in_ael;
+ else e = horz.prev_in_ael;
+
+ while (e)
+ {
+
+ if (e == max_pair)
+ {
+ if (IsHotEdge(horz))
+ {
+ while (horz.vertex_top != e->vertex_top)
+ {
+ AddOutPt(horz, horz.top);
+ UpdateEdgeIntoAEL(&horz);
+ }
+ op = AddLocalMaxPoly(horz, *e, horz.top);
+ if (op && !IsOpen(horz) && op->pt == horz.top)
+ AddTrialHorzJoin(op);
+ }
+ DeleteFromAEL(*e);
+ DeleteFromAEL(horz);
+ return;
+ }
+
+ //if horzEdge is a maxima, keep going until we reach
+ //its maxima pair, otherwise check for break conditions
+ if (vertex_max != horz.vertex_top || IsOpenEnd(horz))
+ {
+ //otherwise stop when 'ae' is beyond the end of the horizontal line
+ if ((is_left_to_right && e->curr_x > horz_right) ||
+ (!is_left_to_right && e->curr_x < horz_left)) break;
+
+ if (e->curr_x == horz.top.x && !IsHorizontal(*e))
+ {
+ pt = NextVertex(horz)->pt;
+ if (is_left_to_right)
+ {
+ //with open paths we'll only break once past horz's end
+ if (IsOpen(*e) && !IsSamePolyType(*e, horz) && !IsHotEdge(*e))
+ {
+ if (TopX(*e, pt.y) > pt.x) break;
+ }
+ //otherwise we'll only break when horz's outslope is greater than e's
+ else if (TopX(*e, pt.y) >= pt.x) break;
+ }
+ else
+ {
+ if (IsOpen(*e) && !IsSamePolyType(*e, horz) && !IsHotEdge(*e))
+ {
+ if (TopX(*e, pt.y) < pt.x) break;
+ }
+ else if (TopX(*e, pt.y) <= pt.x) break;
+ }
+ }
+ }
+
+ pt = Point64(e->curr_x, horz.bot.y);
+
+ if (is_left_to_right)
+ {
+ op = IntersectEdges(horz, *e, pt);
+ SwapPositionsInAEL(horz, *e);
+ // todo: check if op->pt == pt test is still needed
+ // expect op != pt only after AddLocalMaxPoly when horz.outrec == nullptr
+ if (IsHotEdge(horz) && op && !IsOpen(horz) && op->pt == pt)
+ AddTrialHorzJoin(op);
+
+ if (!IsHorizontal(*e) && TestJoinWithPrev1(*e))
+ {
+ op = AddOutPt(*e->prev_in_ael, pt);
+ OutPt* op2 = AddOutPt(*e, pt);
+ AddJoin(op, op2);
+ }
+
+ horz.curr_x = e->curr_x;
+ e = horz.next_in_ael;
+ }
+ else
+ {
+ op = IntersectEdges(*e, horz, pt);
+ SwapPositionsInAEL(*e, horz);
+
+ if (IsHotEdge(horz) && op &&
+ !IsOpen(horz) && op->pt == pt)
+ AddTrialHorzJoin(op);
+
+ if (!IsHorizontal(*e) && TestJoinWithNext1(*e))
+ {
+ op = AddOutPt(*e, pt);
+ OutPt* op2 = AddOutPt(*e->next_in_ael, pt);
+ AddJoin(op, op2);
+ }
+
+ horz.curr_x = e->curr_x;
+ e = horz.prev_in_ael;
+ }
+ }
+
+ //check if we've finished with (consecutive) horizontals ...
+ if (horzIsOpen && IsOpenEnd(horz)) // ie open at top
+ {
+ if (IsHotEdge(horz))
+ {
+ AddOutPt(horz, horz.top);
+ if (IsFront(horz))
+ horz.outrec->front_edge = nullptr;
+ else
+ horz.outrec->back_edge = nullptr;
+ horz.outrec = nullptr;
+ }
+ DeleteFromAEL(horz);
+ return;
+ }
+ else if (NextVertex(horz)->pt.y != horz.top.y)
+ break;
+
+ //still more horizontals in bound to process ...
+ if (IsHotEdge(horz))
+ AddOutPt(horz, horz.top);
+ UpdateEdgeIntoAEL(&horz);
+
+ if (PreserveCollinear && !horzIsOpen && HorzIsSpike(horz))
+ TrimHorz(horz, true);
+
+ is_left_to_right =
+ ResetHorzDirection(horz, max_pair, horz_left, horz_right);
+ }
+
+ if (IsHotEdge(horz))
+ {
+ op = AddOutPt(horz, horz.top);
+ if (!IsOpen(horz))
+ AddTrialHorzJoin(op);
+ }
+ else
+ op = nullptr;
+
+ if ((horzIsOpen && !IsOpenEnd(horz)) ||
+ (!horzIsOpen && vertex_max != horz.vertex_top))
+ {
+ UpdateEdgeIntoAEL(&horz); // this is the end of an intermediate horiz.
+ if (IsOpen(horz)) return;
+
+ if (is_left_to_right && TestJoinWithNext1(horz))
+ {
+ OutPt* op2 = AddOutPt(*horz.next_in_ael, horz.bot);
+ AddJoin(op, op2);
+ }
+ else if (!is_left_to_right && TestJoinWithPrev1(horz))
+ {
+ OutPt* op2 = AddOutPt(*horz.prev_in_ael, horz.bot);
+ AddJoin(op2, op);
+ }
+ }
+ else if (IsHotEdge(horz))
+ AddLocalMaxPoly(horz, *max_pair, horz.top);
+ else
+ {
+ DeleteFromAEL(*max_pair);
+ DeleteFromAEL(horz);
+ }
+ }
+
+
+ void ClipperBase::DoTopOfScanbeam(const int64_t y)
+ {
+ sel_ = nullptr; // sel_ is reused to flag horizontals (see PushHorz below)
+ Active* e = actives_;
+ while (e)
+ {
+ //nb: 'e' will never be horizontal here
+ if (e->top.y == y)
+ {
+ e->curr_x = e->top.x;
+ if (IsMaxima(*e))
+ {
+ e = DoMaxima(*e); // TOP OF BOUND (MAXIMA)
+ continue;
+ }
+ else
+ {
+ //INTERMEDIATE VERTEX ...
+ if (IsHotEdge(*e)) AddOutPt(*e, e->top);
+ UpdateEdgeIntoAEL(e);
+ if (IsHorizontal(*e))
+ PushHorz(*e); // horizontals are processed later
+ }
+ }
+ else // i.e. not the top of the edge
+ e->curr_x = TopX(*e, y);
+
+ e = e->next_in_ael;
+ }
+ }
+
+
+ Active* ClipperBase::DoMaxima(Active& e)
+ {
+ Active* next_e, * prev_e, * max_pair;
+ prev_e = e.prev_in_ael;
+ next_e = e.next_in_ael;
+ if (IsOpenEnd(e))
+ {
+ if (IsHotEdge(e)) AddOutPt(e, e.top);
+ if (!IsHorizontal(e))
+ {
+ if (IsHotEdge(e))
+ {
+ if (IsFront(e))
+ e.outrec->front_edge = nullptr;
+ else
+ e.outrec->back_edge = nullptr;
+ e.outrec = nullptr;
+ }
+ DeleteFromAEL(e);
+ }
+ return next_e;
+ }
+ else
+ {
+ max_pair = GetMaximaPair(e);
+ if (!max_pair) return next_e; // eMaxPair is horizontal
+ }
+
+ //only non-horizontal maxima here.
+ //process any edges between maxima pair ...
+ while (next_e != max_pair)
+ {
+ IntersectEdges(e, *next_e, e.top);
+ SwapPositionsInAEL(e, *next_e);
+ next_e = e.next_in_ael;
+ }
+
+ if (IsOpen(e))
+ {
+ if (IsHotEdge(e))
+ AddLocalMaxPoly(e, *max_pair, e.top);
+ DeleteFromAEL(*max_pair);
+ DeleteFromAEL(e);
+ return (prev_e ? prev_e->next_in_ael : actives_);
+ }
+
+ //here E.next_in_ael == ENext == EMaxPair ...
+ if (IsHotEdge(e))
+ AddLocalMaxPoly(e, *max_pair, e.top);
+
+ DeleteFromAEL(e);
+ DeleteFromAEL(*max_pair);
+ return (prev_e ? prev_e->next_in_ael : actives_);
+ }
+
+
+ void ClipperBase::SafeDeleteOutPtJoiners(OutPt* op)
+ {
+ Joiner* joiner = op->joiner;
+ if (!joiner) return;
+
+ while (joiner)
+ {
+ if (joiner->idx < 0)
+ DeleteTrialHorzJoin(op);
+ else if (horz_joiners_)
+ {
+ if (OutPtInTrialHorzList(joiner->op1))
+ DeleteTrialHorzJoin(joiner->op1);
+ if (OutPtInTrialHorzList(joiner->op2))
+ DeleteTrialHorzJoin(joiner->op2);
+ DeleteJoin(joiner);
+ }
+ else
+ DeleteJoin(joiner);
+ joiner = op->joiner;
+ }
+ }
+
+
+ Joiner* ClipperBase::GetHorzTrialParent(const OutPt* op)
+ {
+ Joiner* joiner = op->joiner;
+ while (joiner)
+ {
+ if (joiner->op1 == op)
+ {
+ if (joiner->next1 && joiner->next1->idx < 0) return joiner;
+ else joiner = joiner->next1;
+ }
+ else
+ {
+ if (joiner->next2 && joiner->next2->idx < 0) return joiner;
+ else joiner = joiner->next1;
+ }
+ }
+ return joiner;
+ }
+
+
+ bool ClipperBase::OutPtInTrialHorzList(OutPt* op)
+ {
+ return op->joiner && ((op->joiner->idx < 0) || GetHorzTrialParent(op));
+ }
+
+
+ void ClipperBase::AddTrialHorzJoin(OutPt* op)
+ {
+ //make sure 'op' isn't added more than once
+ if (!op->outrec->is_open && !OutPtInTrialHorzList(op))
+ horz_joiners_ = new Joiner(op, nullptr, horz_joiners_);
+ }
+
+
+ Joiner* FindTrialJoinParent(Joiner*& joiner, const OutPt* op)
+ {
+ Joiner* parent = joiner;
+ while (parent)
+ {
+ if (op == parent->op1)
+ {
+ if (parent->next1 && parent->next1->idx < 0)
+ {
+ joiner = parent->next1;
+ return parent;
+ }
+ parent = parent->next1;
+ }
+ else
+ {
+ if (parent->next2 && parent->next2->idx < 0)
+ {
+ joiner = parent->next2;
+ return parent;
+ }
+ parent = parent->next2;
+ }
+ }
+ return nullptr;
+ }
+
+
+ void ClipperBase::DeleteTrialHorzJoin(OutPt* op)
+ {
+ if (!horz_joiners_) return;
+
+ Joiner* joiner = op->joiner;
+ Joiner* parentH, * parentOp = nullptr;
+ while (joiner)
+ {
+ if (joiner->idx < 0)
+ {
+ //first remove joiner from FHorzTrials
+ if (joiner == horz_joiners_)
+ horz_joiners_ = joiner->nextH;
+ else
+ {
+ parentH = horz_joiners_;
+ while (parentH->nextH != joiner)
+ parentH = parentH->nextH;
+ parentH->nextH = joiner->nextH;
+ }
+
+ //now remove joiner from op's joiner list
+ if (!parentOp)
+ {
+ //joiner must be first one in list
+ op->joiner = joiner->next1;
+ delete joiner;
+ joiner = op->joiner;
+ }
+ else
+ {
+ //the trial joiner isn't first
+ if (op == parentOp->op1)
+ parentOp->next1 = joiner->next1;
+ else
+ parentOp->next2 = joiner->next1;
+ delete joiner;
+ joiner = parentOp;
+ }
+ }
+ else
+ {
+ //not a trial join so look further along the linked list
+ parentOp = FindTrialJoinParent(joiner, op);
+ if (!parentOp) break;
+ }
+ //loop in case there's more than one trial join
+ }
+ }
+
+
+ inline bool GetHorzExtendedHorzSeg(OutPt*& op, OutPt*& op2)
+ {
+ OutRec* outrec = GetRealOutRec(op->outrec);
+ op2 = op;
+ if (outrec->front_edge)
+ {
+ while (op->prev != outrec->pts &&
+ op->prev->pt.y == op->pt.y) op = op->prev;
+ while (op2 != outrec->pts &&
+ op2->next->pt.y == op2->pt.y) op2 = op2->next;
+ return op2 != op;
+ }
+ else
+ {
+ while (op->prev != op2 && op->prev->pt.y == op->pt.y)
+ op = op->prev;
+ while (op2->next != op && op2->next->pt.y == op2->pt.y)
+ op2 = op2->next;
+ return op2 != op && op2->next != op;
+ }
+ }
+
+
+ inline bool HorzEdgesOverlap(int64_t x1a, int64_t x1b, int64_t x2a, int64_t x2b)
+ {
+ const int64_t minOverlap = 2;
+ if (x1a > x1b + minOverlap)
+ {
+ if (x2a > x2b + minOverlap)
+ return !((x1a <= x2b) || (x2a <= x1b));
+ else
+ return !((x1a <= x2a) || (x2b <= x1b));
+ }
+ else if (x1b > x1a + minOverlap)
+ {
+ if (x2a > x2b + minOverlap)
+ return !((x1b <= x2b) || (x2a <= x1a));
+ else
+ return !((x1b <= x2a) || (x2b <= x1a));
+ }
+ else
+ return false;
+ }
+
+
+ inline bool ValueBetween(int64_t val, int64_t end1, int64_t end2)
+ {
+ //NB accommodates axis aligned between where end1 == end2
+ return ((val != end1) == (val != end2)) &&
+ ((val > end1) == (val < end2));
+ }
+
+
+ inline bool ValueEqualOrBetween(int64_t val, int64_t end1, int64_t end2)
+ {
+ return (val == end1) || (val == end2) || ((val > end1) == (val < end2));
+ }
+
+
+ inline bool PointBetween(Point64 pt, Point64 corner1, Point64 corner2)
+ {
+ //NB points may not be collinear
+ return ValueBetween(pt.x, corner1.x, corner2.x) &&
+ ValueBetween(pt.y, corner1.y, corner2.y);
+ }
+
+ inline bool PointEqualOrBetween(Point64 pt, Point64 corner1, Point64 corner2)
+ {
+ //NB points may not be collinear
+ return ValueEqualOrBetween(pt.x, corner1.x, corner2.x) &&
+ ValueEqualOrBetween(pt.y, corner1.y, corner2.y);
+ }
+
+
+ Joiner* FindJoinParent(const Joiner* joiner, OutPt* op)
+ {
+ Joiner* result = op->joiner;
+ for (; ; )
+ {
+ if (op == result->op1)
+ {
+ if (result->next1 == joiner) return result;
+ else result = result->next1;
+ }
+ else
+ {
+ if (result->next2 == joiner) return result;
+ else result = result->next2;
+ }
+ }
+ }
+
+
+ void ClipperBase::ConvertHorzTrialsToJoins()
+ {
+ while (horz_joiners_)
+ {
+ Joiner* joiner = horz_joiners_;
+ horz_joiners_ = horz_joiners_->nextH;
+ OutPt* op1a = joiner->op1;
+ if (op1a->joiner == joiner)
+ {
+ op1a->joiner = joiner->next1;
+ }
+ else
+ {
+ Joiner* joinerParent = FindJoinParent(joiner, op1a);
+ if (joinerParent->op1 == op1a)
+ joinerParent->next1 = joiner->next1;
+ else
+ joinerParent->next2 = joiner->next1;
+ }
+ delete joiner;
+
+ OutPt* op1b;
+ if (!GetHorzExtendedHorzSeg(op1a, op1b))
+ {
+ CleanCollinear(op1a->outrec);
+ continue;
+ }
+
+ bool joined = false;
+ joiner = horz_joiners_;
+ while (joiner)
+ {
+ OutPt* op2a = joiner->op1, * op2b;
+ if (GetHorzExtendedHorzSeg(op2a, op2b) &&
+ HorzEdgesOverlap(op1a->pt.x, op1b->pt.x, op2a->pt.x, op2b->pt.x))
+ {
+ //overlap found so promote to a 'real' join
+ joined = true;
+ if (op1a->pt == op2b->pt)
+ AddJoin(op1a, op2b);
+ else if (op1b->pt == op2a->pt)
+ AddJoin(op1b, op2a);
+ else if (op1a->pt == op2a->pt)
+ AddJoin(op1a, op2a);
+ else if (op1b->pt == op2b->pt)
+ AddJoin(op1b, op2b);
+ else if (ValueBetween(op1a->pt.x, op2a->pt.x, op2b->pt.x))
+ AddJoin(op1a, InsertOp(op1a->pt, op2a));
+ else if (ValueBetween(op1b->pt.x, op2a->pt.x, op2b->pt.x))
+ AddJoin(op1b, InsertOp(op1b->pt, op2a));
+ else if (ValueBetween(op2a->pt.x, op1a->pt.x, op1b->pt.x))
+ AddJoin(op2a, InsertOp(op2a->pt, op1a));
+ else if (ValueBetween(op2b->pt.x, op1a->pt.x, op1b->pt.x))
+ AddJoin(op2b, InsertOp(op2b->pt, op1a));
+ break;
+ }
+ joiner = joiner->nextH;
+ }
+ if (!joined)
+ CleanCollinear(op1a->outrec);
+ }
+ }
+
+
+ void ClipperBase::AddJoin(OutPt* op1, OutPt* op2)
+ {
+ if ((op1->outrec == op2->outrec) && ((op1 == op2) ||
+ //unless op1.next or op1.prev crosses the start-end divide
+ //don't waste time trying to join adjacent vertices
+ ((op1->next == op2) && (op1 != op1->outrec->pts)) ||
+ ((op2->next == op1) && (op2 != op1->outrec->pts)))) return;
+
+ Joiner* j = new Joiner(op1, op2, nullptr);
+ j->idx = static_cast<int>(joiner_list_.size());
+ joiner_list_.push_back(j);
+ }
+
+
+ void ClipperBase::DeleteJoin(Joiner* joiner)
+ {
+ //This method deletes a single join, and it doesn't check for or
+ //delete trial horz. joins. For that, use the following method.
+ OutPt* op1 = joiner->op1, * op2 = joiner->op2;
+
+ Joiner* parent_joiner;
+ if (op1->joiner != joiner)
+ {
+ parent_joiner = FindJoinParent(joiner, op1);
+ if (parent_joiner->op1 == op1)
+ parent_joiner->next1 = joiner->next1;
+ else
+ parent_joiner->next2 = joiner->next1;
+ }
+ else
+ op1->joiner = joiner->next1;
+
+ if (op2->joiner != joiner)
+ {
+ parent_joiner = FindJoinParent(joiner, op2);
+ if (parent_joiner->op1 == op2)
+ parent_joiner->next1 = joiner->next2;
+ else
+ parent_joiner->next2 = joiner->next2;
+ }
+ else
+ op2->joiner = joiner->next2;
+
+ joiner_list_[joiner->idx] = nullptr;
+ delete joiner;
+ }
+
+
+ void ClipperBase::ProcessJoinerList()
+ {
+ for (Joiner* j : joiner_list_)
+ {
+ if (!j) continue;
+ if (succeeded_)
+ {
+ OutRec* outrec = ProcessJoin(j);
+ CleanCollinear(outrec);
+ }
+ else
+ delete j;
+ }
+
+ joiner_list_.resize(0);
+ }
+
+
+ bool CheckDisposeAdjacent(OutPt*& op, const OutPt* guard, OutRec& outRec)
+ {
+ bool result = false;
+ while (op->prev != op)
+ {
+ if (op->pt == op->prev->pt && op != guard &&
+ op->prev->joiner && !op->joiner)
+ {
+ if (op == outRec.pts) outRec.pts = op->prev;
+ op = DisposeOutPt(op);
+ op = op->prev;
+ }
+ else
+ break;
+ }
+
+ while (op->next != op)
+ {
+ if (op->pt == op->next->pt && op != guard &&
+ op->next->joiner && !op->joiner)
+ {
+ if (op == outRec.pts) outRec.pts = op->prev;
+ op = DisposeOutPt(op);
+ op = op->prev;
+ }
+ else
+ break;
+ }
+ return result;
+ }
+
+
+ inline bool IsValidPath(OutPt* op)
+ {
+ return (op && op->next != op);
+ }
+
+
+ bool CollinearSegsOverlap(const Point64& seg1a, const Point64& seg1b,
+ const Point64& seg2a, const Point64& seg2b)
+ {
+ //precondition: seg1 and seg2 are collinear
+ if (seg1a.x == seg1b.x)
+ {
+ if (seg2a.x != seg1a.x || seg2a.x != seg2b.x) return false;
+ }
+ else if (seg1a.x < seg1b.x)
+ {
+ if (seg2a.x < seg2b.x)
+ {
+ if (seg2a.x >= seg1b.x || seg2b.x <= seg1a.x) return false;
+ }
+ else
+ {
+ if (seg2b.x >= seg1b.x || seg2a.x <= seg1a.x) return false;
+ }
+ }
+ else
+ {
+ if (seg2a.x < seg2b.x)
+ {
+ if (seg2a.x >= seg1a.x || seg2b.x <= seg1b.x) return false;
+ }
+ else
+ {
+ if (seg2b.x >= seg1a.x || seg2a.x <= seg1b.x) return false;
+ }
+ }
+
+ if (seg1a.y == seg1b.y)
+ {
+ if (seg2a.y != seg1a.y || seg2a.y != seg2b.y) return false;
+ }
+ else if (seg1a.y < seg1b.y)
+ {
+ if (seg2a.y < seg2b.y)
+ {
+ if (seg2a.y >= seg1b.y || seg2b.y <= seg1a.y) return false;
+ }
+ else
+ {
+ if (seg2b.y >= seg1b.y || seg2a.y <= seg1a.y) return false;
+ }
+ }
+ else
+ {
+ if (seg2a.y < seg2b.y)
+ {
+ if (seg2a.y >= seg1a.y || seg2b.y <= seg1b.y) return false;
+ }
+ else
+ {
+ if (seg2b.y >= seg1a.y || seg2a.y <= seg1b.y) return false;
+ }
+ }
+ return true;
+ }
+
+ OutRec* ClipperBase::ProcessJoin(Joiner* joiner)
+ {
+ OutPt* op1 = joiner->op1, * op2 = joiner->op2;
+ OutRec* or1 = GetRealOutRec(op1->outrec);
+ OutRec* or2 = GetRealOutRec(op2->outrec);
+ DeleteJoin(joiner);
+
+ if (or2->pts == nullptr) return or1;
+ else if (!IsValidClosedPath(op2))
+ {
+ SafeDisposeOutPts(op2);
+ return or1;
+ }
+ else if ((or1->pts == nullptr) || !IsValidClosedPath(op1))
+ {
+ SafeDisposeOutPts(op1);
+ return or2;
+ }
+ else if (or1 == or2 &&
+ ((op1 == op2) || (op1->next == op2) || (op1->prev == op2))) return or1;
+
+ CheckDisposeAdjacent(op1, op2, *or1);
+ CheckDisposeAdjacent(op2, op1, *or2);
+ if (op1->next == op2 || op2->next == op1) return or1;
+ OutRec* result = or1;
+
+ for (; ; )
+ {
+ if (!IsValidPath(op1) || !IsValidPath(op2) ||
+ (or1 == or2 && (op1->prev == op2 || op1->next == op2))) return or1;
+
+ if (op1->prev->pt == op2->next->pt ||
+ ((CrossProduct(op1->prev->pt, op1->pt, op2->next->pt) == 0) &&
+ CollinearSegsOverlap(op1->prev->pt, op1->pt, op2->pt, op2->next->pt)))
+ {
+ if (or1 == or2)
+ {
+ //SPLIT REQUIRED
+ //make sure op1.prev and op2.next match positions
+ //by inserting an extra vertex if needed
+ if (op1->prev->pt != op2->next->pt)
+ {
+ if (PointEqualOrBetween(op1->prev->pt, op2->pt, op2->next->pt))
+ op2->next = InsertOp(op1->prev->pt, op2);
+ else
+ op1->prev = InsertOp(op2->next->pt, op1->prev);
+ }
+
+ //current to new
+ //op1.p[opA] >>> op1 ... opA \ / op1
+ //op2.n[opB] <<< op2 ... opB / \ op2
+ OutPt* opA = op1->prev, * opB = op2->next;
+ opA->next = opB;
+ opB->prev = opA;
+ op1->prev = op2;
+ op2->next = op1;
+ CompleteSplit(op1, opA, *or1);
+ }
+ else
+ {
+ //JOIN, NOT SPLIT
+ OutPt* opA = op1->prev, * opB = op2->next;
+ opA->next = opB;
+ opB->prev = opA;
+ op1->prev = op2;
+ op2->next = op1;
+
+ //SafeDeleteOutPtJoiners(op2);
+ //DisposeOutPt(op2);
+
+ if (or1->idx < or2->idx)
+ {
+ or1->pts = op1;
+ or2->pts = nullptr;
+ if (or1->owner && (!or2->owner ||
+ or2->owner->idx < or1->owner->idx))
+ or1->owner = or2->owner;
+ or2->owner = or1;
+ }
+ else
+ {
+ result = or2;
+ or2->pts = op1;
+ or1->pts = nullptr;
+ if (or2->owner && (!or1->owner ||
+ or1->owner->idx < or2->owner->idx))
+ or2->owner = or1->owner;
+ or1->owner = or2;
+ }
+ }
+ break;
+ }
+ else if (op1->next->pt == op2->prev->pt ||
+ ((CrossProduct(op1->next->pt, op2->pt, op2->prev->pt) == 0) &&
+ CollinearSegsOverlap(op1->next->pt, op1->pt, op2->pt, op2->prev->pt)))
+ {
+ if (or1 == or2)
+ {
+ //SPLIT REQUIRED
+ //make sure op2.prev and op1.next match positions
+ //by inserting an extra vertex if needed
+ if (op2->prev->pt != op1->next->pt)
+ {
+ if (PointEqualOrBetween(op2->prev->pt, op1->pt, op1->next->pt))
+ op1->next = InsertOp(op2->prev->pt, op1);
+ else
+ op2->prev = InsertOp(op1->next->pt, op2->prev);
+ }
+
+ //current to new
+ //op2.p[opA] >>> op2 ... opA \ / op2
+ //op1.n[opB] <<< op1 ... opB / \ op1
+ OutPt* opA = op2->prev, * opB = op1->next;
+ opA->next = opB;
+ opB->prev = opA;
+ op2->prev = op1;
+ op1->next = op2;
+ CompleteSplit(op1, opA, *or1);
+ }
+ else
+ {
+ //JOIN, NOT SPLIT
+ OutPt* opA = op1->next, * opB = op2->prev;
+ opA->prev = opB;
+ opB->next = opA;
+ op1->next = op2;
+ op2->prev = op1;
+
+ //SafeDeleteOutPtJoiners(op2);
+ //DisposeOutPt(op2);
+
+ if (or1->idx < or2->idx)
+ {
+ or1->pts = op1;
+ or2->pts = nullptr;
+ if (or1->owner && (!or2->owner ||
+ or2->owner->idx < or1->owner->idx))
+ or1->owner = or2->owner;
+ or2->owner = or1;
+ }
+ else
+ {
+ result = or2;
+ or2->pts = op1;
+ or1->pts = nullptr;
+ if (or2->owner && (!or1->owner ||
+ or1->owner->idx < or2->owner->idx))
+ or2->owner = or1->owner;
+ or1->owner = or2;
+ }
+ }
+ break;
+ }
+ else if (PointBetween(op1->next->pt, op2->pt, op2->prev->pt) &&
+ DistanceFromLineSqrd(op1->next->pt, op2->pt, op2->prev->pt) < 2.01)
+ {
+ InsertOp(op1->next->pt, op2->prev);
+ continue;
+ }
+ else if (PointBetween(op2->next->pt, op1->pt, op1->prev->pt) &&
+ DistanceFromLineSqrd(op2->next->pt, op1->pt, op1->prev->pt) < 2.01)
+ {
+ InsertOp(op2->next->pt, op1->prev);
+ continue;
+ }
+ else if (PointBetween(op1->prev->pt, op2->pt, op2->next->pt) &&
+ DistanceFromLineSqrd(op1->prev->pt, op2->pt, op2->next->pt) < 2.01)
+ {
+ InsertOp(op1->prev->pt, op2);
+ continue;
+ }
+ else if (PointBetween(op2->prev->pt, op1->pt, op1->next->pt) &&
+ DistanceFromLineSqrd(op2->prev->pt, op1->pt, op1->next->pt) < 2.01)
+ {
+ InsertOp(op2->prev->pt, op1);
+ continue;
+ }
+
+ //something odd needs tidying up
+ if (CheckDisposeAdjacent(op1, op2, *or1)) continue;
+ else if (CheckDisposeAdjacent(op2, op1, *or1)) continue;
+ else if (op1->prev->pt != op2->next->pt &&
+ (DistanceSqr(op1->prev->pt, op2->next->pt) < 2.01))
+ {
+ op1->prev->pt = op2->next->pt;
+ continue;
+ }
+ else if (op1->next->pt != op2->prev->pt &&
+ (DistanceSqr(op1->next->pt, op2->prev->pt) < 2.01))
+ {
+ op2->prev->pt = op1->next->pt;
+ continue;
+ }
+ else
+ {
+ //OK, there doesn't seem to be a way to join after all
+ //so just tidy up the polygons
+ or1->pts = op1;
+ if (or2 != or1)
+ {
+ or2->pts = op2;
+ CleanCollinear(or2);
+ }
+ break;
+ }
+ }
+ return result;
+
+ }
+
+ inline bool Path1InsidePath2(const OutRec* or1, const OutRec* or2)
+ {
+ PointInPolygonResult result = PointInPolygonResult::IsOn;
+ OutPt* op = or1->pts;
+ do
+ {
+ result = PointInPolygon(op->pt, or2->path);
+ if (result != PointInPolygonResult::IsOn) break;
+ op = op->next;
+ } while (op != or1->pts);
+ if (result == PointInPolygonResult::IsOn)
+ return Area(op) < Area(or2->pts);
+ else
+ return result == PointInPolygonResult::IsInside;
+ }
+
+ inline Rect64 GetBounds(const Path64& path)
+ {
+ if (path.empty()) return Rect64();
+ Rect64 result = invalid_rect;
+ for(const Point64& pt : path)
+ {
+ if (pt.x < result.left) result.left = pt.x;
+ if (pt.x > result.right) result.right = pt.x;
+ if (pt.y < result.top) result.top = pt.y;
+ if (pt.y > result.bottom) result.bottom = pt.y;
+ }
+ return result;
+ }
+
+ bool BuildPath64(OutPt* op, bool reverse, bool isOpen, Path64& path)
+ {
+ if (op->next == op || (!isOpen && op->next == op->prev))
+ return false;
+
+ path.resize(0);
+ Point64 lastPt;
+ OutPt* op2;
+ if (reverse)
+ {
+ lastPt = op->pt;
+ op2 = op->prev;
+ }
+ else
+ {
+ op = op->next;
+ lastPt = op->pt;
+ op2 = op->next;
+ }
+ path.push_back(lastPt);
+
+ while (op2 != op)
+ {
+ if (op2->pt != lastPt)
+ {
+ lastPt = op2->pt;
+ path.push_back(lastPt);
+ }
+ if (reverse)
+ op2 = op2->prev;
+ else
+ op2 = op2->next;
+ }
+
+ if (path.size() == 3 && IsVerySmallTriangle(*op2)) return false;
+ else return true;
+ }
+
+ bool ClipperBase::DeepCheckOwner(OutRec* outrec, OutRec* owner)
+ {
+ if (owner->bounds.IsEmpty()) owner->bounds = GetBounds(owner->path);
+ bool is_inside_owner_bounds = owner->bounds.Contains(outrec->bounds);
+
+ // while looking for the correct owner, check the owner's
+ // splits **before** checking the owner itself because
+ // splits can occur internally, and checking the owner
+ // first would miss the inner split's true ownership
+ if (owner->splits)
+ {
+ for (OutRec* split : *owner->splits)
+ {
+ split = GetRealOutRec(split);
+ if (!split || split->idx <= owner->idx || split == outrec) continue;
+
+ if (split->splits && DeepCheckOwner(outrec, split)) return true;
+
+ if (!split->path.size())
+ BuildPath64(split->pts, ReverseSolution, false, split->path);
+ if (split->bounds.IsEmpty()) split->bounds = GetBounds(split->path);
+
+ if (split->bounds.Contains(outrec->bounds) &&
+ Path1InsidePath2(outrec, split))
+ {
+ outrec->owner = split;
+ return true;
+ }
+ }
+ }
+
+ // only continue past here when not inside recursion
+ if (owner != outrec->owner) return false;
+
+ for (;;)
+ {
+ if (is_inside_owner_bounds && Path1InsidePath2(outrec, outrec->owner))
+ return true;
+ // otherwise keep trying with owner's owner
+ outrec->owner = outrec->owner->owner;
+ if (!outrec->owner) return true; // true or false
+ is_inside_owner_bounds = outrec->owner->bounds.Contains(outrec->bounds);
+ }
+ }
+
+ void Clipper64::BuildPaths64(Paths64& solutionClosed, Paths64* solutionOpen)
+ {
+ solutionClosed.resize(0);
+ solutionClosed.reserve(outrec_list_.size());
+ if (solutionOpen)
+ {
+ solutionOpen->resize(0);
+ solutionOpen->reserve(outrec_list_.size());
+ }
+
+ for (OutRec* outrec : outrec_list_)
+ {
+ if (outrec->pts == nullptr) continue;
+
+ Path64 path;
+ if (solutionOpen && outrec->is_open)
+ {
+ if (BuildPath64(outrec->pts, ReverseSolution, true, path))
+ solutionOpen->emplace_back(std::move(path));
+ }
+ else
+ {
+ //closed paths should always return a Positive orientation
+ if (BuildPath64(outrec->pts, ReverseSolution, false, path))
+ solutionClosed.emplace_back(std::move(path));
+ }
+ }
+ }
+
+ void Clipper64::BuildTree64(PolyPath64& polytree, Paths64& open_paths)
+ {
+ polytree.Clear();
+ open_paths.resize(0);
+ if (has_open_paths_)
+ open_paths.reserve(outrec_list_.size());
+
+ for (OutRec* outrec : outrec_list_)
+ {
+ if (!outrec || !outrec->pts) continue;
+ if (outrec->is_open)
+ {
+ Path64 path;
+ if (BuildPath64(outrec->pts, ReverseSolution, true, path))
+ open_paths.push_back(path);
+ continue;
+ }
+
+ if (!BuildPath64(outrec->pts, ReverseSolution, false, outrec->path))
+ continue;
+ if (outrec->bounds.IsEmpty()) outrec->bounds = GetBounds(outrec->path);
+ outrec->owner = GetRealOutRec(outrec->owner);
+ if (outrec->owner) DeepCheckOwner(outrec, outrec->owner);
+
+ // swap the order when a child preceeds its owner
+ // (because owners must preceed children in polytrees)
+ if (outrec->owner && outrec->idx < outrec->owner->idx)
+ {
+ OutRec* tmp = outrec->owner;
+ outrec_list_[outrec->owner->idx] = outrec;
+ outrec_list_[outrec->idx] = tmp;
+ size_t tmp_idx = outrec->idx;
+ outrec->idx = tmp->idx;
+ tmp->idx = tmp_idx;
+ outrec = tmp;
+ outrec->owner = GetRealOutRec(outrec->owner);
+ BuildPath64(outrec->pts, ReverseSolution, false, outrec->path);
+ if (outrec->bounds.IsEmpty()) outrec->bounds = GetBounds(outrec->path);
+ if (outrec->owner) DeepCheckOwner(outrec, outrec->owner);
+ }
+
+ PolyPath* owner_polypath;
+ if (outrec->owner && outrec->owner->polypath)
+ owner_polypath = outrec->owner->polypath;
+ else
+ owner_polypath = &polytree;
+ outrec->polypath = owner_polypath->AddChild(outrec->path);
+ }
+ }
+
+ bool BuildPathD(OutPt* op, bool reverse, bool isOpen, PathD& path, double inv_scale)
+ {
+ if (op->next == op || (!isOpen && op->next == op->prev)) return false;
+ path.resize(0);
+ Point64 lastPt;
+ OutPt* op2;
+ if (reverse)
+ {
+ lastPt = op->pt;
+ op2 = op->prev;
+ }
+ else
+ {
+ op = op->next;
+ lastPt = op->pt;
+ op2 = op->next;
+ }
+ path.push_back(PointD(lastPt.x * inv_scale, lastPt.y * inv_scale));
+
+ while (op2 != op)
+ {
+ if (op2->pt != lastPt)
+ {
+ lastPt = op2->pt;
+ path.push_back(PointD(lastPt.x * inv_scale, lastPt.y * inv_scale));
+ }
+ if (reverse)
+ op2 = op2->prev;
+ else
+ op2 = op2->next;
+ }
+ if (path.size() == 3 && IsVerySmallTriangle(*op2)) return false;
+ return true;
+ }
+
+ void ClipperD::BuildPathsD(PathsD& solutionClosed, PathsD* solutionOpen)
+ {
+ solutionClosed.resize(0);
+ solutionClosed.reserve(outrec_list_.size());
+ if (solutionOpen)
+ {
+ solutionOpen->resize(0);
+ solutionOpen->reserve(outrec_list_.size());
+ }
+
+ for (OutRec* outrec : outrec_list_)
+ {
+ if (outrec->pts == nullptr) continue;
+
+ PathD path;
+ if (solutionOpen && outrec->is_open)
+ {
+ if (BuildPathD(outrec->pts, ReverseSolution, true, path, invScale_))
+ solutionOpen->emplace_back(std::move(path));
+ }
+ else
+ {
+ //closed paths should always return a Positive orientation
+ if (BuildPathD(outrec->pts, ReverseSolution, false, path, invScale_))
+ solutionClosed.emplace_back(std::move(path));
+ }
+ }
+ }
+
+ void ClipperD::BuildTreeD(PolyPathD& polytree, PathsD& open_paths)
+ {
+ polytree.Clear();
+ open_paths.resize(0);
+ if (has_open_paths_)
+ open_paths.reserve(outrec_list_.size());
+
+ for (OutRec* outrec : outrec_list_)
+ {
+ if (!outrec || !outrec->pts) continue;
+ if (outrec->is_open)
+ {
+ PathD path;
+ if (BuildPathD(outrec->pts, ReverseSolution, true, path, invScale_))
+ open_paths.push_back(path);
+ continue;
+ }
+
+ if (!BuildPath64(outrec->pts, ReverseSolution, false, outrec->path))
+ continue;
+ if (outrec->bounds.IsEmpty()) outrec->bounds = GetBounds(outrec->path);
+ outrec->owner = GetRealOutRec(outrec->owner);
+ if (outrec->owner) DeepCheckOwner(outrec, outrec->owner);
+
+ // swap the order when a child preceeds its owner
+ // (because owners must preceed children in polytrees)
+ if (outrec->owner && outrec->idx < outrec->owner->idx)
+ {
+ OutRec* tmp = outrec->owner;
+ outrec_list_[outrec->owner->idx] = outrec;
+ outrec_list_[outrec->idx] = tmp;
+ size_t tmp_idx = outrec->idx;
+ outrec->idx = tmp->idx;
+ tmp->idx = tmp_idx;
+ outrec = tmp;
+ outrec->owner = GetRealOutRec(outrec->owner);
+ BuildPath64(outrec->pts, ReverseSolution, false, outrec->path);
+ if (outrec->bounds.IsEmpty()) outrec->bounds = GetBounds(outrec->path);
+ if (outrec->owner) DeepCheckOwner(outrec, outrec->owner);
+ }
+
+ PolyPath* owner_polypath;
+ if (outrec->owner && outrec->owner->polypath)
+ owner_polypath = outrec->owner->polypath;
+ else
+ owner_polypath = &polytree;
+ outrec->polypath = owner_polypath->AddChild(outrec->path);
+ }
+ }
+
+} // namespace clipper2lib
diff --git a/clipper.engine.h b/clipper.engine.h
new file mode 100644
index 000000000000..67383f213052
--- /dev/null
+++ b/clipper.engine.h
@@ -0,0 +1,588 @@
+/*******************************************************************************
+* Author : Angus Johnson *
+* Date : 4 November 2022 *
+* Website : http://www.angusj.com *
+* Copyright : Angus Johnson 2010-2022 *
+* Purpose : This is the main polygon clipping module *
+* License : http://www.boost.org/LICENSE_1_0.txt *
+*******************************************************************************/
+
+#ifndef CLIPPER_ENGINE_H
+#define CLIPPER_ENGINE_H
+
+constexpr auto CLIPPER2_VERSION = "1.0.6";
+
+#include <cstdlib>
+#include <queue>
+#include <stdexcept>
+#include <vector>
+#include <functional>
+#include <cstddef>
+#include <cstdint>
+#include "clipper.core.h"
+
+namespace Clipper2Lib {
+
+ struct Scanline;
+ struct IntersectNode;
+ struct Active;
+ struct Vertex;
+ struct LocalMinima;
+ struct OutRec;
+ struct Joiner;
+
+ //Note: all clipping operations except for Difference are commutative.
+ enum class ClipType { None, Intersection, Union, Difference, Xor };
+
+ enum class PathType { Subject, Clip };
+
+ enum class VertexFlags : uint32_t {
+ None = 0, OpenStart = 1, OpenEnd = 2, LocalMax = 4, LocalMin = 8
+ };
+
+ constexpr enum VertexFlags operator &(enum VertexFlags a, enum VertexFlags b)
+ {
+ return (enum VertexFlags)(uint32_t(a) & uint32_t(b));
+ }
+
+ constexpr enum VertexFlags operator |(enum VertexFlags a, enum VertexFlags b)
+ {
+ return (enum VertexFlags)(uint32_t(a) | uint32_t(b));
+ }
+
+ struct Vertex {
+ Point64 pt;
+ Vertex* next = nullptr;
+ Vertex* prev = nullptr;
+ VertexFlags flags = VertexFlags::None;
+ };
+
+ struct OutPt {
+ Point64 pt;
+ OutPt* next = nullptr;
+ OutPt* prev = nullptr;
+ OutRec* outrec;
+ Joiner* joiner = nullptr;
+
+ OutPt(const Point64& pt_, OutRec* outrec_): pt(pt_), outrec(outrec_) {
+ next = this;
+ prev = this;
+ }
+ };
+
+ class PolyPath;
+ class PolyPath64;
+ class PolyPathD;
+ using PolyTree64 = PolyPath64;
+ using PolyTreeD = PolyPathD;
+
+ struct OutRec;
+ typedef std::vector<OutRec*> OutRecList;
+
+ //OutRec: contains a path in the clipping solution. Edges in the AEL will
+ //have OutRec pointers assigned when they form part of the clipping solution.
+ struct OutRec {
+ size_t idx = 0;
+ OutRec* owner = nullptr;
+ OutRecList* splits = nullptr;
+ Active* front_edge = nullptr;
+ Active* back_edge = nullptr;
+ OutPt* pts = nullptr;
+ PolyPath* polypath = nullptr;
+ Rect64 bounds = {};
+ Path64 path;
+ bool is_open = false;
+ ~OutRec() { if (splits) delete splits; };
+ };
+
+ ///////////////////////////////////////////////////////////////////
+ //Important: UP and DOWN here are premised on Y-axis positive down
+ //displays, which is the orientation used in Clipper's development.
+ ///////////////////////////////////////////////////////////////////
+
+ struct Active {
+ Point64 bot;
+ Point64 top;
+ int64_t curr_x = 0; //current (updated at every new scanline)
+ double dx = 0.0;
+ int wind_dx = 1; //1 or -1 depending on winding direction
+ int wind_cnt = 0;
+ int wind_cnt2 = 0; //winding count of the opposite polytype
+ OutRec* outrec = nullptr;
+ //AEL: 'active edge list' (Vatti's AET - active edge table)
+ // a linked list of all edges (from left to right) that are present
+ // (or 'active') within the current scanbeam (a horizontal 'beam' that
+ // sweeps from bottom to top over the paths in the clipping operation).
+ Active* prev_in_ael = nullptr;
+ Active* next_in_ael = nullptr;
+ //SEL: 'sorted edge list' (Vatti's ST - sorted table)
+ // linked list used when sorting edges into their new positions at the
+ // top of scanbeams, but also (re)used to process horizontals.
+ Active* prev_in_sel = nullptr;
+ Active* next_in_sel = nullptr;
+ Active* jump = nullptr;
+ Vertex* vertex_top = nullptr;
+ LocalMinima* local_min = nullptr; // the bottom of an edge 'bound' (also Vatti)
+ bool is_left_bound = false;
+ };
+
+ struct LocalMinima {
+ Vertex* vertex;
+ PathType polytype;
+ bool is_open;
+ LocalMinima(Vertex* v, PathType pt, bool open) :
+ vertex(v), polytype(pt), is_open(open){}
+ };
+
+ struct IntersectNode {
+ Point64 pt;
+ Active* edge1;
+ Active* edge2;
+ IntersectNode() : pt(Point64(0, 0)), edge1(NULL), edge2(NULL) {}
+ IntersectNode(Active* e1, Active* e2, Point64& pt_) :
+ pt(pt_), edge1(e1), edge2(e2)
+ {
+ }
+ };
+
+#ifdef USINGZ
+ typedef std::function<void(const Point64& e1bot, const Point64& e1top,
+ const Point64& e2bot, const Point64& e2top, Point64& pt)> ZCallback64;
+
+ typedef std::function<void(const PointD& e1bot, const PointD& e1top,
+ const PointD& e2bot, const PointD& e2top, PointD& pt)> ZCallbackD;
+#endif
+
+ // ClipperBase -------------------------------------------------------------
+
+ class ClipperBase {
+ private:
+ ClipType cliptype_ = ClipType::None;
+ FillRule fillrule_ = FillRule::EvenOdd;
+ FillRule fillpos = FillRule::Positive;
+ int64_t bot_y_ = 0;
+ bool minima_list_sorted_ = false;
+ bool using_polytree_ = false;
+ Active* actives_ = nullptr;
+ Active *sel_ = nullptr;
+ Joiner *horz_joiners_ = nullptr;
+ std::vector<LocalMinima*> minima_list_; //pointers in case of memory reallocs
+ std::vector<LocalMinima*>::iterator current_locmin_iter_;
+ std::vector<Vertex*> vertex_lists_;
+ std::priority_queue<int64_t> scanline_list_;
+ std::vector<IntersectNode> intersect_nodes_;
+ std::vector<Joiner*> joiner_list_; //pointers in case of memory reallocs
+ void Reset();
+ void InsertScanline(int64_t y);
+ bool PopScanline(int64_t &y);
+ bool PopLocalMinima(int64_t y, LocalMinima *&local_minima);
+ void DisposeAllOutRecs();
+ void DisposeVerticesAndLocalMinima();
+ void DeleteEdges(Active*& e);
+ void AddLocMin(Vertex &vert, PathType polytype, bool is_open);
+ bool IsContributingClosed(const Active &e) const;
+ inline bool IsContributingOpen(const Active &e) const;
+ void SetWindCountForClosedPathEdge(Active &edge);
+ void SetWindCountForOpenPathEdge(Active &e);
+ void InsertLocalMinimaIntoAEL(int64_t bot_y);
+ void InsertLeftEdge(Active &e);
+ inline void PushHorz(Active &e);
+ inline bool PopHorz(Active *&e);
+ inline OutPt* StartOpenPath(Active &e, const Point64& pt);
+ inline void UpdateEdgeIntoAEL(Active *e);
+ OutPt* IntersectEdges(Active &e1, Active &e2, const Point64& pt);
+ inline void DeleteFromAEL(Active &e);
+ inline void AdjustCurrXAndCopyToSEL(const int64_t top_y);
+ void DoIntersections(const int64_t top_y);
+ void AddNewIntersectNode(Active &e1, Active &e2, const int64_t top_y);
+ bool BuildIntersectList(const int64_t top_y);
+ void ProcessIntersectList();
+ void SwapPositionsInAEL(Active& edge1, Active& edge2);
+ OutPt* AddOutPt(const Active &e, const Point64& pt);
+ OutPt* AddLocalMinPoly(Active &e1, Active &e2,
+ const Point64& pt, bool is_new = false);
+ OutPt* AddLocalMaxPoly(Active &e1, Active &e2, const Point64& pt);
+ void DoHorizontal(Active &horz);
+ bool ResetHorzDirection(const Active &horz, const Active *max_pair,
+ int64_t &horz_left, int64_t &horz_right);
+ void DoTopOfScanbeam(const int64_t top_y);
+ Active *DoMaxima(Active &e);
+ void JoinOutrecPaths(Active &e1, Active &e2);
+ void CompleteSplit(OutPt* op1, OutPt* op2, OutRec& outrec);
+ bool ValidateClosedPathEx(OutPt*& outrec);
+ void CleanCollinear(OutRec* outrec);
+ void FixSelfIntersects(OutRec* outrec);
+ void DoSplitOp(OutRec* outRec, OutPt* splitOp);
+ Joiner* GetHorzTrialParent(const OutPt* op);
+ bool OutPtInTrialHorzList(OutPt* op);
+ void SafeDisposeOutPts(OutPt*& op);
+ void SafeDeleteOutPtJoiners(OutPt* op);
+ void AddTrialHorzJoin(OutPt* op);
+ void DeleteTrialHorzJoin(OutPt* op);
+ void ConvertHorzTrialsToJoins();
+ void AddJoin(OutPt* op1, OutPt* op2);
+ void DeleteJoin(Joiner* joiner);
+ void ProcessJoinerList();
+ OutRec* ProcessJoin(Joiner* joiner);
+ protected:
+ bool has_open_paths_ = false;
+ bool succeeded_ = true;
+ std::vector<OutRec*> outrec_list_; //pointers in case list memory reallocated
+ bool ExecuteInternal(ClipType ct, FillRule ft, bool use_polytrees);
+ bool DeepCheckOwner(OutRec* outrec, OutRec* owner);
+#ifdef USINGZ
+ ZCallback64 zCallback_ = nullptr;
+ void SetZ(const Active& e1, const Active& e2, Point64& pt);
+#endif
+ void CleanUp(); // unlike Clear, CleanUp preserves added paths
+ void AddPath(const Path64& path, PathType polytype, bool is_open);
+ void AddPaths(const Paths64& paths, PathType polytype, bool is_open);
+ public:
+ virtual ~ClipperBase();
+ bool PreserveCollinear = true;
+ bool ReverseSolution = false;
+ void Clear();
+ };
+
+ // PolyPath / PolyTree --------------------------------------------------------
+
+ //PolyTree: is intended as a READ-ONLY data structure for CLOSED paths returned
+ //by clipping operations. While this structure is more complex than the
+ //alternative Paths structure, it does preserve path 'ownership' - ie those
+ //paths that contain (or own) other paths. This will be useful to some users.
+
+ class PolyPath {
+ protected:
+ PolyPath* parent_;
+ public:
+ PolyPath(PolyPath* parent = nullptr): parent_(parent){}
+ virtual ~PolyPath() { Clear(); };
+ //https://en.cppreference.com/w/cpp/language/rule_of_three
+ PolyPath(const PolyPath&) = delete;
+ PolyPath& operator=(const PolyPath&) = delete;
+
+ unsigned Level() const
+ {
+ unsigned result = 0;
+ const PolyPath* p = parent_;
+ while (p) { ++result; p = p->parent_; }
+ return result;
+ }
+
+ virtual PolyPath* AddChild(const Path64& path) = 0;
+
+ virtual void Clear() {};
+ virtual size_t Count() const { return 0; }
+
+ const PolyPath* Parent() const { return parent_; }
+
+ bool IsHole() const
+ {
+ const PolyPath* pp = parent_;
+ bool is_hole = pp;
+ while (pp) {
+ is_hole = !is_hole;
+ pp = pp->parent_;
+ }
+ return is_hole;
+ }
+ };
+
+ class PolyPath64 : public PolyPath {
+ private:
+ std::vector<PolyPath64*> childs_;
+ Path64 polygon_;
+ typedef typename std::vector<PolyPath64*>::const_iterator pp64_itor;
+ public:
+ PolyPath64(PolyPath64* parent = nullptr) : PolyPath(parent) {}
+ PolyPath64* operator [] (size_t index) { return static_cast<PolyPath64*>(childs_[index]); }
+ pp64_itor begin() const { return childs_.cbegin(); }
+ pp64_itor end() const { return childs_.cend(); }
+
+ PolyPath64* AddChild(const Path64& path) override
+ {
+ PolyPath64* result = new PolyPath64(this);
+ childs_.push_back(result);
+ result->polygon_ = path;
+ return result;
+ }
+
+ void Clear() override
+ {
+ for (const PolyPath64* child : childs_) delete child;
+ childs_.resize(0);
+ }
+
+ size_t Count() const override
+ {
+ return childs_.size();
+ }
+
+ const Path64& Polygon() const { return polygon_; };
+
+ double Area() const
+ {
+ double result = Clipper2Lib::Area<int64_t>(polygon_);
+ for (const PolyPath64* child : childs_)
+ result += child->Area();
+ return result;
+ }
+
+ friend std::ostream& operator << (std::ostream& outstream, const PolyPath64& polypath)
+ {
+ const size_t level_indent = 4;
+ const size_t coords_per_line = 4;
+ const size_t last_on_line = coords_per_line - 1;
+ unsigned level = polypath.Level();
+ if (level > 0)
+ {
+ std::string level_padding;
+ level_padding.insert(0, (level - 1) * level_indent, ' ');
+ std::string caption = polypath.IsHole() ? "Hole " : "Outer Polygon ";
+ std::string childs = polypath.Count() == 1 ? " child" : " children";
+ outstream << level_padding.c_str() << caption << "with " << polypath.Count() << childs << std::endl;
+ outstream << level_padding;
+ size_t i = 0, highI = polypath.Polygon().size() - 1;
+ for (; i < highI; ++i)
+ {
+ outstream << polypath.Polygon()[i] << ' ';
+ if ((i % coords_per_line) == last_on_line)
+ outstream << std::endl << level_padding;
+ }
+ if (highI > 0) outstream << polypath.Polygon()[i];
+ outstream << std::endl;
+ }
+ for (auto child : polypath)
+ outstream << *child;
+ return outstream;
+ }
+
+ };
+
+ class PolyPathD : public PolyPath {
+ private:
+ std::vector<PolyPathD*> childs_;
+ double inv_scale_;
+ PathD polygon_;
+ typedef typename std::vector<PolyPathD*>::const_iterator ppD_itor;
+ public:
+ PolyPathD(PolyPathD* parent = nullptr) : PolyPath(parent)
+ {
+ inv_scale_ = parent ? parent->inv_scale_ : 1.0;
+ }
+ PolyPathD* operator [] (size_t index)
+ {
+ return static_cast<PolyPathD*>(childs_[index]);
+ }
+ ppD_itor begin() const { return childs_.cbegin(); }
+ ppD_itor end() const { return childs_.cend(); }
+
+ void SetInvScale(double value) { inv_scale_ = value; }
+ double InvScale() { return inv_scale_; }
+ PolyPathD* AddChild(const Path64& path) override
+ {
+ PolyPathD* result = new PolyPathD(this);
+ childs_.push_back(result);
+ result->polygon_ = ScalePath<double, int64_t>(path, inv_scale_);
+ return result;
+ }
+
+ void Clear() override
+ {
+ for (const PolyPathD* child : childs_) delete child;
+ childs_.resize(0);
+ }
+
+ size_t Count() const override
+ {
+ return childs_.size();
+ }
+
+ const PathD& Polygon() const { return polygon_; };
+
+ double Area() const
+ {
+ double result = Clipper2Lib::Area<double>(polygon_);
+ for (const PolyPathD* child : childs_)
+ result += child->Area();
+ return result;
+ }
+ };
+
+ class Clipper64 : public ClipperBase
+ {
+ private:
+ void BuildPaths64(Paths64& solutionClosed, Paths64* solutionOpen);
+ void BuildTree64(PolyPath64& polytree, Paths64& open_paths);
+ public:
+#ifdef USINGZ
+ void SetZCallback(ZCallback64 cb) { zCallback_ = cb; }
+#endif
+
+ void AddSubject(const Paths64& subjects)
+ {
+ AddPaths(subjects, PathType::Subject, false);
+ }
+ void AddOpenSubject(const Paths64& open_subjects)
+ {
+ AddPaths(open_subjects, PathType::Subject, true);
+ }
+ void AddClip(const Paths64& clips)
+ {
+ AddPaths(clips, PathType::Clip, false);
+ }
+
+ bool Execute(ClipType clip_type,
+ FillRule fill_rule, Paths64& closed_paths)
+ {
+ Paths64 dummy;
+ return Execute(clip_type, fill_rule, closed_paths, dummy);
+ }
+
+ bool Execute(ClipType clip_type, FillRule fill_rule,
+ Paths64& closed_paths, Paths64& open_paths)
+ {
+ closed_paths.clear();
+ open_paths.clear();
+ if (ExecuteInternal(clip_type, fill_rule, false))
+ BuildPaths64(closed_paths, &open_paths);
+ CleanUp();
+ return succeeded_;
+ }
+
+ bool Execute(ClipType clip_type, FillRule fill_rule, PolyTree64& polytree)
+ {
+ Paths64 dummy;
+ return Execute(clip_type, fill_rule, polytree, dummy);
+ }
+
+ bool Execute(ClipType clip_type,
+ FillRule fill_rule, PolyTree64& polytree, Paths64& open_paths)
+ {
+ if (ExecuteInternal(clip_type, fill_rule, true))
+ {
+ open_paths.clear();
+ polytree.Clear();
+ BuildTree64(polytree, open_paths);
+ }
+ CleanUp();
+ return succeeded_;
+ }
+ };
+
+ class ClipperD : public ClipperBase {
+ private:
+ double scale_ = 1.0, invScale_ = 1.0;
+#ifdef USINGZ
+ ZCallbackD zCallback_ = nullptr;
+#endif
+ void BuildPathsD(PathsD& solutionClosed, PathsD* solutionOpen);
+ void BuildTreeD(PolyPathD& polytree, PathsD& open_paths);
+ public:
+ explicit ClipperD(int precision = 2) : ClipperBase()
+ {
+ CheckPrecision(precision);
+ // to optimize scaling / descaling precision
+ // set the scale to a power of double's radix (2) (#25)
+ scale_ = std::pow(std::numeric_limits<double>::radix,
+ std::ilogb(std::pow(10, precision)) + 1);
+ invScale_ = 1 / scale_;
+ }
+
+#ifdef USINGZ
+ void SetZCallback(ZCallbackD cb) { zCallback_ = cb; };
+
+ void ZCB(const Point64& e1bot, const Point64& e1top,
+ const Point64& e2bot, const Point64& e2top, Point64& pt)
+ {
+ // de-scale (x & y)
+ // temporarily convert integers to their initial float values
+ // this will slow clipping marginally but will make it much easier
+ // to understand the coordinates passed to the callback function
+ PointD tmp = PointD(pt) * invScale_;
+ PointD e1b = PointD(e1bot) * invScale_;
+ PointD e1t = PointD(e1top) * invScale_;
+ PointD e2b = PointD(e2bot) * invScale_;
+ PointD e2t = PointD(e2top) * invScale_;
+ zCallback_(e1b,e1t, e2b, e2t, tmp);
+ pt.z = tmp.z; // only update 'z'
+ };
+
+ void CheckCallback()
+ {
+ if(zCallback_)
+ // if the user defined float point callback has been assigned
+ // then assign the proxy callback function
+ ClipperBase::zCallback_ =
+ std::bind(&ClipperD::ZCB, this, std::placeholders::_1,
+ std::placeholders::_2, std::placeholders::_3,
+ std::placeholders::_4, std::placeholders::_5);
+ else
+ ClipperBase::zCallback_ = nullptr;
+ }
+
+#endif
+
+ void AddSubject(const PathsD& subjects)
+ {
+ AddPaths(ScalePaths<int64_t, double>(subjects, scale_), PathType::Subject, false);
+ }
+
+ void AddOpenSubject(const PathsD& open_subjects)
+ {
+ AddPaths(ScalePaths<int64_t, double>(open_subjects, scale_), PathType::Subject, true);
+ }
+
+ void AddClip(const PathsD& clips)
+ {
+ AddPaths(ScalePaths<int64_t, double>(clips, scale_), PathType::Clip, false);
+ }
+
+ bool Execute(ClipType clip_type, FillRule fill_rule, PathsD& closed_paths)
+ {
+ PathsD dummy;
+ return Execute(clip_type, fill_rule, closed_paths, dummy);
+ }
+
+ bool Execute(ClipType clip_type,
+ FillRule fill_rule, PathsD& closed_paths, PathsD& open_paths)
+ {
+#ifdef USINGZ
+ CheckCallback();
+#endif
+ if (ExecuteInternal(clip_type, fill_rule, false))
+ {
+ BuildPathsD(closed_paths, &open_paths);
+ }
+ CleanUp();
+ return succeeded_;
+ }
+
+ bool Execute(ClipType clip_type, FillRule fill_rule, PolyTreeD& polytree)
+ {
+ PathsD dummy;
+ return Execute(clip_type, fill_rule, polytree, dummy);
+ }
+
+ bool Execute(ClipType clip_type,
+ FillRule fill_rule, PolyTreeD& polytree, PathsD& open_paths)
+ {
+#ifdef USINGZ
+ CheckCallback();
+#endif
+ if (ExecuteInternal(clip_type, fill_rule, true))
+ {
+ polytree.Clear();
+ polytree.SetInvScale(invScale_);
+ open_paths.clear();
+ BuildTreeD(polytree, open_paths);
+ }
+ CleanUp();
+ return succeeded_;
+ }
+
+ };
+
+} // namespace
+
+#endif // CLIPPER_ENGINE_H