>From an architecture perspective, having the clipper header be exported and >published violates encapsulation and introduces a lib dependence. Can it move >to the src dir, private header?
> On Oct 17, 2018, at 8:45 AM, starseeker--- via brlcad-commits > <brlcad-comm...@lists.sourceforge.net> wrote: > > Revision: 71981 > http://sourceforge.net/p/brlcad/code/71981 > Author: starseeker > Date: 2018-10-17 12:45:54 +0000 (Wed, 17 Oct 2018) > Log Message: > ----------- > Clipper is like the new quickhull - actually easier to embed than try to > maintain in src/other. Move it to libbg for simplicity > > Modified Paths: > -------------- > brlcad/trunk/doc/legal/embedded/CMakeLists.txt > brlcad/trunk/doc/legal/other/CMakeLists.txt > brlcad/trunk/include/bg/CMakeLists.txt > brlcad/trunk/src/libbg/CMakeLists.txt > brlcad/trunk/src/libged/CMakeLists.txt > brlcad/trunk/src/libged/polyclip.cpp > brlcad/trunk/src/other/CMakeLists.txt > > Added Paths: > ----------- > brlcad/trunk/doc/legal/embedded/clipper.txt > brlcad/trunk/include/bg/clipper.hpp > brlcad/trunk/src/libbg/clipper.cxx > > Removed Paths: > ------------- > brlcad/trunk/doc/legal/other/clipper.txt > brlcad/trunk/src/other/clipper/ > brlcad/trunk/src/other/clipper.dist > > Modified: brlcad/trunk/doc/legal/embedded/CMakeLists.txt > =================================================================== > --- brlcad/trunk/doc/legal/embedded/CMakeLists.txt 2018-10-16 12:48:03 UTC > (rev 71980) > +++ brlcad/trunk/doc/legal/embedded/CMakeLists.txt 2018-10-17 12:45:54 UTC > (rev 71981) > @@ -3,6 +3,7 @@ > bullet.txt > chull2d.txt > chull3d.txt > + clipper.txt > db_faa-info.txt > db_nist-info.txt > dehumanize.txt > > Copied: brlcad/trunk/doc/legal/embedded/clipper.txt (from rev 71980, > brlcad/trunk/doc/legal/other/clipper.txt) > =================================================================== > --- brlcad/trunk/doc/legal/embedded/clipper.txt > (rev 0) > +++ brlcad/trunk/doc/legal/embedded/clipper.txt 2018-10-17 12:45:54 UTC > (rev 71981) > @@ -0,0 +1,31 @@ > +http://www.angusj.com/delphi/clipper.php > + > +The Clipper code library, the "Software" (that includes Delphi, C++ & C# > +source code, accompanying samples and documentation), 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 and accompanying documentation covered by > +this license (the "Software") 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. > + > > Modified: brlcad/trunk/doc/legal/other/CMakeLists.txt > =================================================================== > --- brlcad/trunk/doc/legal/other/CMakeLists.txt 2018-10-16 12:48:03 UTC > (rev 71980) > +++ brlcad/trunk/doc/legal/other/CMakeLists.txt 2018-10-17 12:45:54 UTC > (rev 71981) > @@ -1,5 +1,4 @@ > set(other_licenses > - clipper.txt > gct.txt > gdal.txt > incrTcl.txt > > Deleted: brlcad/trunk/doc/legal/other/clipper.txt > =================================================================== > --- brlcad/trunk/doc/legal/other/clipper.txt 2018-10-16 12:48:03 UTC (rev > 71980) > +++ brlcad/trunk/doc/legal/other/clipper.txt 2018-10-17 12:45:54 UTC (rev > 71981) > @@ -1,31 +0,0 @@ > -http://www.angusj.com/delphi/clipper.php > - > -The Clipper code library, the "Software" (that includes Delphi, C++ & C# > -source code, accompanying samples and documentation), 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 and accompanying documentation covered by > -this license (the "Software") 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. > - > > Modified: brlcad/trunk/include/bg/CMakeLists.txt > =================================================================== > --- brlcad/trunk/include/bg/CMakeLists.txt 2018-10-16 12:48:03 UTC (rev > 71980) > +++ brlcad/trunk/include/bg/CMakeLists.txt 2018-10-17 12:45:54 UTC (rev > 71981) > @@ -1,5 +1,6 @@ > set(bg_headers > chull.h > + clipper.hpp > defines.h > obr.h > polygon.h > > Added: brlcad/trunk/include/bg/clipper.hpp > =================================================================== > --- brlcad/trunk/include/bg/clipper.hpp (rev 0) > +++ brlcad/trunk/include/bg/clipper.hpp 2018-10-17 12:45:54 UTC (rev 71981) > @@ -0,0 +1,318 @@ > +/******************************************************************************* > + * > * > + * Author : Angus Johnson > * > + * Version : 4.6 > * > + * Date : 29 October 2011 > * > + * Website : http://www.angusj.com > * > + * Copyright : Angus Johnson 2010-2011 > * > + * > * > + * 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\x9628, 2005 , Long Beach, California, USA > * > + * http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf > * > + * > * > + > *******************************************************************************/ > + > +#ifndef clipper_hpp > +#define clipper_hpp > + > +#include "common.h" > + > +extern "C" { > +#include "bg/defines.h" > +} > + > +#include <vector> > +#include <stdexcept> > +#include <cstring> > +#include <cstdlib> > +#include <ostream> > + > + > +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 }; > + > + typedef signed long long long64; > + typedef unsigned long long ulong64; > + > + struct IntPoint { > + public: > + long64 X; > + long64 Y; > + IntPoint(long64 x = 0, long64 y = 0): X(x), Y(y) {}; > + friend std::ostream& operator <<(std::ostream &s, IntPoint &p); > + }; > + > + typedef std::vector< IntPoint > Polygon; > + typedef std::vector< Polygon > Polygons; > + > + std::ostream& operator <<(std::ostream &s, Polygon &p); > + std::ostream& operator <<(std::ostream &s, Polygons &p); > + > + struct ExPolygon { > + Polygon outer; > + Polygons holes; > + }; > + typedef std::vector< ExPolygon > ExPolygons; > + > + enum JoinType { jtSquare, jtMiter, jtRound }; > + > + BG_EXPORT bool Orientation(const Polygon &poly); > + BG_EXPORT double Area(const Polygon &poly); > + BG_EXPORT void OffsetPolygons(const Polygons &in_polys, > + Polygons &out_polys, double delta, JoinType jointype = jtSquare, > + double MiterLimit = 2); > + > + BG_EXPORT void ReversePoints(Polygon& p); > + BG_EXPORT void ReversePoints(Polygons& p); > + > + //used internally ... > + enum EdgeSide { esLeft, esRight }; > + enum IntersectProtects { ipNone = 0, ipLeft = 1, ipRight = 2, ipBoth = 3 > }; > + > + struct TEdge { > + long64 xbot; > + long64 ybot; > + long64 xcurr; > + long64 ycurr; > + long64 xtop; > + long64 ytop; > + double dx; > + long64 tmpX; > + PolyType polyType; > + 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; > + IntersectNode *next; > + }; > + > + struct LocalMinima { > + long64 Y; > + TEdge *leftBound; > + TEdge *rightBound; > + LocalMinima *next; > + }; > + > + struct Scanbeam { > + long64 Y; > + Scanbeam *next; > + }; > + > + struct OutPt; //forward declaration > + > + struct OutRec { > + int idx; > + bool isHole; > + OutRec *FirstLeft; > + OutRec *AppendLink; > + OutPt *pts; > + OutPt *bottomPt; > + TEdge *bottomE1; > + TEdge *bottomE2; > + }; > + > + struct OutPt { > + int idx; > + IntPoint pt; > + OutPt *next; > + OutPt *prev; > + }; > + > + struct JoinRec { > + IntPoint pt1a; > + IntPoint pt1b; > + int poly1Idx; > + IntPoint pt2a; > + IntPoint pt2b; > + int poly2Idx; > + }; > + > + struct HorzJoinRec { > + TEdge *edge; > + int savedIdx; > + }; > + > + struct IntRect { long64 left; long64 top; long64 right; long64 bottom; }; > + > + typedef std::vector < OutRec* > PolyOutList; > + typedef std::vector < TEdge* > EdgeList; > + typedef std::vector < JoinRec* > JoinList; > + typedef std::vector < HorzJoinRec* > HorzJoinList; > + > + //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 BG_EXPORT ClipperBase > + { > + public: > + ClipperBase(); > + virtual ~ClipperBase(); > + bool AddPolygon(const Polygon &pg, PolyType polyType); > + bool AddPolygons( const Polygons &ppg, PolyType polyType); > + virtual void Clear(); > + IntRect GetBounds(); > + protected: > + void DisposeLocalMinimaList(); > + TEdge* AddBoundsToLML(TEdge *e); > + void PopLocalMinima(); > + virtual void Reset(); > + void InsertLocalMinima(LocalMinima *newLm); > + LocalMinima *m_CurrentLM; > + LocalMinima *m_MinimaList; > + bool m_UseFullRange; > + EdgeList *m_edges; > + }; > + > + class BG_EXPORT Clipper : public virtual ClipperBase > + { > + public: > + Clipper(); > + ~Clipper(); > + bool Execute(ClipType clipType, > + Polygons &solution, > + PolyFillType subjFillType = pftEvenOdd, > + PolyFillType clipFillType = pftEvenOdd); > + bool Execute(ClipType clipType, > + ExPolygons &solution, > + PolyFillType subjFillType = pftEvenOdd, > + PolyFillType clipFillType = pftEvenOdd); > + void Clear(); > + bool ReverseSolution() {return m_ReverseOutput;}; > + void ReverseSolution(bool value) {m_ReverseOutput = value;} > + protected: > + void Reset(); > + virtual bool ExecuteInternal(bool fixHoleLinkages); > + private: > + PolyOutList *m_PolyOuts; > + JoinList *m_Joins; > + HorzJoinList *m_HorizJoins; > + ClipType m_ClipType; > + Scanbeam *m_Scanbeam; > + TEdge *m_ActiveEdges; > + TEdge *m_SortedEdges; > + IntersectNode *m_IntersectNodes; > + bool m_ExecuteLocked; > + PolyFillType m_ClipFillType; > + PolyFillType m_SubjFillType; > + bool m_ReverseOutput; > + void DisposeScanbeamList(); > + void SetWindingCount(TEdge& edge); > + bool IsEvenOddFillType(const TEdge& edge) const; > + bool IsEvenOddAltFillType(const TEdge& edge) const; > + void InsertScanbeam(const long64 Y); > + long64 PopScanbeam(); > + void InsertLocalMinimaIntoAEL(const long64 botY); > + void InsertEdgeIntoAEL(TEdge *edge); > + 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 long64 XPos); > + void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2); > + void DoMaxima(TEdge *e, long64 topY); > + void ProcessHorizontals(); > + void ProcessHorizontal(TEdge *horzEdge); > + void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); > + void AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); > + void AppendPolygon(TEdge *e1, TEdge *e2); > + void DoEdge1(TEdge *edge1, TEdge *edge2, const IntPoint &pt); > + void DoEdge2(TEdge *edge1, TEdge *edge2, const IntPoint &pt); > + void DoBothEdges(TEdge *edge1, TEdge *edge2, const IntPoint &pt); > + void IntersectEdges(TEdge *e1, TEdge *e2, > + const IntPoint &pt, IntersectProtects protects); > + OutRec* CreateOutRec(); > + void AddOutPt(TEdge *e, TEdge *altE, const IntPoint &pt); > + void DisposeAllPolyPts(); > + void DisposeOutRec(PolyOutList::size_type index, bool ignorePts = > false); > + bool ProcessIntersections(const long64 botY, const long64 topY); > + void AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt); > + void BuildIntersectList(const long64 botY, const long64 topY); > + void ProcessIntersectList(); > + void ProcessEdgesAtTopOfScanbeam(const long64 topY); > + void BuildResult(Polygons& polys); > + void BuildResultEx(ExPolygons& polys); > + void SetHoleState(TEdge *e, OutRec *OutRec); > + void DisposeIntersectNodes(); > + bool FixupIntersections(); > + void FixupOutPolygon(OutRec &outRec); > + bool IsHole(TEdge *e); > + void FixHoleLinkage(OutRec *outRec); > + void CheckHoleLinkages1(OutRec *outRec1, OutRec *outRec2); > + void CheckHoleLinkages2(OutRec *outRec1, OutRec *outRec2); > + void AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx = -1, int e2OutIdx = > -1); > + void ClearJoins(); > + void AddHorzJoin(TEdge *e, int idx); > + void ClearHorzJoins(); > + void JoinCommonEdges(bool fixHoleLinkages); > + }; > + > + > //------------------------------------------------------------------------------ > + > //------------------------------------------------------------------------------ > + > + class BG_EXPORT clipperException : public std::exception > + { > + public: > + clipperException(const char* description) { m_descr = new > std::string(description);} > + virtual ~clipperException() throw() { delete m_descr; } > + virtual const char* what() const throw() {return m_descr->c_str();} > + private: > + std::string *m_descr; > + }; > + > //------------------------------------------------------------------------------ > + > +} //ClipperLib namespace > + > +#endif //clipper_hpp > + > +// Local Variables: > +// tab-width: 8 > +// mode: C++ > +// c-basic-offset: 4 > +// indent-tabs-mode: t > +// c-file-style: "stroustrup" > +// End: > +// ex: shiftwidth=4 tabstop=8 > + > > > Property changes on: brlcad/trunk/include/bg/clipper.hpp > ___________________________________________________________________ > Added: svn:eol-style > ## -0,0 +1 ## > +native > \ No newline at end of property > Added: svn:mime-type > ## -0,0 +1 ## > +text/plain > \ No newline at end of property > Modified: brlcad/trunk/src/libbg/CMakeLists.txt > =================================================================== > --- brlcad/trunk/src/libbg/CMakeLists.txt 2018-10-16 12:48:03 UTC (rev > 71980) > +++ brlcad/trunk/src/libbg/CMakeLists.txt 2018-10-17 12:45:54 UTC (rev > 71981) > @@ -11,6 +11,7 @@ > chull.c > QuickHull.cxx > chull3d.cxx > + clipper.cxx > obr.c > polygon.c > polygon_ear_clipping.c > > Added: brlcad/trunk/src/libbg/clipper.cxx > =================================================================== > --- brlcad/trunk/src/libbg/clipper.cxx (rev 0) > +++ brlcad/trunk/src/libbg/clipper.cxx 2018-10-17 12:45:54 UTC (rev 71981) > @@ -0,0 +1,3301 @@ > +/******************************************************************************* > + * > * > + * Author : Angus Johnson > * > + * Version : 4.6 > * > + * Date : 29 October 2011 > * > + * Website : http://www.angusj.com > * > + * Copyright : Angus Johnson 2010-2011 > * > + * > * > + * 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\x9628, 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 "bg/clipper.hpp" > +#include <cmath> > +#include <iostream> > +#include <vector> > +#include <algorithm> > +#include <stdexcept> > +#include <cstring> > +#include <cstdlib> > +#include <ostream> > + > +namespace ClipperLib { > + > + static long64 const loRange = 1518500249; //sqrt(2^63 -1)/2 > + static long64 const hiRange = 6521908912666391106LL; //sqrt(2^127 -1)/2 > + static double const pi = 3.141592653589793238; > + enum Direction { dRightToLeft, dLeftToRight }; > + enum RangeTest { rtLo, rtHi, rtError }; > + > +#define HORIZONTAL (-1.0E+40) > +#define TOLERANCE (1.0e-20) > +#define NEAR_ZERO(val) (((val) > -TOLERANCE) && ((val) < TOLERANCE)) > +#define NEAR_EQUAL(a, b) NEAR_ZERO((a) - (b)) > + > + inline long64 Abs(long64 val) > + { > + if (val < 0) return -val; else return val; > + } > + > //------------------------------------------------------------------------------ > + > + > //------------------------------------------------------------------------------ > + // Int128 class (enables safe math on signed 64bit integers) > + // eg Int128 val1((long64)9223372036854775807); //ie 2^63 -1 > + // Int128 val2((long64)9223372036854775807); > + // Int128 val3 = val1 * val2; > + // val3.AsString => "85070591730234615847396907784232501249" (8.5e+37) > + > //------------------------------------------------------------------------------ > + > + class Int128 > + { > + public: > + > + Int128(long64 _lo = 0) > + { > + hi = 0; > + if (_lo < 0) { > + lo = -_lo; > + Negate(*this); > + } else > + lo = _lo; > + } > + > + Int128(const Int128 &val): hi(val.hi), lo(val.lo){} > + > + long64 operator = (const long64 &val) > + { > + hi = 0; > + lo = Abs(val); > + if (val < 0) Negate(*this); > + return val; > + } > + > + 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 true; > + else if (hi < val.hi) return false; > + else return ulong64(lo) > ulong64(val.lo); > + } > + > + bool operator < (const Int128 &val) const > + { > + if (hi < val.hi) return true; > + else if (hi > val.hi) return false; > + else return ulong64(lo) < ulong64(val.lo); > + } > + > + Int128& operator += (const Int128 &rhs) > + { > + hi += rhs.hi; > + lo += rhs.lo; > + if (ulong64(lo) < ulong64(rhs.lo)) hi++; > + return *this; > + } > + > + Int128 operator + (const Int128 &rhs) const > + { > + Int128 result(*this); > + result+= rhs; > + return result; > + } > + > + Int128& operator -= (const Int128 &rhs) > + { > + Int128 tmp(rhs); > + Negate(tmp); > + *this += tmp; > + return *this; > + } > + > + Int128 operator - (const Int128 &rhs) const > + { > + Int128 result(*this); > + result-= rhs; > + return result; > + } > + > + Int128 operator * (const Int128 &rhs) const { > + if ( !(hi == 0 || hi == -1) || !(rhs.hi == 0 || rhs.hi == -1)) > + throw "Int128 operator*: overflow error"; > + bool negate = (hi < 0) != (rhs.hi < 0); > + > + Int128 tmp(*this); > + if (tmp.hi < 0) Negate(tmp); > + ulong64 int1Hi = ulong64(tmp.lo) >> 32; > + ulong64 int1Lo = ulong64(tmp.lo & 0xFFFFFFFF); > + > + tmp = rhs; > + if (tmp.hi < 0) Negate(tmp); > + ulong64 int2Hi = ulong64(tmp.lo) >> 32; > + ulong64 int2Lo = ulong64(tmp.lo & 0xFFFFFFFF); > + > + //nb: see comments in clipper.pas > + ulong64 a = int1Hi * int2Hi; > + ulong64 b = int1Lo * int2Lo; > + ulong64 c = int1Hi * int2Lo + int1Lo * int2Hi; > + > + tmp.hi = long64(a + (c >> 32)); > + tmp.lo = long64(c << 32); > + tmp.lo += long64(b); > + if (ulong64(tmp.lo) < b) tmp.hi++; > + if (negate) Negate(tmp); > + return tmp; > + } > + > + 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 result(*this), denom(rhs); > + if (result.hi < 0) Negate(result); > + if (denom.hi < 0) Negate(denom); > + if (denom > result) return Int128(0); //result is only a fraction of > 1 > + Negate(denom); > + > + Int128 p(0); > + for (int i = 0; i < 128; ++i) > + { > + p.hi = p.hi << 1; > + if (p.lo < 0) p.hi++; > + p.lo = long64(p.lo) << 1; > + if (result.hi < 0) p.lo++; > + result.hi = result.hi << 1; > + if (result.lo < 0) result.hi++; > + result.lo = long64(result.lo) << 1; > + Int128 p2(p); > + p += denom; > + if (p.hi < 0) p = p2; > + else result.lo++; > + } > + if (negate) Negate(result); > + return result; > + } > + > + double AsDouble() const > + { > + const double shift64 = 18446744073709551616.0; //2^64 > + const double bit64 = 9223372036854775808.0; > + if (hi < 0) > + { > + Int128 tmp(*this); > + Negate(tmp); > + if (tmp.lo < 0) > + return (double)tmp.lo - bit64 - tmp.hi * shift64; > + else > + return -(double)tmp.lo - tmp.hi * shift64; > + } > + else if (lo < 0) > + return -(double)lo + bit64 + hi * shift64; > + else > + return (double)lo + (double)hi * shift64; > + } > + > + //for bug testing ... > + std::string AsString() const > + { > + std::string result; > + unsigned char r = 0; > + Int128 tmp(0), val(*this); > + if (hi < 0) Negate(val); > + result.resize(50); > + std::string::size_type i = result.size() -1; > + while (val.hi != 0 || val.lo != 0) > + { > + Div10(val, tmp, r); > + result[i--] = char('0' + r); > + val = tmp; > + } > + if (hi < 0) result[i--] = '-'; > + result.erase(0,i+1); > + if (result.size() == 0) result = "0"; > + return result; > + } > + > + private: > + long64 hi; > + long64 lo; > + > + static void Negate(Int128 &val) > + { > + if (val.lo == 0) > + { > + if( val.hi == 0) return; > + val.lo = ~val.lo; > + val.hi = ~val.hi +1; > + } > + else > + { > + val.lo = ~val.lo +1; > + val.hi = ~val.hi; > + } > + } > + > + //debugging only ... > + void Div10(const Int128 val, Int128& result, unsigned char & > remainder) const > + { > + remainder = 0; > + result = 0; > + for (int i = 63; i >= 0; --i) > + { > + if ((val.hi & ((long64)1 << i)) != 0) > + remainder = char((remainder * 2) + 1); else > + remainder *= char(2); > + if (remainder >= 10) > + { > + result.hi += ((long64)1 << i); > + remainder -= char(10); > + } > + } > + for (int i = 63; i >= 0; --i) > + { > + if ((val.lo & ((long64)1 << i)) != 0) > + remainder = char((remainder * 2) + 1); else > + remainder *= char(2); > + if (remainder >= 10) > + { > + result.lo += ((long64)1 << i); > + remainder -= char(10); > + } > + } > + } > + }; > + > + > //------------------------------------------------------------------------------ > + > //------------------------------------------------------------------------------ > + > + RangeTest TestRange(const Polygon &pts) > + { > + RangeTest result = rtLo; > + for (Polygon::size_type i = 0; i < pts.size(); ++i) > + { > + if (Abs(pts[i].X) > hiRange || Abs(pts[i].Y) > hiRange) > + return rtError; > + else if (Abs(pts[i].X) > loRange || Abs(pts[i].Y) > loRange) > + result = rtHi; > + } > + return result; > + } > + > //------------------------------------------------------------------------------ > + > + bool Orientation(const Polygon &poly) > + { > + int highI = (int)poly.size() -1; > + if (highI < 2) return false; > + bool UseFullInt64Range = false; > + > + int j = 0, jplus, jminus; > + for (int i = 0; i <= highI; ++i) > + { > + if (Abs(poly[i].X) > hiRange || Abs(poly[i].Y) > hiRange) > + throw "Coordinate exceeds range bounds."; > + if (Abs(poly[i].X) > loRange || Abs(poly[i].Y) > loRange) > + UseFullInt64Range = true; > + if (poly[i].Y < poly[j].Y) continue; > + if ((poly[i].Y > poly[j].Y || poly[i].X < poly[j].X)) j = i; > + }; > + if (j == highI) jplus = 0; > + else jplus = j +1; > + if (j == 0) jminus = highI; > + else jminus = j -1; > + > + IntPoint vec1, vec2; > + //get cross product of vectors of the edges adjacent to highest point ... > + vec1.X = poly[j].X - poly[jminus].X; > + vec1.Y = poly[j].Y - poly[jminus].Y; > + vec2.X = poly[jplus].X - poly[j].X; > + vec2.Y = poly[jplus].Y - poly[j].Y; > + > + if (UseFullInt64Range) > + { > + Int128 cross = Int128(vec1.X) * Int128(vec2.Y) - > + Int128(vec2.X) * Int128(vec1.Y); > + return cross > 0; > + } > + else > + { > + return (vec1.X * vec2.Y - vec2.X * vec1.Y) > 0; > + } > + } > + > //------------------------------------------------------------------------------ > + > + bool Orientation(OutRec *outRec, bool UseFullInt64Range) > + { > + OutPt *opBottom = outRec->pts, *op = outRec->pts->next; > + while (op != outRec->pts) > + { > + if (op->pt.Y >= opBottom->pt.Y) > + { > + if (op->pt.Y > opBottom->pt.Y || op->pt.X < opBottom->pt.X) > + opBottom = op; > + } > + op = op->next; > + } > + > + IntPoint vec1, vec2; > + vec1.X = op->pt.X - op->prev->pt.X; > + vec1.Y = op->pt.Y - op->prev->pt.Y; > + vec2.X = op->next->pt.X - op->pt.X; > + vec2.Y = op->next->pt.Y - op->pt.Y; > + > + if (UseFullInt64Range) > + { > + Int128 cross = Int128(vec1.X) * Int128(vec2.Y) - Int128(vec2.X) * > Int128(vec1.Y); > + return cross > 0; > + } > + else > + { > + return (vec1.X * vec2.Y - vec2.X * vec1.Y) > 0; > + } > + } > + > //------------------------------------------------------------------------------ > + > + inline bool PointsEqual( const IntPoint &pt1, const IntPoint &pt2) > + { > + return ( pt1.X == pt2.X && pt1.Y == pt2.Y ); > + } > + > //------------------------------------------------------------------------------ > + > + double Area(const Polygon &poly) > + { > + int highI = (int)poly.size() -1; > + if (highI < 2) return 0; > + bool UseFullInt64Range; > + RangeTest rt = TestRange(poly); > + switch (rt) { > + case rtLo: > + UseFullInt64Range = false; > + break; > + case rtHi: > + UseFullInt64Range = true; > + break; > + default: > + throw "Coordinate exceeds range bounds."; > + } > + > + if (UseFullInt64Range) { > + Int128 a(0); > + a = (Int128(poly[highI].X) * Int128(poly[0].Y)) - > + Int128(poly[0].X) * Int128(poly[highI].Y); > + for (int i = 0; i < highI; ++i) > + a += Int128(poly[i].X) * Int128(poly[i+1].Y) - > + Int128(poly[i+1].X) * Int128(poly[i].Y); > + return a.AsDouble() / 2; > + } > + else > + { > + double a; > + a = (double)poly[highI].X * poly[0].Y - (double)poly[0].X * > poly[highI].Y; > + for (int i = 0; i < highI; ++i) > + a += (double)poly[i].X * poly[i+1].Y - (double)poly[i+1].X * > poly[i].Y; > + return a/2; > + } > + } > + > //------------------------------------------------------------------------------ > + > + bool PointIsVertex(const IntPoint &pt, OutPt *pp) > + { > + OutPt *pp2 = pp; > + do > + { > + if (PointsEqual(pp2->pt, pt)) return true; > + pp2 = pp2->next; > + } > + while (pp2 != pp); > + return false; > + } > + > //------------------------------------------------------------------------------ > + > + bool PointInPolygon(const IntPoint &pt, OutPt *pp, bool > UseFullInt64Range) > + { > + OutPt *pp2 = pp; > + bool result = false; > + if (UseFullInt64Range) { > + do > + { > + if ((((pp2->pt.Y <= pt.Y) && (pt.Y < pp2->prev->pt.Y)) || > + ((pp2->prev->pt.Y <= pt.Y) && (pt.Y < pp2->pt.Y))) && > + Int128(pt.X - pp2->pt.X) < (Int128(pp2->prev->pt.X - pp2->pt.X) * > + Int128(pt.Y - pp2->pt.Y)) / Int128(pp2->prev->pt.Y - > pp2->pt.Y)) > + result = !result; > + pp2 = pp2->next; > + } > + while (pp2 != pp); > + } > + else > + { > + do > + { > + if ((((pp2->pt.Y <= pt.Y) && (pt.Y < pp2->prev->pt.Y)) || > + ((pp2->prev->pt.Y <= pt.Y) && (pt.Y < pp2->pt.Y))) && > + (pt.X < (pp2->prev->pt.X - pp2->pt.X) * (pt.Y - pp2->pt.Y) / > + (pp2->prev->pt.Y - pp2->pt.Y) + pp2->pt.X )) result = !result; > + pp2 = pp2->next; > + } > + while (pp2 != pp); > + } > + return result; > + } > + > //------------------------------------------------------------------------------ > + > + bool SlopesEqual(TEdge &e1, TEdge &e2, bool UseFullInt64Range) > + { > + if (e1.ybot == e1.ytop) return (e2.ybot == e2.ytop); > + else if (e1.xbot == e1.xtop) return (e2.xbot == e2.xtop); > + else if (UseFullInt64Range) > + return Int128(e1.ytop - e1.ybot) * Int128(e2.xtop - e2.xbot) == > + Int128(e1.xtop - e1.xbot) * Int128(e2.ytop - e2.ybot); > + else return (e1.ytop - e1.ybot)*(e2.xtop - e2.xbot) == > + (e1.xtop - e1.xbot)*(e2.ytop - e2.ybot); > + } > + > //------------------------------------------------------------------------------ > + > + bool SlopesEqual(const IntPoint pt1, const IntPoint pt2, > + const IntPoint pt3, bool UseFullInt64Range) > + { > + if (pt1.Y == pt2.Y) return (pt2.Y == pt3.Y); > + else if (pt1.X == pt2.X) return (pt2.X == pt3.X); > + else if (UseFullInt64Range) > + return Int128(pt1.Y-pt2.Y) * Int128(pt2.X-pt3.X) == > + Int128(pt1.X-pt2.X) * Int128(pt2.Y-pt3.Y); > + else 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) > + { > + if (pt1.Y == pt2.Y) return (pt3.Y == pt4.Y); > + else if (pt1.X == pt2.X) return (pt3.X == pt4.X); > + else if (UseFullInt64Range) > + return Int128(pt1.Y-pt2.Y) * Int128(pt3.X-pt4.X) == > + Int128(pt1.X-pt2.X) * Int128(pt3.Y-pt4.Y); > + else return (pt1.Y-pt2.Y)*(pt3.X-pt4.X) == (pt1.X-pt2.X)*(pt3.Y-pt4.Y); > + } > + > //------------------------------------------------------------------------------ > + > + double GetDx(const IntPoint pt1, const IntPoint pt2) > + { > + if (pt1.Y == pt2.Y) return HORIZONTAL; > + else return > + (double)(pt2.X - pt1.X) / (double)(pt2.Y - pt1.Y); > + } > + > //--------------------------------------------------------------------------- > + > + void SetDx(TEdge &e) > + { > + if (e.ybot == e.ytop) e.dx = HORIZONTAL; > + else e.dx = > + (double)(e.xtop - e.xbot) / (double)(e.ytop - e.ybot); > + } > + > //--------------------------------------------------------------------------- > + > + void SwapSides(TEdge &edge1, TEdge &edge2) > + { > + EdgeSide side = edge1.side; > + edge1.side = edge2.side; > + edge2.side = side; > + } > + > //------------------------------------------------------------------------------ > + > + void SwapPolyIndexes(TEdge &edge1, TEdge &edge2) > + { > + int outIdx = edge1.outIdx; > + edge1.outIdx = edge2.outIdx; > + edge2.outIdx = outIdx; > + } > + > //------------------------------------------------------------------------------ > + > + inline long64 Round(double val) > + { > + if ((val < 0)) return static_cast<long64>(val - 0.5); > + else return static_cast<long64>(val + 0.5); > + } > + > //------------------------------------------------------------------------------ > + > + long64 TopX(TEdge &edge, const long64 currentY) > + { > + if( currentY == edge.ytop ) return edge.xtop; > + return edge.xbot + Round(edge.dx *(currentY - edge.ybot)); > + } > + > //------------------------------------------------------------------------------ > + > + long64 TopX(const IntPoint pt1, const IntPoint pt2, const long64 > currentY) > + { > + //preconditions: pt1.Y <> pt2.Y and pt1.Y > pt2.Y > + if (currentY >= pt1.Y) return pt1.X; > + else if (currentY == pt2.Y) return pt2.X; > + else if (pt1.X == pt2.X) return pt1.X; > + else > + { > + double q = (double)(pt1.X-pt2.X)/(double)(pt1.Y-pt2.Y); > + return Round(pt1.X + (currentY - pt1.Y) *q); > + } > + } > + > //------------------------------------------------------------------------------ > + > + bool IntersectPoint(TEdge &edge1, TEdge &edge2, > + IntPoint &ip, bool UseFullInt64Range) > + { > + double b1, b2; > + if (SlopesEqual(edge1, edge2, UseFullInt64Range)) return false; > + else if (NEAR_ZERO(edge1.dx)) > + { > + ip.X = edge1.xbot; > + if (NEAR_EQUAL(edge2.dx, HORIZONTAL)) > + { > + ip.Y = edge2.ybot; > + } else > + { > + b2 = edge2.ybot - (edge2.xbot/edge2.dx); > + ip.Y = Round(ip.X/edge2.dx + b2); > + } > + } > + else if (NEAR_ZERO(edge2.dx)) > + { > + ip.X = edge2.xbot; > + if (NEAR_EQUAL(edge1.dx, HORIZONTAL)) > + { > + ip.Y = edge1.ybot; > + } else > + { > + b1 = edge1.ybot - (edge1.xbot/edge1.dx); > + ip.Y = Round(ip.X/edge1.dx + b1); > + } > + } else > + { > + b1 = edge1.xbot - edge1.ybot * edge1.dx; > + b2 = edge2.xbot - edge2.ybot * edge2.dx; > + b2 = (b2-b1)/(edge1.dx - edge2.dx); > + ip.Y = Round(b2); > + ip.X = Round(edge1.dx * b2 + b1); > + } > + > + return > + //can be *so close* to the top of one edge that the rounded Y equals > one ytop ... > + (ip.Y == edge1.ytop && ip.Y >= edge2.ytop && edge1.tmpX > > edge2.tmpX) || > + (ip.Y == edge2.ytop && ip.Y >= edge1.ytop && edge1.tmpX > > edge2.tmpX) || > + (ip.Y > edge1.ytop && ip.Y > edge2.ytop); > + } > + > //------------------------------------------------------------------------------ > + > + void ReversePolyPtLinks(OutPt &pp) > + { > + 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 ; > + } > + } > + > //------------------------------------------------------------------------------ > + > + void InitEdge(TEdge *e, TEdge *eNext, > + TEdge *ePrev, const IntPoint &pt, PolyType polyType) > + { > + std::memset( e, 0, sizeof( TEdge )); > + > + e->next = eNext; > + e->prev = ePrev; > + e->xcurr = pt.X; > + e->ycurr = pt.Y; > + if (e->ycurr >= e->next->ycurr) > + { > + e->xbot = e->xcurr; > + e->ybot = e->ycurr; > + e->xtop = e->next->xcurr; > + e->ytop = e->next->ycurr; > + e->windDelta = 1; > + } else > + { > + e->xtop = e->xcurr; > + e->ytop = e->ycurr; > + e->xbot = e->next->xcurr; > + e->ybot = e->next->ycurr; > + e->windDelta = -1; > + } > + SetDx(*e); > + e->polyType = polyType; > + e->outIdx = -1; > + } > + > //------------------------------------------------------------------------------ > + > + inline void SwapX(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.] > + e.xcurr = e.xtop; > + e.xtop = e.xbot; > + e.xbot = e.xcurr; > + } > + > //------------------------------------------------------------------------------ > + > + 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 colinear. > + if ( pt1a.Y == pt1b.Y || Abs((pt1a.X - pt1b.X)/(pt1a.Y - pt1b.Y)) > 1 ) > + { > + 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; > + } > + } > + > //------------------------------------------------------------------------------ > + > + OutPt* PolygonBottom(OutPt* pp) > + { > + OutPt* p = pp->next; > + OutPt* result = pp; > + while (p != pp) > + { > + if (p->pt.Y > result->pt.Y) result = p; > + else if (p->pt.Y == result->pt.Y && p->pt.X < result->pt.X) result = > p; > + p = p->next; > + } > + return result; > + } > + > //------------------------------------------------------------------------------ > + > + bool FindSegment(OutPt* &pp, 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, true) && > + SlopesEqual(pt1a, pt2a, pp->pt, true) && > + GetOverlapSegment(pt1a, pt2a, pp->pt, pp->prev->pt, pt1, pt2)) > + return true; > + pp = pp->next; > + } > + while (pp != pp2); > + return false; > + } > + > //------------------------------------------------------------------------------ > + > + bool Pt3IsBetweenPt1AndPt2(const IntPoint pt1, > + const IntPoint pt2, const IntPoint pt3) > + { > + if (PointsEqual(pt1, pt3) || PointsEqual(pt2, pt3)) return true; > + else if (pt1.X != pt2.X) return (pt1.X < pt3.X) == (pt3.X < pt2.X); > + else return (pt1.Y < pt3.Y) == (pt3.Y < pt2.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; > + } > + > + > //------------------------------------------------------------------------------ > + // ClipperBase class methods ... > + > //------------------------------------------------------------------------------ > + > + ClipperBase::ClipperBase() //constructor > + { > + m_MinimaList = 0; > + m_CurrentLM = 0; > + m_UseFullRange = true; > + m_edges = new EdgeList(); > + } > + > //------------------------------------------------------------------------------ > + > + ClipperBase::~ClipperBase() //destructor > + { > + Clear(); > + delete m_edges; > + m_edges = NULL; > + } > + > //------------------------------------------------------------------------------ > + > + bool ClipperBase::AddPolygon( const Polygon &pg, PolyType polyType) > + { > + int len = (int)pg.size(); > + if (len < 3) return false; > + Polygon p(len); > + p[0] = pg[0]; > + int j = 0; > + > + long64 maxVal; > + if (m_UseFullRange) maxVal = hiRange; else maxVal = loRange; > + > + for (int i = 0; i < len; ++i) > + { > + if (Abs(pg[i].X) > maxVal || Abs(pg[i].Y) > maxVal) > + { > + if (m_UseFullRange) > + throw "Coordinate exceeds range bounds"; > + maxVal = hiRange; > + if (Abs(pg[i].X) > maxVal || Abs(pg[i].Y) > maxVal) > + throw "Coordinate exceeds range bounds"; > + m_UseFullRange = true; > + } > + > + if (i == 0 || PointsEqual(p[j], pg[i])) continue; > + else if (j > 0 && SlopesEqual(p[j-1], p[j], pg[i], m_UseFullRange)) > + { > + if (PointsEqual(p[j-1], pg[i])) j--; > + } else j++; > + p[j] = pg[i]; > + } > + if (j < 2) return false; > + > + len = j+1; > + for (;;) > + { > + //nb: test for point equality before testing slopes ... > + if (PointsEqual(p[j], p[0])) j--; > + else if (PointsEqual(p[0], p[1]) || > + SlopesEqual(p[j], p[0], p[1], m_UseFullRange)) > + p[0] = p[j--]; > + else if (SlopesEqual(p[j-1], p[j], p[0], m_UseFullRange)) j--; > + else if (SlopesEqual(p[0], p[1], p[2], m_UseFullRange)) > + { > + for (int i = 2; i <= j; ++i) p[i-1] = p[i]; > + j--; > + } > + //exit loop if nothing is changed or there are too few vertices ... > + if (j == len-1 || j < 2) break; > + len = j +1; > + } > + if (len < 3) return false; > + > + //create a new edge array ... > + TEdge *edges = new TEdge [len]; > + m_edges->push_back(edges); > + > + //convert vertices to a double-linked-list of edges and initialize ... > + edges[0].xcurr = p[0].X; > + edges[0].ycurr = p[0].Y; > + InitEdge(&edges[len-1], &edges[0], &edges[len-2], p[len-1], polyType); > + for (int i = len-2; i > 0; --i) > + InitEdge(&edges[i], &edges[i+1], &edges[i-1], p[i], polyType); > + InitEdge(&edges[0], &edges[1], &edges[len-1], p[0], polyType); > + > + //reset xcurr & ycurr and find 'eHighest' (given the Y axis coordinates > + //increase downward so the 'highest' edge will have the smallest ytop) > ... > + TEdge *e = &edges[0]; > + TEdge *eHighest = e; > + do > + { > + e->xcurr = e->xbot; > + e->ycurr = e->ybot; > + if (e->ytop < eHighest->ytop) eHighest = e; > + e = e->next; > + } > + while ( e != &edges[0]); > + > + //make sure eHighest is positioned so the following loop works safely ... > + if (eHighest->windDelta > 0) eHighest = eHighest->next; > + if (NEAR_EQUAL(eHighest->dx, HORIZONTAL)) eHighest = eHighest->next; > + > + //finally insert each local minima ... > + e = eHighest; > + do { > + e = AddBoundsToLML(e); > + } > + while( e != eHighest ); > + return true; > + } > + > //------------------------------------------------------------------------------ > + > + 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; > + } > + } > + > //------------------------------------------------------------------------------ > + > + TEdge* ClipperBase::AddBoundsToLML(TEdge *e) > + { > + //Starting at the top of one bound we progress to the bottom where > there's > + //a local minima. We then go to the top of the next bound. These two > bounds > + //form the left and right (or right and left) bounds of the local minima. > + e->nextInLML = 0; > + e = e->next; > + for (;;) > + { > + if (NEAR_EQUAL(e->dx, HORIZONTAL)) > + { > + //nb: proceed through horizontals when approaching from their right, > + // but break on horizontal minima if approaching from their left. > + // This ensures 'local minima' are always on the left of > horizontals. > + if (e->next->ytop < e->ytop && e->next->xbot > e->prev->xbot) break; > + if (e->xtop != e->prev->xbot) SwapX(*e); > + e->nextInLML = e->prev; > + } > + else if (e->ycurr == e->prev->ycurr) break; > + else e->nextInLML = e->prev; > + e = e->next; > + } > + > + //e and e.prev are now at a local minima ... > + LocalMinima* newLm = new LocalMinima; > + newLm->next = 0; > + newLm->Y = e->prev->ybot; > + > + if ( NEAR_EQUAL(e->dx, HORIZONTAL) ) //horizontal edges never start a > left bound > + { > + if (e->xbot != e->prev->xbot) SwapX(*e); > + newLm->leftBound = e->prev; > + newLm->rightBound = e; > + } else if (e->dx < e->prev->dx) > + { > + newLm->leftBound = e->prev; > + newLm->rightBound = e; > + } else > + { > + newLm->leftBound = e; > + newLm->rightBound = e->prev; > + } > + newLm->leftBound->side = esLeft; > + newLm->rightBound->side = esRight; > + InsertLocalMinima( newLm ); > + > + for (;;) > + { > + if ( e->next->ytop == e->ytop && !NEAR_EQUAL(e->next->dx, > HORIZONTAL) ) break; > + e->nextInLML = e->next; > + e = e->next; > + if ( NEAR_EQUAL(e->dx, HORIZONTAL) && e->xbot != e->prev->xtop) > SwapX(*e); > + } > + return e->next; > + } > + > //------------------------------------------------------------------------------ > + > + bool ClipperBase::AddPolygons(const Polygons &ppg, PolyType polyType) > + { > + bool result = true; > + for (Polygons::size_type i = 0; i < ppg.size(); ++i) > + if (AddPolygon(ppg[i], polyType)) result = false; > + return result; > + } > + > //------------------------------------------------------------------------------ > + > + void ClipperBase::Clear() > + { > + DisposeLocalMinimaList(); > + for (EdgeList::size_type i = 0; i < m_edges->size(); ++i) delete [] > m_edges->at(i); > + m_edges->clear(); > + m_UseFullRange = 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; > + while( e ) > + { > + e->xcurr = e->xbot; > + e->ycurr = e->ybot; > + e->side = esLeft; > + e->outIdx = -1; > + e = e->nextInLML; > + } > + e = lm->rightBound; > + while( e ) > + { > + e->xcurr = e->xbot; > + e->ycurr = e->ybot; > + e->side = esRight; > + e->outIdx = -1; > + e = e->nextInLML; > + } > + 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->xbot; > + result.top = lm->leftBound->ybot; > + result.right = lm->leftBound->xbot; > + result.bottom = lm->leftBound->ybot; > + while (lm) > + { > + if (lm->leftBound->ybot > result.bottom) > + result.bottom = lm->leftBound->ybot; > + TEdge* e = lm->leftBound; > + for (;;) { > + TEdge* bottomE = e; > + while (e->nextInLML) > + { > + if (e->xbot < result.left) result.left = e->xbot; > + if (e->xbot > result.right) result.right = e->xbot; > + e = e->nextInLML; > + } > + if (e->xbot < result.left) result.left = e->xbot; > + if (e->xbot > result.right) result.right = e->xbot; > + if (e->xtop < result.left) result.left = e->xtop; > + if (e->xtop > result.right) result.right = e->xtop; > + if (e->ytop < result.top) result.top = e->ytop; > + > + if (bottomE == lm->leftBound) e = lm->rightBound; > + else break; > + } > + lm = lm->next; > + } > + return result; > + } > + > + > + > //------------------------------------------------------------------------------ > + // TClipper methods ... > + > //------------------------------------------------------------------------------ > + > + Clipper::Clipper() : ClipperBase() //constructor > + { > + m_Scanbeam = 0; > + m_ActiveEdges = 0; > + m_SortedEdges = 0; > + m_IntersectNodes = 0; > + m_ExecuteLocked = false; > + m_UseFullRange = false; > + m_ReverseOutput = false; > + m_PolyOuts = new PolyOutList(); > + m_Joins = new JoinList(); > + m_HorizJoins = new HorzJoinList(); > + } > + > //------------------------------------------------------------------------------ > + > + Clipper::~Clipper() //destructor > + { > + Clear(); > + DisposeScanbeamList(); > + delete m_PolyOuts; > + delete m_Joins; > + delete m_HorizJoins; > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::Clear() > + { > + if (m_edges->size() == 0) return; //avoids problems with ClipperBase > destructor > + DisposeAllPolyPts(); > + ClipperBase::Clear(); > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::DisposeScanbeamList() > + { > + while ( m_Scanbeam ) { > + Scanbeam* sb2 = m_Scanbeam->next; > + delete m_Scanbeam; > + m_Scanbeam = sb2; > + } > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::Reset() > + { > + ClipperBase::Reset(); > + m_Scanbeam = 0; > + m_ActiveEdges = 0; > + m_SortedEdges = 0; > + LocalMinima* lm = m_MinimaList; > + while (lm) > + { > + InsertScanbeam(lm->Y); > + InsertScanbeam(lm->leftBound->ytop); > + lm = lm->next; > + } > + } > + > //------------------------------------------------------------------------------ > + > + bool Clipper::Execute(ClipType clipType, Polygons &solution, > + PolyFillType subjFillType, PolyFillType clipFillType) > + { > + if( m_ExecuteLocked ) return false; > + m_ExecuteLocked = true; > + solution.resize(0); > + m_SubjFillType = subjFillType; > + m_ClipFillType = clipFillType; > + m_ClipType = clipType; > + bool succeeded = ExecuteInternal(false); > + if (succeeded) BuildResult(solution); > + m_ExecuteLocked = false; > + return succeeded; > + } > + > //------------------------------------------------------------------------------ > + > + bool Clipper::Execute(ClipType clipType, ExPolygons &solution, > + PolyFillType subjFillType, PolyFillType clipFillType) > + { > + if( m_ExecuteLocked ) return false; > + m_ExecuteLocked = true; > + solution.resize(0); > + m_SubjFillType = subjFillType; > + m_ClipFillType = clipFillType; > + m_ClipType = clipType; > + bool succeeded = ExecuteInternal(true); > + if (succeeded) BuildResultEx(solution); > + m_ExecuteLocked = false; > + return succeeded; > + } > + > //------------------------------------------------------------------------------ > + > + bool PolySort(OutRec *or1, OutRec *or2) > + { > + if (or1 == or2) return false; > + if (!or1->pts || !or2->pts) > + { > + if (or1->pts != or2->pts) > + { > + if (or1->pts) return true; else return false; > + } > + else return false; > + } > + int i1, i2; > + if (or1->isHole) > + i1 = or1->FirstLeft->idx; else > + i1 = or1->idx; > + if (or2->isHole) > + i2 = or2->FirstLeft->idx; else > + i2 = or2->idx; > + int result = i1 - i2; > + if (result == 0 && (or1->isHole != or2->isHole)) > + { > + if (or1->isHole) return false; > + else return true; > + } > + else return result < 0; > + } > + > //------------------------------------------------------------------------------ > + > + OutRec* FindAppendLinkEnd(OutRec *outRec) > + { > + while (outRec->AppendLink) outRec = outRec->AppendLink; > + return outRec; > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::FixHoleLinkage(OutRec *outRec) > + { > + OutRec *tmp; > + if (outRec->bottomPt) > + tmp = m_PolyOuts->at(outRec->bottomPt->idx)->FirstLeft; > + else > + tmp = outRec->FirstLeft; > + if (outRec == tmp) throw clipperException("HoleLinkage error"); > + > + if (tmp) > + { > + if (tmp->AppendLink) tmp = FindAppendLinkEnd(tmp); > + if (tmp == outRec) tmp = 0; > + else if (tmp->isHole) > + { > + FixHoleLinkage(tmp); > + tmp = tmp->FirstLeft; > + } > + } > + outRec->FirstLeft = tmp; > + if (!tmp) outRec->isHole = false; > + outRec->AppendLink = 0; > + } > + > //------------------------------------------------------------------------------ > + > + bool Clipper::ExecuteInternal(bool fixHoleLinkages) > + { > + bool succeeded; > + try { > + Reset(); > + if (!m_CurrentLM ) return true; > + long64 botY = PopScanbeam(); > + do { > + InsertLocalMinimaIntoAEL(botY); > + ClearHorzJoins(); > + ProcessHorizontals(); > + long64 topY = PopScanbeam(); > + succeeded = ProcessIntersections(botY, topY); > + if (!succeeded) break; > + ProcessEdgesAtTopOfScanbeam(topY); > + botY = topY; > + } while( m_Scanbeam ); > + } > + catch(...) { > + succeeded = false; > + } > + > + if (succeeded) > + { > + //tidy up output polygons and fix orientations where necessary ... > + for (PolyOutList::size_type i = 0; i < m_PolyOuts->size(); ++i) > + { > + OutRec *outRec = m_PolyOuts->at(i); > + if (!outRec->pts) continue; > + FixupOutPolygon(*outRec); > + if (!outRec->pts) continue; > + if (outRec->isHole && fixHoleLinkages) FixHoleLinkage(outRec); > + if (outRec->isHole == > + (m_ReverseOutput ^ Orientation(outRec, m_UseFullRange))) > + ReversePolyPtLinks(*outRec->pts); > + } > + > + JoinCommonEdges(fixHoleLinkages); > + if (fixHoleLinkages) > + std::sort(m_PolyOuts->begin(), m_PolyOuts->end(), PolySort); > + } > + > + ClearJoins(); > + ClearHorzJoins(); > + return succeeded; > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::InsertScanbeam(const long64 Y) > + { > + if( !m_Scanbeam ) > + { > + m_Scanbeam = new Scanbeam; > + m_Scanbeam->next = 0; > + m_Scanbeam->Y = Y; > + } > + else if( Y > m_Scanbeam->Y ) > + { > + Scanbeam* newSb = new Scanbeam; > + newSb->Y = Y; > + newSb->next = m_Scanbeam; > + m_Scanbeam = newSb; > + } else > + { > + Scanbeam* sb2 = m_Scanbeam; > + while( sb2->next && ( Y <= sb2->next->Y ) ) sb2 = sb2->next; > + if( Y == sb2->Y ) return; //ie ignores duplicates > + Scanbeam* newSb = new Scanbeam; > + newSb->Y = Y; > + newSb->next = sb2->next; > + sb2->next = newSb; > + } > + } > + > //------------------------------------------------------------------------------ > + > + long64 Clipper::PopScanbeam() > + { > + long64 Y = m_Scanbeam->Y; > + Scanbeam* sb2 = m_Scanbeam; > + m_Scanbeam = m_Scanbeam->next; > + delete sb2; > + return Y; > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::DisposeAllPolyPts(){ > + for (PolyOutList::size_type i = 0; i < m_PolyOuts->size(); ++i) > + DisposeOutRec(i); > + m_PolyOuts->clear(); > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::DisposeOutRec(PolyOutList::size_type index, bool ignorePts) > + { > + OutRec *outRec = m_PolyOuts->at(index); > + if (!ignorePts && outRec->pts) DisposeOutPts(outRec->pts); > + delete outRec; > + m_PolyOuts->at(index) = 0; > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::SetWindingCount(TEdge &edge) > + { > + TEdge *e = edge.prevInAEL; > + //find the edge of the same polytype that immediately precedes 'edge' in > AEL > + while ( e && e->polyType != edge.polyType ) e = e->prevInAEL; > + if ( !e ) > + { > + edge.windCnt = edge.windDelta; > + edge.windCnt2 = 0; > + e = m_ActiveEdges; //ie get ready to calc windCnt2 > + } else if ( IsEvenOddFillType(edge) ) > + { > + //EvenOdd filling ... > + edge.windCnt = 1; > + 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 ) > + { > + if (Abs(e->windCnt) > 1) > + { > + if (e->windDelta * edge.windDelta < 0) edge.windCnt = e->windCnt; > + else edge.windCnt = e->windCnt + edge.windDelta; > + } else > + edge.windCnt = e->windCnt + e->windDelta + edge.windDelta; > + } else > + { > + if ( Abs(e->windCnt) > 1 && e->windDelta * edge.windDelta < 0) > + edge.windCnt = e->windCnt; > + else if ( e->windCnt + edge.windDelta == 0 ) > + edge.windCnt = e->windCnt; > + 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 ) > + { > + 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.polyType == ptSubject) > + return m_SubjFillType == pftEvenOdd; else > + return m_ClipFillType == pftEvenOdd; > + } > + > //------------------------------------------------------------------------------ > + > + bool Clipper::IsEvenOddAltFillType(const TEdge& edge) const > + { > + if (edge.polyType == ptSubject) > + return m_ClipFillType == pftEvenOdd; else > + return m_SubjFillType == pftEvenOdd; > + } > + > //------------------------------------------------------------------------------ > + > + bool Clipper::IsContributing(const TEdge& edge) const > + { > + PolyFillType pft, pft2; > + if (edge.polyType == ptSubject) > + { > + pft = m_SubjFillType; > + pft2 = m_ClipFillType; > + } else > + { > + pft = m_ClipFillType; > + pft2 = m_SubjFillType; > + } > + > + switch(pft) > + { > + case pftEvenOdd: > + 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); > + } > + case ctUnion: > + switch(pft2) > + { > + case pftEvenOdd: > + case pftNonZero: > + return (edge.windCnt2 == 0); > + case pftPositive: > + return (edge.windCnt2 <= 0); > + default: > + return (edge.windCnt2 >= 0); > + } > + case ctDifference: > + if (edge.polyType == 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); > + } > + case ctXor: > + std::cerr << "Unhandled ClipType ctXor\n"; > + return false; > + } > + return true; > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt) > + { > + if( NEAR_EQUAL(e2->dx, HORIZONTAL) || ( e1->dx > e2->dx ) ) > + { > + AddOutPt( e1, e2, pt ); > + e2->outIdx = e1->outIdx; > + e1->side = esLeft; > + e2->side = esRight; > + } else > + { > + AddOutPt( e2, e1, pt ); > + e1->outIdx = e2->outIdx; > + e1->side = esRight; > + e2->side = esLeft; > + } > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt) > + { > + AddOutPt( e1, 0, pt ); > + if( e1->outIdx == e2->outIdx ) > + { > + e1->outIdx = -1; > + e2->outIdx = -1; > + } > + else > + AppendPolygon( e1, e2 ); > + } > + > //------------------------------------------------------------------------------ > + > + 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; > + if (!m_ActiveEdges) return; > + m_SortedEdges->prevInSEL = 0; > + e = e->nextInAEL; > + while ( e ) > + { > + e->prevInSEL = e->prevInAEL; > + e->prevInSEL->nextInSEL = e; > + e->nextInSEL = 0; > + e = e->nextInAEL; > + } > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx, int e2OutIdx) > + { > + JoinRec* jr = new JoinRec; > + if (e1OutIdx >= 0) > + jr->poly1Idx = e1OutIdx; else > + jr->poly1Idx = e1->outIdx; > + jr->pt1a = IntPoint(e1->xcurr, e1->ycurr); > + jr->pt1b = IntPoint(e1->xtop, e1->ytop); > + if (e2OutIdx >= 0) > + jr->poly2Idx = e2OutIdx; else > + jr->poly2Idx = e2->outIdx; > + jr->pt2a = IntPoint(e2->xcurr, e2->ycurr); > + jr->pt2b = IntPoint(e2->xtop, e2->ytop); > + m_Joins->push_back(jr); > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::ClearJoins() > + { > + for (JoinList::size_type i = 0; i < m_Joins->size(); i++) > + delete m_Joins->at(i); > + m_Joins->resize(0); > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::AddHorzJoin(TEdge *e, int idx) > + { > + HorzJoinRec* hj = new HorzJoinRec; > + hj->edge = e; > + hj->savedIdx = idx; > + m_HorizJoins->push_back(hj); > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::ClearHorzJoins() > + { > + for (HorzJoinList::size_type i = 0; i < m_HorizJoins->size(); i++) > + delete m_HorizJoins->at(i); > + m_HorizJoins->resize(0); > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::InsertLocalMinimaIntoAEL( const long64 botY) > + { > + while( m_CurrentLM && ( m_CurrentLM->Y == botY ) ) > + { > + TEdge* lb = m_CurrentLM->leftBound; > + TEdge* rb = m_CurrentLM->rightBound; > + > + InsertEdgeIntoAEL( lb ); > + InsertScanbeam( lb->ytop ); > + InsertEdgeIntoAEL( rb ); > + > + if (IsEvenOddFillType(*lb)) > + { > + lb->windDelta = 1; > + rb->windDelta = 1; > + } > + else > + { > + rb->windDelta = -lb->windDelta; > + } > + SetWindingCount( *lb ); > + rb->windCnt = lb->windCnt; > + rb->windCnt2 = lb->windCnt2; > + > + if( NEAR_EQUAL(rb->dx, HORIZONTAL) ) > + { > + //nb: only rightbounds can have a horizontal bottom edge > + AddEdgeToSEL( rb ); > + InsertScanbeam( rb->nextInLML->ytop ); > + } > + else > + InsertScanbeam( rb->ytop ); > + > + if( IsContributing(*lb) ) > + AddLocalMinPoly( lb, rb, IntPoint(lb->xcurr, m_CurrentLM->Y) ); > + > + //if output polygons share an edge, they'll need joining later ... > + if (lb->outIdx >= 0 && lb->prevInAEL && > + lb->prevInAEL->outIdx >= 0 && lb->prevInAEL->xcurr == lb->xbot && > + SlopesEqual(*lb, *lb->prevInAEL, m_UseFullRange)) > + AddJoin(lb, lb->prevInAEL); > + > + //if any output polygons share an edge, they'll need joining later > ... > + if (rb->outIdx >= 0) > + { > + if (NEAR_EQUAL(rb->dx, HORIZONTAL)) > + { > + for (HorzJoinList::size_type i = 0; i < m_HorizJoins->size(); > ++i) > + { > + IntPoint pt, pt2; //returned by GetOverlapSegment() but unused > here. > + HorzJoinRec* hj = m_HorizJoins->at(i); > + //if horizontals rb and hj.edge overlap, flag for joining later > ... > + if (GetOverlapSegment(IntPoint(hj->edge->xbot, hj->edge->ybot), > + IntPoint(hj->edge->xtop, hj->edge->ytop), > + IntPoint(rb->xbot, rb->ybot), > + IntPoint(rb->xtop, rb->ytop), pt, pt2)) > + AddJoin(hj->edge, rb, hj->savedIdx); > + } > + } > + } > + > + if( lb->nextInAEL != rb ) > + { > + if (rb->outIdx >= 0 && rb->prevInAEL->outIdx >= 0 && > + SlopesEqual(*rb->prevInAEL, *rb, m_UseFullRange)) > + AddJoin(rb, rb->prevInAEL); > + > + TEdge* e = lb->nextInAEL; > + IntPoint pt = IntPoint(lb->xcurr, lb->ycurr); > + while( e != rb ) > + { > + if(!e) throw clipperException("InsertLocalMinimaIntoAEL: missing > rightbound!"); > + //nb: For calculating winding counts etc, IntersectEdges() > assumes > + //that param1 will be to the right of param2 ABOVE the > intersection ... > + IntersectEdges( rb , e , pt , ipNone); //order important here > + e = e->nextInAEL; > + } > + } > + PopLocalMinima(); > + } > + } > + > //------------------------------------------------------------------------------ > + > + 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; > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::IntersectEdges(TEdge *e1, TEdge *e2, > + const IntPoint &pt, IntersectProtects protects) > + { > + //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 = !(ipLeft & protects) && !e1->nextInLML && > + e1->xtop == pt.X && e1->ytop == pt.Y; > + bool e2stops = !(ipRight & protects) && !e2->nextInLML && > + e2->xtop == pt.X && e2->ytop == pt.Y; > + bool e1Contributing = ( e1->outIdx >= 0 ); > + bool e2contributing = ( e2->outIdx >= 0 ); > + > + //update winding counts... > + //assumes that e1 will be to the right of e2 ABOVE the intersection > + if ( e1->polyType == e2->polyType ) > + { > + 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->polyType == ptSubject) > + { > + e1FillType = m_SubjFillType; > + e1FillType2 = m_ClipFillType; > + } else > + { > + e1FillType = m_ClipFillType; > + e1FillType2 = m_SubjFillType; > + } > + if (e2->polyType == ptSubject) > + { > + e2FillType = m_SubjFillType; > + e2FillType2 = m_ClipFillType; > + } else > + { > + e2FillType = m_ClipFillType; > + e2FillType2 = m_SubjFillType; > + } > + > + long64 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->polyType != e2->polyType && m_ClipType != ctXor) ) > + AddLocalMaxPoly(e1, e2, pt); > + else > + DoBothEdges( e1, e2, pt ); > + } > + else if ( e1Contributing ) > + { > + if ((e2Wc == 0 || e2Wc == 1) && > + (m_ClipType != ctIntersection || > + e2->polyType == ptSubject || (e2->windCnt2 != 0))) > + DoEdge1(e1, e2, pt); > + } > + else if ( e2contributing ) > + { > + if ((e1Wc == 0 || e1Wc == 1) && > + (m_ClipType != ctIntersection || > + e1->polyType == ptSubject || (e1->windCnt2 != 0))) > + DoEdge2(e1, e2, pt); > + } > + else if ( (e1Wc == 0 || e1Wc == 1) && > + (e2Wc == 0 || e2Wc == 1) && !e1stops && !e2stops ) > + { > + //neither edge is currently contributing ... > + > + long64 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->polyType != e2->polyType) > + 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->polyType == ptClip && e2->polyType == ptClip && > + e1Wc2 > 0 && e2Wc2 > 0) || > + (e1->polyType == ptSubject && e2->polyType == 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) > + { > + isHole = !isHole; > + if (! outRec->FirstLeft) > + outRec->FirstLeft = m_PolyOuts->at(e2->outIdx); > + } > + e2 = e2->prevInAEL; > + } > + if (isHole) outRec->isHole = true; > + } > + > //------------------------------------------------------------------------------ > + > + bool GetNextNonDupOutPt(OutPt* pp, OutPt*& next) > + { > + next = pp->next; > + while (next != pp && PointsEqual(pp->pt, next->pt)) > + next = next->next; > + return next != pp; > + } > + > //------------------------------------------------------------------------------ > + > + bool GetPrevNonDupOutPt(OutPt* pp, OutPt*& prev) > + { > + prev = pp->prev; > + while (prev != pp && PointsEqual(pp->pt, prev->pt)) > + prev = prev->prev; > + return prev != pp; > + } > + > //------------------------------------------------------------------------------ > + > + OutRec* GetLowermostRec(OutRec *outRec1, OutRec *outRec2) > + { > + //work out which polygon fragment has the correct hole state ... > + 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 (outRec1->bottomE2 == 0) return outRec2; > + else if (outRec2->bottomE2 == 0) return outRec1; > + else > + { > + double dx1 = std::max(outRec1->bottomE1->dx, outRec1->bottomE2->dx); > + double dx2 = std::max(outRec2->bottomE1->dx, outRec2->bottomE2->dx); > + if (dx2 > dx1) return outRec2; else return outRec1; > + } > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::AppendPolygon(TEdge *e1, TEdge *e2) > + { > + //get the start and ends of both output polygons ... > + OutRec *outRec1 = m_PolyOuts->at(e1->outIdx); > + OutRec *outRec2 = m_PolyOuts->at(e2->outIdx); > + OutRec *holeStateRec = GetLowermostRec(outRec1, outRec2); > + > + //fixup hole status ... > + if (holeStateRec == outRec2) > + outRec1->isHole = outRec2->isHole; > + else > + outRec2->isHole = outRec1->isHole; > + > + 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; > + } > + > + if (holeStateRec == outRec2) > + { > + outRec1->bottomPt = outRec2->bottomPt; > + outRec1->bottomPt->idx = outRec1->idx; > + outRec1->bottomE1 = outRec2->bottomE1; > + outRec1->bottomE2 = outRec2->bottomE2; > + > + if (outRec2->FirstLeft != outRec1) > + outRec1->FirstLeft = outRec2->FirstLeft; > + } > + outRec2->pts = 0; > + outRec2->bottomPt = 0; > + outRec2->AppendLink = outRec1; > + int OKIdx = e1->outIdx; > + int ObsoleteIdx = e2->outIdx; > + > + e1->outIdx = -1; //nb: safe because we only get here via AddLocalMaxPoly > + e2->outIdx = -1; > + > + TEdge* e = m_ActiveEdges; > + while( e ) > + { > + if( e->outIdx == ObsoleteIdx ) > + { > + e->outIdx = OKIdx; > + e->side = side; > + break; > + } > + e = e->nextInAEL; > + } > + > + for (JoinList::size_type i = 0; i < m_Joins->size(); ++i) > + { > + if (m_Joins->at(i)->poly1Idx == ObsoleteIdx) > m_Joins->at(i)->poly1Idx = OKIdx; > + if (m_Joins->at(i)->poly2Idx == ObsoleteIdx) > m_Joins->at(i)->poly2Idx = OKIdx; > + } > + > + for (HorzJoinList::size_type i = 0; i < m_HorizJoins->size(); ++i) > + { > + if (m_HorizJoins->at(i)->savedIdx == ObsoleteIdx) > + m_HorizJoins->at(i)->savedIdx = OKIdx; > + } > + > + } > + > //------------------------------------------------------------------------------ > + > + OutRec* Clipper::CreateOutRec() > + { > + OutRec* result = new OutRec; > + result->isHole = false; > + result->FirstLeft = 0; > + result->AppendLink = 0; > + result->pts = 0; > + result->bottomPt = 0; > + return result; > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::AddOutPt(TEdge *e, TEdge *altE, const IntPoint &pt) > + { > + bool ToFront = (e->side == esLeft); > + if( e->outIdx < 0 ) > + { > + OutRec *outRec = CreateOutRec(); > + m_PolyOuts->push_back(outRec); > + outRec->idx = (int)m_PolyOuts->size()-1; > + e->outIdx = outRec->idx; > + OutPt* op = new OutPt; > + outRec->pts = op; > + outRec->bottomE1 = e; > + outRec->bottomE2 = altE; > + outRec->bottomPt = op; > + op->pt = pt; > + op->idx = outRec->idx; > + op->next = op; > + op->prev = op; > + SetHoleState(e, outRec); > + } else > + { > + OutRec *outRec = m_PolyOuts->at(e->outIdx); > + OutPt* op = outRec->pts; > + if ((ToFront && PointsEqual(pt, op->pt)) || > + (!ToFront && PointsEqual(pt, op->prev->pt))) return; > + OutPt* op2 = new OutPt; > + op2->pt = pt; > + op2->idx = outRec->idx; > + if (op2->pt.Y == outRec->bottomPt->pt.Y && > + op2->pt.X < outRec->bottomPt->pt.X) > + { > + outRec->bottomPt = op2; > + outRec->bottomE1 = e; > + outRec->bottomE2 = altE; > + } > + op2->next = op; > + op2->prev = op->prev; > + op2->prev->next = op2; > + op->prev = op2; > + if (ToFront) outRec->pts = op2; > + } > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::ProcessHorizontals() > + { > + TEdge* horzEdge = m_SortedEdges; > + while( horzEdge ) > + { > + DeleteFromSEL( horzEdge ); > + ProcessHorizontal( horzEdge ); > + horzEdge = m_SortedEdges; > + } > + } > + > //------------------------------------------------------------------------------ > + > + bool Clipper::IsTopHorz(const long64 XPos) > + { > + TEdge* e = m_SortedEdges; > + while( e ) > + { > + if( ( XPos >= std::min(e->xcurr, e->xtop) ) && > + ( XPos <= std::max(e->xcurr, e->xtop) ) ) return false; > + e = e->nextInSEL; > + } > + return true; > + } > + > //------------------------------------------------------------------------------ > + > + bool IsMinima(TEdge *e) > + { > + return e && (e->prev->nextInLML != e) && (e->next->nextInLML != e); > + } > + > //------------------------------------------------------------------------------ > + > + bool IsMaxima(TEdge *e, const long64 Y) > + { > + return e && e->ytop == Y && !e->nextInLML; > + } > + > //------------------------------------------------------------------------------ > + > + bool IsIntermediate(TEdge *e, const long64 Y) > + { > + return e->ytop == Y && e->nextInLML; > + } > + > //------------------------------------------------------------------------------ > + > + TEdge *GetMaximaPair(TEdge *e) > + { > + if( !IsMaxima(e->next, e->ytop) || e->next->xtop != e->xtop ) > + return e->prev; else > + return e->next; > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::SwapPositionsInAEL(TEdge *edge1, TEdge *edge2) > + { > + if( !edge1->nextInAEL && !edge1->prevInAEL ) return; > + if( !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) > + { > + if( dir == dLeftToRight ) return e->nextInAEL; > + else return e->prevInAEL; > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::ProcessHorizontal(TEdge *horzEdge) > + { > + Direction dir; > + long64 horzLeft, horzRight; > + > + if( horzEdge->xcurr < horzEdge->xtop ) > + { > + horzLeft = horzEdge->xcurr; > + horzRight = horzEdge->xtop; > + dir = dLeftToRight; > + } else > + { > + horzLeft = horzEdge->xtop; > + horzRight = horzEdge->xcurr; > + dir = dRightToLeft; > + } > + > + TEdge* eMaxPair; > + if( horzEdge->nextInLML ) eMaxPair = 0; > + else eMaxPair = GetMaximaPair(horzEdge); > + > + TEdge* e = GetNextInAEL( horzEdge , dir ); > + while( e ) > + { > + TEdge* eNext = GetNextInAEL( e, dir ); > + > + if (eMaxPair || > + ((dir == dLeftToRight) && (e->xcurr <= horzRight)) || > + ((dir == dRightToLeft) && (e->xcurr >= horzLeft))) > + { > + //ok, so far it looks like we're still in range of the horizontal > edge > + if ( e->xcurr == horzEdge->xtop && !eMaxPair ) > + { > + if (SlopesEqual(*e, *horzEdge->nextInLML, m_UseFullRange)) > + { > + //if output polygons share an edge, they'll need joining later > ... > + if (horzEdge->outIdx >= 0 && e->outIdx >= 0) > + AddJoin(horzEdge->nextInLML, e, horzEdge->outIdx); > + break; //we've reached the end of the horizontal line > + } > + else if (e->dx < horzEdge->nextInLML->dx) > + //we really have got to the end of the intermediate horz edge so > quit. > + //nb: More -ve slopes follow more +ve slopes ABOVE the > horizontal. > + break; > + } > + > + if( e == eMaxPair ) > + { > + //horzEdge is evidently a maxima horizontal and we've arrived at > its end. > + if (dir == dLeftToRight) > + IntersectEdges(horzEdge, e, IntPoint(e->xcurr, horzEdge->ycurr), > ipNone); > + else > + IntersectEdges(e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr), > ipNone); > + if (eMaxPair->outIdx >= 0) throw > clipperException("ProcessHorizontal error"); > + return; > + } > + else if( NEAR_EQUAL(e->dx, HORIZONTAL) && !IsMinima(e) && > !(e->xcurr > e->xtop) ) > + { > + //An overlapping horizontal edge. Overlapping horizontal edges > are > + //processed as if layered with the current horizontal edge > (horizEdge) > + //being infinitesimally lower that the next (e). Therfore, we > + //intersect with e only if e.xcurr is within the bounds of > horzEdge ... > + if( dir == dLeftToRight ) > + IntersectEdges( horzEdge , e, IntPoint(e->xcurr, > horzEdge->ycurr), > + (IsTopHorz( e->xcurr ))? ipLeft : ipBoth ); > + else > + IntersectEdges( e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr), > + (IsTopHorz( e->xcurr ))? ipRight : ipBoth ); > + } > + else if( dir == dLeftToRight ) > + { > + IntersectEdges( horzEdge, e, IntPoint(e->xcurr, horzEdge->ycurr), > + (IsTopHorz( e->xcurr ))? ipLeft : ipBoth ); > + } > + else > + { > + IntersectEdges( e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr), > + (IsTopHorz( e->xcurr ))? ipRight : ipBoth ); > + } > + SwapPositionsInAEL( horzEdge, e ); > + } > + else if( (dir == dLeftToRight && e->xcurr > horzRight && > m_SortedEdges) || > + (dir == dRightToLeft && e->xcurr < horzLeft && m_SortedEdges) ) > break; > + e = eNext; > + } //end while > + > + if( horzEdge->nextInLML ) > + { > + if( horzEdge->outIdx >= 0 ) > + AddOutPt( horzEdge, 0, IntPoint(horzEdge->xtop, horzEdge->ytop)); > + UpdateEdgeIntoAEL( horzEdge ); > + } > + else > + { > + if ( horzEdge->outIdx >= 0 ) > + IntersectEdges( horzEdge, eMaxPair, > + IntPoint(horzEdge->xtop, horzEdge->ycurr), ipBoth); > + if (eMaxPair->outIdx >= 0) throw clipperException("ProcessHorizontal > error"); > + DeleteFromAEL(eMaxPair); > + DeleteFromAEL(horzEdge); > + } > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::UpdateEdgeIntoAEL(TEdge *&e) > + { > + if( !e->nextInLML ) throw > + clipperException("UpdateEdgeIntoAEL: invalid call"); > + TEdge* AelPrev = e->prevInAEL; > + TEdge* AelNext = e->nextInAEL; > + e->nextInLML->outIdx = e->outIdx; > + 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->prevInAEL = AelPrev; > + e->nextInAEL = AelNext; > + if( !NEAR_EQUAL(e->dx, HORIZONTAL) ) InsertScanbeam( e->ytop ); > + } > + > //------------------------------------------------------------------------------ > + > + bool Clipper::ProcessIntersections(const long64 botY, const long64 topY) > + { > + if( !m_ActiveEdges ) return true; > + try { > + BuildIntersectList(botY, topY); > + if ( !m_IntersectNodes) return true; > + if ( FixupIntersections() ) ProcessIntersectList(); > + else return false; > + } > + catch(...) { > + m_SortedEdges = 0; > + DisposeIntersectNodes(); > + throw clipperException("ProcessIntersections error"); > + } > + return true; > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::DisposeIntersectNodes() > + { > + while ( m_IntersectNodes ) > + { > + IntersectNode* iNode = m_IntersectNodes->next; > + delete m_IntersectNodes; > + m_IntersectNodes = iNode; > + } > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::BuildIntersectList(const long64 botY, const long64 topY) > + { > + if ( !m_ActiveEdges ) return; > + > + //prepare for sorting ... > + TEdge* e = m_ActiveEdges; > + e->tmpX = TopX( *e, topY ); > + m_SortedEdges = e; > + m_SortedEdges->prevInSEL = 0; > + e = e->nextInAEL; > + while( e ) > + { > + e->prevInSEL = e->prevInAEL; > + e->prevInSEL->nextInSEL = e; > + e->nextInSEL = 0; > + e->tmpX = TopX( *e, topY ); > + e = e->nextInAEL; > + } > + > + //bubblesort ... > + bool isModified = true; > + while( isModified && m_SortedEdges ) > + { > + isModified = false; > + e = m_SortedEdges; > + while( e->nextInSEL ) > + { > + TEdge *eNext = e->nextInSEL; > + IntPoint pt; > + if(e->tmpX > eNext->tmpX && > + IntersectPoint(*e, *eNext, pt, m_UseFullRange)) > + { > + if (pt.Y > botY) > + { > + pt.Y = botY; > + pt.X = TopX(*e, pt.Y); > + } > + AddIntersectNode( e, eNext, pt ); > + SwapPositionsInSEL(e, eNext); > + isModified = true; > + } > + else > + e = eNext; > + } > + if( e->prevInSEL ) e->prevInSEL->nextInSEL = 0; > + else break; > + } > + m_SortedEdges = 0; > + } > + > //------------------------------------------------------------------------------ > + > + bool Process1Before2(IntersectNode &node1, IntersectNode &node2) > + { > + bool result; > + if (node1.pt.Y == node2.pt.Y) > + { > + if (node1.edge1 == node2.edge1 || node1.edge2 == node2.edge1) > + { > + result = node2.pt.X > node1.pt.X; > + if (node2.edge1->dx > 0) return !result; else return result; > + } > + else if (node1.edge1 == node2.edge2 || node1.edge2 == node2.edge2) > + { > + result = node2.pt.X > node1.pt.X; > + if (node2.edge2->dx > 0) return !result; else return result; > + } > + else return node2.pt.X > node1.pt.X; > + } > + else return node1.pt.Y > node2.pt.Y; > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt) > + { > + IntersectNode* newNode = new IntersectNode; > + newNode->edge1 = e1; > + newNode->edge2 = e2; > + newNode->pt = pt; > + newNode->next = 0; > + if( !m_IntersectNodes ) m_IntersectNodes = newNode; > + else if( Process1Before2(*newNode, *m_IntersectNodes) ) > + { > + newNode->next = m_IntersectNodes; > + m_IntersectNodes = newNode; > + } > + else > + { > + IntersectNode* iNode = m_IntersectNodes; > + while( iNode->next && Process1Before2(*iNode->next, *newNode) ) > + iNode = iNode->next; > + newNode->next = iNode->next; > + iNode->next = newNode; > + } > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::ProcessIntersectList() > + { > + while( m_IntersectNodes ) > + { > + IntersectNode* iNode = m_IntersectNodes->next; > + { > + IntersectEdges( m_IntersectNodes->edge1 , > + m_IntersectNodes->edge2 , m_IntersectNodes->pt, ipBoth ); > + SwapPositionsInAEL( m_IntersectNodes->edge1 , > m_IntersectNodes->edge2 ); > + } > + delete m_IntersectNodes; > + m_IntersectNodes = iNode; > + } > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::DoMaxima(TEdge *e, long64 topY) > + { > + TEdge* eMaxPair = GetMaximaPair(e); > + long64 X = e->xtop; > + TEdge* eNext = e->nextInAEL; > + while( eNext != eMaxPair ) > + { > + if (!eNext) throw clipperException("DoMaxima error"); > + IntersectEdges( e, eNext, IntPoint(X, topY), ipBoth ); > + eNext = eNext->nextInAEL; > + } > + if( e->outIdx < 0 && eMaxPair->outIdx < 0 ) > + { > + DeleteFromAEL( e ); > + DeleteFromAEL( eMaxPair ); > + } > + else if( e->outIdx >= 0 && eMaxPair->outIdx >= 0 ) > + { > + IntersectEdges( e, eMaxPair, IntPoint(X, topY), ipNone ); > + } > + else throw clipperException("DoMaxima error"); > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::ProcessEdgesAtTopOfScanbeam(const long64 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. > + if( IsMaxima(e, topY) && !NEAR_EQUAL(GetMaximaPair(e)->dx, > HORIZONTAL) ) > + { > + //'e' might be removed from AEL, as may any following edges so ... > + TEdge* ePrior = e->prevInAEL; > + DoMaxima(e, topY); > + if( !ePrior ) e = m_ActiveEdges; > + else e = ePrior->nextInAEL; > + } > + else > + { > + //2. promote horizontal edges, otherwise update xcurr and ycurr ... > + if( IsIntermediate(e, topY) && NEAR_EQUAL(e->nextInLML->dx, > HORIZONTAL) ) > + { > + if (e->outIdx >= 0) > + { > + AddOutPt(e, 0, IntPoint(e->xtop, e->ytop)); > + > + for (HorzJoinList::size_type i = 0; i < m_HorizJoins->size(); > ++i) > + { > + IntPoint pt, pt2; > + HorzJoinRec* hj = m_HorizJoins->at(i); > + if (GetOverlapSegment(IntPoint(hj->edge->xbot, > hj->edge->ybot), > + IntPoint(hj->edge->xtop, hj->edge->ytop), > + IntPoint(e->nextInLML->xbot, e->nextInLML->ybot), > + IntPoint(e->nextInLML->xtop, e->nextInLML->ytop), pt, > pt2)) > + AddJoin(hj->edge, e->nextInLML, hj->savedIdx, e->outIdx); > + } > + > + AddHorzJoin(e->nextInLML, e->outIdx); > + } > + UpdateEdgeIntoAEL(e); > + AddEdgeToSEL(e); > + } else > + { > + //this just simplifies horizontal processing ... > + e->xcurr = TopX( *e, topY ); > + e->ycurr = topY; > + } > + e = e->nextInAEL; > + } > + } > + > + //3. Process horizontals at the top of the scanbeam ... > + ProcessHorizontals(); > + > + //4. Promote intermediate vertices ... > + e = m_ActiveEdges; > + while( e ) > + { > + if( IsIntermediate( e, topY ) ) > + { > + if( e->outIdx >= 0 ) AddOutPt(e, 0, IntPoint(e->xtop,e->ytop)); > + UpdateEdgeIntoAEL(e); > + > + //if output polygons share an edge, they'll need joining later ... > + if (e->outIdx >= 0 && e->prevInAEL && e->prevInAEL->outIdx >= 0 && > + e->prevInAEL->xcurr == e->xbot && e->prevInAEL->ycurr == e->ybot > && > + SlopesEqual(IntPoint(e->xbot,e->ybot), IntPoint(e->xtop, > e->ytop), > + IntPoint(e->xbot,e->ybot), > + IntPoint(e->prevInAEL->xtop, e->prevInAEL->ytop), > m_UseFullRange)) > + { > + AddOutPt(e->prevInAEL, 0, IntPoint(e->xbot, e->ybot)); > + AddJoin(e, e->prevInAEL); > + } > + else if (e->outIdx >= 0 && e->nextInAEL && e->nextInAEL->outIdx >= 0 > && > + e->nextInAEL->ycurr > e->nextInAEL->ytop && > + e->nextInAEL->ycurr < e->nextInAEL->ybot && > + e->nextInAEL->xcurr == e->xbot && e->nextInAEL->ycurr == e->ybot > && > + SlopesEqual(IntPoint(e->xbot,e->ybot), IntPoint(e->xtop, > e->ytop), > + IntPoint(e->xbot,e->ybot), > + IntPoint(e->nextInAEL->xtop, e->nextInAEL->ytop), > m_UseFullRange)) > + { > + AddOutPt(e->nextInAEL, 0, IntPoint(e->xbot, e->ybot)); > + AddJoin(e, e->nextInAEL); > + } > + } > + 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.pts = outRec.bottomPt; > + OutPt *pp = outRec.bottomPt; > + > + for (;;) > + { > + if (pp->prev == pp || pp->prev == pp->next ) > + { > + DisposeOutPts(pp); > + outRec.pts = 0; > + outRec.bottomPt = 0; > + return; > + } > + //test for duplicate points and for same slope (cross-product) ... > + if ( PointsEqual(pp->pt, pp->next->pt) || > + SlopesEqual(pp->prev->pt, pp->pt, pp->next->pt, m_UseFullRange) ) > + { > + lastOK = 0; > + OutPt *tmp = pp; > + if (pp == outRec.bottomPt) > + { > + if (tmp->prev->pt.Y > tmp->next->pt.Y) > + outRec.bottomPt = tmp->prev; else > + outRec.bottomPt = tmp->next; > + outRec.pts = outRec.bottomPt; > + outRec.bottomPt->idx = outRec.idx; > + } > + 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; > + } > + } > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::BuildResult(Polygons &polys) > + { > + int k = 0; > + polys.resize(m_PolyOuts->size()); > + for (PolyOutList::size_type i = 0; i < m_PolyOuts->size(); ++i) > + { > + if (m_PolyOuts->at(i)->pts) > + { > + Polygon* pg = &polys[k]; > + pg->clear(); > + OutPt* p = m_PolyOuts->at(i)->pts; > + do > + { > + pg->push_back(p->pt); > + p = p->next; > + } while (p != m_PolyOuts->at(i)->pts); > + //make sure each polygon has at least 3 vertices ... > + if (pg->size() < 3) pg->clear(); else k++; > + } > + } > + polys.resize(k); > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::BuildResultEx(ExPolygons &polys) > + { > + PolyOutList::size_type i = 0; > + int k = 0; > + polys.resize(0); > + polys.reserve(m_PolyOuts->size()); > + while (i < m_PolyOuts->size() && m_PolyOuts->at(i)->pts) > + { > + ExPolygon epg; > + OutPt* p = m_PolyOuts->at(i)->pts; > + do { > + epg.outer.push_back(p->pt); > + p = p->next; > + } while (p != m_PolyOuts->at(i)->pts); > + i++; > + //make sure polygons have at least 3 vertices ... > + if (epg.outer.size() < 3) continue; > + while (i < m_PolyOuts->size() > + && m_PolyOuts->at(i)->pts && m_PolyOuts->at(i)->isHole) > + { > + Polygon pg; > + p = m_PolyOuts->at(i)->pts; > + do { > + pg.push_back(p->pt); > + p = p->next; > + } while (p != m_PolyOuts->at(i)->pts); > + epg.holes.push_back(pg); > + i++; > + } > + polys.push_back(epg); > + k++; > + } > + polys.resize(k); > + } > + > //------------------------------------------------------------------------------ > + > + void SwapIntersectNodes(IntersectNode &int1, IntersectNode &int2) > + { > + TEdge *e1 = int1.edge1; > + TEdge *e2 = int1.edge2; > + IntPoint p = int1.pt; > + > + int1.edge1 = int2.edge1; > + int1.edge2 = int2.edge2; > + int1.pt = int2.pt; > + > + int2.edge1 = e1; > + int2.edge2 = e2; > + int2.pt = p; > + } > + > //------------------------------------------------------------------------------ > + > + bool Clipper::FixupIntersections() > + { > + if ( !m_IntersectNodes->next ) return true; > + > + CopyAELToSEL(); > + IntersectNode *int1 = m_IntersectNodes; > + IntersectNode *int2 = m_IntersectNodes->next; > + while (int2) > + { > + TEdge *e1 = int1->edge1; > + TEdge *e2; > + if (e1->prevInSEL == int1->edge2) e2 = e1->prevInSEL; > + else if (e1->nextInSEL == int1->edge2) e2 = e1->nextInSEL; > + else > + { > + //The current intersection is out of order, so try and swap it with > + //a subsequent intersection ... > + while (int2) > + { > + if (int2->edge1->nextInSEL == int2->edge2 || > + int2->edge1->prevInSEL == int2->edge2) break; > + else int2 = int2->next; > + } > + if ( !int2 ) return false; //oops!!! > + > + //found an intersect node that can be swapped ... > + SwapIntersectNodes(*int1, *int2); > + e1 = int1->edge1; > + e2 = int1->edge2; > + } > + SwapPositionsInSEL(e1, e2); > + int1 = int1->next; > + int2 = int1->next; > + } > + > + m_SortedEdges = 0; > + > + //finally, check the last intersection too ... > + return (int1->edge1->prevInSEL == int1->edge2 || > + int1->edge1->nextInSEL == int1->edge2); > + } > + > //------------------------------------------------------------------------------ > + > + bool E2InsertsBeforeE1(TEdge &e1, TEdge &e2) > + { > + if (e2.xcurr == e1.xcurr) return e2.dx > e1.dx; > + else return e2.xcurr < e1.xcurr; > + } > + > //------------------------------------------------------------------------------ > + > + void Clipper::InsertEdgeIntoAEL(TEdge *edge) > + { > + edge->prevInAEL = 0; > + edge->nextInAEL = 0; > + if( !m_ActiveEdges ) > + { > + m_ActiveEdges = edge; > + } > + else if( E2InsertsBeforeE1(*m_ActiveEdges, *edge) ) > + { > + edge->nextInAEL = m_ActiveEdges; > + m_ActiveEdges->prevInAEL = edge; > + m_ActiveEdges = edge; > + } else > + { > + TEdge* e = m_ActiveEdges; > + while( e->nextInAEL && !E2InsertsBeforeE1(*e->nextInAEL , *edge) ) > + e = e->nextInAEL; > + edge->nextInAEL = e->nextInAEL; > + if( e->nextInAEL ) e->nextInAEL->prevInAEL = edge; > + edge->prevInAEL = e; > + e->nextInAEL = edge; > + } > + } > + //---------------------------------------------------------------------- > + > + void Clipper::DoEdge1(TEdge *edge1, TEdge *edge2, const IntPoint &pt) > + { > + AddOutPt(edge1, edge2, pt); > + SwapSides(*edge1, *edge2); > + SwapPolyIndexes(*edge1, *edge2); > + } > + //---------------------------------------------------------------------- > + > + void Clipper::DoEdge2(TEdge *edge1, TEdge *edge2, const IntPoint &pt) > + { > + AddOutPt(edge2, edge1, pt); > + SwapSides(*edge1, *edge2); > + SwapPolyIndexes(*edge1, *edge2); > + } > + //---------------------------------------------------------------------- > + > + void Clipper::DoBothEdges(TEdge *edge1, TEdge *edge2, const IntPoint &pt) > + { > + AddOutPt(edge1, edge2, pt); > + AddOutPt(edge2, edge1, pt); > + SwapSides( *edge1 , *edge2 ); > + SwapPolyIndexes( *edge1 , *edge2 ); > + } > + //---------------------------------------------------------------------- > + > + void Clipper::CheckHoleLinkages1(OutRec *outRec1, OutRec *outRec2) > + { > + //when a polygon is split into 2 polygons, make sure any holes the > original > + //polygon contained link to the correct polygon ... > + for (PolyOutList::size_type i = 0; i < m_PolyOuts->size(); ++i) > + { > + OutRec *orec = m_PolyOuts->at(i); > + if (orec->isHole && orec->bottomPt && orec->FirstLeft == outRec1 && > + !PointInPolygon(orec->bottomPt->pt, outRec1->pts, > m_UseFullRange)) > + orec->FirstLeft = outRec2; > + } > + } > + //---------------------------------------------------------------------- > + > + void Clipper::CheckHoleLinkages2(OutRec *outRec1, OutRec *outRec2) > + { > + //if a hole is owned by outRec2 then make it owned by outRec1 ... > + for (PolyOutList::size_type i = 0; i < m_PolyOuts->size(); ++i) > + if (m_PolyOuts->at(i)->isHole && m_PolyOuts->at(i)->bottomPt && > > @@ Diff output truncated at 100000 characters. @@ > This was sent by the SourceForge.net collaborative development platform, the > world's largest Open Source development site. > > > > _______________________________________________ > BRL-CAD Source Commits mailing list > brlcad-comm...@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/brlcad-commits _______________________________________________ BRL-CAD Developer mailing list brlcad-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/brlcad-devel
