Welcome to mirror list, hosted at ThFree Co, Russian Federation.

github.com/Ultimaker/CuraEngine.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/libs
diff options
context:
space:
mode:
authorSkeen <skeen@cs.au.dk>2014-04-07 00:24:19 +0400
committerSkeen <skeen@cs.au.dk>2014-04-07 00:24:19 +0400
commitd7d9b5b9a4a5aa6b138a3fa1e3c19b2f5f50f5bd (patch)
tree01c8c54d2b9dd9127807febe1577e83b4ebb654c /libs
parentd00682c56f5c6e7a8080c9dfaffc03e40595d960 (diff)
Moved clipper to a libraries folder.
Added a DO_NOT_CHANGE_THESE files, nothing developers that the sources in this folder, is not to be changed directly in this repository, but should rather be modified in their respective repositories. Updated the Makefile to build this library. Updated the Makefile to include the libs folder, as a isystem include I.e. do not throw errors, warnings, ect. from these headers. Updated intpoint, and polygon to include clipper via. compiler lookup.
Diffstat (limited to 'libs')
-rw-r--r--libs/DO_NOT_CHANGE_THESE3
-rw-r--r--libs/clipper/License.txt26
-rw-r--r--libs/clipper/README376
-rw-r--r--libs/clipper/clipper.cpp4610
-rw-r--r--libs/clipper/clipper.hpp398
5 files changed, 5413 insertions, 0 deletions
diff --git a/libs/DO_NOT_CHANGE_THESE b/libs/DO_NOT_CHANGE_THESE
new file mode 100644
index 000000000..768cf535f
--- /dev/null
+++ b/libs/DO_NOT_CHANGE_THESE
@@ -0,0 +1,3 @@
+These libraries are extern, and while they're utilized by this project,
+they are in fact not actually developed on this repository.
+If changes are desired for these projects, please refer to their official repositories.
diff --git a/libs/clipper/License.txt b/libs/clipper/License.txt
new file mode 100644
index 000000000..36f45dff5
--- /dev/null
+++ b/libs/clipper/License.txt
@@ -0,0 +1,26 @@
+The Clipper Library (including Delphi, C++ & C# source code, other accompanying
+code, examples and documentation), hereafter called "the Software", has been
+released under the following license, terms and conditions:
+
+Boost Software License - Version 1.0 - August 17th, 2003
+http://www.boost.org/LICENSE_1_0.txt
+
+Permission is hereby granted, free of charge, to any person or organization
+obtaining a copy of the Software covered by this license to use, reproduce,
+display, distribute, execute, and transmit the Software, and to prepare
+derivative works of the Software, and to permit third-parties to whom the
+Software is furnished to do so, all subject to the following:
+
+The copyright notices in the Software and this entire statement, including the
+above license grant, this restriction and the following disclaimer, must be
+included in all copies of the Software, in whole or in part, and all derivative
+works of the Software, unless such copies or derivative works are solely in the
+form of machine-executable object code generated by a source language processor.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT SHALL
+THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE FOR ANY
+DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, ARISING
+FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/libs/clipper/README b/libs/clipper/README
new file mode 100644
index 000000000..b471615f7
--- /dev/null
+++ b/libs/clipper/README
@@ -0,0 +1,376 @@
+=====================================================================
+Clipper Change Log
+=====================================================================
+
+v6.1.3 (19 January 2014)
+* Fixed potential endless loop condition when adding open
+ paths to Clipper.
+* Fixed missing implementation of SimplifyPolygon function
+ in C++ code.
+* Fixed incorrect upper range constant for polygon coordinates
+ in Delphi code.
+* Added PointInPolygon function.
+* Overloaded MinkowskiSum function to accommodate multi-contour
+ paths.
+
+v6.1.2 (15 December 2013)
+* Fixed broken C++ header file.
+* Minor improvement to joining polygons.
+
+v6.1.1 (13 December 2013)
+* Fixed a couple of bugs affecting open paths that could
+ raise unhandled exceptions.
+
+v6.1.0 (12 December 2013)
+* Deleted: Previously deprecated code has been removed.
+* Modified: The OffsetPaths function is now deprecated as it has
+ been replaced by the ClipperOffset class which is much more
+ flexible.
+* Bugfixes: Several minor bugs have been fixed including
+ occasionally an incorrect nesting within the PolyTree structure.
+
+v6.0.0 (30 October 2013)
+* Added: Open path (polyline) clipping. A new 'Curves' demo
+ application showcases this (see the 'Curves' directory).
+* Update: Major improvement in the merging of
+ shared/collinear edges in clip solutions (see Execute).
+* Added: The IntPoint structure now has an optional 'Z' member.
+ (See the precompiler directive use_xyz.)
+* Added: Users can now force Clipper to use 32bit integers
+ (via the precompiler directive use_int32) instead of using
+ 64bit integers.
+* Modified: To accommodate open paths, the Polygon and Polygons
+ structures have been renamed Path and Paths respectively. The
+ AddPolygon and AddPolygons methods of the ClipperBase class
+ have been renamed AddPath and AddPaths respectively. Several
+ other functions have been similarly renamed.
+* Modified: The PolyNode Class has a new IsOpen property.
+* Modified: The Clipper class has a new ZFillFunction property.
+* Added: MinkowskiSum and MinkowskiDiff functions added.
+* Added: Several other new functions have been added including
+ PolyTreeToPaths, OpenPathsFromPolyTree and ClosedPathsFromPolyTree.
+* Added: The Clipper constructor now accepts an optional InitOptions
+ parameter to simplify setting properties.
+* Bugfixes: Numerous minor bugs have been fixed.
+* Deprecated: Version 6 is a major upgrade from previous versions
+ and quite a number of changes have been made to exposed structures
+ and functions. To minimize inconvenience to existing library users,
+ some code has been retained and some added to maintain backward
+ compatibility. However, because this code will be removed in a
+ future update, it has been marked as deprecated and a precompiler
+ directive use_deprecated has been defined.
+
+v5.1.6 (23 May 2013)
+* BugFix: CleanPolygon function was buggy.
+* Changed: The behaviour of the 'miter' JoinType has been
+ changed so that when squaring occurs, it's no longer
+ extended up to the miter limit but is squared off at
+ exactly 'delta' units. (This improves the look of mitering
+ with larger limits at acute angles.)
+* Added: New OffsetPolyLines function
+* Update: Minor code refactoring and optimisations
+
+v5.1.5 (5 May 2013)
+* Added: ForceSimple property to Clipper class
+* Update: Improved documentation
+
+v5.1.4 (24 March 2013)
+* Update: CleanPolygon function enhanced.
+* Update: Documentation improved.
+
+v5.1.3 (14 March 2013)
+* Bugfix: Minor bugfixes.
+* Update: Documentation significantly improved.
+
+v5.1.2 (26 February 2013)
+* Bugfix: PolyNode class was missing a constructor.
+* Update: The MiterLimit parameter in the OffsetPolygons
+ function has been renamed Limit and can now also be used to
+ limit the number of vertices used to construct arcs when
+ JoinType is set to jtRound.
+
+v5.1.0 (17 February 2013)
+* Update: ExPolygons has been replaced with the PolyTree &
+ PolyNode classes to more fully represent the parent-child
+ relationships of the polygons returned by Clipper.
+* Added: New CleanPolygon and CleanPolygons functions.
+* Bugfix: Another orientation bug fixed.
+
+v5.0.2 - 30 December 2012
+* Bugfix: Significant fixes in and tidy of the internal
+ Int128 class (which is used only when polygon coordinate
+ values are greater than ±0x3FFFFFFF (~1.07e9)).
+* Update: The Area algorithm has been updated and is faster.
+* Update: Documentation updates. The newish but undocumented
+ 'CheckInputs' parameter of the OffsetPolygons function has been
+ renamed 'AutoFix' and documented too. The comments on rounding
+ have also been improved (ie clearer and expanded).
+
+v4.10.0 - 25 December 2012
+* Bugfix: Orientation bugs should now be resolved (finally!).
+* Bugfix: Bug in Int128 class
+
+v4.9.8 - 2 December 2012
+* Bugfix: Further fixes to rare Orientation bug.
+
+v4.9.7 - 29 November 2012
+* Bugfix: Bug that very rarely returned the wrong polygon
+ orientation.
+* Bugfix: Obscure bug affecting OffsetPolygons when using
+ jtRound for the JoinType parameter and when polygons also
+ contain very large coordinate values (> +/-100000000000).
+
+v4.9.6 - 9 November 2012
+* Bugfix: Another obscure bug related to joining polygons.
+
+v4.9.4 - 2 November 2012
+* Bugfix: Bugs in Int128 class occasionally causing
+ wrong orientations.
+* Bugfix: Further fixes related to joining polygons.
+
+v4.9.0 - 9 October 2012
+* Bugfix: Obscure bug related to joining polygons.
+
+v4.8.9 - 25 September 2012
+* Bugfix: Obscure bug related to precision of intersections.
+
+v4.8.8 - 30 August 2012
+* Bugfix: Fixed bug in OffsetPolygons function introduced in
+ version 4.8.5.
+
+v4.8.7 - 24 August 2012
+* Bugfix: ReversePolygon function in C++ translation was broken.
+* Bugfix: Two obscure bugs affecting orientation fixed too.
+
+v4.8.6 - 11 August 2012
+* Bugfix: Potential for memory overflow errors when using
+ ExPolygons structure.
+* Bugfix: The polygon coordinate range has been reduced to
+ +/- 0x3FFFFFFFFFFFFFFF (4.6e18).
+* Update: ReversePolygons function was misnamed ReversePoints in C++.
+* Update: SimplifyPolygon function now takes a PolyFillType parameter.
+
+v4.8.5 - 15 July 2012
+* Bugfix: Potential for memory overflow errors in OffsetPolygons().
+
+v4.8.4 - 1 June 2012
+* Bugfix: Another obscure bug affecting ExPolygons structure.
+
+v4.8.3 - 27 May 2012
+* Bugfix: Obscure bug causing incorrect removal of a vertex.
+
+v4.8.2 - 21 May 2012
+* Bugfix: Obscure bug could cause an exception when using
+ ExPolygon structure.
+
+v4.8.1 - 12 May 2012
+* Update: Cody tidy and minor bug fixes.
+
+v4.8.0 - 30 April 2012
+* Bugfix: Occasional errors in orientation fixed.
+* Update: Added notes on rounding to the documentation.
+
+v4.7.6 - 11 April 2012
+* Fixed a bug in Orientation function (affecting C# translations only).
+* Minor documentation update.
+
+v4.7.5 - 28 March 2012
+* Bugfix: Fixed a recently introduced bug that occasionally caused an
+ unhandled exception in C++ and C# translations.
+
+v4.7.4 - 15 March 2012
+* Bugfix: Another minor bugfix.
+
+v4.7.2 - 4 March 2012
+* Bugfix: Fixed bug introduced in ver 4.7 which sometimes caused
+ an exception if ExPolygon structure was passed to Clipper's
+ Execute method.
+
+v4.7.1 - 3 March 2012
+* Bugfix: Rare crash when JoinCommonEdges joined polygons that
+ 'cancelled' each other.
+* Bugfix: Clipper's internal Orientation method occasionally
+ returned wrong result.
+* Update: Improved C# code (thanks to numerous excellent suggestions
+ from David Piepgrass)
+
+v4.7 - 10 February 2012
+* Improved the joining of output polygons sharing a common edge.
+
+v4.6.6 - 3 February 2012
+* Bugfix: Another obscure bug occasionally causing incorrect
+ polygon orientation.
+
+v4.6.5 - 17 January 2012
+* Bugfix: Obscure bug occasionally causing incorrect hole
+ assignment in ExPolygon structure.
+
+v4.6.4 - 8 November 2011
+* Added: SimplifyPolygon and SimplifyPolygons functions.
+
+v4.6.3 - 11 November 2011
+* Bugfix: Fixed another minor mitering bug in OffsetPolygons.
+
+v4.6.2 - 10 November 2011
+* Bugfix: Fixed a rare bug in the orientation of polygons
+ returned by Clipper's Execute() method.
+* Bugfix: Previous update introduced a mitering bug in the
+ OffsetPolygons function.
+
+v4.6 - 29 October 2011
+* Added: Support for Positive and Negative polygon fill
+ types (in addition to the EvenOdd and NonZero fill types).
+* Bugfix: The OffsetPolygons function was generating the
+ occasional artefact when 'shrinking' polygons.
+
+v4.5.5 - 8 October 2011
+* Bugfix: Fixed an obscure bug in Clipper's JoinCommonEdges
+ method.
+* Update: Replaced IsClockwise function with Orientation
+ function. The orientation issues affecting OffsetPolygons
+ should now be finally resolved.
+* Change: The Area function once again returns a signed value.
+
+v4.5.1 - 28 September 2011
+* Deleted: The UseFullCoordinateRange property has been
+ deleted since integer range is now managed implicitly.
+* BugFix: Minor bug in OffsetPolygon mitering.
+* Change: C# JoinType enum moved from Clipper class to
+ ClipperLib namespace.
+* Change: The Area function now returns the absolute area
+ (irrespective of orientation).
+* Change: The IsClockwise function now requires a second
+ parameter - YAxisPositiveUpward - to accommodate displays
+ with Y-axis oriented in either direction
+
+v4.4.4 - 10 September 2011
+* Change: Deleted jtButt from JoinType (used by the
+ OffsetPolygons function).
+* BugFix: Fixed another minor bug in OffsetPolygons function.
+* Update: Further improvements to the help file
+
+v4.4.3 - 29 August 2011
+* BugFix: fixed a minor rounding issue in OffsetPolygons
+ function (affected C++ & C# translations).
+* BugFix: fixed a minor bug in OffsetPolygons' function
+ declaration (affected C++ translation only).
+* Change: 'clipper' namespace changed to 'ClipperLib'
+ namespace in both C++ and C# code to remove the ambiguity
+ between the Clipper class and the namespace. (This also
+ required numerous updates to the accompanying demos.)
+
+v4.4.2 - 26 August 2011
+* BugFix: minor bugfixes in Clipper.
+* Update: the OffsetPolygons function has been significantly
+ improved by offering 4 different join styles.
+
+v4.4.0 - 6 August 2011
+* BugFix: A number of minor bugs have been fixed that mostly
+ affected the new ExPolygons structure.
+
+v4.3.0 - 17 June 2011
+* New: ExPolygons structure that explicitly associates 'hole'
+ polygons with their 'outer' container polygons.
+* New: Execute method overloaded so the solution parameter
+ can now be either Polygons or ExPolygons.
+* BugFix: Fixed a rare bug in solution polygons orientation.
+
+v4.2.8 - 21 May 2011
+* Update: JoinCommonEdges() improved once more.
+* BugFix: Several minor bugs fixed.
+
+v4.2.6 - 1 May 2011
+* Bugfix: minor bug in SlopesEqual function.
+* Update: Merging of output polygons sharing common edges
+ has been significantly inproved
+
+v4.2.4 - 26 April 2011
+ Input polygon coordinates can now contain the full range of
+ signed 64bit integers (ie +/-9,223,372,036,854,775,807). This
+ means that floating point values can be converted to and from
+ Clipper's 64bit integer coordinates structure (IntPoint) and
+ still retain a precision of up to 18 decimal places. However,
+ since the large-integer math that supports this expanded range
+ imposes a small cost on performance (~15%), a new property
+ UseFullCoordinateRange has been added to the Clipper class to
+ allow users the choice of whether or not to use this expanded
+ coordinate range. If this property is disabled, coordinate values
+ are restricted to +/-1,500,000,000.
+
+v4.2 - 12 April 2011
+ JoinCommonEdges() code significantly improved plus other minor
+ improvements.
+
+v4.1.2 - 9 April 2011
+* Update: Minor code tidy.
+* Bugfix: Possible endless loop in JoinCommonEdges() in clipper.pas.
+
+v4.1.1 - 8 April 2011
+* Update: All polygon coordinates are now stored as 64bit integers
+ (though they're still restricted to range -1.5e9 to +1.5e9 pending
+ the inclusion of code supporting 64bit math).
+* Change: AddPolygon and AddPolygons methods now return boolean
+ values.
+* Bugfix: Bug in JoinCommonEdges() caused potential endless loop.
+* Bugfix: Bug in IsClockwise(). (C++ code only)
+
+v4.0 - 5 April 2011
+* Clipper 4 is a major rewrite of earlier versions. The biggest
+ change is that floating point values are no longer used,
+ except for the storing of edge slope values. The main benefit
+ of this is the issue of numerical robustness has been
+ addressed. Due to other major code improvements Clipper v4
+ is approximately 40% faster than Clipper v3.
+* The AddPolyPolygon method has been renamed to AddPolygons.
+* The IgnoreOrientation property has been removed.
+* The clipper_misc library has been merged back into the
+ main clipper library.
+
+v3.1.0 - 17 February 2011
+* Bugfix: Obscure bug in TClipperBase.SetDx method that caused
+ problems with very small edges ( edges <1/1000th pixel in size).
+
+v3.0.3 - 9 February 2011
+* Bugfix: Significant bug, but only in C# code.
+* Update: Minor refactoring.
+
+v3.0 - 31 January 2011
+* Update: Major rewrite of the portion of code that calculates
+ the output polygons' orientation.
+* Update: Help file significantly improved.
+* Change: Renamed ForceOrientation property to IgnoreOrientation.
+ If the orientation of output polygons is not important, or can
+ be managed separately, clipping routines can be sped up by about
+ 60% by setting IgnoreOrientation to true. Defaults to false.
+* Change: The OffsetPolygon and Area functions have been moved to
+ the new unit - clipper_misc.
+
+2.99 - 15 January 2011
+* Bugfix: Obscure bug in AddPolygon method could cause an endless loop.
+
+2.8 - 20 November 2010
+* Updated: Output polygons which previously shared a common
+ edge are now merged.
+* Changed: The orientation of outer polygons is now clockwise
+ when the display's Y axis is positive downwards (as is
+ typical for most Windows applications). Inner polygons
+ (holes) have the opposite orientation.
+* Added: Support module for Cairo Graphics Library (with demo).
+* Updated: C# and C++ demos.
+
+2.522 - 15 October 2010
+* Added C# translation (thanks to Olivier Lejeune) and
+ a link to Ruby bindings (thanks to Mike Owens).
+
+2.0 - 30 July 2010
+* Clipper now clips using both the Even-Odd (alternate) and
+ Non-Zero (winding) polygon filling rules. (Previously Clipper
+ assumed the Even-Odd rule for polygon filling.)
+
+1.4c - 16 June 2010
+* Added C++ support for AGG graphics library
+
+1.2s - 2 June 2010
+* Added C++ translation of clipper.pas
+
+1.0 - 9 May 2010 \ No newline at end of file
diff --git a/libs/clipper/clipper.cpp b/libs/clipper/clipper.cpp
new file mode 100644
index 000000000..1317a2a2a
--- /dev/null
+++ b/libs/clipper/clipper.cpp
@@ -0,0 +1,4610 @@
+/*******************************************************************************
+* *
+* Author : Angus Johnson *
+* Version : 6.1.3a *
+* Date : 22 January 2014 *
+* Website : http://www.angusj.com *
+* Copyright : Angus Johnson 2010-2014 *
+* *
+* License: *
+* Use, modification & distribution is subject to Boost Software License Ver 1. *
+* http://www.boost.org/LICENSE_1_0.txt *
+* *
+* Attributions: *
+* The code in this library is an extension of Bala Vatti's clipping algorithm: *
+* "A generic solution to polygon clipping" *
+* Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63. *
+* http://portal.acm.org/citation.cfm?id=129906 *
+* *
+* Computer graphics and geometric modeling: implementation and algorithms *
+* By Max K. Agoston *
+* Springer; 1 edition (January 4, 2005) *
+* http://books.google.com/books?q=vatti+clipping+agoston *
+* *
+* See also: *
+* "Polygon Offsetting by Computing Winding Numbers" *
+* Paper no. DETC2005-85513 pp. 565-575 *
+* ASME 2005 International Design Engineering Technical Conferences *
+* and Computers and Information in Engineering Conference (IDETC/CIE2005) *
+* September 24-28, 2005 , Long Beach, California, USA *
+* http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf *
+* *
+*******************************************************************************/
+
+/*******************************************************************************
+* *
+* This is a translation of the Delphi Clipper library and the naming style *
+* used has retained a Delphi flavour. *
+* *
+*******************************************************************************/
+
+#include "clipper.hpp"
+#include <cmath>
+#include <vector>
+#include <algorithm>
+#include <stdexcept>
+#include <cstring>
+#include <cstdlib>
+#include <ostream>
+#include <functional>
+
+namespace ClipperLib {
+
+#ifdef use_int32
+ static cInt const loRange = 46340;
+ static cInt const hiRange = 46340;
+#else
+ static cInt const loRange = 0x3FFFFFFF;
+ static cInt const hiRange = 0x3FFFFFFFFFFFFFFFLL;
+ typedef unsigned long long ulong64;
+#endif
+
+static double const pi = 3.141592653589793238;
+static double const two_pi = pi *2;
+static double const def_arc_tolerance = 0.25;
+
+enum Direction { dRightToLeft, dLeftToRight };
+
+static int const Unassigned = -1; //edge not currently 'owning' a solution
+static int const Skip = -2; //edge that would otherwise close a path
+
+#define HORIZONTAL (-1.0E+40)
+#define TOLERANCE (1.0e-20)
+#define NEAR_ZERO(val) (((val) > -TOLERANCE) && ((val) < TOLERANCE))
+
+struct TEdge {
+ IntPoint Bot;
+ IntPoint Curr;
+ IntPoint Top;
+ IntPoint Delta;
+ double Dx;
+ PolyType PolyTyp;
+ EdgeSide Side;
+ int WindDelta; //1 or -1 depending on winding direction
+ int WindCnt;
+ int WindCnt2; //winding count of the opposite polytype
+ int OutIdx;
+ TEdge *Next;
+ TEdge *Prev;
+ TEdge *NextInLML;
+ TEdge *NextInAEL;
+ TEdge *PrevInAEL;
+ TEdge *NextInSEL;
+ TEdge *PrevInSEL;
+};
+
+struct IntersectNode {
+ TEdge *Edge1;
+ TEdge *Edge2;
+ IntPoint Pt;
+};
+
+struct LocalMinima {
+ cInt Y;
+ TEdge *LeftBound;
+ TEdge *RightBound;
+ LocalMinima *Next;
+};
+
+struct OutPt;
+
+struct OutRec {
+ int Idx;
+ bool IsHole;
+ bool IsOpen;
+ OutRec *FirstLeft; //see comments in clipper.pas
+ PolyNode *PolyNd;
+ OutPt *Pts;
+ OutPt *BottomPt;
+};
+
+struct OutPt {
+ int Idx;
+ IntPoint Pt;
+ OutPt *Next;
+ OutPt *Prev;
+};
+
+struct Join {
+ OutPt *OutPt1;
+ OutPt *OutPt2;
+ IntPoint OffPt;
+};
+
+//------------------------------------------------------------------------------
+//------------------------------------------------------------------------------
+
+inline cInt Round(double val)
+{
+ if ((val < 0)) return static_cast<cInt>(val - 0.5);
+ else return static_cast<cInt>(val + 0.5);
+}
+//------------------------------------------------------------------------------
+
+inline cInt Abs(cInt val)
+{
+ return val < 0 ? -val : val;
+}
+
+//------------------------------------------------------------------------------
+// PolyTree methods ...
+//------------------------------------------------------------------------------
+
+void PolyTree::Clear()
+{
+ for (PolyNodes::size_type i = 0; i < AllNodes.size(); ++i)
+ delete AllNodes[i];
+ AllNodes.resize(0);
+ Childs.resize(0);
+}
+//------------------------------------------------------------------------------
+
+PolyNode* PolyTree::GetFirst() const
+{
+ if (!Childs.empty())
+ return Childs[0];
+ else
+ return 0;
+}
+//------------------------------------------------------------------------------
+
+int PolyTree::Total() const
+{
+ return (int)AllNodes.size();
+}
+
+//------------------------------------------------------------------------------
+// PolyNode methods ...
+//------------------------------------------------------------------------------
+
+PolyNode::PolyNode(): Childs(), Parent(0), Index(0), m_IsOpen(false)
+{
+}
+//------------------------------------------------------------------------------
+
+int PolyNode::ChildCount() const
+{
+ return (int)Childs.size();
+}
+//------------------------------------------------------------------------------
+
+void PolyNode::AddChild(PolyNode& child)
+{
+ unsigned cnt = (unsigned)Childs.size();
+ Childs.push_back(&child);
+ child.Parent = this;
+ child.Index = cnt;
+}
+//------------------------------------------------------------------------------
+
+PolyNode* PolyNode::GetNext() const
+{
+ if (!Childs.empty())
+ return Childs[0];
+ else
+ return GetNextSiblingUp();
+}
+//------------------------------------------------------------------------------
+
+PolyNode* PolyNode::GetNextSiblingUp() const
+{
+ if (!Parent) //protects against PolyTree.GetNextSiblingUp()
+ return 0;
+ else if (Index == Parent->Childs.size() - 1)
+ return Parent->GetNextSiblingUp();
+ else
+ return Parent->Childs[Index + 1];
+}
+//------------------------------------------------------------------------------
+
+bool PolyNode::IsHole() const
+{
+ bool result = true;
+ PolyNode* node = Parent;
+ while (node)
+ {
+ result = !result;
+ node = node->Parent;
+ }
+ return result;
+}
+//------------------------------------------------------------------------------
+
+bool PolyNode::IsOpen() const
+{
+ return m_IsOpen;
+}
+//------------------------------------------------------------------------------
+
+#ifndef use_int32
+
+//------------------------------------------------------------------------------
+// Int128 class (enables safe math on signed 64bit integers)
+// eg Int128 val1((cInt)9223372036854775807); //ie 2^63 -1
+// Int128 val2((cInt)9223372036854775807);
+// Int128 val3 = val1 * val2;
+// val3.AsString => "85070591730234615847396907784232501249" (8.5e+37)
+//------------------------------------------------------------------------------
+
+class Int128
+{
+ public:
+
+ cUInt lo;
+ cInt hi;
+
+ Int128(cInt _lo = 0)
+ {
+ lo = (cUInt)_lo;
+ if (_lo < 0) hi = -1; else hi = 0;
+ }
+
+
+ Int128(const Int128 &val): lo(val.lo), hi(val.hi){}
+
+ Int128(const cInt& _hi, const ulong64& _lo): lo(_lo), hi(_hi){}
+
+ Int128& operator = (const cInt &val)
+ {
+ lo = (ulong64)val;
+ if (val < 0) hi = -1; else hi = 0;
+ return *this;
+ }
+
+ bool operator == (const Int128 &val) const
+ {return (hi == val.hi && lo == val.lo);}
+
+ bool operator != (const Int128 &val) const
+ { return !(*this == val);}
+
+ bool operator > (const Int128 &val) const
+ {
+ if (hi != val.hi)
+ return hi > val.hi;
+ else
+ return lo > val.lo;
+ }
+
+ bool operator < (const Int128 &val) const
+ {
+ if (hi != val.hi)
+ return hi < val.hi;
+ else
+ return lo < val.lo;
+ }
+
+ bool operator >= (const Int128 &val) const
+ { return !(*this < val);}
+
+ bool operator <= (const Int128 &val) const
+ { return !(*this > val);}
+
+ Int128& operator += (const Int128 &rhs)
+ {
+ hi += rhs.hi;
+ lo += rhs.lo;
+ if (lo < rhs.lo) hi++;
+ return *this;
+ }
+
+ Int128 operator + (const Int128 &rhs) const
+ {
+ Int128 result(*this);
+ result+= rhs;
+ return result;
+ }
+
+ Int128& operator -= (const Int128 &rhs)
+ {
+ *this += -rhs;
+ return *this;
+ }
+
+ Int128 operator - (const Int128 &rhs) const
+ {
+ Int128 result(*this);
+ result -= rhs;
+ return result;
+ }
+
+ Int128 operator-() const //unary negation
+ {
+ if (lo == 0)
+ return Int128(-hi,0);
+ else
+ return Int128(~hi,~lo +1);
+ }
+
+ Int128 operator/ (const Int128 &rhs) const
+ {
+ if (rhs.lo == 0 && rhs.hi == 0)
+ throw "Int128 operator/: divide by zero";
+
+ bool negate = (rhs.hi < 0) != (hi < 0);
+ Int128 dividend = *this;
+ Int128 divisor = rhs;
+ if (dividend.hi < 0) dividend = -dividend;
+ if (divisor.hi < 0) divisor = -divisor;
+
+ if (divisor < dividend)
+ {
+ Int128 result = Int128(0);
+ Int128 cntr = Int128(1);
+ while (divisor.hi >= 0 && !(divisor > dividend))
+ {
+ divisor.hi <<= 1;
+ if ((cInt)divisor.lo < 0) divisor.hi++;
+ divisor.lo <<= 1;
+
+ cntr.hi <<= 1;
+ if ((cInt)cntr.lo < 0) cntr.hi++;
+ cntr.lo <<= 1;
+ }
+ divisor.lo >>= 1;
+ if ((divisor.hi & 1) == 1)
+ divisor.lo |= 0x8000000000000000LL;
+ divisor.hi = (ulong64)divisor.hi >> 1;
+
+ cntr.lo >>= 1;
+ if ((cntr.hi & 1) == 1)
+ cntr.lo |= 0x8000000000000000LL;
+ cntr.hi >>= 1;
+
+ while (cntr.hi != 0 || cntr.lo != 0)
+ {
+ if (!(dividend < divisor))
+ {
+ dividend -= divisor;
+ result.hi |= cntr.hi;
+ result.lo |= cntr.lo;
+ }
+ divisor.lo >>= 1;
+ if ((divisor.hi & 1) == 1)
+ divisor.lo |= 0x8000000000000000LL;
+ divisor.hi >>= 1;
+
+ cntr.lo >>= 1;
+ if ((cntr.hi & 1) == 1)
+ cntr.lo |= 0x8000000000000000LL;
+ cntr.hi >>= 1;
+ }
+ if (negate) result = -result;
+ return result;
+ }
+ else if (rhs.hi == this->hi && rhs.lo == this->lo)
+ return Int128(negate ? -1: 1);
+ else
+ return Int128(0);
+ }
+
+ double AsDouble() const
+ {
+ const double shift64 = 18446744073709551616.0; //2^64
+ if (hi < 0)
+ {
+ cUInt lo_ = ~lo + 1;
+ if (lo_ == 0) return (double)hi * shift64;
+ else return -(double)(lo_ + ~hi * shift64);
+ }
+ else
+ return (double)(lo + hi * shift64);
+ }
+
+};
+//------------------------------------------------------------------------------
+
+Int128 Int128Mul (cInt lhs, cInt rhs)
+{
+ bool negate = (lhs < 0) != (rhs < 0);
+
+ if (lhs < 0) lhs = -lhs;
+ ulong64 int1Hi = ulong64(lhs) >> 32;
+ ulong64 int1Lo = ulong64(lhs & 0xFFFFFFFF);
+
+ if (rhs < 0) rhs = -rhs;
+ ulong64 int2Hi = ulong64(rhs) >> 32;
+ ulong64 int2Lo = ulong64(rhs & 0xFFFFFFFF);
+
+ //nb: see comments in clipper.pas
+ ulong64 a = int1Hi * int2Hi;
+ ulong64 b = int1Lo * int2Lo;
+ ulong64 c = int1Hi * int2Lo + int1Lo * int2Hi;
+
+ Int128 tmp;
+ tmp.hi = cInt(a + (c >> 32));
+ tmp.lo = cInt(c << 32);
+ tmp.lo += cInt(b);
+ if (tmp.lo < b) tmp.hi++;
+ if (negate) tmp = -tmp;
+ return tmp;
+};
+#endif
+
+//------------------------------------------------------------------------------
+// Miscellaneous global functions
+//------------------------------------------------------------------------------
+
+bool Orientation(const Path &poly)
+{
+ return Area(poly) >= 0;
+}
+//------------------------------------------------------------------------------
+
+double Area(const Path &poly)
+{
+ int size = (int)poly.size();
+ if (size < 3) return 0;
+
+ double a = 0;
+ for (int i = 0, j = size -1; i < size; ++i)
+ {
+ a += ((double)poly[j].X + poly[i].X) * ((double)poly[j].Y - poly[i].Y);
+ j = i;
+ }
+ return -a * 0.5;
+}
+//------------------------------------------------------------------------------
+
+double Area(const OutRec &outRec)
+{
+ OutPt *op = outRec.Pts;
+ if (!op) return 0;
+ double a = 0;
+ do {
+ a += (double)(op->Prev->Pt.X + op->Pt.X) * (double)(op->Prev->Pt.Y - op->Pt.Y);
+ op = op->Next;
+ } while (op != outRec.Pts);
+ return a * 0.5;
+}
+//------------------------------------------------------------------------------
+
+bool PointIsVertex(const IntPoint &Pt, OutPt *pp)
+{
+ OutPt *pp2 = pp;
+ do
+ {
+ if (pp2->Pt == Pt) return true;
+ pp2 = pp2->Next;
+ }
+ while (pp2 != pp);
+ return false;
+}
+//------------------------------------------------------------------------------
+
+int PointInPolygon (const IntPoint &pt, const Path &path)
+{
+ //returns 0 if false, +1 if true, -1 if pt ON polygon boundary
+ //http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf
+ int result = 0;
+ size_t cnt = path.size();
+ if (cnt < 3) return 0;
+ IntPoint ip = path[0];
+ for(size_t i = 1; i <= cnt; ++i)
+ {
+ IntPoint ipNext = (i == cnt ? path[0] : path[i]);
+ if (ipNext.Y == pt.Y)
+ {
+ if ((ipNext.X == pt.X) || (ip.Y == pt.Y &&
+ ((ipNext.X > pt.X) == (ip.X < pt.X)))) return -1;
+ }
+ if ((ip.Y < pt.Y) != (ipNext.Y < pt.Y))
+ {
+ if (ip.X >= pt.X)
+ {
+ if (ipNext.X > pt.X) result = 1 - result;
+ else
+ {
+ double d = (double)(ip.X - pt.X) * (ipNext.Y - pt.Y) -
+ (double)(ipNext.X - pt.X) * (ip.Y - pt.Y);
+ if (!d) return -1;
+ if ((d > 0) == (ipNext.Y > ip.Y)) result = 1 - result;
+ }
+ } else
+ {
+ if (ipNext.X > pt.X)
+ {
+ double d = (double)(ip.X - pt.X) * (ipNext.Y - pt.Y) -
+ (double)(ipNext.X - pt.X) * (ip.Y - pt.Y);
+ if (!d) return -1;
+ if ((d > 0) == (ipNext.Y > ip.Y)) result = 1 - result;
+ }
+ }
+ }
+ ip = ipNext;
+ }
+ return result;
+}
+//------------------------------------------------------------------------------
+
+int PointInPolygon (const IntPoint &pt, OutPt *op)
+{
+ //returns 0 if false, +1 if true, -1 if pt ON polygon boundary
+ //http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf
+ int result = 0;
+ OutPt* startOp = op;
+ for(;;)
+ {
+ if (op->Next->Pt.Y == pt.Y)
+ {
+ if ((op->Next->Pt.X == pt.X) || (op->Pt.Y == pt.Y &&
+ ((op->Next->Pt.X > pt.X) == (op->Pt.X < pt.X)))) return -1;
+ }
+ if ((op->Pt.Y < pt.Y) != (op->Next->Pt.Y < pt.Y))
+ {
+ if (op->Pt.X >= pt.X)
+ {
+ if (op->Next->Pt.X > pt.X) result = 1 - result;
+ else
+ {
+ double d = (double)(op->Pt.X - pt.X) * (op->Next->Pt.Y - pt.Y) -
+ (double)(op->Next->Pt.X - pt.X) * (op->Pt.Y - pt.Y);
+ if (!d) return -1;
+ if ((d > 0) == (op->Next->Pt.Y > op->Pt.Y)) result = 1 - result;
+ }
+ } else
+ {
+ if (op->Next->Pt.X > pt.X)
+ {
+ double d = (double)(op->Pt.X - pt.X) * (op->Next->Pt.Y - pt.Y) -
+ (double)(op->Next->Pt.X - pt.X) * (op->Pt.Y - pt.Y);
+ if (!d) return -1;
+ if ((d > 0) == (op->Next->Pt.Y > op->Pt.Y)) result = 1 - result;
+ }
+ }
+ }
+ op = op->Next;
+ if (startOp == op) break;
+ }
+ return result;
+}
+//------------------------------------------------------------------------------
+
+bool Poly2ContainsPoly1(OutPt *OutPt1, OutPt *OutPt2)
+{
+ OutPt* op = OutPt1;
+ do
+ {
+ int res = PointInPolygon(op->Pt, OutPt2);
+ if (res >= 0) return res != 0;
+ op = op->Next;
+ }
+ while (op != OutPt1);
+ return true;
+}
+//----------------------------------------------------------------------
+
+bool SlopesEqual(const TEdge &e1, const TEdge &e2, bool UseFullInt64Range)
+{
+#ifndef use_int32
+ if (UseFullInt64Range)
+ return Int128Mul(e1.Delta.Y, e2.Delta.X) == Int128Mul(e1.Delta.X, e2.Delta.Y);
+ else
+#endif
+ return e1.Delta.Y * e2.Delta.X == e1.Delta.X * e2.Delta.Y;
+}
+//------------------------------------------------------------------------------
+
+bool SlopesEqual(const IntPoint pt1, const IntPoint pt2,
+ const IntPoint pt3, bool UseFullInt64Range)
+{
+#ifndef use_int32
+ if (UseFullInt64Range)
+ return Int128Mul(pt1.Y-pt2.Y, pt2.X-pt3.X) == Int128Mul(pt1.X-pt2.X, pt2.Y-pt3.Y);
+ else
+#endif
+ return (pt1.Y-pt2.Y)*(pt2.X-pt3.X) == (pt1.X-pt2.X)*(pt2.Y-pt3.Y);
+}
+//------------------------------------------------------------------------------
+
+bool SlopesEqual(const IntPoint pt1, const IntPoint pt2,
+ const IntPoint pt3, const IntPoint pt4, bool UseFullInt64Range)
+{
+#ifndef use_int32
+ if (UseFullInt64Range)
+ return Int128Mul(pt1.Y-pt2.Y, pt3.X-pt4.X) == Int128Mul(pt1.X-pt2.X, pt3.Y-pt4.Y);
+ else
+#endif
+ return (pt1.Y-pt2.Y)*(pt3.X-pt4.X) == (pt1.X-pt2.X)*(pt3.Y-pt4.Y);
+}
+//------------------------------------------------------------------------------
+
+inline bool IsHorizontal(TEdge &e)
+{
+ return e.Delta.Y == 0;
+}
+//------------------------------------------------------------------------------
+
+inline double GetDx(const IntPoint pt1, const IntPoint pt2)
+{
+ return (pt1.Y == pt2.Y) ?
+ HORIZONTAL : (double)(pt2.X - pt1.X) / (pt2.Y - pt1.Y);
+}
+//---------------------------------------------------------------------------
+
+inline void SetDx(TEdge &e)
+{
+ e.Delta.X = (e.Top.X - e.Bot.X);
+ e.Delta.Y = (e.Top.Y - e.Bot.Y);
+
+ if (e.Delta.Y == 0) e.Dx = HORIZONTAL;
+ else e.Dx = (double)(e.Delta.X) / e.Delta.Y;
+}
+//---------------------------------------------------------------------------
+
+inline void SwapSides(TEdge &Edge1, TEdge &Edge2)
+{
+ EdgeSide Side = Edge1.Side;
+ Edge1.Side = Edge2.Side;
+ Edge2.Side = Side;
+}
+//------------------------------------------------------------------------------
+
+inline void SwapPolyIndexes(TEdge &Edge1, TEdge &Edge2)
+{
+ int OutIdx = Edge1.OutIdx;
+ Edge1.OutIdx = Edge2.OutIdx;
+ Edge2.OutIdx = OutIdx;
+}
+//------------------------------------------------------------------------------
+
+inline cInt TopX(TEdge &edge, const cInt currentY)
+{
+ return ( currentY == edge.Top.Y ) ?
+ edge.Top.X : edge.Bot.X + Round(edge.Dx *(currentY - edge.Bot.Y));
+}
+//------------------------------------------------------------------------------
+
+bool IntersectPoint(TEdge &Edge1, TEdge &Edge2,
+ IntPoint &ip, bool UseFullInt64Range)
+{
+#ifdef use_xyz
+ ip.Z = 0;
+#endif
+ double b1, b2;
+ //nb: with very large coordinate values, it's possible for SlopesEqual() to
+ //return false but for the edge.Dx value be equal due to double precision rounding.
+ if (SlopesEqual(Edge1, Edge2, UseFullInt64Range) || Edge1.Dx == Edge2.Dx)
+ {
+ if (Edge2.Bot.Y > Edge1.Bot.Y) ip = Edge2.Bot;
+ else ip = Edge1.Bot;
+ return false;
+ }
+ else if (Edge1.Delta.X == 0)
+ {
+ ip.X = Edge1.Bot.X;
+ if (IsHorizontal(Edge2))
+ ip.Y = Edge2.Bot.Y;
+ else
+ {
+ b2 = Edge2.Bot.Y - (Edge2.Bot.X / Edge2.Dx);
+ ip.Y = Round(ip.X / Edge2.Dx + b2);
+ }
+ }
+ else if (Edge2.Delta.X == 0)
+ {
+ ip.X = Edge2.Bot.X;
+ if (IsHorizontal(Edge1))
+ ip.Y = Edge1.Bot.Y;
+ else
+ {
+ b1 = Edge1.Bot.Y - (Edge1.Bot.X / Edge1.Dx);
+ ip.Y = Round(ip.X / Edge1.Dx + b1);
+ }
+ }
+ else
+ {
+ b1 = Edge1.Bot.X - Edge1.Bot.Y * Edge1.Dx;
+ b2 = Edge2.Bot.X - Edge2.Bot.Y * Edge2.Dx;
+ double q = (b2-b1) / (Edge1.Dx - Edge2.Dx);
+ ip.Y = Round(q);
+ if (std::fabs(Edge1.Dx) < std::fabs(Edge2.Dx))
+ ip.X = Round(Edge1.Dx * q + b1);
+ else
+ ip.X = Round(Edge2.Dx * q + b2);
+ }
+
+ if (ip.Y < Edge1.Top.Y || ip.Y < Edge2.Top.Y)
+ {
+ if (Edge1.Top.Y > Edge2.Top.Y)
+ ip.Y = Edge1.Top.Y;
+ else
+ ip.Y = Edge2.Top.Y;
+ if (std::fabs(Edge1.Dx) < std::fabs(Edge2.Dx))
+ ip.X = TopX(Edge1, ip.Y);
+ else
+ ip.X = TopX(Edge2, ip.Y);
+ }
+ return true;
+}
+//------------------------------------------------------------------------------
+
+void ReversePolyPtLinks(OutPt *pp)
+{
+ if (!pp) return;
+ OutPt *pp1, *pp2;
+ pp1 = pp;
+ do {
+ pp2 = pp1->Next;
+ pp1->Next = pp1->Prev;
+ pp1->Prev = pp2;
+ pp1 = pp2;
+ } while( pp1 != pp );
+}
+//------------------------------------------------------------------------------
+
+void DisposeOutPts(OutPt*& pp)
+{
+ if (pp == 0) return;
+ pp->Prev->Next = 0;
+ while( pp )
+ {
+ OutPt *tmpPp = pp;
+ pp = pp->Next;
+ delete tmpPp;
+ }
+}
+//------------------------------------------------------------------------------
+
+inline void InitEdge(TEdge* e, TEdge* eNext, TEdge* ePrev, const IntPoint& Pt)
+{
+ std::memset(e, 0, sizeof(TEdge));
+ e->Next = eNext;
+ e->Prev = ePrev;
+ e->Curr = Pt;
+ e->OutIdx = Unassigned;
+}
+//------------------------------------------------------------------------------
+
+void InitEdge2(TEdge& e, PolyType Pt)
+{
+ if (e.Curr.Y >= e.Next->Curr.Y)
+ {
+ e.Bot = e.Curr;
+ e.Top = e.Next->Curr;
+ } else
+ {
+ e.Top = e.Curr;
+ e.Bot = e.Next->Curr;
+ }
+ SetDx(e);
+ e.PolyTyp = Pt;
+}
+//------------------------------------------------------------------------------
+
+TEdge* RemoveEdge(TEdge* e)
+{
+ //removes e from double_linked_list (but without removing from memory)
+ e->Prev->Next = e->Next;
+ e->Next->Prev = e->Prev;
+ TEdge* result = e->Next;
+ e->Prev = 0; //flag as removed (see ClipperBase.Clear)
+ return result;
+}
+//------------------------------------------------------------------------------
+
+inline void ReverseHorizontal(TEdge &e)
+{
+ //swap horizontal edges' Top and Bottom x's so they follow the natural
+ //progression of the bounds - ie so their xbots will align with the
+ //adjoining lower edge. [Helpful in the ProcessHorizontal() method.]
+ cInt tmp = e.Top.X;
+ e.Top.X = e.Bot.X;
+ e.Bot.X = tmp;
+#ifdef use_xyz
+ tmp = e.Top.Z;
+ e.Top.Z = e.Bot.Z;
+ e.Bot.Z = tmp;
+#endif
+}
+//------------------------------------------------------------------------------
+
+void SwapPoints(IntPoint &pt1, IntPoint &pt2)
+{
+ IntPoint tmp = pt1;
+ pt1 = pt2;
+ pt2 = tmp;
+}
+//------------------------------------------------------------------------------
+
+bool GetOverlapSegment(IntPoint pt1a, IntPoint pt1b, IntPoint pt2a,
+ IntPoint pt2b, IntPoint &pt1, IntPoint &pt2)
+{
+ //precondition: segments are Collinear.
+ if (Abs(pt1a.X - pt1b.X) > Abs(pt1a.Y - pt1b.Y))
+ {
+ if (pt1a.X > pt1b.X) SwapPoints(pt1a, pt1b);
+ if (pt2a.X > pt2b.X) SwapPoints(pt2a, pt2b);
+ if (pt1a.X > pt2a.X) pt1 = pt1a; else pt1 = pt2a;
+ if (pt1b.X < pt2b.X) pt2 = pt1b; else pt2 = pt2b;
+ return pt1.X < pt2.X;
+ } else
+ {
+ if (pt1a.Y < pt1b.Y) SwapPoints(pt1a, pt1b);
+ if (pt2a.Y < pt2b.Y) SwapPoints(pt2a, pt2b);
+ if (pt1a.Y < pt2a.Y) pt1 = pt1a; else pt1 = pt2a;
+ if (pt1b.Y > pt2b.Y) pt2 = pt1b; else pt2 = pt2b;
+ return pt1.Y > pt2.Y;
+ }
+}
+//------------------------------------------------------------------------------
+
+bool FirstIsBottomPt(const OutPt* btmPt1, const OutPt* btmPt2)
+{
+ OutPt *p = btmPt1->Prev;
+ while ((p->Pt == btmPt1->Pt) && (p != btmPt1)) p = p->Prev;
+ double dx1p = std::fabs(GetDx(btmPt1->Pt, p->Pt));
+ p = btmPt1->Next;
+ while ((p->Pt == btmPt1->Pt) && (p != btmPt1)) p = p->Next;
+ double dx1n = std::fabs(GetDx(btmPt1->Pt, p->Pt));
+
+ p = btmPt2->Prev;
+ while ((p->Pt == btmPt2->Pt) && (p != btmPt2)) p = p->Prev;
+ double dx2p = std::fabs(GetDx(btmPt2->Pt, p->Pt));
+ p = btmPt2->Next;
+ while ((p->Pt == btmPt2->Pt) && (p != btmPt2)) p = p->Next;
+ double dx2n = std::fabs(GetDx(btmPt2->Pt, p->Pt));
+ return (dx1p >= dx2p && dx1p >= dx2n) || (dx1n >= dx2p && dx1n >= dx2n);
+}
+//------------------------------------------------------------------------------
+
+OutPt* GetBottomPt(OutPt *pp)
+{
+ OutPt* dups = 0;
+ OutPt* p = pp->Next;
+ while (p != pp)
+ {
+ if (p->Pt.Y > pp->Pt.Y)
+ {
+ pp = p;
+ dups = 0;
+ }
+ else if (p->Pt.Y == pp->Pt.Y && p->Pt.X <= pp->Pt.X)
+ {
+ if (p->Pt.X < pp->Pt.X)
+ {
+ dups = 0;
+ pp = p;
+ } else
+ {
+ if (p->Next != pp && p->Prev != pp) dups = p;
+ }
+ }
+ p = p->Next;
+ }
+ if (dups)
+ {
+ //there appears to be at least 2 vertices at BottomPt so ...
+ while (dups != p)
+ {
+ if (!FirstIsBottomPt(p, dups)) pp = dups;
+ dups = dups->Next;
+ while (dups->Pt != pp->Pt) dups = dups->Next;
+ }
+ }
+ return pp;
+}
+//------------------------------------------------------------------------------
+
+bool FindSegment(OutPt* &pp, bool UseFullInt64Range,
+ IntPoint &pt1, IntPoint &pt2)
+{
+ //OutPt1 & OutPt2 => the overlap segment (if the function returns true)
+ if (!pp) return false;
+ OutPt* pp2 = pp;
+ IntPoint pt1a = pt1, pt2a = pt2;
+ do
+ {
+ if (SlopesEqual(pt1a, pt2a, pp->Pt, pp->Prev->Pt, UseFullInt64Range) &&
+ SlopesEqual(pt1a, pt2a, pp->Pt, UseFullInt64Range) &&
+ GetOverlapSegment(pt1a, pt2a, pp->Pt, pp->Prev->Pt, pt1, pt2))
+ return true;
+ pp = pp->Next;
+ }
+ while (pp != pp2);
+ return false;
+}
+//------------------------------------------------------------------------------
+
+bool Pt2IsBetweenPt1AndPt3(const IntPoint pt1,
+ const IntPoint pt2, const IntPoint pt3)
+{
+ if ((pt1 == pt3) || (pt1 == pt2) || (pt3 == pt2))
+ return false;
+ else if (pt1.X != pt3.X)
+ return (pt2.X > pt1.X) == (pt2.X < pt3.X);
+ else
+ return (pt2.Y > pt1.Y) == (pt2.Y < pt3.Y);
+}
+//------------------------------------------------------------------------------
+
+OutPt* InsertPolyPtBetween(OutPt* p1, OutPt* p2, const IntPoint Pt)
+{
+ if (p1 == p2) throw "JoinError";
+ OutPt* result = new OutPt;
+ result->Pt = Pt;
+ if (p2 == p1->Next)
+ {
+ p1->Next = result;
+ p2->Prev = result;
+ result->Next = p2;
+ result->Prev = p1;
+ } else
+ {
+ p2->Next = result;
+ p1->Prev = result;
+ result->Next = p1;
+ result->Prev = p2;
+ }
+ return result;
+}
+//------------------------------------------------------------------------------
+
+bool HorzSegmentsOverlap(const IntPoint& pt1a, const IntPoint& pt1b,
+ const IntPoint& pt2a, const IntPoint& pt2b)
+{
+ //precondition: both segments are horizontal
+ if ((pt1a.X > pt2a.X) == (pt1a.X < pt2b.X)) return true;
+ else if ((pt1b.X > pt2a.X) == (pt1b.X < pt2b.X)) return true;
+ else if ((pt2a.X > pt1a.X) == (pt2a.X < pt1b.X)) return true;
+ else if ((pt2b.X > pt1a.X) == (pt2b.X < pt1b.X)) return true;
+ else if ((pt1a.X == pt2a.X) && (pt1b.X == pt2b.X)) return true;
+ else if ((pt1a.X == pt2b.X) && (pt1b.X == pt2a.X)) return true;
+ else return false;
+}
+
+
+//------------------------------------------------------------------------------
+// ClipperBase class methods ...
+//------------------------------------------------------------------------------
+
+ClipperBase::ClipperBase() //constructor
+{
+ m_MinimaList = 0;
+ m_CurrentLM = 0;
+ m_UseFullRange = false;
+}
+//------------------------------------------------------------------------------
+
+ClipperBase::~ClipperBase() //destructor
+{
+ Clear();
+}
+//------------------------------------------------------------------------------
+
+void RangeTest(const IntPoint& Pt, bool& useFullRange)
+{
+ if (useFullRange)
+ {
+ if (Pt.X > hiRange || Pt.Y > hiRange || -Pt.X > hiRange || -Pt.Y > hiRange)
+ throw "Coordinate outside allowed range";
+ }
+ else if (Pt.X > loRange|| Pt.Y > loRange || -Pt.X > loRange || -Pt.Y > loRange)
+ {
+ useFullRange = true;
+ RangeTest(Pt, useFullRange);
+ }
+}
+//------------------------------------------------------------------------------
+
+TEdge* FindNextLocMin(TEdge* E)
+{
+ for (;;)
+ {
+ while (E->Bot != E->Prev->Bot || E->Curr == E->Top) E = E->Next;
+ if (!IsHorizontal(*E) && !IsHorizontal(*E->Prev)) break;
+ while (IsHorizontal(*E->Prev)) E = E->Prev;
+ TEdge* E2 = E;
+ while (IsHorizontal(*E)) E = E->Next;
+ if (E->Top.Y == E->Prev->Bot.Y) continue; //ie just an intermediate horz.
+ if (E2->Prev->Bot.X < E->Bot.X) E = E2;
+ break;
+ }
+ return E;
+}
+//------------------------------------------------------------------------------
+
+TEdge* ClipperBase::ProcessBound(TEdge* E, bool IsClockwise)
+{
+ TEdge *EStart = E, *Result = E;
+ TEdge *Horz = 0;
+ cInt StartX;
+ if (IsHorizontal(*E))
+ {
+ //it's possible for adjacent overlapping horz edges to start heading left
+ //before finishing right, so ...
+ if (IsClockwise) StartX = E->Prev->Bot.X;
+ else StartX = E->Next->Bot.X;
+ if (E->Bot.X != StartX) ReverseHorizontal(*E);
+ }
+
+ if (Result->OutIdx != Skip)
+ {
+ if (IsClockwise)
+ {
+ while (Result->Top.Y == Result->Next->Bot.Y && Result->Next->OutIdx != Skip)
+ Result = Result->Next;
+ if (IsHorizontal(*Result) && Result->Next->OutIdx != Skip)
+ {
+ //nb: at the top of a bound, horizontals are added to the bound
+ //only when the preceding edge attaches to the horizontal's left vertex
+ //unless a Skip edge is encountered when that becomes the top divide
+ Horz = Result;
+ while (IsHorizontal(*Horz->Prev)) Horz = Horz->Prev;
+ if (Horz->Prev->Top.X == Result->Next->Top.X)
+ {
+ if (!IsClockwise) Result = Horz->Prev;
+ }
+ else if (Horz->Prev->Top.X > Result->Next->Top.X) Result = Horz->Prev;
+ }
+ while (E != Result)
+ {
+ E->NextInLML = E->Next;
+ if (IsHorizontal(*E) && E != EStart &&
+ E->Bot.X != E->Prev->Top.X) ReverseHorizontal(*E);
+ E = E->Next;
+ }
+ if (IsHorizontal(*E) && E != EStart && E->Bot.X != E->Prev->Top.X)
+ ReverseHorizontal(*E);
+ Result = Result->Next; //move to the edge just beyond current bound
+ } else
+ {
+ while (Result->Top.Y == Result->Prev->Bot.Y && Result->Prev->OutIdx != Skip)
+ Result = Result->Prev;
+ if (IsHorizontal(*Result) && Result->Prev->OutIdx != Skip)
+ {
+ Horz = Result;
+ while (IsHorizontal(*Horz->Next)) Horz = Horz->Next;
+ if (Horz->Next->Top.X == Result->Prev->Top.X)
+ {
+ if (!IsClockwise) Result = Horz->Next;
+ }
+ else if (Horz->Next->Top.X > Result->Prev->Top.X) Result = Horz->Next;
+ }
+
+ while (E != Result)
+ {
+ E->NextInLML = E->Prev;
+ if (IsHorizontal(*E) && E != EStart && E->Bot.X != E->Next->Top.X)
+ ReverseHorizontal(*E);
+ E = E->Prev;
+ }
+ if (IsHorizontal(*E) && E != EStart && E->Bot.X != E->Next->Top.X)
+ ReverseHorizontal(*E);
+ Result = Result->Prev; //move to the edge just beyond current bound
+ }
+ }
+
+ if (Result->OutIdx == Skip)
+ {
+ //if edges still remain in the current bound beyond the skip edge then
+ //create another LocMin and call ProcessBound once more
+ E = Result;
+ if (IsClockwise)
+ {
+ while (E->Top.Y == E->Next->Bot.Y) E = E->Next;
+ //don't include top horizontals when parsing a bound a second time,
+ //they will be contained in the opposite bound ...
+ while (E != Result && IsHorizontal(*E)) E = E->Prev;
+ } else
+ {
+ while (E->Top.Y == E->Prev->Bot.Y) E = E->Prev;
+ while (E != Result && IsHorizontal(*E)) E = E->Next;
+ }
+ if (E == Result)
+ {
+ if (IsClockwise) Result = E->Next;
+ else Result = E->Prev;
+ } else
+ {
+ //there are more edges in the bound beyond result starting with E
+ if (IsClockwise)
+ E = Result->Next;
+ else
+ E = Result->Prev;
+ LocalMinima* locMin = new LocalMinima;
+ locMin->Next = 0;
+ locMin->Y = E->Bot.Y;
+ locMin->LeftBound = 0;
+ locMin->RightBound = E;
+ locMin->RightBound->WindDelta = 0;
+ Result = ProcessBound(locMin->RightBound, IsClockwise);
+ InsertLocalMinima(locMin);
+ }
+ }
+ return Result;
+}
+//------------------------------------------------------------------------------
+
+bool ClipperBase::AddPath(const Path &pg, PolyType PolyTyp, bool Closed)
+{
+#ifdef use_lines
+ if (!Closed && PolyTyp == ptClip)
+ throw clipperException("AddPath: Open paths must be subject.");
+#else
+ if (!Closed)
+ throw clipperException("AddPath: Open paths have been disabled.");
+#endif
+
+ int highI = (int)pg.size() -1;
+ if (Closed) while (highI > 0 && (pg[highI] == pg[0])) --highI;
+ while (highI > 0 && (pg[highI] == pg[highI -1])) --highI;
+ if ((Closed && highI < 2) || (!Closed && highI < 1)) return false;
+
+ //create a new edge array ...
+ TEdge *edges = new TEdge [highI +1];
+
+ bool IsFlat = true;
+ //1. Basic (first) edge initialization ...
+ try
+ {
+ edges[1].Curr = pg[1];
+ RangeTest(pg[0], m_UseFullRange);
+ RangeTest(pg[highI], m_UseFullRange);
+ InitEdge(&edges[0], &edges[1], &edges[highI], pg[0]);
+ InitEdge(&edges[highI], &edges[0], &edges[highI-1], pg[highI]);
+ for (int i = highI - 1; i >= 1; --i)
+ {
+ RangeTest(pg[i], m_UseFullRange);
+ InitEdge(&edges[i], &edges[i+1], &edges[i-1], pg[i]);
+ }
+ }
+ catch(...)
+ {
+ delete [] edges;
+ throw; //range test fails
+ }
+ TEdge *eStart = &edges[0];
+
+ //2. Remove duplicate vertices, and (when closed) collinear edges ...
+ TEdge *E = eStart, *eLoopStop = eStart;
+ for (;;)
+ {
+ if ((E->Curr == E->Next->Curr))
+ {
+ if (E == E->Next) break;
+ if (E == eStart) eStart = E->Next;
+ E = RemoveEdge(E);
+ eLoopStop = E;
+ continue;
+ }
+ if (E->Prev == E->Next)
+ break; //only two vertices
+ else if (Closed &&
+ SlopesEqual(E->Prev->Curr, E->Curr, E->Next->Curr, m_UseFullRange) &&
+ (!m_PreserveCollinear ||
+ !Pt2IsBetweenPt1AndPt3(E->Prev->Curr, E->Curr, E->Next->Curr)))
+ {
+ //Collinear edges are allowed for open paths but in closed paths
+ //the default is to merge adjacent collinear edges into a single edge.
+ //However, if the PreserveCollinear property is enabled, only overlapping
+ //collinear edges (ie spikes) will be removed from closed paths.
+ if (E == eStart) eStart = E->Next;
+ E = RemoveEdge(E);
+ E = E->Prev;
+ eLoopStop = E;
+ continue;
+ }
+ E = E->Next;
+ if (E == eLoopStop) break;
+ }
+
+ if ((!Closed && (E == E->Next)) || (Closed && (E->Prev == E->Next)))
+ {
+ delete [] edges;
+ return false;
+ }
+
+ if (!Closed)
+ {
+ m_HasOpenPaths = true;
+ eStart->Prev->OutIdx = Skip;
+ }
+
+ //3. Do second stage of edge initialization ...
+ E = eStart;
+ do
+ {
+ InitEdge2(*E, PolyTyp);
+ E = E->Next;
+ if (IsFlat && E->Curr.Y != eStart->Curr.Y) IsFlat = false;
+ }
+ while (E != eStart);
+
+ //4. Finally, add edge bounds to LocalMinima list ...
+
+ //Totally flat paths must be handled differently when adding them
+ //to LocalMinima list to avoid endless loops etc ...
+ if (IsFlat)
+ {
+ if (Closed)
+ {
+ delete [] edges;
+ return false;
+ }
+ E->Prev->OutIdx = Skip;
+ if (E->Prev->Bot.X < E->Prev->Top.X) ReverseHorizontal(*E->Prev);
+ LocalMinima* locMin = new LocalMinima();
+ locMin->Next = 0;
+ locMin->Y = E->Bot.Y;
+ locMin->LeftBound = 0;
+ locMin->RightBound = E;
+ locMin->RightBound->Side = esRight;
+ locMin->RightBound->WindDelta = 0;
+ while (E->Next->OutIdx != Skip)
+ {
+ E->NextInLML = E->Next;
+ if (E->Bot.X != E->Prev->Top.X) ReverseHorizontal(*E);
+ E = E->Next;
+ }
+ InsertLocalMinima(locMin);
+ m_edges.push_back(edges);
+ return true;
+ }
+
+ m_edges.push_back(edges);
+ bool clockwise;
+ TEdge* EMin = 0;
+ for (;;)
+ {
+ E = FindNextLocMin(E);
+ if (E == EMin) break;
+ else if (!EMin) EMin = E;
+
+ //E and E.Prev now share a local minima (left aligned if horizontal).
+ //Compare their slopes to find which starts which bound ...
+ LocalMinima* locMin = new LocalMinima;
+ locMin->Next = 0;
+ locMin->Y = E->Bot.Y;
+ if (E->Dx < E->Prev->Dx)
+ {
+ locMin->LeftBound = E->Prev;
+ locMin->RightBound = E;
+ clockwise = false; //Q.nextInLML = Q.prev
+ } else
+ {
+ locMin->LeftBound = E;
+ locMin->RightBound = E->Prev;
+ clockwise = true; //Q.nextInLML = Q.next
+ }
+ locMin->LeftBound->Side = esLeft;
+ locMin->RightBound->Side = esRight;
+
+ if (!Closed) locMin->LeftBound->WindDelta = 0;
+ else if (locMin->LeftBound->Next == locMin->RightBound)
+ locMin->LeftBound->WindDelta = -1;
+ else locMin->LeftBound->WindDelta = 1;
+ locMin->RightBound->WindDelta = -locMin->LeftBound->WindDelta;
+
+ E = ProcessBound(locMin->LeftBound, clockwise);
+ TEdge* E2 = ProcessBound(locMin->RightBound, !clockwise);
+
+ if (locMin->LeftBound->OutIdx == Skip)
+ locMin->LeftBound = 0;
+ else if (locMin->RightBound->OutIdx == Skip)
+ locMin->RightBound = 0;
+ InsertLocalMinima(locMin);
+ if (!clockwise) E = E2;
+ }
+ return true;
+}
+//------------------------------------------------------------------------------
+
+bool ClipperBase::AddPaths(const Paths &ppg, PolyType PolyTyp, bool Closed)
+{
+ bool result = false;
+ for (Paths::size_type i = 0; i < ppg.size(); ++i)
+ if (AddPath(ppg[i], PolyTyp, Closed)) result = true;
+ return result;
+}
+//------------------------------------------------------------------------------
+
+void ClipperBase::InsertLocalMinima(LocalMinima *newLm)
+{
+ if( ! m_MinimaList )
+ {
+ m_MinimaList = newLm;
+ }
+ else if( newLm->Y >= m_MinimaList->Y )
+ {
+ newLm->Next = m_MinimaList;
+ m_MinimaList = newLm;
+ } else
+ {
+ LocalMinima* tmpLm = m_MinimaList;
+ while( tmpLm->Next && ( newLm->Y < tmpLm->Next->Y ) )
+ tmpLm = tmpLm->Next;
+ newLm->Next = tmpLm->Next;
+ tmpLm->Next = newLm;
+ }
+}
+//------------------------------------------------------------------------------
+
+void ClipperBase::Clear()
+{
+ DisposeLocalMinimaList();
+ for (EdgeList::size_type i = 0; i < m_edges.size(); ++i)
+ {
+ //for each edge array in turn, find the first used edge and
+ //check for and remove any hiddenPts in each edge in the array.
+ TEdge* edges = m_edges[i];
+ delete [] edges;
+ }
+ m_edges.clear();
+ m_UseFullRange = false;
+ m_HasOpenPaths = false;
+}
+//------------------------------------------------------------------------------
+
+void ClipperBase::Reset()
+{
+ m_CurrentLM = m_MinimaList;
+ if( !m_CurrentLM ) return; //ie nothing to process
+
+ //reset all edges ...
+ LocalMinima* lm = m_MinimaList;
+ while( lm )
+ {
+ TEdge* e = lm->LeftBound;
+ if (e)
+ {
+ e->Curr = e->Bot;
+ e->Side = esLeft;
+ e->OutIdx = Unassigned;
+ }
+
+ e = lm->RightBound;
+ if (e)
+ {
+ e->Curr = e->Bot;
+ e->Side = esRight;
+ e->OutIdx = Unassigned;
+ }
+ lm = lm->Next;
+ }
+}
+//------------------------------------------------------------------------------
+
+void ClipperBase::DisposeLocalMinimaList()
+{
+ while( m_MinimaList )
+ {
+ LocalMinima* tmpLm = m_MinimaList->Next;
+ delete m_MinimaList;
+ m_MinimaList = tmpLm;
+ }
+ m_CurrentLM = 0;
+}
+//------------------------------------------------------------------------------
+
+void ClipperBase::PopLocalMinima()
+{
+ if( ! m_CurrentLM ) return;
+ m_CurrentLM = m_CurrentLM->Next;
+}
+//------------------------------------------------------------------------------
+
+IntRect ClipperBase::GetBounds()
+{
+ IntRect result;
+ LocalMinima* lm = m_MinimaList;
+ if (!lm)
+ {
+ result.left = result.top = result.right = result.bottom = 0;
+ return result;
+ }
+ result.left = lm->LeftBound->Bot.X;
+ result.top = lm->LeftBound->Bot.Y;
+ result.right = lm->LeftBound->Bot.X;
+ result.bottom = lm->LeftBound->Bot.Y;
+ while (lm)
+ {
+ if (lm->LeftBound->Bot.Y > result.bottom)
+ result.bottom = lm->LeftBound->Bot.Y;
+ TEdge* e = lm->LeftBound;
+ for (;;) {
+ TEdge* bottomE = e;
+ while (e->NextInLML)
+ {
+ if (e->Bot.X < result.left) result.left = e->Bot.X;
+ if (e->Bot.X > result.right) result.right = e->Bot.X;
+ e = e->NextInLML;
+ }
+ if (e->Bot.X < result.left) result.left = e->Bot.X;
+ if (e->Bot.X > result.right) result.right = e->Bot.X;
+ if (e->Top.X < result.left) result.left = e->Top.X;
+ if (e->Top.X > result.right) result.right = e->Top.X;
+ if (e->Top.Y < result.top) result.top = e->Top.Y;
+
+ if (bottomE == lm->LeftBound) e = lm->RightBound;
+ else break;
+ }
+ lm = lm->Next;
+ }
+ return result;
+}
+
+//------------------------------------------------------------------------------
+// TClipper methods ...
+//------------------------------------------------------------------------------
+
+Clipper::Clipper(int initOptions) : ClipperBase() //constructor
+{
+ m_ActiveEdges = 0;
+ m_SortedEdges = 0;
+ m_ExecuteLocked = false;
+ m_UseFullRange = false;
+ m_ReverseOutput = ((initOptions & ioReverseSolution) != 0);
+ m_StrictSimple = ((initOptions & ioStrictlySimple) != 0);
+ m_PreserveCollinear = ((initOptions & ioPreserveCollinear) != 0);
+ m_HasOpenPaths = false;
+#ifdef use_xyz
+ m_ZFill = 0;
+#endif
+}
+//------------------------------------------------------------------------------
+
+Clipper::~Clipper() //destructor
+{
+ Clear();
+ m_Scanbeam.clear();
+}
+//------------------------------------------------------------------------------
+
+#ifdef use_xyz
+void Clipper::ZFillFunction(TZFillCallback zFillFunc)
+{
+ m_ZFill = zFillFunc;
+}
+//------------------------------------------------------------------------------
+#endif
+
+void Clipper::Reset()
+{
+ ClipperBase::Reset();
+ m_Scanbeam.clear();
+ m_ActiveEdges = 0;
+ m_SortedEdges = 0;
+ LocalMinima* lm = m_MinimaList;
+ while (lm)
+ {
+ InsertScanbeam(lm->Y);
+ lm = lm->Next;
+ }
+}
+//------------------------------------------------------------------------------
+
+bool Clipper::Execute(ClipType clipType, Paths &solution,
+ PolyFillType subjFillType, PolyFillType clipFillType)
+{
+ if( m_ExecuteLocked ) return false;
+ if (m_HasOpenPaths)
+ throw clipperException("Error: PolyTree struct is need for open path clipping.");
+ m_ExecuteLocked = true;
+ solution.resize(0);
+ m_SubjFillType = subjFillType;
+ m_ClipFillType = clipFillType;
+ m_ClipType = clipType;
+ m_UsingPolyTree = false;
+ bool succeeded = ExecuteInternal();
+ if (succeeded) BuildResult(solution);
+ DisposeAllOutRecs();
+ m_ExecuteLocked = false;
+ return succeeded;
+}
+//------------------------------------------------------------------------------
+
+bool Clipper::Execute(ClipType clipType, PolyTree& polytree,
+ PolyFillType subjFillType, PolyFillType clipFillType)
+{
+ if( m_ExecuteLocked ) return false;
+ m_ExecuteLocked = true;
+ m_SubjFillType = subjFillType;
+ m_ClipFillType = clipFillType;
+ m_ClipType = clipType;
+ m_UsingPolyTree = true;
+ bool succeeded = ExecuteInternal();
+ if (succeeded) BuildResult2(polytree);
+ DisposeAllOutRecs();
+ m_ExecuteLocked = false;
+ return succeeded;
+}
+//------------------------------------------------------------------------------
+
+void Clipper::FixHoleLinkage(OutRec &outrec)
+{
+ //skip OutRecs that (a) contain outermost polygons or
+ //(b) already have the correct owner/child linkage ...
+ if (!outrec.FirstLeft ||
+ (outrec.IsHole != outrec.FirstLeft->IsHole &&
+ outrec.FirstLeft->Pts)) return;
+
+ OutRec* orfl = outrec.FirstLeft;
+ while (orfl && ((orfl->IsHole == outrec.IsHole) || !orfl->Pts))
+ orfl = orfl->FirstLeft;
+ outrec.FirstLeft = orfl;
+}
+//------------------------------------------------------------------------------
+
+bool Clipper::ExecuteInternal()
+{
+ bool succeeded = true;
+ try {
+ Reset();
+ if (!m_CurrentLM) return false;
+ cInt botY = PopScanbeam();
+ do {
+ InsertLocalMinimaIntoAEL(botY);
+ ClearGhostJoins();
+ ProcessHorizontals(false);
+ if (m_Scanbeam.empty()) break;
+ cInt topY = PopScanbeam();
+ succeeded = ProcessIntersections(botY, topY);
+ if (!succeeded) break;
+ ProcessEdgesAtTopOfScanbeam(topY);
+ botY = topY;
+ } while (!m_Scanbeam.empty() || m_CurrentLM);
+ }
+ catch(...)
+ {
+ succeeded = false;
+ }
+
+ if (succeeded)
+ {
+ //fix orientations ...
+ for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
+ {
+ OutRec *outRec = m_PolyOuts[i];
+ if (!outRec->Pts || outRec->IsOpen) continue;
+ if ((outRec->IsHole ^ m_ReverseOutput) == (Area(*outRec) > 0))
+ ReversePolyPtLinks(outRec->Pts);
+ }
+
+ if (!m_Joins.empty()) JoinCommonEdges();
+
+ //unfortunately FixupOutPolygon() must be done after JoinCommonEdges()
+ for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
+ {
+ OutRec *outRec = m_PolyOuts[i];
+ if (outRec->Pts && !outRec->IsOpen)
+ FixupOutPolygon(*outRec);
+ }
+
+ if (m_StrictSimple) DoSimplePolygons();
+ }
+
+ ClearJoins();
+ ClearGhostJoins();
+ return succeeded;
+}
+//------------------------------------------------------------------------------
+
+void Clipper::InsertScanbeam(const cInt Y)
+{
+ m_Scanbeam.insert(Y);
+}
+//------------------------------------------------------------------------------
+
+cInt Clipper::PopScanbeam()
+{
+ cInt Y = *m_Scanbeam.begin();
+ m_Scanbeam.erase(m_Scanbeam.begin());
+ return Y;
+}
+//------------------------------------------------------------------------------
+
+void Clipper::DisposeAllOutRecs(){
+ for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
+ DisposeOutRec(i);
+ m_PolyOuts.clear();
+}
+//------------------------------------------------------------------------------
+
+void Clipper::DisposeOutRec(PolyOutList::size_type index)
+{
+ OutRec *outRec = m_PolyOuts[index];
+ if (outRec->Pts) DisposeOutPts(outRec->Pts);
+ delete outRec;
+ m_PolyOuts[index] = 0;
+}
+//------------------------------------------------------------------------------
+
+void Clipper::SetWindingCount(TEdge &edge)
+{
+ TEdge *e = edge.PrevInAEL;
+ //find the edge of the same polytype that immediately preceeds 'edge' in AEL
+ while (e && ((e->PolyTyp != edge.PolyTyp) || (e->WindDelta == 0))) e = e->PrevInAEL;
+ if (!e)
+ {
+ edge.WindCnt = (edge.WindDelta == 0 ? 1 : edge.WindDelta);
+ edge.WindCnt2 = 0;
+ e = m_ActiveEdges; //ie get ready to calc WindCnt2
+ }
+ else if (edge.WindDelta == 0 && m_ClipType != ctUnion)
+ {
+ edge.WindCnt = 1;
+ edge.WindCnt2 = e->WindCnt2;
+ e = e->NextInAEL; //ie get ready to calc WindCnt2
+ }
+ else if (IsEvenOddFillType(edge))
+ {
+ //EvenOdd filling ...
+ if (edge.WindDelta == 0)
+ {
+ //are we inside a subj polygon ...
+ bool Inside = true;
+ TEdge *e2 = e->PrevInAEL;
+ while (e2)
+ {
+ if (e2->PolyTyp == e->PolyTyp && e2->WindDelta != 0)
+ Inside = !Inside;
+ e2 = e2->PrevInAEL;
+ }
+ edge.WindCnt = (Inside ? 0 : 1);
+ }
+ else
+ {
+ edge.WindCnt = edge.WindDelta;
+ }
+ edge.WindCnt2 = e->WindCnt2;
+ e = e->NextInAEL; //ie get ready to calc WindCnt2
+ }
+ else
+ {
+ //nonZero, Positive or Negative filling ...
+ if (e->WindCnt * e->WindDelta < 0)
+ {
+ //prev edge is 'decreasing' WindCount (WC) toward zero
+ //so we're outside the previous polygon ...
+ if (Abs(e->WindCnt) > 1)
+ {
+ //outside prev poly but still inside another.
+ //when reversing direction of prev poly use the same WC
+ if (e->WindDelta * edge.WindDelta < 0) edge.WindCnt = e->WindCnt;
+ //otherwise continue to 'decrease' WC ...
+ else edge.WindCnt = e->WindCnt + edge.WindDelta;
+ }
+ else
+ //now outside all polys of same polytype so set own WC ...
+ edge.WindCnt = (edge.WindDelta == 0 ? 1 : edge.WindDelta);
+ } else
+ {
+ //prev edge is 'increasing' WindCount (WC) away from zero
+ //so we're inside the previous polygon ...
+ if (edge.WindDelta == 0)
+ edge.WindCnt = (e->WindCnt < 0 ? e->WindCnt - 1 : e->WindCnt + 1);
+ //if wind direction is reversing prev then use same WC
+ else if (e->WindDelta * edge.WindDelta < 0) edge.WindCnt = e->WindCnt;
+ //otherwise add to WC ...
+ else edge.WindCnt = e->WindCnt + edge.WindDelta;
+ }
+ edge.WindCnt2 = e->WindCnt2;
+ e = e->NextInAEL; //ie get ready to calc WindCnt2
+ }
+
+ //update WindCnt2 ...
+ if (IsEvenOddAltFillType(edge))
+ {
+ //EvenOdd filling ...
+ while (e != &edge)
+ {
+ if (e->WindDelta != 0)
+ edge.WindCnt2 = (edge.WindCnt2 == 0 ? 1 : 0);
+ e = e->NextInAEL;
+ }
+ } else
+ {
+ //nonZero, Positive or Negative filling ...
+ while ( e != &edge )
+ {
+ edge.WindCnt2 += e->WindDelta;
+ e = e->NextInAEL;
+ }
+ }
+}
+//------------------------------------------------------------------------------
+
+bool Clipper::IsEvenOddFillType(const TEdge& edge) const
+{
+ if (edge.PolyTyp == ptSubject)
+ return m_SubjFillType == pftEvenOdd; else
+ return m_ClipFillType == pftEvenOdd;
+}
+//------------------------------------------------------------------------------
+
+bool Clipper::IsEvenOddAltFillType(const TEdge& edge) const
+{
+ if (edge.PolyTyp == ptSubject)
+ return m_ClipFillType == pftEvenOdd; else
+ return m_SubjFillType == pftEvenOdd;
+}
+//------------------------------------------------------------------------------
+
+bool Clipper::IsContributing(const TEdge& edge) const
+{
+ PolyFillType pft, pft2;
+ if (edge.PolyTyp == ptSubject)
+ {
+ pft = m_SubjFillType;
+ pft2 = m_ClipFillType;
+ } else
+ {
+ pft = m_ClipFillType;
+ pft2 = m_SubjFillType;
+ }
+
+ switch(pft)
+ {
+ case pftEvenOdd:
+ //return false if a subj line has been flagged as inside a subj polygon
+ if (edge.WindDelta == 0 && edge.WindCnt != 1) return false;
+ break;
+ case pftNonZero:
+ if (Abs(edge.WindCnt) != 1) return false;
+ break;
+ case pftPositive:
+ if (edge.WindCnt != 1) return false;
+ break;
+ default: //pftNegative
+ if (edge.WindCnt != -1) return false;
+ }
+
+ switch(m_ClipType)
+ {
+ case ctIntersection:
+ switch(pft2)
+ {
+ case pftEvenOdd:
+ case pftNonZero:
+ return (edge.WindCnt2 != 0);
+ case pftPositive:
+ return (edge.WindCnt2 > 0);
+ default:
+ return (edge.WindCnt2 < 0);
+ }
+ break;
+ case ctUnion:
+ switch(pft2)
+ {
+ case pftEvenOdd:
+ case pftNonZero:
+ return (edge.WindCnt2 == 0);
+ case pftPositive:
+ return (edge.WindCnt2 <= 0);
+ default:
+ return (edge.WindCnt2 >= 0);
+ }
+ break;
+ case ctDifference:
+ if (edge.PolyTyp == ptSubject)
+ switch(pft2)
+ {
+ case pftEvenOdd:
+ case pftNonZero:
+ return (edge.WindCnt2 == 0);
+ case pftPositive:
+ return (edge.WindCnt2 <= 0);
+ default:
+ return (edge.WindCnt2 >= 0);
+ }
+ else
+ switch(pft2)
+ {
+ case pftEvenOdd:
+ case pftNonZero:
+ return (edge.WindCnt2 != 0);
+ case pftPositive:
+ return (edge.WindCnt2 > 0);
+ default:
+ return (edge.WindCnt2 < 0);
+ }
+ break;
+ case ctXor:
+ if (edge.WindDelta == 0) //XOr always contributing unless open
+ switch(pft2)
+ {
+ case pftEvenOdd:
+ case pftNonZero:
+ return (edge.WindCnt2 == 0);
+ case pftPositive:
+ return (edge.WindCnt2 <= 0);
+ default:
+ return (edge.WindCnt2 >= 0);
+ }
+ else
+ return true;
+ break;
+ default:
+ return true;
+ }
+}
+//------------------------------------------------------------------------------
+
+OutPt* Clipper::AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &Pt)
+{
+ OutPt* result;
+ TEdge *e, *prevE;
+ if (IsHorizontal(*e2) || ( e1->Dx > e2->Dx ))
+ {
+ result = AddOutPt(e1, Pt);
+ e2->OutIdx = e1->OutIdx;
+ e1->Side = esLeft;
+ e2->Side = esRight;
+ e = e1;
+ if (e->PrevInAEL == e2)
+ prevE = e2->PrevInAEL;
+ else
+ prevE = e->PrevInAEL;
+ } else
+ {
+ result = AddOutPt(e2, Pt);
+ e1->OutIdx = e2->OutIdx;
+ e1->Side = esRight;
+ e2->Side = esLeft;
+ e = e2;
+ if (e->PrevInAEL == e1)
+ prevE = e1->PrevInAEL;
+ else
+ prevE = e->PrevInAEL;
+ }
+
+ if (prevE && prevE->OutIdx >= 0 &&
+ (TopX(*prevE, Pt.Y) == TopX(*e, Pt.Y)) &&
+ SlopesEqual(*e, *prevE, m_UseFullRange) &&
+ (e->WindDelta != 0) && (prevE->WindDelta != 0))
+ {
+ OutPt* outPt = AddOutPt(prevE, Pt);
+ AddJoin(result, outPt, e->Top);
+ }
+ return result;
+}
+//------------------------------------------------------------------------------
+
+void Clipper::AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &Pt)
+{
+ AddOutPt( e1, Pt );
+ if (e2->WindDelta == 0) AddOutPt(e2, Pt);
+ if( e1->OutIdx == e2->OutIdx )
+ {
+ e1->OutIdx = Unassigned;
+ e2->OutIdx = Unassigned;
+ }
+ else if (e1->OutIdx < e2->OutIdx)
+ AppendPolygon(e1, e2);
+ else
+ AppendPolygon(e2, e1);
+}
+//------------------------------------------------------------------------------
+
+void Clipper::AddEdgeToSEL(TEdge *edge)
+{
+ //SEL pointers in PEdge are reused to build a list of horizontal edges.
+ //However, we don't need to worry about order with horizontal edge processing.
+ if( !m_SortedEdges )
+ {
+ m_SortedEdges = edge;
+ edge->PrevInSEL = 0;
+ edge->NextInSEL = 0;
+ }
+ else
+ {
+ edge->NextInSEL = m_SortedEdges;
+ edge->PrevInSEL = 0;
+ m_SortedEdges->PrevInSEL = edge;
+ m_SortedEdges = edge;
+ }
+}
+//------------------------------------------------------------------------------
+
+void Clipper::CopyAELToSEL()
+{
+ TEdge* e = m_ActiveEdges;
+ m_SortedEdges = e;
+ while ( e )
+ {
+ e->PrevInSEL = e->PrevInAEL;
+ e->NextInSEL = e->NextInAEL;
+ e = e->NextInAEL;
+ }
+}
+//------------------------------------------------------------------------------
+
+void Clipper::AddJoin(OutPt *op1, OutPt *op2, const IntPoint OffPt)
+{
+ Join* j = new Join;
+ j->OutPt1 = op1;
+ j->OutPt2 = op2;
+ j->OffPt = OffPt;
+ m_Joins.push_back(j);
+}
+//------------------------------------------------------------------------------
+
+void Clipper::ClearJoins()
+{
+ for (JoinList::size_type i = 0; i < m_Joins.size(); i++)
+ delete m_Joins[i];
+ m_Joins.resize(0);
+}
+//------------------------------------------------------------------------------
+
+void Clipper::ClearGhostJoins()
+{
+ for (JoinList::size_type i = 0; i < m_GhostJoins.size(); i++)
+ delete m_GhostJoins[i];
+ m_GhostJoins.resize(0);
+}
+//------------------------------------------------------------------------------
+
+void Clipper::AddGhostJoin(OutPt *op, const IntPoint OffPt)
+{
+ Join* j = new Join;
+ j->OutPt1 = op;
+ j->OutPt2 = 0;
+ j->OffPt = OffPt;
+ m_GhostJoins.push_back(j);
+}
+//------------------------------------------------------------------------------
+
+void Clipper::InsertLocalMinimaIntoAEL(const cInt botY)
+{
+ while( m_CurrentLM && ( m_CurrentLM->Y == botY ) )
+ {
+ TEdge* lb = m_CurrentLM->LeftBound;
+ TEdge* rb = m_CurrentLM->RightBound;
+ PopLocalMinima();
+ OutPt *Op1 = 0;
+ if (!lb)
+ {
+ //nb: don't insert LB into either AEL or SEL
+ InsertEdgeIntoAEL(rb, 0);
+ SetWindingCount(*rb);
+ if (IsContributing(*rb))
+ Op1 = AddOutPt(rb, rb->Bot);
+ }
+ else if (!rb)
+ {
+ InsertEdgeIntoAEL(lb, 0);
+ SetWindingCount(*lb);
+ if (IsContributing(*lb))
+ Op1 = AddOutPt(lb, lb->Bot);
+ InsertScanbeam(lb->Top.Y);
+ }
+ else
+ {
+ InsertEdgeIntoAEL(lb, 0);
+ InsertEdgeIntoAEL(rb, lb);
+ SetWindingCount( *lb );
+ rb->WindCnt = lb->WindCnt;
+ rb->WindCnt2 = lb->WindCnt2;
+ if (IsContributing(*lb))
+ Op1 = AddLocalMinPoly(lb, rb, lb->Bot);
+ InsertScanbeam(lb->Top.Y);
+ }
+
+ if (rb)
+ {
+ if(IsHorizontal(*rb)) AddEdgeToSEL(rb);
+ else InsertScanbeam( rb->Top.Y );
+ }
+
+ if (!lb || !rb) continue;
+
+ //if any output polygons share an edge, they'll need joining later ...
+ if (Op1 && IsHorizontal(*rb) &&
+ m_GhostJoins.size() > 0 && (rb->WindDelta != 0))
+ {
+ for (JoinList::size_type i = 0; i < m_GhostJoins.size(); ++i)
+ {
+ Join* jr = m_GhostJoins[i];
+ //if the horizontal Rb and a 'ghost' horizontal overlap, then convert
+ //the 'ghost' join to a real join ready for later ...
+ if (HorzSegmentsOverlap(jr->OutPt1->Pt, jr->OffPt, rb->Bot, rb->Top))
+ AddJoin(jr->OutPt1, Op1, jr->OffPt);
+ }
+ }
+
+ if (lb->OutIdx >= 0 && lb->PrevInAEL &&
+ lb->PrevInAEL->Curr.X == lb->Bot.X &&
+ lb->PrevInAEL->OutIdx >= 0 &&
+ SlopesEqual(*lb->PrevInAEL, *lb, m_UseFullRange) &&
+ (lb->WindDelta != 0) && (lb->PrevInAEL->WindDelta != 0))
+ {
+ OutPt *Op2 = AddOutPt(lb->PrevInAEL, lb->Bot);
+ AddJoin(Op1, Op2, lb->Top);
+ }
+
+ if(lb->NextInAEL != rb)
+ {
+
+ if (rb->OutIdx >= 0 && rb->PrevInAEL->OutIdx >= 0 &&
+ SlopesEqual(*rb->PrevInAEL, *rb, m_UseFullRange) &&
+ (rb->WindDelta != 0) && (rb->PrevInAEL->WindDelta != 0))
+ {
+ OutPt *Op2 = AddOutPt(rb->PrevInAEL, rb->Bot);
+ AddJoin(Op1, Op2, rb->Top);
+ }
+
+ TEdge* e = lb->NextInAEL;
+ if (e)
+ {
+ while( e != rb )
+ {
+ //nb: For calculating winding counts etc, IntersectEdges() assumes
+ //that param1 will be to the Right of param2 ABOVE the intersection ...
+ IntersectEdges(rb , e , lb->Curr); //order important here
+ e = e->NextInAEL;
+ }
+ }
+ }
+
+ }
+}
+//------------------------------------------------------------------------------
+
+void Clipper::DeleteFromAEL(TEdge *e)
+{
+ TEdge* AelPrev = e->PrevInAEL;
+ TEdge* AelNext = e->NextInAEL;
+ if( !AelPrev && !AelNext && (e != m_ActiveEdges) ) return; //already deleted
+ if( AelPrev ) AelPrev->NextInAEL = AelNext;
+ else m_ActiveEdges = AelNext;
+ if( AelNext ) AelNext->PrevInAEL = AelPrev;
+ e->NextInAEL = 0;
+ e->PrevInAEL = 0;
+}
+//------------------------------------------------------------------------------
+
+void Clipper::DeleteFromSEL(TEdge *e)
+{
+ TEdge* SelPrev = e->PrevInSEL;
+ TEdge* SelNext = e->NextInSEL;
+ if( !SelPrev && !SelNext && (e != m_SortedEdges) ) return; //already deleted
+ if( SelPrev ) SelPrev->NextInSEL = SelNext;
+ else m_SortedEdges = SelNext;
+ if( SelNext ) SelNext->PrevInSEL = SelPrev;
+ e->NextInSEL = 0;
+ e->PrevInSEL = 0;
+}
+//------------------------------------------------------------------------------
+
+#ifdef use_xyz
+
+void Clipper::SetZ(IntPoint& pt, TEdge& e)
+{
+ pt.Z = 0;
+ if (m_ZFill)
+ {
+ //put the 'preferred' point as first parameter ...
+ if (e.OutIdx < 0)
+ (*m_ZFill)(e.Bot, e.Top, pt); //outside a path so presume entering
+ else
+ (*m_ZFill)(e.Top, e.Bot, pt); //inside a path so presume exiting
+ }
+}
+//------------------------------------------------------------------------------
+#endif
+
+void Clipper::IntersectEdges(TEdge *e1, TEdge *e2,
+ const IntPoint &Pt, bool protect)
+{
+ //e1 will be to the Left of e2 BELOW the intersection. Therefore e1 is before
+ //e2 in AEL except when e1 is being inserted at the intersection point ...
+ bool e1stops = !protect && !e1->NextInLML &&
+ e1->Top.X == Pt.X && e1->Top.Y == Pt.Y;
+ bool e2stops = !protect && !e2->NextInLML &&
+ e2->Top.X == Pt.X && e2->Top.Y == Pt.Y;
+ bool e1Contributing = ( e1->OutIdx >= 0 );
+ bool e2Contributing = ( e2->OutIdx >= 0 );
+
+#ifdef use_lines
+ //if either edge is on an OPEN path ...
+ if (e1->WindDelta == 0 || e2->WindDelta == 0)
+ {
+ //ignore subject-subject open path intersections UNLESS they
+ //are both open paths, AND they are both 'contributing maximas' ...
+ if (e1->WindDelta == 0 && e2->WindDelta == 0)
+ {
+ if ((e1stops || e2stops) && e1Contributing && e2Contributing)
+ AddLocalMaxPoly(e1, e2, Pt);
+ }
+
+ //if intersecting a subj line with a subj poly ...
+ else if (e1->PolyTyp == e2->PolyTyp &&
+ e1->WindDelta != e2->WindDelta && m_ClipType == ctUnion)
+ {
+ if (e1->WindDelta == 0)
+ {
+ if (e2Contributing)
+ {
+ AddOutPt(e1, Pt);
+ if (e1Contributing) e1->OutIdx = Unassigned;
+ }
+ }
+ else
+ {
+ if (e1Contributing)
+ {
+ AddOutPt(e2, Pt);
+ if (e2Contributing) e2->OutIdx = Unassigned;
+ }
+ }
+ }
+ else if (e1->PolyTyp != e2->PolyTyp)
+ {
+ //toggle subj open path OutIdx on/off when Abs(clip.WndCnt) == 1 ...
+ if ((e1->WindDelta == 0) && abs(e2->WindCnt) == 1 &&
+ (m_ClipType != ctUnion || e2->WindCnt2 == 0))
+ {
+ AddOutPt(e1, Pt);
+ if (e1Contributing) e1->OutIdx = Unassigned;
+ }
+ else if ((e2->WindDelta == 0) && (abs(e1->WindCnt) == 1) &&
+ (m_ClipType != ctUnion || e1->WindCnt2 == 0))
+ {
+ AddOutPt(e2, Pt);
+ if (e2Contributing) e2->OutIdx = Unassigned;
+ }
+ }
+
+ if (e1stops)
+ if (e1->OutIdx < 0) DeleteFromAEL(e1);
+ else throw clipperException("Error intersecting polylines");
+ if (e2stops)
+ if (e2->OutIdx < 0) DeleteFromAEL(e2);
+ else throw clipperException("Error intersecting polylines");
+ return;
+ }
+#endif
+
+ //update winding counts...
+ //assumes that e1 will be to the Right of e2 ABOVE the intersection
+ if ( e1->PolyTyp == e2->PolyTyp )
+ {
+ if ( IsEvenOddFillType( *e1) )
+ {
+ int oldE1WindCnt = e1->WindCnt;
+ e1->WindCnt = e2->WindCnt;
+ e2->WindCnt = oldE1WindCnt;
+ } else
+ {
+ if (e1->WindCnt + e2->WindDelta == 0 ) e1->WindCnt = -e1->WindCnt;
+ else e1->WindCnt += e2->WindDelta;
+ if ( e2->WindCnt - e1->WindDelta == 0 ) e2->WindCnt = -e2->WindCnt;
+ else e2->WindCnt -= e1->WindDelta;
+ }
+ } else
+ {
+ if (!IsEvenOddFillType(*e2)) e1->WindCnt2 += e2->WindDelta;
+ else e1->WindCnt2 = ( e1->WindCnt2 == 0 ) ? 1 : 0;
+ if (!IsEvenOddFillType(*e1)) e2->WindCnt2 -= e1->WindDelta;
+ else e2->WindCnt2 = ( e2->WindCnt2 == 0 ) ? 1 : 0;
+ }
+
+ PolyFillType e1FillType, e2FillType, e1FillType2, e2FillType2;
+ if (e1->PolyTyp == ptSubject)
+ {
+ e1FillType = m_SubjFillType;
+ e1FillType2 = m_ClipFillType;
+ } else
+ {
+ e1FillType = m_ClipFillType;
+ e1FillType2 = m_SubjFillType;
+ }
+ if (e2->PolyTyp == ptSubject)
+ {
+ e2FillType = m_SubjFillType;
+ e2FillType2 = m_ClipFillType;
+ } else
+ {
+ e2FillType = m_ClipFillType;
+ e2FillType2 = m_SubjFillType;
+ }
+
+ cInt e1Wc, e2Wc;
+ switch (e1FillType)
+ {
+ case pftPositive: e1Wc = e1->WindCnt; break;
+ case pftNegative: e1Wc = -e1->WindCnt; break;
+ default: e1Wc = Abs(e1->WindCnt);
+ }
+ switch(e2FillType)
+ {
+ case pftPositive: e2Wc = e2->WindCnt; break;
+ case pftNegative: e2Wc = -e2->WindCnt; break;
+ default: e2Wc = Abs(e2->WindCnt);
+ }
+
+ if ( e1Contributing && e2Contributing )
+ {
+ if ( e1stops || e2stops ||
+ (e1Wc != 0 && e1Wc != 1) || (e2Wc != 0 && e2Wc != 1) ||
+ (e1->PolyTyp != e2->PolyTyp && m_ClipType != ctXor) )
+ AddLocalMaxPoly(e1, e2, Pt);
+ else
+ {
+ AddOutPt(e1, Pt);
+ AddOutPt(e2, Pt);
+ SwapSides( *e1 , *e2 );
+ SwapPolyIndexes( *e1 , *e2 );
+ }
+ }
+ else if ( e1Contributing )
+ {
+ if (e2Wc == 0 || e2Wc == 1)
+ {
+ AddOutPt(e1, Pt);
+ SwapSides(*e1, *e2);
+ SwapPolyIndexes(*e1, *e2);
+ }
+ }
+ else if ( e2Contributing )
+ {
+ if (e1Wc == 0 || e1Wc == 1)
+ {
+ AddOutPt(e2, Pt);
+ SwapSides(*e1, *e2);
+ SwapPolyIndexes(*e1, *e2);
+ }
+ }
+ else if ( (e1Wc == 0 || e1Wc == 1) &&
+ (e2Wc == 0 || e2Wc == 1) && !e1stops && !e2stops )
+ {
+ //neither edge is currently contributing ...
+
+ cInt e1Wc2, e2Wc2;
+ switch (e1FillType2)
+ {
+ case pftPositive: e1Wc2 = e1->WindCnt2; break;
+ case pftNegative : e1Wc2 = -e1->WindCnt2; break;
+ default: e1Wc2 = Abs(e1->WindCnt2);
+ }
+ switch (e2FillType2)
+ {
+ case pftPositive: e2Wc2 = e2->WindCnt2; break;
+ case pftNegative: e2Wc2 = -e2->WindCnt2; break;
+ default: e2Wc2 = Abs(e2->WindCnt2);
+ }
+
+ if (e1->PolyTyp != e2->PolyTyp)
+ AddLocalMinPoly(e1, e2, Pt);
+ else if (e1Wc == 1 && e2Wc == 1)
+ switch( m_ClipType ) {
+ case ctIntersection:
+ if (e1Wc2 > 0 && e2Wc2 > 0)
+ AddLocalMinPoly(e1, e2, Pt);
+ break;
+ case ctUnion:
+ if ( e1Wc2 <= 0 && e2Wc2 <= 0 )
+ AddLocalMinPoly(e1, e2, Pt);
+ break;
+ case ctDifference:
+ if (((e1->PolyTyp == ptClip) && (e1Wc2 > 0) && (e2Wc2 > 0)) ||
+ ((e1->PolyTyp == ptSubject) && (e1Wc2 <= 0) && (e2Wc2 <= 0)))
+ AddLocalMinPoly(e1, e2, Pt);
+ break;
+ case ctXor:
+ AddLocalMinPoly(e1, e2, Pt);
+ }
+ else
+ SwapSides( *e1, *e2 );
+ }
+
+ if( (e1stops != e2stops) &&
+ ( (e1stops && (e1->OutIdx >= 0)) || (e2stops && (e2->OutIdx >= 0)) ) )
+ {
+ SwapSides( *e1, *e2 );
+ SwapPolyIndexes( *e1, *e2 );
+ }
+
+ //finally, delete any non-contributing maxima edges ...
+ if( e1stops ) DeleteFromAEL( e1 );
+ if( e2stops ) DeleteFromAEL( e2 );
+}
+//------------------------------------------------------------------------------
+
+void Clipper::SetHoleState(TEdge *e, OutRec *outrec)
+{
+ bool IsHole = false;
+ TEdge *e2 = e->PrevInAEL;
+ while (e2)
+ {
+ if (e2->OutIdx >= 0 && e2->WindDelta != 0)
+ {
+ IsHole = !IsHole;
+ if (! outrec->FirstLeft)
+ outrec->FirstLeft = m_PolyOuts[e2->OutIdx];
+ }
+ e2 = e2->PrevInAEL;
+ }
+ if (IsHole) outrec->IsHole = true;
+}
+//------------------------------------------------------------------------------
+
+OutRec* GetLowermostRec(OutRec *outRec1, OutRec *outRec2)
+{
+ //work out which polygon fragment has the correct hole state ...
+ if (!outRec1->BottomPt)
+ outRec1->BottomPt = GetBottomPt(outRec1->Pts);
+ if (!outRec2->BottomPt)
+ outRec2->BottomPt = GetBottomPt(outRec2->Pts);
+ OutPt *OutPt1 = outRec1->BottomPt;
+ OutPt *OutPt2 = outRec2->BottomPt;
+ if (OutPt1->Pt.Y > OutPt2->Pt.Y) return outRec1;
+ else if (OutPt1->Pt.Y < OutPt2->Pt.Y) return outRec2;
+ else if (OutPt1->Pt.X < OutPt2->Pt.X) return outRec1;
+ else if (OutPt1->Pt.X > OutPt2->Pt.X) return outRec2;
+ else if (OutPt1->Next == OutPt1) return outRec2;
+ else if (OutPt2->Next == OutPt2) return outRec1;
+ else if (FirstIsBottomPt(OutPt1, OutPt2)) return outRec1;
+ else return outRec2;
+}
+//------------------------------------------------------------------------------
+
+bool Param1RightOfParam2(OutRec* outRec1, OutRec* outRec2)
+{
+ do
+ {
+ outRec1 = outRec1->FirstLeft;
+ if (outRec1 == outRec2) return true;
+ } while (outRec1);
+ return false;
+}
+//------------------------------------------------------------------------------
+
+OutRec* Clipper::GetOutRec(int Idx)
+{
+ OutRec* outrec = m_PolyOuts[Idx];
+ while (outrec != m_PolyOuts[outrec->Idx])
+ outrec = m_PolyOuts[outrec->Idx];
+ return outrec;
+}
+//------------------------------------------------------------------------------
+
+void Clipper::AppendPolygon(TEdge *e1, TEdge *e2)
+{
+ //get the start and ends of both output polygons ...
+ OutRec *outRec1 = m_PolyOuts[e1->OutIdx];
+ OutRec *outRec2 = m_PolyOuts[e2->OutIdx];
+
+ OutRec *holeStateRec;
+ if (Param1RightOfParam2(outRec1, outRec2))
+ holeStateRec = outRec2;
+ else if (Param1RightOfParam2(outRec2, outRec1))
+ holeStateRec = outRec1;
+ else
+ holeStateRec = GetLowermostRec(outRec1, outRec2);
+
+ //get the start and ends of both output polygons and
+ //join e2 poly onto e1 poly and delete pointers to e2 ...
+
+ OutPt* p1_lft = outRec1->Pts;
+ OutPt* p1_rt = p1_lft->Prev;
+ OutPt* p2_lft = outRec2->Pts;
+ OutPt* p2_rt = p2_lft->Prev;
+
+ EdgeSide Side;
+ //join e2 poly onto e1 poly and delete pointers to e2 ...
+ if( e1->Side == esLeft )
+ {
+ if( e2->Side == esLeft )
+ {
+ //z y x a b c
+ ReversePolyPtLinks(p2_lft);
+ p2_lft->Next = p1_lft;
+ p1_lft->Prev = p2_lft;
+ p1_rt->Next = p2_rt;
+ p2_rt->Prev = p1_rt;
+ outRec1->Pts = p2_rt;
+ } else
+ {
+ //x y z a b c
+ p2_rt->Next = p1_lft;
+ p1_lft->Prev = p2_rt;
+ p2_lft->Prev = p1_rt;
+ p1_rt->Next = p2_lft;
+ outRec1->Pts = p2_lft;
+ }
+ Side = esLeft;
+ } else
+ {
+ if( e2->Side == esRight )
+ {
+ //a b c z y x
+ ReversePolyPtLinks(p2_lft);
+ p1_rt->Next = p2_rt;
+ p2_rt->Prev = p1_rt;
+ p2_lft->Next = p1_lft;
+ p1_lft->Prev = p2_lft;
+ } else
+ {
+ //a b c x y z
+ p1_rt->Next = p2_lft;
+ p2_lft->Prev = p1_rt;
+ p1_lft->Prev = p2_rt;
+ p2_rt->Next = p1_lft;
+ }
+ Side = esRight;
+ }
+
+ outRec1->BottomPt = 0;
+ if (holeStateRec == outRec2)
+ {
+ if (outRec2->FirstLeft != outRec1)
+ outRec1->FirstLeft = outRec2->FirstLeft;
+ outRec1->IsHole = outRec2->IsHole;
+ }
+ outRec2->Pts = 0;
+ outRec2->BottomPt = 0;
+ outRec2->FirstLeft = outRec1;
+
+ int OKIdx = e1->OutIdx;
+ int ObsoleteIdx = e2->OutIdx;
+
+ e1->OutIdx = Unassigned; //nb: safe because we only get here via AddLocalMaxPoly
+ e2->OutIdx = Unassigned;
+
+ TEdge* e = m_ActiveEdges;
+ while( e )
+ {
+ if( e->OutIdx == ObsoleteIdx )
+ {
+ e->OutIdx = OKIdx;
+ e->Side = Side;
+ break;
+ }
+ e = e->NextInAEL;
+ }
+
+ outRec2->Idx = outRec1->Idx;
+}
+//------------------------------------------------------------------------------
+
+OutRec* Clipper::CreateOutRec()
+{
+ OutRec* result = new OutRec;
+ result->IsHole = false;
+ result->IsOpen = false;
+ result->FirstLeft = 0;
+ result->Pts = 0;
+ result->BottomPt = 0;
+ result->PolyNd = 0;
+ m_PolyOuts.push_back(result);
+ result->Idx = (int)m_PolyOuts.size()-1;
+ return result;
+}
+//------------------------------------------------------------------------------
+
+OutPt* Clipper::AddOutPt(TEdge *e, const IntPoint &pt)
+{
+ bool ToFront = (e->Side == esLeft);
+ if( e->OutIdx < 0 )
+ {
+ OutRec *outRec = CreateOutRec();
+ outRec->IsOpen = (e->WindDelta == 0);
+ OutPt* newOp = new OutPt;
+ outRec->Pts = newOp;
+ newOp->Idx = outRec->Idx;
+ newOp->Pt = pt;
+ newOp->Next = newOp;
+ newOp->Prev = newOp;
+ if (!outRec->IsOpen)
+ SetHoleState(e, outRec);
+#ifdef use_xyz
+ if (pt == e->Bot) newOp->Pt = e->Bot;
+ else if (pt == e->Top) newOp->Pt = e->Top;
+ else SetZ(newOp->Pt, *e);
+#endif
+ e->OutIdx = outRec->Idx; //nb: do this after SetZ !
+ return newOp;
+ } else
+ {
+ OutRec *outRec = m_PolyOuts[e->OutIdx];
+ //OutRec.Pts is the 'Left-most' point & OutRec.Pts.Prev is the 'Right-most'
+ OutPt* op = outRec->Pts;
+
+ if (ToFront && (pt == op->Pt)) return op;
+ else if (!ToFront && (pt == op->Prev->Pt)) return op->Prev;
+
+ OutPt* newOp = new OutPt;
+ newOp->Idx = outRec->Idx;
+ newOp->Pt = pt;
+ newOp->Next = op;
+ newOp->Prev = op->Prev;
+ newOp->Prev->Next = newOp;
+ op->Prev = newOp;
+ if (ToFront) outRec->Pts = newOp;
+#ifdef use_xyz
+ if (pt == e->Bot) newOp->Pt = e->Bot;
+ else if (pt == e->Top) newOp->Pt = e->Top;
+ else SetZ(newOp->Pt, *e);
+#endif
+ return newOp;
+ }
+}
+//------------------------------------------------------------------------------
+
+void Clipper::ProcessHorizontals(bool IsTopOfScanbeam)
+{
+ TEdge* horzEdge = m_SortedEdges;
+ while(horzEdge)
+ {
+ DeleteFromSEL(horzEdge);
+ ProcessHorizontal(horzEdge, IsTopOfScanbeam);
+ horzEdge = m_SortedEdges;
+ }
+}
+//------------------------------------------------------------------------------
+
+inline bool IsMinima(TEdge *e)
+{
+ return e && (e->Prev->NextInLML != e) && (e->Next->NextInLML != e);
+}
+//------------------------------------------------------------------------------
+
+inline bool IsMaxima(TEdge *e, const cInt Y)
+{
+ return e && e->Top.Y == Y && !e->NextInLML;
+}
+//------------------------------------------------------------------------------
+
+inline bool IsIntermediate(TEdge *e, const cInt Y)
+{
+ return e->Top.Y == Y && e->NextInLML;
+}
+//------------------------------------------------------------------------------
+
+TEdge *GetMaximaPair(TEdge *e)
+{
+ TEdge* result = 0;
+ if ((e->Next->Top == e->Top) && !e->Next->NextInLML)
+ result = e->Next;
+ else if ((e->Prev->Top == e->Top) && !e->Prev->NextInLML)
+ result = e->Prev;
+
+ if (result && (result->OutIdx == Skip ||
+ //result is false if both NextInAEL & PrevInAEL are nil & not horizontal ...
+ (result->NextInAEL == result->PrevInAEL && !IsHorizontal(*result))))
+ return 0;
+ return result;
+}
+//------------------------------------------------------------------------------
+
+void Clipper::SwapPositionsInAEL(TEdge *Edge1, TEdge *Edge2)
+{
+ //check that one or other edge hasn't already been removed from AEL ...
+ if (Edge1->NextInAEL == Edge1->PrevInAEL ||
+ Edge2->NextInAEL == Edge2->PrevInAEL) return;
+
+ if( Edge1->NextInAEL == Edge2 )
+ {
+ TEdge* Next = Edge2->NextInAEL;
+ if( Next ) Next->PrevInAEL = Edge1;
+ TEdge* Prev = Edge1->PrevInAEL;
+ if( Prev ) Prev->NextInAEL = Edge2;
+ Edge2->PrevInAEL = Prev;
+ Edge2->NextInAEL = Edge1;
+ Edge1->PrevInAEL = Edge2;
+ Edge1->NextInAEL = Next;
+ }
+ else if( Edge2->NextInAEL == Edge1 )
+ {
+ TEdge* Next = Edge1->NextInAEL;
+ if( Next ) Next->PrevInAEL = Edge2;
+ TEdge* Prev = Edge2->PrevInAEL;
+ if( Prev ) Prev->NextInAEL = Edge1;
+ Edge1->PrevInAEL = Prev;
+ Edge1->NextInAEL = Edge2;
+ Edge2->PrevInAEL = Edge1;
+ Edge2->NextInAEL = Next;
+ }
+ else
+ {
+ TEdge* Next = Edge1->NextInAEL;
+ TEdge* Prev = Edge1->PrevInAEL;
+ Edge1->NextInAEL = Edge2->NextInAEL;
+ if( Edge1->NextInAEL ) Edge1->NextInAEL->PrevInAEL = Edge1;
+ Edge1->PrevInAEL = Edge2->PrevInAEL;
+ if( Edge1->PrevInAEL ) Edge1->PrevInAEL->NextInAEL = Edge1;
+ Edge2->NextInAEL = Next;
+ if( Edge2->NextInAEL ) Edge2->NextInAEL->PrevInAEL = Edge2;
+ Edge2->PrevInAEL = Prev;
+ if( Edge2->PrevInAEL ) Edge2->PrevInAEL->NextInAEL = Edge2;
+ }
+
+ if( !Edge1->PrevInAEL ) m_ActiveEdges = Edge1;
+ else if( !Edge2->PrevInAEL ) m_ActiveEdges = Edge2;
+}
+//------------------------------------------------------------------------------
+
+void Clipper::SwapPositionsInSEL(TEdge *Edge1, TEdge *Edge2)
+{
+ if( !( Edge1->NextInSEL ) && !( Edge1->PrevInSEL ) ) return;
+ if( !( Edge2->NextInSEL ) && !( Edge2->PrevInSEL ) ) return;
+
+ if( Edge1->NextInSEL == Edge2 )
+ {
+ TEdge* Next = Edge2->NextInSEL;
+ if( Next ) Next->PrevInSEL = Edge1;
+ TEdge* Prev = Edge1->PrevInSEL;
+ if( Prev ) Prev->NextInSEL = Edge2;
+ Edge2->PrevInSEL = Prev;
+ Edge2->NextInSEL = Edge1;
+ Edge1->PrevInSEL = Edge2;
+ Edge1->NextInSEL = Next;
+ }
+ else if( Edge2->NextInSEL == Edge1 )
+ {
+ TEdge* Next = Edge1->NextInSEL;
+ if( Next ) Next->PrevInSEL = Edge2;
+ TEdge* Prev = Edge2->PrevInSEL;
+ if( Prev ) Prev->NextInSEL = Edge1;
+ Edge1->PrevInSEL = Prev;
+ Edge1->NextInSEL = Edge2;
+ Edge2->PrevInSEL = Edge1;
+ Edge2->NextInSEL = Next;
+ }
+ else
+ {
+ TEdge* Next = Edge1->NextInSEL;
+ TEdge* Prev = Edge1->PrevInSEL;
+ Edge1->NextInSEL = Edge2->NextInSEL;
+ if( Edge1->NextInSEL ) Edge1->NextInSEL->PrevInSEL = Edge1;
+ Edge1->PrevInSEL = Edge2->PrevInSEL;
+ if( Edge1->PrevInSEL ) Edge1->PrevInSEL->NextInSEL = Edge1;
+ Edge2->NextInSEL = Next;
+ if( Edge2->NextInSEL ) Edge2->NextInSEL->PrevInSEL = Edge2;
+ Edge2->PrevInSEL = Prev;
+ if( Edge2->PrevInSEL ) Edge2->PrevInSEL->NextInSEL = Edge2;
+ }
+
+ if( !Edge1->PrevInSEL ) m_SortedEdges = Edge1;
+ else if( !Edge2->PrevInSEL ) m_SortedEdges = Edge2;
+}
+//------------------------------------------------------------------------------
+
+TEdge* GetNextInAEL(TEdge *e, Direction dir)
+{
+ return dir == dLeftToRight ? e->NextInAEL : e->PrevInAEL;
+}
+//------------------------------------------------------------------------------
+
+void GetHorzDirection(TEdge& HorzEdge, Direction& Dir, cInt& Left, cInt& Right)
+{
+ if (HorzEdge.Bot.X < HorzEdge.Top.X)
+ {
+ Left = HorzEdge.Bot.X;
+ Right = HorzEdge.Top.X;
+ Dir = dLeftToRight;
+ } else
+ {
+ Left = HorzEdge.Top.X;
+ Right = HorzEdge.Bot.X;
+ Dir = dRightToLeft;
+ }
+}
+//------------------------------------------------------------------------
+
+void Clipper::PrepareHorzJoins(TEdge* horzEdge, bool isTopOfScanbeam)
+{
+ //get the last Op for this horizontal edge
+ //the point may be anywhere along the horizontal ...
+ OutPt* outPt = m_PolyOuts[horzEdge->OutIdx]->Pts;
+ if (horzEdge->Side != esLeft) outPt = outPt->Prev;
+
+ //First, match up overlapping horizontal edges (eg when one polygon's
+ //intermediate horz edge overlaps an intermediate horz edge of another, or
+ //when one polygon sits on top of another) ...
+ //for (JoinList::size_type i = 0; i < m_GhostJoins.size(); ++i)
+ //{
+ // Join* j = m_GhostJoins[i];
+ // if (HorzSegmentsOverlap(j->OutPt1->Pt, j->OffPt, horzEdge->Bot, horzEdge->Top))
+ // AddJoin(j->OutPt1, outPt, j->OffPt);
+ //}
+
+ //Also, since horizontal edges at the top of one SB are often removed from
+ //the AEL before we process the horizontal edges at the bottom of the next,
+ //we need to create 'ghost' Join records of 'contrubuting' horizontals that
+ //we can compare with horizontals at the bottom of the next SB.
+ if (isTopOfScanbeam)
+ {
+ if (outPt->Pt == horzEdge->Top)
+ AddGhostJoin(outPt, horzEdge->Bot);
+ else
+ AddGhostJoin(outPt, horzEdge->Top);
+ }
+}
+//------------------------------------------------------------------------------
+
+/*******************************************************************************
+* 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 other HE Bot.Xs only [#] *
+* (or they could intersect with Top.Xs only, ie EITHER Bot.Xs OR Top.Xs), *
+* and with other non-horizontal edges [*]. Once these intersections are *
+* processed, intermediate HEs then 'promote' the Edge above (NextInLML) into *
+* the AEL. These 'promoted' edges may in turn intersect [%] with other HEs. *
+*******************************************************************************/
+
+void Clipper::ProcessHorizontal(TEdge *horzEdge, bool isTopOfScanbeam)
+{
+ Direction dir;
+ cInt horzLeft, horzRight;
+
+ GetHorzDirection(*horzEdge, dir, horzLeft, horzRight);
+
+ TEdge* eLastHorz = horzEdge, *eMaxPair = 0;
+ while (eLastHorz->NextInLML && IsHorizontal(*eLastHorz->NextInLML))
+ eLastHorz = eLastHorz->NextInLML;
+ if (!eLastHorz->NextInLML)
+ eMaxPair = GetMaximaPair(eLastHorz);
+
+ for (;;)
+ {
+ bool IsLastHorz = (horzEdge == eLastHorz);
+ TEdge* e = GetNextInAEL(horzEdge, dir);
+ while(e)
+ {
+ //Break if we've got to the end of an intermediate horizontal edge ...
+ //nb: Smaller Dx's are to the right of larger Dx's ABOVE the horizontal.
+ if (e->Curr.X == horzEdge->Top.X && horzEdge->NextInLML &&
+ e->Dx < horzEdge->NextInLML->Dx) break;
+
+ TEdge* eNext = GetNextInAEL(e, dir); //saves eNext for later
+
+ if ((dir == dLeftToRight && e->Curr.X <= horzRight) ||
+ (dir == dRightToLeft && e->Curr.X >= horzLeft))
+ {
+ if (horzEdge->OutIdx >= 0 && horzEdge->WindDelta != 0)
+ PrepareHorzJoins(horzEdge, isTopOfScanbeam);
+ //so far we're still in range of the horizontal Edge but make sure
+ //we're at the last of consec. horizontals when matching with eMaxPair
+ if(e == eMaxPair && IsLastHorz)
+ {
+ if (dir == dLeftToRight)
+ IntersectEdges(horzEdge, e, e->Top);
+ else
+ IntersectEdges(e, horzEdge, e->Top);
+ if (eMaxPair->OutIdx >= 0) throw clipperException("ProcessHorizontal error");
+ return;
+ }
+ else if(dir == dLeftToRight)
+ {
+ IntPoint Pt = IntPoint(e->Curr.X, horzEdge->Curr.Y);
+ IntersectEdges(horzEdge, e, Pt, true);
+ }
+ else
+ {
+ IntPoint Pt = IntPoint(e->Curr.X, horzEdge->Curr.Y);
+ IntersectEdges( e, horzEdge, Pt, true);
+ }
+ SwapPositionsInAEL( horzEdge, e );
+ }
+ else if( (dir == dLeftToRight && e->Curr.X >= horzRight) ||
+ (dir == dRightToLeft && e->Curr.X <= horzLeft) ) break;
+ e = eNext;
+ } //end while
+
+ if (horzEdge->OutIdx >= 0 && horzEdge->WindDelta != 0)
+ PrepareHorzJoins(horzEdge, isTopOfScanbeam);
+
+ if (horzEdge->NextInLML && IsHorizontal(*horzEdge->NextInLML))
+ {
+ UpdateEdgeIntoAEL(horzEdge);
+ if (horzEdge->OutIdx >= 0) AddOutPt(horzEdge, horzEdge->Bot);
+ GetHorzDirection(*horzEdge, dir, horzLeft, horzRight);
+ } else
+ break;
+ } //end for (;;)
+
+ if(horzEdge->NextInLML)
+ {
+ if(horzEdge->OutIdx >= 0)
+ {
+ OutPt* op1 = AddOutPt( horzEdge, horzEdge->Top);
+ UpdateEdgeIntoAEL(horzEdge);
+ if (horzEdge->WindDelta == 0) return;
+ //nb: HorzEdge is no longer horizontal here
+ TEdge* ePrev = horzEdge->PrevInAEL;
+ TEdge* eNext = horzEdge->NextInAEL;
+ if (ePrev && ePrev->Curr.X == horzEdge->Bot.X &&
+ ePrev->Curr.Y == horzEdge->Bot.Y && ePrev->WindDelta != 0 &&
+ (ePrev->OutIdx >= 0 && ePrev->Curr.Y > ePrev->Top.Y &&
+ SlopesEqual(*horzEdge, *ePrev, m_UseFullRange)))
+ {
+ OutPt* op2 = AddOutPt(ePrev, horzEdge->Bot);
+ AddJoin(op1, op2, horzEdge->Top);
+ }
+ else if (eNext && eNext->Curr.X == horzEdge->Bot.X &&
+ eNext->Curr.Y == horzEdge->Bot.Y && eNext->WindDelta != 0 &&
+ eNext->OutIdx >= 0 && eNext->Curr.Y > eNext->Top.Y &&
+ SlopesEqual(*horzEdge, *eNext, m_UseFullRange))
+ {
+ OutPt* op2 = AddOutPt(eNext, horzEdge->Bot);
+ AddJoin(op1, op2, horzEdge->Top);
+ }
+ }
+ else
+ UpdateEdgeIntoAEL(horzEdge);
+ }
+ else if (eMaxPair)
+ {
+ if (eMaxPair->OutIdx >= 0)
+ {
+ if (dir == dLeftToRight)
+ IntersectEdges(horzEdge, eMaxPair, horzEdge->Top);
+ else
+ IntersectEdges(eMaxPair, horzEdge, horzEdge->Top);
+ if (eMaxPair->OutIdx >= 0)
+ throw clipperException("ProcessHorizontal error");
+ } else
+ {
+ DeleteFromAEL(horzEdge);
+ DeleteFromAEL(eMaxPair);
+ }
+ } else
+ {
+ if (horzEdge->OutIdx >= 0) AddOutPt(horzEdge, horzEdge->Top);
+ DeleteFromAEL(horzEdge);
+ }
+}
+//------------------------------------------------------------------------------
+
+void Clipper::UpdateEdgeIntoAEL(TEdge *&e)
+{
+ if( !e->NextInLML ) throw
+ clipperException("UpdateEdgeIntoAEL: invalid call");
+
+ e->NextInLML->OutIdx = e->OutIdx;
+ TEdge* AelPrev = e->PrevInAEL;
+ TEdge* AelNext = e->NextInAEL;
+ if (AelPrev) AelPrev->NextInAEL = e->NextInLML;
+ else m_ActiveEdges = e->NextInLML;
+ if (AelNext) AelNext->PrevInAEL = e->NextInLML;
+ e->NextInLML->Side = e->Side;
+ e->NextInLML->WindDelta = e->WindDelta;
+ e->NextInLML->WindCnt = e->WindCnt;
+ e->NextInLML->WindCnt2 = e->WindCnt2;
+ e = e->NextInLML;
+ e->Curr = e->Bot;
+ e->PrevInAEL = AelPrev;
+ e->NextInAEL = AelNext;
+ if (!IsHorizontal(*e)) InsertScanbeam(e->Top.Y);
+}
+//------------------------------------------------------------------------------
+
+bool Clipper::ProcessIntersections(const cInt botY, const cInt topY)
+{
+ if( !m_ActiveEdges ) return true;
+ try {
+ BuildIntersectList(botY, topY);
+ size_t IlSize = m_IntersectList.size();
+ if (IlSize == 0) return true;
+ if (IlSize == 1 || FixupIntersectionOrder()) ProcessIntersectList();
+ else return false;
+ }
+ catch(...)
+ {
+ m_SortedEdges = 0;
+ DisposeIntersectNodes();
+ throw clipperException("ProcessIntersections error");
+ }
+ m_SortedEdges = 0;
+ return true;
+}
+//------------------------------------------------------------------------------
+
+void Clipper::DisposeIntersectNodes()
+{
+ for (size_t i = 0; i < m_IntersectList.size(); ++i )
+ delete m_IntersectList[i];
+ m_IntersectList.clear();
+}
+//------------------------------------------------------------------------------
+
+void Clipper::BuildIntersectList(const cInt botY, const cInt topY)
+{
+ if ( !m_ActiveEdges ) return;
+
+ //prepare for sorting ...
+ TEdge* e = m_ActiveEdges;
+ m_SortedEdges = e;
+ while( e )
+ {
+ e->PrevInSEL = e->PrevInAEL;
+ e->NextInSEL = e->NextInAEL;
+ e->Curr.X = TopX( *e, topY );
+ e = e->NextInAEL;
+ }
+
+ //bubblesort ...
+ bool isModified;
+ do
+ {
+ isModified = false;
+ e = m_SortedEdges;
+ while( e->NextInSEL )
+ {
+ TEdge *eNext = e->NextInSEL;
+ IntPoint Pt;
+ if(e->Curr.X > eNext->Curr.X)
+ {
+ if (!IntersectPoint(*e, *eNext, Pt, m_UseFullRange) && e->Curr.X > eNext->Curr.X +1)
+ throw clipperException("Intersection error");
+ if (Pt.Y > botY)
+ {
+ Pt.Y = botY;
+ if (std::fabs(e->Dx) > std::fabs(eNext->Dx))
+ Pt.X = TopX(*eNext, botY); else
+ Pt.X = TopX(*e, botY);
+ }
+
+ IntersectNode * newNode = new IntersectNode;
+ newNode->Edge1 = e;
+ newNode->Edge2 = eNext;
+ newNode->Pt = Pt;
+ m_IntersectList.push_back(newNode);
+
+ SwapPositionsInSEL(e, eNext);
+ isModified = true;
+ }
+ else
+ e = eNext;
+ }
+ if( e->PrevInSEL ) e->PrevInSEL->NextInSEL = 0;
+ else break;
+ }
+ while ( isModified );
+ m_SortedEdges = 0; //important
+}
+//------------------------------------------------------------------------------
+
+
+void Clipper::ProcessIntersectList()
+{
+ for (size_t i = 0; i < m_IntersectList.size(); ++i)
+ {
+ IntersectNode* iNode = m_IntersectList[i];
+ {
+ IntersectEdges( iNode->Edge1, iNode->Edge2, iNode->Pt, true);
+ SwapPositionsInAEL( iNode->Edge1 , iNode->Edge2 );
+ }
+ delete iNode;
+ }
+ m_IntersectList.clear();
+}
+//------------------------------------------------------------------------------
+
+bool IntersectListSort(IntersectNode* node1, IntersectNode* node2)
+{
+ return node2->Pt.Y < node1->Pt.Y;
+}
+//------------------------------------------------------------------------------
+
+inline bool EdgesAdjacent(const IntersectNode &inode)
+{
+ return (inode.Edge1->NextInSEL == inode.Edge2) ||
+ (inode.Edge1->PrevInSEL == inode.Edge2);
+}
+//------------------------------------------------------------------------------
+
+bool Clipper::FixupIntersectionOrder()
+{
+ //pre-condition: intersections are sorted Bottom-most first.
+ //Now it's crucial that intersections are made only between adjacent edges,
+ //so to ensure this the order of intersections may need adjusting ...
+ CopyAELToSEL();
+ std::sort(m_IntersectList.begin(), m_IntersectList.end(), IntersectListSort);
+ size_t cnt = m_IntersectList.size();
+ for (size_t i = 0; i < cnt; ++i)
+ {
+ if (!EdgesAdjacent(*m_IntersectList[i]))
+ {
+ size_t j = i + 1;
+ while (j < cnt && !EdgesAdjacent(*m_IntersectList[j])) j++;
+ if (j == cnt) return false;
+ std::swap(m_IntersectList[i], m_IntersectList[j]);
+ }
+ SwapPositionsInSEL(m_IntersectList[i]->Edge1, m_IntersectList[i]->Edge2);
+ }
+ return true;
+}
+//------------------------------------------------------------------------------
+
+void Clipper::DoMaxima(TEdge *e)
+{
+ TEdge* eMaxPair = GetMaximaPair(e);
+ if (!eMaxPair)
+ {
+ if (e->OutIdx >= 0)
+ AddOutPt(e, e->Top);
+ DeleteFromAEL(e);
+ return;
+ }
+
+ TEdge* eNext = e->NextInAEL;
+ while(eNext && eNext != eMaxPair)
+ {
+ IntersectEdges(e, eNext, e->Top, true);
+ SwapPositionsInAEL(e, eNext);
+ eNext = e->NextInAEL;
+ }
+
+ if(e->OutIdx == Unassigned && eMaxPair->OutIdx == Unassigned)
+ {
+ DeleteFromAEL(e);
+ DeleteFromAEL(eMaxPair);
+ }
+ else if( e->OutIdx >= 0 && eMaxPair->OutIdx >= 0 )
+ {
+ IntersectEdges( e, eMaxPair, e->Top);
+ }
+#ifdef use_lines
+ else if (e->WindDelta == 0)
+ {
+ if (e->OutIdx >= 0)
+ {
+ AddOutPt(e, e->Top);
+ e->OutIdx = Unassigned;
+ }
+ DeleteFromAEL(e);
+
+ if (eMaxPair->OutIdx >= 0)
+ {
+ AddOutPt(eMaxPair, e->Top);
+ eMaxPair->OutIdx = Unassigned;
+ }
+ DeleteFromAEL(eMaxPair);
+ }
+#endif
+ else throw clipperException("DoMaxima error");
+}
+//------------------------------------------------------------------------------
+
+void Clipper::ProcessEdgesAtTopOfScanbeam(const cInt topY)
+{
+ TEdge* e = m_ActiveEdges;
+ while( e )
+ {
+ //1. process maxima, treating them as if they're 'bent' horizontal edges,
+ // but exclude maxima with horizontal edges. nb: e can't be a horizontal.
+ bool IsMaximaEdge = IsMaxima(e, topY);
+
+ if(IsMaximaEdge)
+ {
+ TEdge* eMaxPair = GetMaximaPair(e);
+ IsMaximaEdge = (!eMaxPair || !IsHorizontal(*eMaxPair));
+ }
+
+ if(IsMaximaEdge)
+ {
+ TEdge* ePrev = e->PrevInAEL;
+ DoMaxima(e);
+ if( !ePrev ) e = m_ActiveEdges;
+ else e = ePrev->NextInAEL;
+ }
+ else
+ {
+ //2. promote horizontal edges, otherwise update Curr.X and Curr.Y ...
+ if (IsIntermediate(e, topY) && IsHorizontal(*e->NextInLML))
+ {
+ UpdateEdgeIntoAEL(e);
+ if (e->OutIdx >= 0)
+ AddOutPt(e, e->Bot);
+ AddEdgeToSEL(e);
+ }
+ else
+ {
+ e->Curr.X = TopX( *e, topY );
+ e->Curr.Y = topY;
+ }
+
+ if (m_StrictSimple)
+ {
+ TEdge* ePrev = e->PrevInAEL;
+ if ((e->OutIdx >= 0) && (e->WindDelta != 0) && ePrev && (ePrev->OutIdx >= 0) &&
+ (ePrev->Curr.X == e->Curr.X) && (ePrev->WindDelta != 0))
+ {
+ OutPt* op = AddOutPt(ePrev, e->Curr);
+ OutPt* op2 = AddOutPt(e, e->Curr);
+ AddJoin(op, op2, e->Curr); //StrictlySimple (type-3) join
+ }
+ }
+
+ e = e->NextInAEL;
+ }
+ }
+
+ //3. Process horizontals at the Top of the scanbeam ...
+ ProcessHorizontals(true);
+
+ //4. Promote intermediate vertices ...
+ e = m_ActiveEdges;
+ while(e)
+ {
+ if(IsIntermediate(e, topY))
+ {
+ OutPt* op = 0;
+ if( e->OutIdx >= 0 )
+ op = AddOutPt(e, e->Top);
+ UpdateEdgeIntoAEL(e);
+
+ //if output polygons share an edge, they'll need joining later ...
+ TEdge* ePrev = e->PrevInAEL;
+ TEdge* eNext = e->NextInAEL;
+ if (ePrev && ePrev->Curr.X == e->Bot.X &&
+ ePrev->Curr.Y == e->Bot.Y && op &&
+ ePrev->OutIdx >= 0 && ePrev->Curr.Y > ePrev->Top.Y &&
+ SlopesEqual(*e, *ePrev, m_UseFullRange) &&
+ (e->WindDelta != 0) && (ePrev->WindDelta != 0))
+ {
+ OutPt* op2 = AddOutPt(ePrev, e->Bot);
+ AddJoin(op, op2, e->Top);
+ }
+ else if (eNext && eNext->Curr.X == e->Bot.X &&
+ eNext->Curr.Y == e->Bot.Y && op &&
+ eNext->OutIdx >= 0 && eNext->Curr.Y > eNext->Top.Y &&
+ SlopesEqual(*e, *eNext, m_UseFullRange) &&
+ (e->WindDelta != 0) && (eNext->WindDelta != 0))
+ {
+ OutPt* op2 = AddOutPt(eNext, e->Bot);
+ AddJoin(op, op2, e->Top);
+ }
+ }
+ e = e->NextInAEL;
+ }
+}
+//------------------------------------------------------------------------------
+
+void Clipper::FixupOutPolygon(OutRec &outrec)
+{
+ //FixupOutPolygon() - removes duplicate points and simplifies consecutive
+ //parallel edges by removing the middle vertex.
+ OutPt *lastOK = 0;
+ outrec.BottomPt = 0;
+ OutPt *pp = outrec.Pts;
+
+ for (;;)
+ {
+ if (pp->Prev == pp || pp->Prev == pp->Next )
+ {
+ DisposeOutPts(pp);
+ outrec.Pts = 0;
+ return;
+ }
+
+ //test for duplicate points and collinear edges ...
+ if ((pp->Pt == pp->Next->Pt) || (pp->Pt == pp->Prev->Pt) ||
+ (SlopesEqual(pp->Prev->Pt, pp->Pt, pp->Next->Pt, m_UseFullRange) &&
+ (!m_PreserveCollinear ||
+ !Pt2IsBetweenPt1AndPt3(pp->Prev->Pt, pp->Pt, pp->Next->Pt))))
+ {
+ lastOK = 0;
+ OutPt *tmp = pp;
+ pp->Prev->Next = pp->Next;
+ pp->Next->Prev = pp->Prev;
+ pp = pp->Prev;
+ delete tmp;
+ }
+ else if (pp == lastOK) break;
+ else
+ {
+ if (!lastOK) lastOK = pp;
+ pp = pp->Next;
+ }
+ }
+ outrec.Pts = pp;
+}
+//------------------------------------------------------------------------------
+
+int PointCount(OutPt *Pts)
+{
+ if (!Pts) return 0;
+ int result = 0;
+ OutPt* p = Pts;
+ do
+ {
+ result++;
+ p = p->Next;
+ }
+ while (p != Pts);
+ return result;
+}
+//------------------------------------------------------------------------------
+
+void Clipper::BuildResult(Paths &polys)
+{
+ polys.reserve(m_PolyOuts.size());
+ for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
+ {
+ if (!m_PolyOuts[i]->Pts) continue;
+ Path pg;
+ OutPt* p = m_PolyOuts[i]->Pts->Prev;
+ int cnt = PointCount(p);
+ if (cnt < 2) continue;
+ pg.reserve(cnt);
+ for (int i = 0; i < cnt; ++i)
+ {
+ pg.push_back(p->Pt);
+ p = p->Prev;
+ }
+ polys.push_back(pg);
+ }
+}
+//------------------------------------------------------------------------------
+
+void Clipper::BuildResult2(PolyTree& polytree)
+{
+ polytree.Clear();
+ polytree.AllNodes.reserve(m_PolyOuts.size());
+ //add each output polygon/contour to polytree ...
+ for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); i++)
+ {
+ OutRec* outRec = m_PolyOuts[i];
+ int cnt = PointCount(outRec->Pts);
+ if ((outRec->IsOpen && cnt < 2) || (!outRec->IsOpen && cnt < 3)) continue;
+ FixHoleLinkage(*outRec);
+ PolyNode* pn = new PolyNode();
+ //nb: polytree takes ownership of all the PolyNodes
+ polytree.AllNodes.push_back(pn);
+ outRec->PolyNd = pn;
+ pn->Parent = 0;
+ pn->Index = 0;
+ pn->Contour.reserve(cnt);
+ OutPt *op = outRec->Pts->Prev;
+ for (int j = 0; j < cnt; j++)
+ {
+ pn->Contour.push_back(op->Pt);
+ op = op->Prev;
+ }
+ }
+
+ //fixup PolyNode links etc ...
+ polytree.Childs.reserve(m_PolyOuts.size());
+ for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); i++)
+ {
+ OutRec* outRec = m_PolyOuts[i];
+ if (!outRec->PolyNd) continue;
+ if (outRec->IsOpen)
+ {
+ outRec->PolyNd->m_IsOpen = true;
+ polytree.AddChild(*outRec->PolyNd);
+ }
+ else if (outRec->FirstLeft && outRec->FirstLeft->PolyNd)
+ outRec->FirstLeft->PolyNd->AddChild(*outRec->PolyNd);
+ else
+ polytree.AddChild(*outRec->PolyNd);
+ }
+}
+//------------------------------------------------------------------------------
+
+void SwapIntersectNodes(IntersectNode &int1, IntersectNode &int2)
+{
+ //just swap the contents (because fIntersectNodes is a single-linked-list)
+ IntersectNode inode = int1; //gets a copy of Int1
+ int1.Edge1 = int2.Edge1;
+ int1.Edge2 = int2.Edge2;
+ int1.Pt = int2.Pt;
+ int2.Edge1 = inode.Edge1;
+ int2.Edge2 = inode.Edge2;
+ int2.Pt = inode.Pt;
+}
+//------------------------------------------------------------------------------
+
+inline bool E2InsertsBeforeE1(TEdge &e1, TEdge &e2)
+{
+ if (e2.Curr.X == e1.Curr.X)
+ {
+ if (e2.Top.Y > e1.Top.Y)
+ return e2.Top.X < TopX(e1, e2.Top.Y);
+ else return e1.Top.X > TopX(e2, e1.Top.Y);
+ }
+ else return e2.Curr.X < e1.Curr.X;
+}
+//------------------------------------------------------------------------------
+
+bool GetOverlap(const cInt a1, const cInt a2, const cInt b1, const cInt b2,
+ cInt& Left, cInt& Right)
+{
+ if (a1 < a2)
+ {
+ if (b1 < b2) {Left = std::max(a1,b1); Right = std::min(a2,b2);}
+ else {Left = std::max(a1,b2); Right = std::min(a2,b1);}
+ }
+ else
+ {
+ if (b1 < b2) {Left = std::max(a2,b1); Right = std::min(a1,b2);}
+ else {Left = std::max(a2,b2); Right = std::min(a1,b1);}
+ }
+ return Left < Right;
+}
+//------------------------------------------------------------------------------
+
+inline void UpdateOutPtIdxs(OutRec& outrec)
+{
+ OutPt* op = outrec.Pts;
+ do
+ {
+ op->Idx = outrec.Idx;
+ op = op->Prev;
+ }
+ while(op != outrec.Pts);
+}
+//------------------------------------------------------------------------------
+
+void Clipper::InsertEdgeIntoAEL(TEdge *edge, TEdge* startEdge)
+{
+ if(!m_ActiveEdges)
+ {
+ edge->PrevInAEL = 0;
+ edge->NextInAEL = 0;
+ m_ActiveEdges = edge;
+ }
+ else if(!startEdge && E2InsertsBeforeE1(*m_ActiveEdges, *edge))
+ {
+ edge->PrevInAEL = 0;
+ edge->NextInAEL = m_ActiveEdges;
+ m_ActiveEdges->PrevInAEL = edge;
+ m_ActiveEdges = edge;
+ }
+ else
+ {
+ if(!startEdge) startEdge = m_ActiveEdges;
+ while(startEdge->NextInAEL &&
+ !E2InsertsBeforeE1(*startEdge->NextInAEL , *edge))
+ startEdge = startEdge->NextInAEL;
+ edge->NextInAEL = startEdge->NextInAEL;
+ if(startEdge->NextInAEL) startEdge->NextInAEL->PrevInAEL = edge;
+ edge->PrevInAEL = startEdge;
+ startEdge->NextInAEL = edge;
+ }
+}
+//----------------------------------------------------------------------
+
+OutPt* DupOutPt(OutPt* outPt, bool InsertAfter)
+{
+ OutPt* result = new OutPt;
+ result->Pt = outPt->Pt;
+ result->Idx = outPt->Idx;
+ if (InsertAfter)
+ {
+ result->Next = outPt->Next;
+ result->Prev = outPt;
+ outPt->Next->Prev = result;
+ outPt->Next = result;
+ }
+ else
+ {
+ result->Prev = outPt->Prev;
+ result->Next = outPt;
+ outPt->Prev->Next = result;
+ outPt->Prev = result;
+ }
+ return result;
+}
+//------------------------------------------------------------------------------
+
+bool JoinHorz(OutPt* op1, OutPt* op1b, OutPt* op2, OutPt* op2b,
+ const IntPoint Pt, bool DiscardLeft)
+{
+ Direction Dir1 = (op1->Pt.X > op1b->Pt.X ? dRightToLeft : dLeftToRight);
+ Direction Dir2 = (op2->Pt.X > op2b->Pt.X ? dRightToLeft : dLeftToRight);
+ if (Dir1 == Dir2) return false;
+
+ //When DiscardLeft, we want Op1b to be on the Left of Op1, otherwise we
+ //want Op1b to be on the Right. (And likewise with Op2 and Op2b.)
+ //So, to facilitate this while inserting Op1b and Op2b ...
+ //when DiscardLeft, make sure we're AT or RIGHT of Pt before adding Op1b,
+ //otherwise make sure we're AT or LEFT of Pt. (Likewise with Op2b.)
+ if (Dir1 == dLeftToRight)
+ {
+ while (op1->Next->Pt.X <= Pt.X &&
+ op1->Next->Pt.X >= op1->Pt.X && op1->Next->Pt.Y == Pt.Y)
+ op1 = op1->Next;
+ if (DiscardLeft && (op1->Pt.X != Pt.X)) op1 = op1->Next;
+ op1b = DupOutPt(op1, !DiscardLeft);
+ if (op1b->Pt != Pt)
+ {
+ op1 = op1b;
+ op1->Pt = Pt;
+ op1b = DupOutPt(op1, !DiscardLeft);
+ }
+ }
+ else
+ {
+ while (op1->Next->Pt.X >= Pt.X &&
+ op1->Next->Pt.X <= op1->Pt.X && op1->Next->Pt.Y == Pt.Y)
+ op1 = op1->Next;
+ if (!DiscardLeft && (op1->Pt.X != Pt.X)) op1 = op1->Next;
+ op1b = DupOutPt(op1, DiscardLeft);
+ if (op1b->Pt != Pt)
+ {
+ op1 = op1b;
+ op1->Pt = Pt;
+ op1b = DupOutPt(op1, DiscardLeft);
+ }
+ }
+
+ if (Dir2 == dLeftToRight)
+ {
+ while (op2->Next->Pt.X <= Pt.X &&
+ op2->Next->Pt.X >= op2->Pt.X && op2->Next->Pt.Y == Pt.Y)
+ op2 = op2->Next;
+ if (DiscardLeft && (op2->Pt.X != Pt.X)) op2 = op2->Next;
+ op2b = DupOutPt(op2, !DiscardLeft);
+ if (op2b->Pt != Pt)
+ {
+ op2 = op2b;
+ op2->Pt = Pt;
+ op2b = DupOutPt(op2, !DiscardLeft);
+ };
+ } else
+ {
+ while (op2->Next->Pt.X >= Pt.X &&
+ op2->Next->Pt.X <= op2->Pt.X && op2->Next->Pt.Y == Pt.Y)
+ op2 = op2->Next;
+ if (!DiscardLeft && (op2->Pt.X != Pt.X)) op2 = op2->Next;
+ op2b = DupOutPt(op2, DiscardLeft);
+ if (op2b->Pt != Pt)
+ {
+ op2 = op2b;
+ op2->Pt = Pt;
+ op2b = DupOutPt(op2, DiscardLeft);
+ };
+ };
+
+ if ((Dir1 == dLeftToRight) == DiscardLeft)
+ {
+ op1->Prev = op2;
+ op2->Next = op1;
+ op1b->Next = op2b;
+ op2b->Prev = op1b;
+ }
+ else
+ {
+ op1->Next = op2;
+ op2->Prev = op1;
+ op1b->Prev = op2b;
+ op2b->Next = op1b;
+ }
+ return true;
+}
+//------------------------------------------------------------------------------
+
+bool Clipper::JoinPoints(Join *j, OutRec* outRec1, OutRec* outRec2)
+{
+ OutPt *op1 = j->OutPt1, *op1b;
+ OutPt *op2 = j->OutPt2, *op2b;
+
+ //There are 3 kinds of joins for output polygons ...
+ //1. Horizontal joins where Join.OutPt1 & Join.OutPt2 are a vertices anywhere
+ //along (horizontal) collinear edges (& Join.OffPt is on the same horizontal).
+ //2. Non-horizontal joins where Join.OutPt1 & Join.OutPt2 are at the same
+ //location at the Bottom of the overlapping segment (& Join.OffPt is above).
+ //3. StrictSimple joins where edges touch but are not collinear and where
+ //Join.OutPt1, Join.OutPt2 & Join.OffPt all share the same point.
+ bool isHorizontal = (j->OutPt1->Pt.Y == j->OffPt.Y);
+
+ if (isHorizontal && (j->OffPt == j->OutPt1->Pt) &&
+ (j->OffPt == j->OutPt2->Pt))
+ {
+ //Strictly Simple join ...
+ op1b = j->OutPt1->Next;
+ while (op1b != op1 && (op1b->Pt == j->OffPt))
+ op1b = op1b->Next;
+ bool reverse1 = (op1b->Pt.Y > j->OffPt.Y);
+ op2b = j->OutPt2->Next;
+ while (op2b != op2 && (op2b->Pt == j->OffPt))
+ op2b = op2b->Next;
+ bool reverse2 = (op2b->Pt.Y > j->OffPt.Y);
+ if (reverse1 == reverse2) return false;
+ if (reverse1)
+ {
+ op1b = DupOutPt(op1, false);
+ op2b = DupOutPt(op2, true);
+ op1->Prev = op2;
+ op2->Next = op1;
+ op1b->Next = op2b;
+ op2b->Prev = op1b;
+ j->OutPt1 = op1;
+ j->OutPt2 = op1b;
+ return true;
+ } else
+ {
+ op1b = DupOutPt(op1, true);
+ op2b = DupOutPt(op2, false);
+ op1->Next = op2;
+ op2->Prev = op1;
+ op1b->Prev = op2b;
+ op2b->Next = op1b;
+ j->OutPt1 = op1;
+ j->OutPt2 = op1b;
+ return true;
+ }
+ }
+ else if (isHorizontal)
+ {
+ //treat horizontal joins differently to non-horizontal joins since with
+ //them we're not yet sure where the overlapping is. OutPt1.Pt & OutPt2.Pt
+ //may be anywhere along the horizontal edge.
+ op1b = op1;
+ while (op1->Prev->Pt.Y == op1->Pt.Y && op1->Prev != op1b && op1->Prev != op2)
+ op1 = op1->Prev;
+ while (op1b->Next->Pt.Y == op1b->Pt.Y && op1b->Next != op1 && op1b->Next != op2)
+ op1b = op1b->Next;
+ if (op1b->Next == op1 || op1b->Next == op2) return false; //a flat 'polygon'
+
+ op2b = op2;
+ while (op2->Prev->Pt.Y == op2->Pt.Y && op2->Prev != op2b && op2->Prev != op1b)
+ op2 = op2->Prev;
+ while (op2b->Next->Pt.Y == op2b->Pt.Y && op2b->Next != op2 && op2b->Next != op1)
+ op2b = op2b->Next;
+ if (op2b->Next == op2 || op2b->Next == op1) return false; //a flat 'polygon'
+
+ cInt Left, Right;
+ //Op1 --> Op1b & Op2 --> Op2b are the extremites of the horizontal edges
+ if (!GetOverlap(op1->Pt.X, op1b->Pt.X, op2->Pt.X, op2b->Pt.X, Left, Right))
+ return false;
+
+ //DiscardLeftSide: when overlapping edges are joined, a spike will created
+ //which needs to be cleaned up. However, we don't want Op1 or Op2 caught up
+ //on the discard Side as either may still be needed for other joins ...
+ IntPoint Pt;
+ bool DiscardLeftSide;
+ if (op1->Pt.X >= Left && op1->Pt.X <= Right)
+ {
+ Pt = op1->Pt; DiscardLeftSide = (op1->Pt.X > op1b->Pt.X);
+ }
+ else if (op2->Pt.X >= Left&& op2->Pt.X <= Right)
+ {
+ Pt = op2->Pt; DiscardLeftSide = (op2->Pt.X > op2b->Pt.X);
+ }
+ else if (op1b->Pt.X >= Left && op1b->Pt.X <= Right)
+ {
+ Pt = op1b->Pt; DiscardLeftSide = op1b->Pt.X > op1->Pt.X;
+ }
+ else
+ {
+ Pt = op2b->Pt; DiscardLeftSide = (op2b->Pt.X > op2->Pt.X);
+ }
+ j->OutPt1 = op1; j->OutPt2 = op2;
+ return JoinHorz(op1, op1b, op2, op2b, Pt, DiscardLeftSide);
+ } else
+ {
+ //nb: For non-horizontal joins ...
+ // 1. Jr.OutPt1.Pt.Y == Jr.OutPt2.Pt.Y
+ // 2. Jr.OutPt1.Pt > Jr.OffPt.Y
+
+ //make sure the polygons are correctly oriented ...
+ op1b = op1->Next;
+ while ((op1b->Pt == op1->Pt) && (op1b != op1)) op1b = op1b->Next;
+ bool Reverse1 = ((op1b->Pt.Y > op1->Pt.Y) ||
+ !SlopesEqual(op1->Pt, op1b->Pt, j->OffPt, m_UseFullRange));
+ if (Reverse1)
+ {
+ op1b = op1->Prev;
+ while ((op1b->Pt == op1->Pt) && (op1b != op1)) op1b = op1b->Prev;
+ if ((op1b->Pt.Y > op1->Pt.Y) ||
+ !SlopesEqual(op1->Pt, op1b->Pt, j->OffPt, m_UseFullRange)) return false;
+ };
+ op2b = op2->Next;
+ while ((op2b->Pt == op2->Pt) && (op2b != op2))op2b = op2b->Next;
+ bool Reverse2 = ((op2b->Pt.Y > op2->Pt.Y) ||
+ !SlopesEqual(op2->Pt, op2b->Pt, j->OffPt, m_UseFullRange));
+ if (Reverse2)
+ {
+ op2b = op2->Prev;
+ while ((op2b->Pt == op2->Pt) && (op2b != op2)) op2b = op2b->Prev;
+ if ((op2b->Pt.Y > op2->Pt.Y) ||
+ !SlopesEqual(op2->Pt, op2b->Pt, j->OffPt, m_UseFullRange)) return false;
+ }
+
+ if ((op1b == op1) || (op2b == op2) || (op1b == op2b) ||
+ ((outRec1 == outRec2) && (Reverse1 == Reverse2))) return false;
+
+ if (Reverse1)
+ {
+ op1b = DupOutPt(op1, false);
+ op2b = DupOutPt(op2, true);
+ op1->Prev = op2;
+ op2->Next = op1;
+ op1b->Next = op2b;
+ op2b->Prev = op1b;
+ j->OutPt1 = op1;
+ j->OutPt2 = op1b;
+ return true;
+ } else
+ {
+ op1b = DupOutPt(op1, true);
+ op2b = DupOutPt(op2, false);
+ op1->Next = op2;
+ op2->Prev = op1;
+ op1b->Prev = op2b;
+ op2b->Next = op1b;
+ j->OutPt1 = op1;
+ j->OutPt2 = op1b;
+ return true;
+ }
+ }
+}
+//----------------------------------------------------------------------
+
+void Clipper::FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec)
+{
+
+ for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
+ {
+ OutRec* outRec = m_PolyOuts[i];
+ if (outRec->Pts && outRec->FirstLeft == OldOutRec)
+ {
+ if (Poly2ContainsPoly1(outRec->Pts, NewOutRec->Pts))
+ outRec->FirstLeft = NewOutRec;
+ }
+ }
+}
+//----------------------------------------------------------------------
+
+void Clipper::FixupFirstLefts2(OutRec* OldOutRec, OutRec* NewOutRec)
+{
+ for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
+ {
+ OutRec* outRec = m_PolyOuts[i];
+ if (outRec->FirstLeft == OldOutRec) outRec->FirstLeft = NewOutRec;
+ }
+}
+//----------------------------------------------------------------------
+
+static OutRec* ParseFirstLeft(OutRec* FirstLeft)
+{
+ while (FirstLeft && !FirstLeft->Pts)
+ FirstLeft = FirstLeft->FirstLeft;
+ return FirstLeft;
+}
+//------------------------------------------------------------------------------
+
+void Clipper::JoinCommonEdges()
+{
+ for (JoinList::size_type i = 0; i < m_Joins.size(); i++)
+ {
+ Join* join = m_Joins[i];
+
+ OutRec *outRec1 = GetOutRec(join->OutPt1->Idx);
+ OutRec *outRec2 = GetOutRec(join->OutPt2->Idx);
+
+ if (!outRec1->Pts || !outRec2->Pts) continue;
+
+ //get the polygon fragment with the correct hole state (FirstLeft)
+ //before calling JoinPoints() ...
+ OutRec *holeStateRec;
+ if (outRec1 == outRec2) holeStateRec = outRec1;
+ else if (Param1RightOfParam2(outRec1, outRec2)) holeStateRec = outRec2;
+ else if (Param1RightOfParam2(outRec2, outRec1)) holeStateRec = outRec1;
+ else holeStateRec = GetLowermostRec(outRec1, outRec2);
+
+ if (!JoinPoints(join, outRec1, outRec2)) continue;
+
+ if (outRec1 == outRec2)
+ {
+ //instead of joining two polygons, we've just created a new one by
+ //splitting one polygon into two.
+ outRec1->Pts = join->OutPt1;
+ outRec1->BottomPt = 0;
+ outRec2 = CreateOutRec();
+ outRec2->Pts = join->OutPt2;
+
+ //update all OutRec2.Pts Idx's ...
+ UpdateOutPtIdxs(*outRec2);
+
+ //We now need to check every OutRec.FirstLeft pointer. If it points
+ //to OutRec1 it may need to point to OutRec2 instead ...
+ if (m_UsingPolyTree)
+ for (PolyOutList::size_type j = 0; j < m_PolyOuts.size() - 1; j++)
+ {
+ OutRec* oRec = m_PolyOuts[j];
+ if (!oRec->Pts || ParseFirstLeft(oRec->FirstLeft) != outRec1 ||
+ oRec->IsHole == outRec1->IsHole) continue;
+ if (Poly2ContainsPoly1(oRec->Pts, join->OutPt2))
+ oRec->FirstLeft = outRec2;
+ }
+
+ if (Poly2ContainsPoly1(outRec2->Pts, outRec1->Pts))
+ {
+ //outRec2 is contained by outRec1 ...
+ outRec2->IsHole = !outRec1->IsHole;
+ outRec2->FirstLeft = outRec1;
+
+ //fixup FirstLeft pointers that may need reassigning to OutRec1
+ if (m_UsingPolyTree) FixupFirstLefts2(outRec2, outRec1);
+
+ if ((outRec2->IsHole ^ m_ReverseOutput) == (Area(*outRec2) > 0))
+ ReversePolyPtLinks(outRec2->Pts);
+
+ } else if (Poly2ContainsPoly1(outRec1->Pts, outRec2->Pts))
+ {
+ //outRec1 is contained by outRec2 ...
+ outRec2->IsHole = outRec1->IsHole;
+ outRec1->IsHole = !outRec2->IsHole;
+ outRec2->FirstLeft = outRec1->FirstLeft;
+ outRec1->FirstLeft = outRec2;
+
+ //fixup FirstLeft pointers that may need reassigning to OutRec1
+ if (m_UsingPolyTree) FixupFirstLefts2(outRec1, outRec2);
+
+ if ((outRec1->IsHole ^ m_ReverseOutput) == (Area(*outRec1) > 0))
+ ReversePolyPtLinks(outRec1->Pts);
+ }
+ else
+ {
+ //the 2 polygons are completely separate ...
+ outRec2->IsHole = outRec1->IsHole;
+ outRec2->FirstLeft = outRec1->FirstLeft;
+
+ //fixup FirstLeft pointers that may need reassigning to OutRec2
+ if (m_UsingPolyTree) FixupFirstLefts1(outRec1, outRec2);
+ }
+
+ } else
+ {
+ //joined 2 polygons together ...
+
+ outRec2->Pts = 0;
+ outRec2->BottomPt = 0;
+ outRec2->Idx = outRec1->Idx;
+
+ outRec1->IsHole = holeStateRec->IsHole;
+ if (holeStateRec == outRec2)
+ outRec1->FirstLeft = outRec2->FirstLeft;
+ outRec2->FirstLeft = outRec1;
+
+ //fixup FirstLeft pointers that may need reassigning to OutRec1
+ if (m_UsingPolyTree) FixupFirstLefts2(outRec2, outRec1);
+ }
+ }
+}
+
+//------------------------------------------------------------------------------
+// ClipperOffset support functions ...
+//------------------------------------------------------------------------------
+
+DoublePoint GetUnitNormal(const IntPoint &pt1, const IntPoint &pt2)
+{
+ if(pt2.X == pt1.X && pt2.Y == pt1.Y)
+ return DoublePoint(0, 0);
+
+ double Dx = (double)(pt2.X - pt1.X);
+ double dy = (double)(pt2.Y - pt1.Y);
+ double f = 1 *1.0/ std::sqrt( Dx*Dx + dy*dy );
+ Dx *= f;
+ dy *= f;
+ return DoublePoint(dy, -Dx);
+}
+
+//------------------------------------------------------------------------------
+// ClipperOffset class
+//------------------------------------------------------------------------------
+
+ClipperOffset::ClipperOffset(double miterLimit, double arcTolerance)
+{
+ this->MiterLimit = miterLimit;
+ this->ArcTolerance = arcTolerance;
+ m_lowest.X = -1;
+}
+//------------------------------------------------------------------------------
+
+ClipperOffset::~ClipperOffset()
+{
+ Clear();
+}
+//------------------------------------------------------------------------------
+
+void ClipperOffset::Clear()
+{
+ for (int i = 0; i < m_polyNodes.ChildCount(); ++i)
+ delete m_polyNodes.Childs[i];
+ m_polyNodes.Childs.clear();
+ m_lowest.X = -1;
+}
+//------------------------------------------------------------------------------
+
+void ClipperOffset::AddPath(const Path& path, JoinType joinType, EndType endType)
+{
+ int highI = (int)path.size() - 1;
+ if (highI < 0) return;
+ PolyNode* newNode = new PolyNode();
+ newNode->m_jointype = joinType;
+ newNode->m_endtype = endType;
+
+ //strip duplicate points from path and also get index to the lowest point ...
+ if (endType == etClosedLine || endType == etClosedPolygon)
+ while (highI > 0 && path[0] == path[highI]) highI--;
+ newNode->Contour.reserve(highI + 1);
+ newNode->Contour.push_back(path[0]);
+ int j = 0, k = 0;
+ for (int i = 1; i <= highI; i++)
+ if (newNode->Contour[j] != path[i])
+ {
+ j++;
+ newNode->Contour.push_back(path[i]);
+ if (path[i].Y > newNode->Contour[k].Y ||
+ (path[i].Y == newNode->Contour[k].Y &&
+ path[i].X < newNode->Contour[k].X)) k = j;
+ }
+ if ((endType == etClosedPolygon && j < 2) ||
+ (endType != etClosedPolygon && j < 0))
+ {
+ delete newNode;
+ return;
+ }
+ m_polyNodes.AddChild(*newNode);
+
+ //if this path's lowest pt is lower than all the others then update m_lowest
+ if (endType != etClosedPolygon) return;
+ if (m_lowest.X < 0)
+ m_lowest = IntPoint(0, k);
+ else
+ {
+ IntPoint ip = m_polyNodes.Childs[(int)m_lowest.X]->Contour[(int)m_lowest.Y];
+ if (newNode->Contour[k].Y > ip.Y ||
+ (newNode->Contour[k].Y == ip.Y &&
+ newNode->Contour[k].X < ip.X))
+ m_lowest = IntPoint(m_polyNodes.ChildCount() - 1, k);
+ }
+}
+//------------------------------------------------------------------------------
+
+void ClipperOffset::AddPaths(const Paths& paths, JoinType joinType, EndType endType)
+{
+ for (Paths::size_type i = 0; i < paths.size(); ++i)
+ AddPath(paths[i], joinType, endType);
+}
+//------------------------------------------------------------------------------
+
+void ClipperOffset::FixOrientations()
+{
+ //fixup orientations of all closed paths if the orientation of the
+ //closed path with the lowermost vertex is wrong ...
+ if (m_lowest.X >= 0 &&
+ !Orientation(m_polyNodes.Childs[(int)m_lowest.X]->Contour))
+ {
+ for (int i = 0; i < m_polyNodes.ChildCount(); ++i)
+ {
+ PolyNode& node = *m_polyNodes.Childs[i];
+ if (node.m_endtype == etClosedPolygon ||
+ (node.m_endtype == etClosedLine && Orientation(node.Contour)))
+ ReversePath(node.Contour);
+ }
+ } else
+ {
+ for (int i = 0; i < m_polyNodes.ChildCount(); ++i)
+ {
+ PolyNode& node = *m_polyNodes.Childs[i];
+ if (node.m_endtype == etClosedLine && !Orientation(node.Contour))
+ ReversePath(node.Contour);
+ }
+ }
+}
+//------------------------------------------------------------------------------
+
+void ClipperOffset::Execute(Paths& solution, double delta)
+{
+ solution.clear();
+ FixOrientations();
+ DoOffset(delta);
+
+ //now clean up 'corners' ...
+ Clipper clpr;
+ clpr.AddPaths(m_destPolys, ptSubject, true);
+ if (delta > 0)
+ {
+ clpr.Execute(ctUnion, solution, pftPositive, pftPositive);
+ }
+ else
+ {
+ IntRect r = clpr.GetBounds();
+ Path outer(4);
+ outer[0] = IntPoint(r.left - 10, r.bottom + 10);
+ outer[1] = IntPoint(r.right + 10, r.bottom + 10);
+ outer[2] = IntPoint(r.right + 10, r.top - 10);
+ outer[3] = IntPoint(r.left - 10, r.top - 10);
+
+ clpr.AddPath(outer, ptSubject, true);
+ clpr.ReverseSolution(true);
+ clpr.Execute(ctUnion, solution, pftNegative, pftNegative);
+ if (solution.size() > 0) solution.erase(solution.begin());
+ }
+}
+//------------------------------------------------------------------------------
+
+void ClipperOffset::Execute(PolyTree& solution, double delta)
+{
+ solution.Clear();
+ FixOrientations();
+ DoOffset(delta);
+
+ //now clean up 'corners' ...
+ Clipper clpr;
+ clpr.AddPaths(m_destPolys, ptSubject, true);
+ if (delta > 0)
+ {
+ clpr.Execute(ctUnion, solution, pftPositive, pftPositive);
+ }
+ else
+ {
+ IntRect r = clpr.GetBounds();
+ Path outer(4);
+ outer[0] = IntPoint(r.left - 10, r.bottom + 10);
+ outer[1] = IntPoint(r.right + 10, r.bottom + 10);
+ outer[2] = IntPoint(r.right + 10, r.top - 10);
+ outer[3] = IntPoint(r.left - 10, r.top - 10);
+
+ clpr.AddPath(outer, ptSubject, true);
+ clpr.ReverseSolution(true);
+ clpr.Execute(ctUnion, solution, pftNegative, pftNegative);
+ //remove the outer PolyNode rectangle ...
+ if (solution.ChildCount() == 1 && solution.Childs[0]->ChildCount() > 0)
+ {
+ PolyNode* outerNode = solution.Childs[0];
+ solution.Childs.reserve(outerNode->ChildCount());
+ solution.Childs[0] = outerNode->Childs[0];
+ for (int i = 1; i < outerNode->ChildCount(); ++i)
+ solution.AddChild(*outerNode->Childs[i]);
+ }
+ else
+ solution.Clear();
+ }
+}
+//------------------------------------------------------------------------------
+
+void ClipperOffset::DoOffset(double delta)
+{
+ m_destPolys.clear();
+ m_delta = delta;
+
+ //if Zero offset, just copy any CLOSED polygons to m_p and return ...
+ if (NEAR_ZERO(delta))
+ {
+ m_destPolys.reserve(m_polyNodes.ChildCount());
+ for (int i = 0; i < m_polyNodes.ChildCount(); i++)
+ {
+ PolyNode& node = *m_polyNodes.Childs[i];
+ if (node.m_endtype == etClosedPolygon)
+ m_destPolys.push_back(node.Contour);
+ }
+ return;
+ }
+
+ //see offset_triginometry3.svg in the documentation folder ...
+ if (MiterLimit > 2) m_miterLim = 2/(MiterLimit * MiterLimit);
+ else m_miterLim = 0.5;
+
+ double y;
+ if (ArcTolerance <= 0.0) y = def_arc_tolerance;
+ else if (ArcTolerance > std::fabs(delta) * def_arc_tolerance)
+ y = std::fabs(delta) * def_arc_tolerance;
+ else y = ArcTolerance;
+ //see offset_triginometry2.svg in the documentation folder ...
+ double steps = pi / std::acos(1 - y / std::fabs(delta));
+ if (steps > std::fabs(delta) * pi)
+ steps = std::fabs(delta) * pi; //ie excessive precision check
+ m_sin = std::sin(two_pi / steps);
+ m_cos = std::cos(two_pi / steps);
+ m_StepsPerRad = steps / two_pi;
+ if (delta < 0.0) m_sin = -m_sin;
+
+ m_destPolys.reserve(m_polyNodes.ChildCount() * 2);
+ for (int i = 0; i < m_polyNodes.ChildCount(); i++)
+ {
+ PolyNode& node = *m_polyNodes.Childs[i];
+ m_srcPoly = node.Contour;
+
+ int len = (int)m_srcPoly.size();
+ if (len == 0 || (delta <= 0 && (len < 3 || node.m_endtype != etClosedPolygon)))
+ continue;
+
+ m_destPoly.clear();
+ if (len == 1)
+ {
+ if (node.m_jointype == jtRound)
+ {
+ double X = 1.0, Y = 0.0;
+ for (cInt j = 1; j <= steps; j++)
+ {
+ m_destPoly.push_back(IntPoint(
+ Round(m_srcPoly[0].X + X * delta),
+ Round(m_srcPoly[0].Y + Y * delta)));
+ double X2 = X;
+ X = X * m_cos - m_sin * Y;
+ Y = X2 * m_sin + Y * m_cos;
+ }
+ }
+ else
+ {
+ double X = -1.0, Y = -1.0;
+ for (int j = 0; j < 4; ++j)
+ {
+ m_destPoly.push_back(IntPoint(
+ Round(m_srcPoly[0].X + X * delta),
+ Round(m_srcPoly[0].Y + Y * delta)));
+ if (X < 0) X = 1;
+ else if (Y < 0) Y = 1;
+ else X = -1;
+ }
+ }
+ m_destPolys.push_back(m_destPoly);
+ continue;
+ }
+ //build m_normals ...
+ m_normals.clear();
+ m_normals.reserve(len);
+ for (int j = 0; j < len - 1; ++j)
+ m_normals.push_back(GetUnitNormal(m_srcPoly[j], m_srcPoly[j + 1]));
+ if (node.m_endtype == etClosedLine || node.m_endtype == etClosedPolygon)
+ m_normals.push_back(GetUnitNormal(m_srcPoly[len - 1], m_srcPoly[0]));
+ else
+ m_normals.push_back(DoublePoint(m_normals[len - 2]));
+
+ if (node.m_endtype == etClosedPolygon)
+ {
+ int k = len - 1;
+ for (int j = 0; j < len; ++j)
+ OffsetPoint(j, k, node.m_jointype);
+ m_destPolys.push_back(m_destPoly);
+ }
+ else if (node.m_endtype == etClosedLine)
+ {
+ int k = len - 1;
+ for (int j = 0; j < len; ++j)
+ OffsetPoint(j, k, node.m_jointype);
+ m_destPolys.push_back(m_destPoly);
+ m_destPoly.clear();
+ //re-build m_normals ...
+ DoublePoint n = m_normals[len -1];
+ for (int j = len - 1; j > 0; j--)
+ m_normals[j] = DoublePoint(-m_normals[j - 1].X, -m_normals[j - 1].Y);
+ m_normals[0] = DoublePoint(-n.X, -n.Y);
+ k = 0;
+ for (int j = len - 1; j >= 0; j--)
+ OffsetPoint(j, k, node.m_jointype);
+ m_destPolys.push_back(m_destPoly);
+ }
+ else
+ {
+ int k = 0;
+ for (int j = 1; j < len - 1; ++j)
+ OffsetPoint(j, k, node.m_jointype);
+
+ IntPoint pt1;
+ if (node.m_endtype == etOpenButt)
+ {
+ int j = len - 1;
+ pt1 = IntPoint((cInt)Round(m_srcPoly[j].X + m_normals[j].X *
+ delta), (cInt)Round(m_srcPoly[j].Y + m_normals[j].Y * delta));
+ m_destPoly.push_back(pt1);
+ pt1 = IntPoint((cInt)Round(m_srcPoly[j].X - m_normals[j].X *
+ delta), (cInt)Round(m_srcPoly[j].Y - m_normals[j].Y * delta));
+ m_destPoly.push_back(pt1);
+ }
+ else
+ {
+ int j = len - 1;
+ k = len - 2;
+ m_sinA = 0;
+ m_normals[j] = DoublePoint(-m_normals[j].X, -m_normals[j].Y);
+ if (node.m_endtype == etOpenSquare)
+ DoSquare(j, k);
+ else
+ DoRound(j, k);
+ }
+
+ //re-build m_normals ...
+ for (int j = len - 1; j > 0; j--)
+ m_normals[j] = DoublePoint(-m_normals[j - 1].X, -m_normals[j - 1].Y);
+ m_normals[0] = DoublePoint(-m_normals[1].X, -m_normals[1].Y);
+
+ k = len - 1;
+ for (int j = k - 1; j > 0; --j) OffsetPoint(j, k, node.m_jointype);
+
+ if (node.m_endtype == etOpenButt)
+ {
+ pt1 = IntPoint((cInt)Round(m_srcPoly[0].X - m_normals[0].X * delta),
+ (cInt)Round(m_srcPoly[0].Y - m_normals[0].Y * delta));
+ m_destPoly.push_back(pt1);
+ pt1 = IntPoint((cInt)Round(m_srcPoly[0].X + m_normals[0].X * delta),
+ (cInt)Round(m_srcPoly[0].Y + m_normals[0].Y * delta));
+ m_destPoly.push_back(pt1);
+ }
+ else
+ {
+ k = 1;
+ m_sinA = 0;
+ if (node.m_endtype == etOpenSquare)
+ DoSquare(0, 1);
+ else
+ DoRound(0, 1);
+ }
+ m_destPolys.push_back(m_destPoly);
+ }
+ }
+}
+//------------------------------------------------------------------------------
+
+void ClipperOffset::OffsetPoint(int j, int& k, JoinType jointype)
+{
+ m_sinA = (m_normals[k].X * m_normals[j].Y - m_normals[j].X * m_normals[k].Y);
+ if (m_sinA * m_delta < 1.0 && m_sinA * m_delta > -1.0) return;
+ else if (m_sinA > 1.0) m_sinA = 1.0;
+ else if (m_sinA < -1.0) m_sinA = -1.0;
+
+ if (m_sinA * m_delta < 0)
+ {
+ m_destPoly.push_back(IntPoint(Round(m_srcPoly[j].X + m_normals[k].X * m_delta),
+ Round(m_srcPoly[j].Y + m_normals[k].Y * m_delta)));
+ m_destPoly.push_back(m_srcPoly[j]);
+ m_destPoly.push_back(IntPoint(Round(m_srcPoly[j].X + m_normals[j].X * m_delta),
+ Round(m_srcPoly[j].Y + m_normals[j].Y * m_delta)));
+ }
+ else
+ switch (jointype)
+ {
+ case jtMiter:
+ {
+ double r = 1 + (m_normals[j].X * m_normals[k].X +
+ m_normals[j].Y * m_normals[k].Y);
+ if (r >= m_miterLim) DoMiter(j, k, r); else DoSquare(j, k);
+ break;
+ }
+ case jtSquare: DoSquare(j, k); break;
+ case jtRound: DoRound(j, k); break;
+ }
+ k = j;
+}
+//------------------------------------------------------------------------------
+
+void ClipperOffset::DoSquare(int j, int k)
+{
+ double dx = std::tan(std::atan2(m_sinA,
+ m_normals[k].X * m_normals[j].X + m_normals[k].Y * m_normals[j].Y) / 4);
+ m_destPoly.push_back(IntPoint(
+ Round(m_srcPoly[j].X + m_delta * (m_normals[k].X - m_normals[k].Y * dx)),
+ Round(m_srcPoly[j].Y + m_delta * (m_normals[k].Y + m_normals[k].X * dx))));
+ m_destPoly.push_back(IntPoint(
+ Round(m_srcPoly[j].X + m_delta * (m_normals[j].X + m_normals[j].Y * dx)),
+ Round(m_srcPoly[j].Y + m_delta * (m_normals[j].Y - m_normals[j].X * dx))));
+}
+//------------------------------------------------------------------------------
+
+void ClipperOffset::DoMiter(int j, int k, double r)
+{
+ double q = m_delta / r;
+ m_destPoly.push_back(IntPoint(Round(m_srcPoly[j].X + (m_normals[k].X + m_normals[j].X) * q),
+ Round(m_srcPoly[j].Y + (m_normals[k].Y + m_normals[j].Y) * q)));
+}
+//------------------------------------------------------------------------------
+
+void ClipperOffset::DoRound(int j, int k)
+{
+ double a = std::atan2(m_sinA,
+ m_normals[k].X * m_normals[j].X + m_normals[k].Y * m_normals[j].Y);
+ int steps = (int)Round(m_StepsPerRad * std::fabs(a));
+
+ double X = m_normals[k].X, Y = m_normals[k].Y, X2;
+ for (int i = 0; i < steps; ++i)
+ {
+ m_destPoly.push_back(IntPoint(
+ Round(m_srcPoly[j].X + X * m_delta),
+ Round(m_srcPoly[j].Y + Y * m_delta)));
+ X2 = X;
+ X = X * m_cos - m_sin * Y;
+ Y = X2 * m_sin + Y * m_cos;
+ }
+ m_destPoly.push_back(IntPoint(
+ Round(m_srcPoly[j].X + m_normals[j].X * m_delta),
+ Round(m_srcPoly[j].Y + m_normals[j].Y * m_delta)));
+}
+
+//------------------------------------------------------------------------------
+// Miscellaneous public functions
+//------------------------------------------------------------------------------
+
+void Clipper::DoSimplePolygons()
+{
+ PolyOutList::size_type i = 0;
+ while (i < m_PolyOuts.size())
+ {
+ OutRec* outrec = m_PolyOuts[i++];
+ OutPt* op = outrec->Pts;
+ if (!op) continue;
+ do //for each Pt in Polygon until duplicate found do ...
+ {
+ OutPt* op2 = op->Next;
+ while (op2 != outrec->Pts)
+ {
+ if ((op->Pt == op2->Pt) && op2->Next != op && op2->Prev != op)
+ {
+ //split the polygon into two ...
+ OutPt* op3 = op->Prev;
+ OutPt* op4 = op2->Prev;
+ op->Prev = op4;
+ op4->Next = op;
+ op2->Prev = op3;
+ op3->Next = op2;
+
+ outrec->Pts = op;
+ OutRec* outrec2 = CreateOutRec();
+ outrec2->Pts = op2;
+ UpdateOutPtIdxs(*outrec2);
+ if (Poly2ContainsPoly1(outrec2->Pts, outrec->Pts))
+ {
+ //OutRec2 is contained by OutRec1 ...
+ outrec2->IsHole = !outrec->IsHole;
+ outrec2->FirstLeft = outrec;
+ }
+ else
+ if (Poly2ContainsPoly1(outrec->Pts, outrec2->Pts))
+ {
+ //OutRec1 is contained by OutRec2 ...
+ outrec2->IsHole = outrec->IsHole;
+ outrec->IsHole = !outrec2->IsHole;
+ outrec2->FirstLeft = outrec->FirstLeft;
+ outrec->FirstLeft = outrec2;
+ } else
+ {
+ //the 2 polygons are separate ...
+ outrec2->IsHole = outrec->IsHole;
+ outrec2->FirstLeft = outrec->FirstLeft;
+ }
+ op2 = op; //ie get ready for the Next iteration
+ }
+ op2 = op2->Next;
+ }
+ op = op->Next;
+ }
+ while (op != outrec->Pts);
+ }
+}
+//------------------------------------------------------------------------------
+
+void ReversePath(Path& p)
+{
+ std::reverse(p.begin(), p.end());
+}
+//------------------------------------------------------------------------------
+
+void ReversePaths(Paths& p)
+{
+ for (Paths::size_type i = 0; i < p.size(); ++i)
+ ReversePath(p[i]);
+}
+//------------------------------------------------------------------------------
+
+void SimplifyPolygon(const Path &in_poly, Paths &out_polys, PolyFillType fillType)
+{
+ Clipper c;
+ c.StrictlySimple(true);
+ c.AddPath(in_poly, ptSubject, true);
+ c.Execute(ctUnion, out_polys, fillType, fillType);
+}
+//------------------------------------------------------------------------------
+
+void SimplifyPolygons(const Paths &in_polys, Paths &out_polys, PolyFillType fillType)
+{
+ Clipper c;
+ c.StrictlySimple(true);
+ c.AddPaths(in_polys, ptSubject, true);
+ c.Execute(ctUnion, out_polys, fillType, fillType);
+}
+//------------------------------------------------------------------------------
+
+void SimplifyPolygons(Paths &polys, PolyFillType fillType)
+{
+ SimplifyPolygons(polys, polys, fillType);
+}
+//------------------------------------------------------------------------------
+
+inline double DistanceSqrd(const IntPoint& pt1, const IntPoint& pt2)
+{
+ double Dx = ((double)pt1.X - pt2.X);
+ double dy = ((double)pt1.Y - pt2.Y);
+ return (Dx*Dx + dy*dy);
+}
+//------------------------------------------------------------------------------
+
+double DistanceFromLineSqrd(
+ const IntPoint& pt, const IntPoint& ln1, const IntPoint& ln2)
+{
+ //The equation of a line in general form (Ax + By + C = 0)
+ //given 2 points (x¹,y¹) & (x²,y²) is ...
+ //(y¹ - y²)x + (x² - x¹)y + (y² - y¹)x¹ - (x² - x¹)y¹ = 0
+ //A = (y¹ - y²); B = (x² - x¹); C = (y² - y¹)x¹ - (x² - x¹)y¹
+ //perpendicular distance of point (x³,y³) = (Ax³ + By³ + C)/Sqrt(A² + B²)
+ //see http://en.wikipedia.org/wiki/Perpendicular_distance
+ double A = double(ln1.Y - ln2.Y);
+ double B = double(ln2.X - ln1.X);
+ double C = A * ln1.X + B * ln1.Y;
+ C = A * pt.X + B * pt.Y - C;
+ return (C * C) / (A * A + B * B);
+}
+//---------------------------------------------------------------------------
+
+bool SlopesNearCollinear(const IntPoint& pt1,
+ const IntPoint& pt2, const IntPoint& pt3, double distSqrd)
+{
+ return DistanceFromLineSqrd(pt2, pt1, pt3) < distSqrd;
+}
+//------------------------------------------------------------------------------
+
+bool PointsAreClose(IntPoint pt1, IntPoint pt2, double distSqrd)
+{
+ double Dx = (double)pt1.X - pt2.X;
+ double dy = (double)pt1.Y - pt2.Y;
+ return ((Dx * Dx) + (dy * dy) <= distSqrd);
+}
+//------------------------------------------------------------------------------
+
+OutPt* ExcludeOp(OutPt* op)
+{
+ OutPt* result = op->Prev;
+ result->Next = op->Next;
+ op->Next->Prev = result;
+ result->Idx = 0;
+ return result;
+}
+//------------------------------------------------------------------------------
+
+void CleanPolygon(const Path& in_poly, Path& out_poly, double distance)
+{
+ //distance = proximity in units/pixels below which vertices
+ //will be stripped. Default ~= sqrt(2).
+
+ size_t size = in_poly.size();
+
+ if (size == 0)
+ {
+ out_poly.clear();
+ return;
+ }
+
+ OutPt* outPts = new OutPt[size];
+ for (size_t i = 0; i < size; ++i)
+ {
+ outPts[i].Pt = in_poly[i];
+ outPts[i].Next = &outPts[(i + 1) % size];
+ outPts[i].Next->Prev = &outPts[i];
+ outPts[i].Idx = 0;
+ }
+
+ double distSqrd = distance * distance;
+ OutPt* op = &outPts[0];
+ while (op->Idx == 0 && op->Next != op->Prev)
+ {
+ if (PointsAreClose(op->Pt, op->Prev->Pt, distSqrd))
+ {
+ op = ExcludeOp(op);
+ size--;
+ }
+ else if (PointsAreClose(op->Prev->Pt, op->Next->Pt, distSqrd))
+ {
+ ExcludeOp(op->Next);
+ op = ExcludeOp(op);
+ size -= 2;
+ }
+ else if (SlopesNearCollinear(op->Prev->Pt, op->Pt, op->Next->Pt, distSqrd))
+ {
+ op = ExcludeOp(op);
+ size--;
+ }
+ else
+ {
+ op->Idx = 1;
+ op = op->Next;
+ }
+ }
+
+ if (size < 3) size = 0;
+ out_poly.resize(size);
+ for (size_t i = 0; i < size; ++i)
+ {
+ out_poly[i] = op->Pt;
+ op = op->Next;
+ }
+ delete [] outPts;
+}
+//------------------------------------------------------------------------------
+
+void CleanPolygon(Path& poly, double distance)
+{
+ CleanPolygon(poly, poly, distance);
+}
+//------------------------------------------------------------------------------
+
+void CleanPolygons(const Paths& in_polys, Paths& out_polys, double distance)
+{
+ for (Paths::size_type i = 0; i < in_polys.size(); ++i)
+ CleanPolygon(in_polys[i], out_polys[i], distance);
+}
+//------------------------------------------------------------------------------
+
+void CleanPolygons(Paths& polys, double distance)
+{
+ CleanPolygons(polys, polys, distance);
+}
+//------------------------------------------------------------------------------
+
+void Minkowski(const Path& poly, const Path& path,
+ Paths& solution, bool isSum, bool isClosed)
+{
+ int delta = (isClosed ? 1 : 0);
+ size_t polyCnt = poly.size();
+ size_t pathCnt = path.size();
+ Paths pp;
+ pp.reserve(pathCnt);
+ if (isSum)
+ for (size_t i = 0; i < pathCnt; ++i)
+ {
+ Path p;
+ p.reserve(polyCnt);
+ for (size_t j = 0; j < poly.size(); ++j)
+ p.push_back(IntPoint(path[i].X + poly[j].X, path[i].Y + poly[j].Y));
+ pp.push_back(p);
+ }
+ else
+ for (size_t i = 0; i < pathCnt; ++i)
+ {
+ Path p;
+ p.reserve(polyCnt);
+ for (size_t j = 0; j < poly.size(); ++j)
+ p.push_back(IntPoint(path[i].X - poly[j].X, path[i].Y - poly[j].Y));
+ pp.push_back(p);
+ }
+
+ Paths quads;
+ quads.reserve((pathCnt + delta) * (polyCnt + 1));
+ for (size_t i = 0; i < pathCnt - 1 + delta; ++i)
+ for (size_t j = 0; j < polyCnt; ++j)
+ {
+ Path quad;
+ quad.reserve(4);
+ quad.push_back(pp[i % pathCnt][j % polyCnt]);
+ quad.push_back(pp[(i + 1) % pathCnt][j % polyCnt]);
+ quad.push_back(pp[(i + 1) % pathCnt][(j + 1) % polyCnt]);
+ quad.push_back(pp[i % pathCnt][(j + 1) % polyCnt]);
+ if (!Orientation(quad)) ReversePath(quad);
+ quads.push_back(quad);
+ }
+
+ Clipper c;
+ c.AddPaths(quads, ptSubject, true);
+ c.Execute(ctUnion, solution, pftNonZero, pftNonZero);
+}
+//------------------------------------------------------------------------------
+
+void MinkowskiSum(const Path& pattern, const Path& path, Paths& solution, bool pathIsClosed)
+{
+ Minkowski(pattern, path, solution, true, pathIsClosed);
+}
+//------------------------------------------------------------------------------
+
+void MinkowskiSum(const Path& pattern, const Paths& paths, Paths& solution,
+ PolyFillType pathFillType, bool pathIsClosed)
+{
+ Clipper c;
+ for (size_t i = 0; i < paths.size(); ++i)
+ {
+ Paths tmp;
+ Minkowski(pattern, paths[i], tmp, true, pathIsClosed);
+ c.AddPaths(tmp, ptSubject, true);
+ }
+ if (pathIsClosed) c.AddPaths(paths, ptClip, true);
+ c.Execute(ctUnion, solution, pathFillType, pathFillType);
+}
+//------------------------------------------------------------------------------
+
+void MinkowskiDiff(const Path& poly1, const Path& poly2, Paths& solution)
+{
+ Minkowski(poly1, poly2, solution, false, true);
+}
+//------------------------------------------------------------------------------
+
+enum NodeType {ntAny, ntOpen, ntClosed};
+
+void AddPolyNodeToPolygons(const PolyNode& polynode, NodeType nodetype, Paths& paths)
+{
+ bool match = true;
+ if (nodetype == ntClosed) match = !polynode.IsOpen();
+ else if (nodetype == ntOpen) return;
+
+ if (!polynode.Contour.empty() && match)
+ paths.push_back(polynode.Contour);
+ for (int i = 0; i < polynode.ChildCount(); ++i)
+ AddPolyNodeToPolygons(*polynode.Childs[i], nodetype, paths);
+}
+//------------------------------------------------------------------------------
+
+void PolyTreeToPaths(const PolyTree& polytree, Paths& paths)
+{
+ paths.resize(0);
+ paths.reserve(polytree.Total());
+ AddPolyNodeToPolygons(polytree, ntAny, paths);
+}
+//------------------------------------------------------------------------------
+
+void ClosedPathsFromPolyTree(const PolyTree& polytree, Paths& paths)
+{
+ paths.resize(0);
+ paths.reserve(polytree.Total());
+ AddPolyNodeToPolygons(polytree, ntClosed, paths);
+}
+//------------------------------------------------------------------------------
+
+void OpenPathsFromPolyTree(PolyTree& polytree, Paths& paths)
+{
+ paths.resize(0);
+ paths.reserve(polytree.Total());
+ //Open paths are top level only, so ...
+ for (int i = 0; i < polytree.ChildCount(); ++i)
+ if (polytree.Childs[i]->IsOpen())
+ paths.push_back(polytree.Childs[i]->Contour);
+}
+//------------------------------------------------------------------------------
+
+std::ostream& operator <<(std::ostream &s, const IntPoint &p)
+{
+ s << "(" << p.X << "," << p.Y << ")";
+ return s;
+}
+//------------------------------------------------------------------------------
+
+std::ostream& operator <<(std::ostream &s, const Path &p)
+{
+ if (p.empty()) return s;
+ Path::size_type last = p.size() -1;
+ for (Path::size_type i = 0; i < last; i++)
+ s << "(" << p[i].X << "," << p[i].Y << "), ";
+ s << "(" << p[last].X << "," << p[last].Y << ")\n";
+ return s;
+}
+//------------------------------------------------------------------------------
+
+std::ostream& operator <<(std::ostream &s, const Paths &p)
+{
+ for (Paths::size_type i = 0; i < p.size(); i++)
+ s << p[i];
+ s << "\n";
+ return s;
+}
+//------------------------------------------------------------------------------
+
+#ifdef use_deprecated
+
+void OffsetPaths(const Paths &in_polys, Paths &out_polys,
+ double delta, JoinType jointype, EndType_ endtype, double limit)
+{
+ ClipperOffset co(limit, limit);
+ co.AddPaths(in_polys, jointype, (EndType)endtype);
+ co.Execute(out_polys, delta);
+}
+//------------------------------------------------------------------------------
+
+#endif
+
+
+} //ClipperLib namespace
diff --git a/libs/clipper/clipper.hpp b/libs/clipper/clipper.hpp
new file mode 100644
index 000000000..84870141e
--- /dev/null
+++ b/libs/clipper/clipper.hpp
@@ -0,0 +1,398 @@
+/*******************************************************************************
+* *
+* Author : Angus Johnson *
+* Version : 6.1.3a *
+* Date : 22 January 2014 *
+* Website : http://www.angusj.com *
+* Copyright : Angus Johnson 2010-2014 *
+* *
+* License: *
+* Use, modification & distribution is subject to Boost Software License Ver 1. *
+* http://www.boost.org/LICENSE_1_0.txt *
+* *
+* Attributions: *
+* The code in this library is an extension of Bala Vatti's clipping algorithm: *
+* "A generic solution to polygon clipping" *
+* Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63. *
+* http://portal.acm.org/citation.cfm?id=129906 *
+* *
+* Computer graphics and geometric modeling: implementation and algorithms *
+* By Max K. Agoston *
+* Springer; 1 edition (January 4, 2005) *
+* http://books.google.com/books?q=vatti+clipping+agoston *
+* *
+* See also: *
+* "Polygon Offsetting by Computing Winding Numbers" *
+* Paper no. DETC2005-85513 pp. 565-575 *
+* ASME 2005 International Design Engineering Technical Conferences *
+* and Computers and Information in Engineering Conference (IDETC/CIE2005) *
+* September 24-28, 2005 , Long Beach, California, USA *
+* http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf *
+* *
+*******************************************************************************/
+
+#ifndef clipper_hpp
+#define clipper_hpp
+
+#define CLIPPER_VERSION "6.1.3"
+
+//use_int32: When enabled 32bit ints are used instead of 64bit ints. This
+//improve performance but coordinate values are limited to the range +/- 46340
+//#define use_int32
+
+//use_xyz: adds a Z member to IntPoint. Adds a minor cost to perfomance.
+//#define use_xyz
+
+//use_lines: Enables line clipping. Adds a very minor cost to performance.
+//#define use_lines
+
+//use_deprecated: Enables support for the obsolete OffsetPaths() function
+//which has been replace with the ClipperOffset class.
+#define use_deprecated
+
+#include <vector>
+#include <set>
+#include <stdexcept>
+#include <cstring>
+#include <cstdlib>
+#include <ostream>
+#include <functional>
+
+namespace ClipperLib {
+
+enum ClipType { ctIntersection, ctUnion, ctDifference, ctXor };
+enum PolyType { ptSubject, ptClip };
+//By far the most widely used winding rules for polygon filling are
+//EvenOdd & NonZero (GDI, GDI+, XLib, OpenGL, Cairo, AGG, Quartz, SVG, Gr32)
+//Others rules include Positive, Negative and ABS_GTR_EQ_TWO (only in OpenGL)
+//see http://glprogramming.com/red/chapter11.html
+enum PolyFillType { pftEvenOdd, pftNonZero, pftPositive, pftNegative };
+
+#ifdef use_int32
+typedef int cInt;
+typedef unsigned int cUInt;
+#else
+typedef signed long long cInt;
+typedef unsigned long long cUInt;
+#endif
+
+struct IntPoint {
+ cInt X;
+ cInt Y;
+#ifdef use_xyz
+ cInt Z;
+ IntPoint(cInt x = 0, cInt y = 0, cInt z = 0): X(x), Y(y), Z(z) {};
+#else
+ IntPoint(cInt x = 0, cInt y = 0): X(x), Y(y) {};
+#endif
+
+ friend inline bool operator== (const IntPoint& a, const IntPoint& b)
+ {
+ return a.X == b.X && a.Y == b.Y;
+ }
+ friend inline bool operator!= (const IntPoint& a, const IntPoint& b)
+ {
+ return a.X != b.X || a.Y != b.Y;
+ }
+};
+//------------------------------------------------------------------------------
+
+typedef std::vector< IntPoint > Path;
+typedef std::vector< Path > Paths;
+
+inline Path& operator <<(Path& poly, const IntPoint& p) {poly.push_back(p); return poly;}
+inline Paths& operator <<(Paths& polys, const Path& p) {polys.push_back(p); return polys;}
+
+std::ostream& operator <<(std::ostream &s, const IntPoint &p);
+std::ostream& operator <<(std::ostream &s, const Path &p);
+std::ostream& operator <<(std::ostream &s, const Paths &p);
+
+struct DoublePoint
+{
+ double X;
+ double Y;
+ DoublePoint(double x = 0, double y = 0) : X(x), Y(y) {}
+ DoublePoint(IntPoint ip) : X((double)ip.X), Y((double)ip.Y) {}
+};
+//------------------------------------------------------------------------------
+
+#ifdef use_xyz
+typedef void (*TZFillCallback)(IntPoint& z1, IntPoint& z2, IntPoint& pt);
+#endif
+
+enum InitOptions {ioReverseSolution = 1, ioStrictlySimple = 2, ioPreserveCollinear = 4};
+enum JoinType {jtSquare, jtRound, jtMiter};
+enum EndType {etClosedPolygon, etClosedLine, etOpenButt, etOpenSquare, etOpenRound};
+#ifdef use_deprecated
+ enum EndType_ {etClosed, etButt = 2, etSquare, etRound};
+#endif
+
+class PolyNode;
+typedef std::vector< PolyNode* > PolyNodes;
+
+class PolyNode
+{
+public:
+ PolyNode();
+ Path Contour;
+ PolyNodes Childs;
+ PolyNode* Parent;
+ PolyNode* GetNext() const;
+ bool IsHole() const;
+ bool IsOpen() const;
+ int ChildCount() const;
+private:
+ unsigned Index; //node index in Parent.Childs
+ bool m_IsOpen;
+ JoinType m_jointype;
+ EndType m_endtype;
+ PolyNode* GetNextSiblingUp() const;
+ void AddChild(PolyNode& child);
+ friend class Clipper; //to access Index
+ friend class ClipperOffset;
+};
+
+class PolyTree: public PolyNode
+{
+public:
+ ~PolyTree(){Clear();};
+ PolyNode* GetFirst() const;
+ void Clear();
+ int Total() const;
+private:
+ PolyNodes AllNodes;
+ friend class Clipper; //to access AllNodes
+};
+
+bool Orientation(const Path &poly);
+double Area(const Path &poly);
+int PointInPolygon(const IntPoint &pt, const Path &path);
+
+#ifdef use_deprecated
+ void OffsetPaths(const Paths &in_polys, Paths &out_polys,
+ double delta, JoinType jointype, EndType_ endtype, double limit = 0);
+#endif
+
+void SimplifyPolygon(const Path &in_poly, Paths &out_polys, PolyFillType fillType = pftEvenOdd);
+void SimplifyPolygons(const Paths &in_polys, Paths &out_polys, PolyFillType fillType = pftEvenOdd);
+void SimplifyPolygons(Paths &polys, PolyFillType fillType = pftEvenOdd);
+
+void CleanPolygon(const Path& in_poly, Path& out_poly, double distance = 1.415);
+void CleanPolygon(Path& poly, double distance = 1.415);
+void CleanPolygons(const Paths& in_polys, Paths& out_polys, double distance = 1.415);
+void CleanPolygons(Paths& polys, double distance = 1.415);
+
+void MinkowskiSum(const Path& pattern, const Path& path, Paths& solution, bool pathIsClosed);
+void MinkowskiSum(const Path& pattern, const Paths& paths,
+ Paths& solution, PolyFillType pathFillType, bool pathIsClosed);
+void MinkowskiDiff(const Path& poly1, const Path& poly2, Paths& solution);
+
+void PolyTreeToPaths(const PolyTree& polytree, Paths& paths);
+void ClosedPathsFromPolyTree(const PolyTree& polytree, Paths& paths);
+void OpenPathsFromPolyTree(PolyTree& polytree, Paths& paths);
+
+void ReversePath(Path& p);
+void ReversePaths(Paths& p);
+
+struct IntRect { cInt left; cInt top; cInt right; cInt bottom; };
+
+//enums that are used internally ...
+enum EdgeSide { esLeft = 1, esRight = 2};
+
+//forward declarations (for stuff used internally) ...
+struct TEdge;
+struct IntersectNode;
+struct LocalMinima;
+struct Scanbeam;
+struct OutPt;
+struct OutRec;
+struct Join;
+
+typedef std::vector < OutRec* > PolyOutList;
+typedef std::vector < TEdge* > EdgeList;
+typedef std::vector < Join* > JoinList;
+typedef std::vector < IntersectNode* > IntersectList;
+
+
+//------------------------------------------------------------------------------
+
+//ClipperBase is the ancestor to the Clipper class. It should not be
+//instantiated directly. This class simply abstracts the conversion of sets of
+//polygon coordinates into edge objects that are stored in a LocalMinima list.
+class ClipperBase
+{
+public:
+ ClipperBase();
+ virtual ~ClipperBase();
+ bool AddPath(const Path &pg, PolyType PolyTyp, bool Closed);
+ bool AddPaths(const Paths &ppg, PolyType PolyTyp, bool Closed);
+ virtual void Clear();
+ IntRect GetBounds();
+ bool PreserveCollinear() {return m_PreserveCollinear;};
+ void PreserveCollinear(bool value) {m_PreserveCollinear = value;};
+protected:
+ void DisposeLocalMinimaList();
+ TEdge* AddBoundsToLML(TEdge *e, bool IsClosed);
+ void PopLocalMinima();
+ virtual void Reset();
+ TEdge* ProcessBound(TEdge* E, bool IsClockwise);
+ void InsertLocalMinima(LocalMinima *newLm);
+ void DoMinimaLML(TEdge* E1, TEdge* E2, bool IsClosed);
+ TEdge* DescendToMin(TEdge *&E);
+ void AscendToMax(TEdge *&E, bool Appending, bool IsClosed);
+ LocalMinima *m_CurrentLM;
+ LocalMinima *m_MinimaList;
+ bool m_UseFullRange;
+ EdgeList m_edges;
+ bool m_PreserveCollinear;
+ bool m_HasOpenPaths;
+};
+//------------------------------------------------------------------------------
+
+class Clipper : public virtual ClipperBase
+{
+public:
+ Clipper(int initOptions = 0);
+ ~Clipper();
+ bool Execute(ClipType clipType,
+ Paths &solution,
+ PolyFillType subjFillType = pftEvenOdd,
+ PolyFillType clipFillType = pftEvenOdd);
+ bool Execute(ClipType clipType,
+ PolyTree &polytree,
+ PolyFillType subjFillType = pftEvenOdd,
+ PolyFillType clipFillType = pftEvenOdd);
+ bool ReverseSolution() {return m_ReverseOutput;};
+ void ReverseSolution(bool value) {m_ReverseOutput = value;};
+ bool StrictlySimple() {return m_StrictSimple;};
+ void StrictlySimple(bool value) {m_StrictSimple = value;};
+ //set the callback function for z value filling on intersections (otherwise Z is 0)
+#ifdef use_xyz
+ void ZFillFunction(TZFillCallback zFillFunc);
+#endif
+protected:
+ void Reset();
+ virtual bool ExecuteInternal();
+private:
+ PolyOutList m_PolyOuts;
+ JoinList m_Joins;
+ JoinList m_GhostJoins;
+ IntersectList m_IntersectList;
+ ClipType m_ClipType;
+ std::set< cInt, std::greater<cInt> > m_Scanbeam;
+ TEdge *m_ActiveEdges;
+ TEdge *m_SortedEdges;
+ bool m_ExecuteLocked;
+ PolyFillType m_ClipFillType;
+ PolyFillType m_SubjFillType;
+ bool m_ReverseOutput;
+ bool m_UsingPolyTree;
+ bool m_StrictSimple;
+#ifdef use_xyz
+ TZFillCallback m_ZFill; //custom callback
+#endif
+ void SetWindingCount(TEdge& edge);
+ bool IsEvenOddFillType(const TEdge& edge) const;
+ bool IsEvenOddAltFillType(const TEdge& edge) const;
+ void InsertScanbeam(const cInt Y);
+ cInt PopScanbeam();
+ void InsertLocalMinimaIntoAEL(const cInt botY);
+ void InsertEdgeIntoAEL(TEdge *edge, TEdge* startEdge);
+ void AddEdgeToSEL(TEdge *edge);
+ void CopyAELToSEL();
+ void DeleteFromSEL(TEdge *e);
+ void DeleteFromAEL(TEdge *e);
+ void UpdateEdgeIntoAEL(TEdge *&e);
+ void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2);
+ bool IsContributing(const TEdge& edge) const;
+ bool IsTopHorz(const cInt XPos);
+ void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2);
+ void DoMaxima(TEdge *e);
+ void PrepareHorzJoins(TEdge* horzEdge, bool isTopOfScanbeam);
+ void ProcessHorizontals(bool IsTopOfScanbeam);
+ void ProcessHorizontal(TEdge *horzEdge, bool isTopOfScanbeam);
+ void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
+ OutPt* AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
+ OutRec* GetOutRec(int idx);
+ void AppendPolygon(TEdge *e1, TEdge *e2);
+ void IntersectEdges(TEdge *e1, TEdge *e2,
+ const IntPoint &pt, bool protect = false);
+ OutRec* CreateOutRec();
+ OutPt* AddOutPt(TEdge *e, const IntPoint &pt);
+ void DisposeAllOutRecs();
+ void DisposeOutRec(PolyOutList::size_type index);
+ bool ProcessIntersections(const cInt botY, const cInt topY);
+ void BuildIntersectList(const cInt botY, const cInt topY);
+ void ProcessIntersectList();
+ void ProcessEdgesAtTopOfScanbeam(const cInt topY);
+ void BuildResult(Paths& polys);
+ void BuildResult2(PolyTree& polytree);
+ void SetHoleState(TEdge *e, OutRec *outrec);
+ void DisposeIntersectNodes();
+ bool FixupIntersectionOrder();
+ void FixupOutPolygon(OutRec &outrec);
+ bool IsHole(TEdge *e);
+ bool FindOwnerFromSplitRecs(OutRec &outRec, OutRec *&currOrfl);
+ void FixHoleLinkage(OutRec &outrec);
+ void AddJoin(OutPt *op1, OutPt *op2, const IntPoint offPt);
+ void ClearJoins();
+ void ClearGhostJoins();
+ void AddGhostJoin(OutPt *op, const IntPoint offPt);
+ bool JoinPoints(Join *j, OutRec* outRec1, OutRec* outRec2);
+ void JoinCommonEdges();
+ void DoSimplePolygons();
+ void FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec);
+ void FixupFirstLefts2(OutRec* OldOutRec, OutRec* NewOutRec);
+#ifdef use_xyz
+ void SetZ(IntPoint& pt, TEdge& e);
+#endif
+};
+//------------------------------------------------------------------------------
+
+class ClipperOffset
+{
+public:
+ ClipperOffset(double miterLimit = 2.0, double roundPrecision = 0.25);
+ ~ClipperOffset();
+ void AddPath(const Path& path, JoinType joinType, EndType endType);
+ void AddPaths(const Paths& paths, JoinType joinType, EndType endType);
+ void Execute(Paths& solution, double delta);
+ void Execute(PolyTree& solution, double delta);
+ void Clear();
+ double MiterLimit;
+ double ArcTolerance;
+private:
+ Paths m_destPolys;
+ Path m_srcPoly;
+ Path m_destPoly;
+ std::vector<DoublePoint> m_normals;
+ double m_delta, m_sinA, m_sin, m_cos;
+ double m_miterLim, m_StepsPerRad;
+ IntPoint m_lowest;
+ PolyNode m_polyNodes;
+
+ void FixOrientations();
+ void DoOffset(double delta);
+ void OffsetPoint(int j, int& k, JoinType jointype);
+ void DoSquare(int j, int k);
+ void DoMiter(int j, int k, double r);
+ void DoRound(int j, int k);
+};
+//------------------------------------------------------------------------------
+
+class clipperException : public std::exception
+{
+ public:
+ clipperException(const char* description): m_descr(description) {}
+ virtual ~clipperException() throw() {}
+ virtual const char* what() const throw() {return m_descr.c_str();}
+ private:
+ std::string m_descr;
+};
+//------------------------------------------------------------------------------
+
+} //ClipperLib namespace
+
+#endif //clipper_hpp
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-11 11:36:34 +0300