clipper.hpp   clipper.hpp 
/************************************************************************** ***** /************************************************************************** *****
* * * *
* Author : Angus Johnson * * Author : Angus Johnson *
* Version : 6.0.0 * Version : 6.1.0
* *
* Date : 30 October 2013 * Date : 11 December 2013
* *
* Website : http://www.angusj.com * * Website : http://www.angusj.com *
* Copyright : Angus Johnson 2010-2013 * * Copyright : Angus Johnson 2010-2013 *
* * * *
* 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.0.0" #define CLIPPER_VERSION "6.1.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
skipping to change at line 130 skipping to change at line 130
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 (*TZFillCallback)(IntPoint& z1, IntPoint& z2, IntPoint& pt);
#endif #endif
enum InitOptions {ioReverseSolution = 1, ioStrictlySimple = 2, ioPreserveCo
llinear = 4};
enum JoinType {jtSquare, jtRound, jtMiter};
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();
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
bool m_IsOpen; bool m_IsOpen;
JoinType m_jointype;
EndType m_endtype;
PolyNode* GetNextSiblingUp() const; PolyNode* GetNextSiblingUp() const;
unsigned Index; //node index in Parent.Childs
void AddChild(PolyNode& child); void AddChild(PolyNode& child);
friend class Clipper; //to access Index friend class Clipper; //to access Index
friend class ClipperOffset;
}; };
class PolyTree: public PolyNode class PolyTree: public PolyNode
{ {
public: public:
~PolyTree(){Clear();}; ~PolyTree(){Clear();};
PolyNode* GetFirst() const; PolyNode* GetFirst() const;
void Clear(); void Clear();
int Total() const; int Total() const;
private: private:
PolyNodes AllNodes; PolyNodes AllNodes;
friend class Clipper; //to access AllNodes friend class Clipper; //to access AllNodes
}; };
enum InitOptions {ioReverseSolution = 1, ioStrictlySimple = 2, ioPreserveCo
llinear = 4};
enum JoinType {jtSquare, jtRound, jtMiter};
enum EndType {etClosed, etButt, etSquare, etRound};
bool Orientation(const Path &poly); bool Orientation(const Path &poly);
double Area(const Path &poly); double Area(const Path &poly);
#ifdef use_deprecated #ifdef use_deprecated
void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys, void OffsetPaths(const Paths &in_polys, Paths &out_polys,
double delta, JoinType jointype = jtSquare, double limit = 0, bool auto double delta, JoinType jointype, EndType_ endtype, double limit = 0);
Fix = true);
void PolyTreeToPolygons(const PolyTree& polytree, Paths& paths);
void ReversePolygon(Path& p);
void ReversePolygons(Paths& p);
#endif #endif
void OffsetPaths(const Paths &in_polys, Paths &out_polys,
double delta, JoinType jointype, EndType endtype, double limit = 0);
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 MinkowkiSum(const Path& poly, const Path& path, Paths& solution, bool void MinkowskiSum(const Path& poly, const Path& path, Paths& solution, bool
isClosed); isClosed);
void MinkowkiDiff(const Path& poly, const Path& path, Paths& solution, bool void MinkowskiDiff(const Path& poly, const Path& path, Paths& solution, boo
isClosed); l isClosed);
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; };
skipping to change at line 218 skipping to change at line 218
struct IntersectNode; struct IntersectNode;
struct LocalMinima; struct LocalMinima;
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;
//------------------------------------------------------------------------- ----- //------------------------------------------------------------------------- -----
//ClipperBase is the ancestor to the Clipper class. It should not be //ClipperBase is the ancestor to the Clipper class. It should not be
//instantiated directly. This class simply abstracts the conversion of sets of //instantiated directly. This class simply abstracts the conversion of sets of
//polygon coordinates into edge objects that are stored in a LocalMinima li st. //polygon coordinates into edge objects that are stored in a LocalMinima li st.
class ClipperBase class ClipperBase
{ {
public: public:
ClipperBase(); ClipperBase();
skipping to change at line 246 skipping to change at line 247
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);
void InsertLocalMinima(LocalMinima *newLm); 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_CurrentLM;
LocalMinima *m_MinimaList; LocalMinima *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;
skipping to change at line 288 skipping to change at line 290
#ifdef use_xyz #ifdef use_xyz
void ZFillFunction(TZFillCallback zFillFunc); void ZFillFunction(TZFillCallback 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;
ClipType m_ClipType; ClipType m_ClipType;
std::set< cInt, std::greater<cInt> > m_Scanbeam; std::set< cInt, std::greater<cInt> > m_Scanbeam;
TEdge *m_ActiveEdges; TEdge *m_ActiveEdges;
TEdge *m_SortedEdges; TEdge *m_SortedEdges;
IntersectNode *m_IntersectNodes;
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 TZFillCallback m_ZFill; //custom callback
#endif #endif
void SetWindingCount(TEdge& edge); void SetWindingCount(TEdge& edge);
skipping to change at line 333 skipping to change at line 335
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,
const IntPoint &pt, bool protect = false); 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 InsertIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt);
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);
void SetHoleState(TEdge *e, OutRec *outrec); void SetHoleState(TEdge *e, OutRec *outrec);
void DisposeIntersectNodes(); void DisposeIntersectNodes();
bool FixupIntersectionOrder(); bool FixupIntersectionOrder();
void FixupOutPolygon(OutRec &outrec); void FixupOutPolygon(OutRec &outrec);
bool IsHole(TEdge *e); bool IsHole(TEdge *e);
bool FindOwnerFromSplitRecs(OutRec &outRec, OutRec *&currOrfl);
void FixHoleLinkage(OutRec &outrec); void FixHoleLinkage(OutRec &outrec);
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(const Join *j, OutPt *&p1, OutPt *&p2); bool JoinPoints(const Join *j, OutPt *&p1, OutPt *&p2);
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& e);
#endif #endif
}; };
//------------------------------------------------------------------------- ----- //------------------------------------------------------------------------- -----
class ClipperOffset
{
public:
ClipperOffset(double miterLimit = 2.0, double roundPrecision = 0.25);
~ClipperOffset();
void AddPath(const Path& path, JoinType joinType, EndType endType);
void AddPaths(const Paths& paths, JoinType joinType, EndType endType);
void Execute(Paths& solution, double delta);
void Execute(PolyTree& solution, double delta);
void Clear();
double MiterLimit;
double ArcTolerance;
private:
Paths m_destPolys;
Path m_srcPoly;
Path m_destPoly;
std::vector<DoublePoint> m_normals;
double m_delta, m_sinA, m_sin, m_cos;
double m_miterLim, m_StepsPerRad;
IntPoint m_lowest;
PolyNode m_polyNodes;
void FixOrientations();
void DoOffset(double delta);
void OffsetPoint(int j, int& k, JoinType jointype);
void DoSquare(int j, int k);
void DoMiter(int j, int k, double r);
void DoRound(int j, int k);
};
//-------------------------------------------------------------------------
-----
class clipperException : public std::exception class clipperException : public std::exception
{ {
public: public:
clipperException(const char* description): m_descr(description) {} clipperException(const char* description): m_descr(description) {}
virtual ~clipperException() throw() {} virtual ~clipperException() throw() {}
virtual const char* what() const throw() {return m_descr.c_str();} virtual const char* what() const throw() {return m_descr.c_str();}
private: private:
std::string m_descr; std::string m_descr;
}; };
//------------------------------------------------------------------------- ----- //------------------------------------------------------------------------- -----
 End of changes. 18 change blocks. 
26 lines changed or deleted 60 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/