clipper.hpp   clipper.hpp 
/************************************************************************** ***** /************************************************************************** *****
* * * *
* Author : Angus Johnson * * Author : Angus Johnson *
* Version : 6.1.3 * Version : 6.2.0
* *
* Date : 19 January 2014 * Date : 2 October 2014
* *
* Website : http://www.angusj.com * * Website : http://www.angusj.com *
* Copyright : Angus Johnson 2010-2014 * * Copyright : Angus Johnson 2010-2014 *
* * * *
* License: * * License: *
* Use, modification & distribution is subject to Boost Software License Ver 1. * * Use, modification & distribution is subject to Boost Software License Ver 1. *
* http://www.boost.org/LICENSE_1_0.txt * * http://www.boost.org/LICENSE_1_0.txt *
* * * *
* Attributions: * * Attributions: *
* The code in this library is an extension of Bala Vatti's clipping algorit hm: * * The code in this library is an extension of Bala Vatti's clipping algorit hm: *
* "A generic solution to polygon clipping" * * "A generic solution to polygon clipping" *
skipping to change at line 37 skipping to change at line 37
* ASME 2005 International Design Engineering Technical Conferences * * ASME 2005 International Design Engineering Technical Conferences *
* and Computers and Information in Engineering Conference (IDETC/CIE2005) * * and Computers and Information in Engineering Conference (IDETC/CIE2005) *
* September 24-28, 2005 , Long Beach, California, USA * * September 24-28, 2005 , Long Beach, California, USA *
* http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf * * http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf *
* * * *
*************************************************************************** ****/ *************************************************************************** ****/
#ifndef clipper_hpp #ifndef clipper_hpp
#define clipper_hpp #define clipper_hpp
#define CLIPPER_VERSION "6.1.3" #define CLIPPER_VERSION "6.2.0"
//use_int32: When enabled 32bit ints are used instead of 64bit ints. This //use_int32: When enabled 32bit ints are used instead of 64bit ints. This
//improve performance but coordinate values are limited to the range +/- 46 340 //improve performance but coordinate values are limited to the range +/- 46 340
//#define use_int32 //#define use_int32
//use_xyz: adds a Z member to IntPoint. Adds a minor cost to perfomance. //use_xyz: adds a Z member to IntPoint. Adds a minor cost to perfomance.
//#define use_xyz //#define use_xyz
//use_lines: Enables line clipping. Adds a very minor cost to performance. //use_lines: Enables line clipping. Adds a very minor cost to performance.
//#define use_lines //#define use_lines
//use_deprecated: Enables support for the obsolete OffsetPaths() function //use_deprecated: Enables temporary support for the obsolete functions
//which has been replace with the ClipperOffset class. //#define use_deprecated
#define use_deprecated
#include <vector> #include <vector>
#include <set> #include <set>
#include <stdexcept> #include <stdexcept>
#include <cstring> #include <cstring>
#include <cstdlib> #include <cstdlib>
#include <ostream> #include <ostream>
#include <functional> #include <functional>
#include <queue>
namespace ClipperLib { namespace ClipperLib {
enum ClipType { ctIntersection, ctUnion, ctDifference, ctXor }; enum ClipType { ctIntersection, ctUnion, ctDifference, ctXor };
enum PolyType { ptSubject, ptClip }; enum PolyType { ptSubject, ptClip };
//By far the most widely used winding rules for polygon filling are //By far the most widely used winding rules for polygon filling are
//EvenOdd & NonZero (GDI, GDI+, XLib, OpenGL, Cairo, AGG, Quartz, SVG, Gr32 ) //EvenOdd & NonZero (GDI, GDI+, XLib, OpenGL, Cairo, AGG, Quartz, SVG, Gr32 )
//Others rules include Positive, Negative and ABS_GTR_EQ_TWO (only in OpenG L) //Others rules include Positive, Negative and ABS_GTR_EQ_TWO (only in OpenG L)
//see http://glprogramming.com/red/chapter11.html //see http://glprogramming.com/red/chapter11.html
enum PolyFillType { pftEvenOdd, pftNonZero, pftPositive, pftNegative }; enum PolyFillType { pftEvenOdd, pftNonZero, pftPositive, pftNegative };
#ifdef use_int32 #ifdef use_int32
typedef int cInt; typedef int cInt;
typedef unsigned int cUInt; static cInt const loRange = 0x7FFF;
static cInt const hiRange = 0x7FFF;
#else #else
typedef signed long long cInt; typedef signed long long cInt;
typedef unsigned long long cUInt; static cInt const loRange = 0x3FFFFFFF;
static cInt const hiRange = 0x3FFFFFFFFFFFFFFFLL;
typedef signed long long long64; //used by Int128 class
typedef unsigned long long ulong64;
#endif #endif
struct IntPoint { struct IntPoint {
cInt X; cInt X;
cInt Y; cInt Y;
#ifdef use_xyz #ifdef use_xyz
cInt Z; cInt Z;
IntPoint(cInt x = 0, cInt y = 0, cInt z = 0): X(x), Y(y), Z(z) {}; IntPoint(cInt x = 0, cInt y = 0, cInt z = 0): X(x), Y(y), Z(z) {};
#else #else
IntPoint(cInt x = 0, cInt y = 0): X(x), Y(y) {}; IntPoint(cInt x = 0, cInt y = 0): X(x), Y(y) {};
skipping to change at line 120 skipping to change at line 125
struct DoublePoint struct DoublePoint
{ {
double X; double X;
double Y; double Y;
DoublePoint(double x = 0, double y = 0) : X(x), Y(y) {} DoublePoint(double x = 0, double y = 0) : X(x), Y(y) {}
DoublePoint(IntPoint ip) : X((double)ip.X), Y((double)ip.Y) {} DoublePoint(IntPoint ip) : X((double)ip.X), Y((double)ip.Y) {}
}; };
//------------------------------------------------------------------------- ----- //------------------------------------------------------------------------- -----
#ifdef use_xyz #ifdef use_xyz
typedef void (*TZFillCallback)(IntPoint& z1, IntPoint& z2, IntPoint& pt); typedef void (*ZFillCallback)(IntPoint& e1bot, IntPoint& e1top, IntPoint& e 2bot, IntPoint& e2top, IntPoint& pt);
#endif #endif
enum InitOptions {ioReverseSolution = 1, ioStrictlySimple = 2, ioPreserveCo llinear = 4}; enum InitOptions {ioReverseSolution = 1, ioStrictlySimple = 2, ioPreserveCo llinear = 4};
enum JoinType {jtSquare, jtRound, jtMiter}; enum JoinType {jtSquare, jtRound, jtMiter};
enum EndType {etClosedPolygon, etClosedLine, etOpenButt, etOpenSquare, etOp enRound}; enum EndType {etClosedPolygon, etClosedLine, etOpenButt, etOpenSquare, etOp enRound};
#ifdef use_deprecated
enum EndType_ {etClosed, etButt = 2, etSquare, etRound};
#endif
class PolyNode; class PolyNode;
typedef std::vector< PolyNode* > PolyNodes; typedef std::vector< PolyNode* > PolyNodes;
class PolyNode class PolyNode
{ {
public: public:
PolyNode(); PolyNode();
virtual ~PolyNode(){};
Path Contour; Path Contour;
PolyNodes Childs; PolyNodes Childs;
PolyNode* Parent; PolyNode* Parent;
PolyNode* GetNext() const; PolyNode* GetNext() const;
bool IsHole() const; bool IsHole() const;
bool IsOpen() const; bool IsOpen() const;
int ChildCount() const; int ChildCount() const;
private: private:
unsigned Index; //node index in Parent.Childs unsigned Index; //node index in Parent.Childs
bool m_IsOpen; bool m_IsOpen;
skipping to change at line 171 skipping to change at line 174
int Total() const; int Total() const;
private: private:
PolyNodes AllNodes; PolyNodes AllNodes;
friend class Clipper; //to access AllNodes friend class Clipper; //to access AllNodes
}; };
bool Orientation(const Path &poly); bool Orientation(const Path &poly);
double Area(const Path &poly); double Area(const Path &poly);
int PointInPolygon(const IntPoint &pt, const Path &path); int PointInPolygon(const IntPoint &pt, const Path &path);
#ifdef use_deprecated
void OffsetPaths(const Paths &in_polys, Paths &out_polys,
double delta, JoinType jointype, EndType_ endtype, double limit = 0);
#endif
void SimplifyPolygon(const Path &in_poly, Paths &out_polys, PolyFillType fi llType = pftEvenOdd); void SimplifyPolygon(const Path &in_poly, Paths &out_polys, PolyFillType fi llType = pftEvenOdd);
void SimplifyPolygons(const Paths &in_polys, Paths &out_polys, PolyFillType fillType = pftEvenOdd); void SimplifyPolygons(const Paths &in_polys, Paths &out_polys, PolyFillType fillType = pftEvenOdd);
void SimplifyPolygons(Paths &polys, PolyFillType fillType = pftEvenOdd); void SimplifyPolygons(Paths &polys, PolyFillType fillType = pftEvenOdd);
void CleanPolygon(const Path& in_poly, Path& out_poly, double distance = 1. 415); void CleanPolygon(const Path& in_poly, Path& out_poly, double distance = 1. 415);
void CleanPolygon(Path& poly, double distance = 1.415); void CleanPolygon(Path& poly, double distance = 1.415);
void CleanPolygons(const Paths& in_polys, Paths& out_polys, double distance = 1.415); void CleanPolygons(const Paths& in_polys, Paths& out_polys, double distance = 1.415);
void CleanPolygons(Paths& polys, double distance = 1.415); void CleanPolygons(Paths& polys, double distance = 1.415);
void MinkowskiSum(const Path& pattern, const Path& path, Paths& solution, b ool pathIsClosed); void MinkowskiSum(const Path& pattern, const Path& path, Paths& solution, b ool pathIsClosed);
void MinkowskiSum(const Path& pattern, const Paths& paths, void MinkowskiSum(const Path& pattern, const Paths& paths, Paths& solution,
Paths& solution, PolyFillType pathFillType, bool pathIsClosed); bool pathIsClosed);
void MinkowskiDiff(const Path& poly1, const Path& poly2, Paths& solution); void MinkowskiDiff(const Path& poly1, const Path& poly2, Paths& solution);
void PolyTreeToPaths(const PolyTree& polytree, Paths& paths); void PolyTreeToPaths(const PolyTree& polytree, Paths& paths);
void ClosedPathsFromPolyTree(const PolyTree& polytree, Paths& paths); void ClosedPathsFromPolyTree(const PolyTree& polytree, Paths& paths);
void OpenPathsFromPolyTree(PolyTree& polytree, Paths& paths); void OpenPathsFromPolyTree(PolyTree& polytree, Paths& paths);
void ReversePath(Path& p); void ReversePath(Path& p);
void ReversePaths(Paths& p); void ReversePaths(Paths& p);
struct IntRect { cInt left; cInt top; cInt right; cInt bottom; }; struct IntRect { cInt left; cInt top; cInt right; cInt bottom; };
//enums that are used internally ... //enums that are used internally ...
enum EdgeSide { esLeft = 1, esRight = 2}; enum EdgeSide { esLeft = 1, esRight = 2};
//forward declarations (for stuff used internally) ... //forward declarations (for stuff used internally) ...
struct TEdge; struct TEdge;
struct IntersectNode; struct IntersectNode;
struct LocalMinima; struct LocalMinimum;
struct Scanbeam; struct Scanbeam;
struct OutPt; struct OutPt;
struct OutRec; struct OutRec;
struct Join; struct Join;
typedef std::vector < OutRec* > PolyOutList; typedef std::vector < OutRec* > PolyOutList;
typedef std::vector < TEdge* > EdgeList; typedef std::vector < TEdge* > EdgeList;
typedef std::vector < Join* > JoinList; typedef std::vector < Join* > JoinList;
typedef std::vector < IntersectNode* > IntersectList; typedef std::vector < IntersectNode* > IntersectList;
skipping to change at line 238 skipping to change at line 235
virtual void Clear(); virtual void Clear();
IntRect GetBounds(); IntRect GetBounds();
bool PreserveCollinear() {return m_PreserveCollinear;}; bool PreserveCollinear() {return m_PreserveCollinear;};
void PreserveCollinear(bool value) {m_PreserveCollinear = value;}; void PreserveCollinear(bool value) {m_PreserveCollinear = value;};
protected: protected:
void DisposeLocalMinimaList(); void DisposeLocalMinimaList();
TEdge* AddBoundsToLML(TEdge *e, bool IsClosed); TEdge* AddBoundsToLML(TEdge *e, bool IsClosed);
void PopLocalMinima(); void PopLocalMinima();
virtual void Reset(); virtual void Reset();
TEdge* ProcessBound(TEdge* E, bool IsClockwise); TEdge* ProcessBound(TEdge* E, bool IsClockwise);
void InsertLocalMinima(LocalMinima *newLm);
void DoMinimaLML(TEdge* E1, TEdge* E2, bool IsClosed); void DoMinimaLML(TEdge* E1, TEdge* E2, bool IsClosed);
TEdge* DescendToMin(TEdge *&E); TEdge* DescendToMin(TEdge *&E);
void AscendToMax(TEdge *&E, bool Appending, bool IsClosed); void AscendToMax(TEdge *&E, bool Appending, bool IsClosed);
LocalMinima *m_CurrentLM;
LocalMinima *m_MinimaList; typedef std::vector<LocalMinimum> MinimaList;
MinimaList::iterator m_CurrentLM;
MinimaList m_MinimaList;
bool m_UseFullRange; bool m_UseFullRange;
EdgeList m_edges; EdgeList m_edges;
bool m_PreserveCollinear; bool m_PreserveCollinear;
bool m_HasOpenPaths; bool m_HasOpenPaths;
}; };
//------------------------------------------------------------------------- ----- //------------------------------------------------------------------------- -----
class Clipper : public virtual ClipperBase class Clipper : public virtual ClipperBase
{ {
public: public:
skipping to change at line 270 skipping to change at line 269
bool Execute(ClipType clipType, bool Execute(ClipType clipType,
PolyTree &polytree, PolyTree &polytree,
PolyFillType subjFillType = pftEvenOdd, PolyFillType subjFillType = pftEvenOdd,
PolyFillType clipFillType = pftEvenOdd); PolyFillType clipFillType = pftEvenOdd);
bool ReverseSolution() {return m_ReverseOutput;}; bool ReverseSolution() {return m_ReverseOutput;};
void ReverseSolution(bool value) {m_ReverseOutput = value;}; void ReverseSolution(bool value) {m_ReverseOutput = value;};
bool StrictlySimple() {return m_StrictSimple;}; bool StrictlySimple() {return m_StrictSimple;};
void StrictlySimple(bool value) {m_StrictSimple = value;}; void StrictlySimple(bool value) {m_StrictSimple = value;};
//set the callback function for z value filling on intersections (otherwi se Z is 0) //set the callback function for z value filling on intersections (otherwi se Z is 0)
#ifdef use_xyz #ifdef use_xyz
void ZFillFunction(TZFillCallback zFillFunc); void ZFillFunction(ZFillCallback zFillFunc);
#endif #endif
protected: protected:
void Reset(); void Reset();
virtual bool ExecuteInternal(); virtual bool ExecuteInternal();
private: private:
PolyOutList m_PolyOuts; PolyOutList m_PolyOuts;
JoinList m_Joins; JoinList m_Joins;
JoinList m_GhostJoins; JoinList m_GhostJoins;
IntersectList m_IntersectList; IntersectList m_IntersectList;
ClipType m_ClipType; ClipType m_ClipType;
std::set< cInt, std::greater<cInt> > m_Scanbeam; typedef std::priority_queue<cInt> ScanbeamList;
ScanbeamList m_Scanbeam;
TEdge *m_ActiveEdges; TEdge *m_ActiveEdges;
TEdge *m_SortedEdges; TEdge *m_SortedEdges;
bool m_ExecuteLocked; bool m_ExecuteLocked;
PolyFillType m_ClipFillType; PolyFillType m_ClipFillType;
PolyFillType m_SubjFillType; PolyFillType m_SubjFillType;
bool m_ReverseOutput; bool m_ReverseOutput;
bool m_UsingPolyTree; bool m_UsingPolyTree;
bool m_StrictSimple; bool m_StrictSimple;
#ifdef use_xyz #ifdef use_xyz
TZFillCallback m_ZFill; //custom callback ZFillCallback m_ZFill; //custom callback
#endif #endif
void SetWindingCount(TEdge& edge); void SetWindingCount(TEdge& edge);
bool IsEvenOddFillType(const TEdge& edge) const; bool IsEvenOddFillType(const TEdge& edge) const;
bool IsEvenOddAltFillType(const TEdge& edge) const; bool IsEvenOddAltFillType(const TEdge& edge) const;
void InsertScanbeam(const cInt Y); void InsertScanbeam(const cInt Y);
cInt PopScanbeam(); cInt PopScanbeam();
void InsertLocalMinimaIntoAEL(const cInt botY); void InsertLocalMinimaIntoAEL(const cInt botY);
void InsertEdgeIntoAEL(TEdge *edge, TEdge* startEdge); void InsertEdgeIntoAEL(TEdge *edge, TEdge* startEdge);
void AddEdgeToSEL(TEdge *edge); void AddEdgeToSEL(TEdge *edge);
void CopyAELToSEL(); void CopyAELToSEL();
void DeleteFromSEL(TEdge *e); void DeleteFromSEL(TEdge *e);
void DeleteFromAEL(TEdge *e); void DeleteFromAEL(TEdge *e);
void UpdateEdgeIntoAEL(TEdge *&e); void UpdateEdgeIntoAEL(TEdge *&e);
void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2); void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2);
bool IsContributing(const TEdge& edge) const; bool IsContributing(const TEdge& edge) const;
bool IsTopHorz(const cInt XPos); bool IsTopHorz(const cInt XPos);
void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2); void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2);
void DoMaxima(TEdge *e); void DoMaxima(TEdge *e);
void PrepareHorzJoins(TEdge* horzEdge, bool isTopOfScanbeam);
void ProcessHorizontals(bool IsTopOfScanbeam); void ProcessHorizontals(bool IsTopOfScanbeam);
void ProcessHorizontal(TEdge *horzEdge, bool isTopOfScanbeam); void ProcessHorizontal(TEdge *horzEdge, bool isTopOfScanbeam);
void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
OutPt* AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); OutPt* AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
OutRec* GetOutRec(int idx); OutRec* GetOutRec(int idx);
void AppendPolygon(TEdge *e1, TEdge *e2); void AppendPolygon(TEdge *e1, TEdge *e2);
void IntersectEdges(TEdge *e1, TEdge *e2, void IntersectEdges(TEdge *e1, TEdge *e2, IntPoint &pt);
const IntPoint &pt, bool protect = false);
OutRec* CreateOutRec(); OutRec* CreateOutRec();
OutPt* AddOutPt(TEdge *e, const IntPoint &pt); OutPt* AddOutPt(TEdge *e, const IntPoint &pt);
void DisposeAllOutRecs(); void DisposeAllOutRecs();
void DisposeOutRec(PolyOutList::size_type index); void DisposeOutRec(PolyOutList::size_type index);
bool ProcessIntersections(const cInt botY, const cInt topY); bool ProcessIntersections(const cInt botY, const cInt topY);
void BuildIntersectList(const cInt botY, const cInt topY); void BuildIntersectList(const cInt botY, const cInt topY);
void ProcessIntersectList(); void ProcessIntersectList();
void ProcessEdgesAtTopOfScanbeam(const cInt topY); void ProcessEdgesAtTopOfScanbeam(const cInt topY);
void BuildResult(Paths& polys); void BuildResult(Paths& polys);
void BuildResult2(PolyTree& polytree); void BuildResult2(PolyTree& polytree);
skipping to change at line 346 skipping to change at line 344
void AddJoin(OutPt *op1, OutPt *op2, const IntPoint offPt); void AddJoin(OutPt *op1, OutPt *op2, const IntPoint offPt);
void ClearJoins(); void ClearJoins();
void ClearGhostJoins(); void ClearGhostJoins();
void AddGhostJoin(OutPt *op, const IntPoint offPt); void AddGhostJoin(OutPt *op, const IntPoint offPt);
bool JoinPoints(Join *j, OutRec* outRec1, OutRec* outRec2); bool JoinPoints(Join *j, OutRec* outRec1, OutRec* outRec2);
void JoinCommonEdges(); void JoinCommonEdges();
void DoSimplePolygons(); void DoSimplePolygons();
void FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec); void FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec);
void FixupFirstLefts2(OutRec* OldOutRec, OutRec* NewOutRec); void FixupFirstLefts2(OutRec* OldOutRec, OutRec* NewOutRec);
#ifdef use_xyz #ifdef use_xyz
void SetZ(IntPoint& pt, TEdge& e); void SetZ(IntPoint& pt, TEdge& e1, TEdge& e2);
#endif #endif
}; };
//------------------------------------------------------------------------- ----- //------------------------------------------------------------------------- -----
class ClipperOffset class ClipperOffset
{ {
public: public:
ClipperOffset(double miterLimit = 2.0, double roundPrecision = 0.25); ClipperOffset(double miterLimit = 2.0, double roundPrecision = 0.25);
~ClipperOffset(); ~ClipperOffset();
void AddPath(const Path& path, JoinType joinType, EndType endType); void AddPath(const Path& path, JoinType joinType, EndType endType);
 End of changes. 20 change blocks. 
34 lines changed or deleted 33 lines changed or added

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/