clipper.hpp   clipper.hpp 
/************************************************************************** ***** /************************************************************************** *****
* * * *
* Author : Angus Johnson * * Author : Angus Johnson *
* Version : 5.0.3 * Version : 5.1.0
* *
* Date : 12 January 2013 * Date : 1 February 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 29 skipping to change at line 29
* Computer graphics and geometric modeling: implementation and algorithms * * Computer graphics and geometric modeling: implementation and algorithms *
* By Max K. Agoston * * By Max K. Agoston *
* Springer; 1 edition (January 4, 2005) * * Springer; 1 edition (January 4, 2005) *
* http://books.google.com/books?q=vatti+clipping+agoston * * http://books.google.com/books?q=vatti+clipping+agoston *
* * * *
* See also: * * See also: *
* "Polygon Offsetting by Computing Winding Numbers" * * "Polygon Offsetting by Computing Winding Numbers" *
* Paper no. DETC2005-85513 pp. 565-575 * * Paper no. DETC2005-85513 pp. 565-575 *
* 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
#include <vector> #include <vector>
#include <stdexcept> #include <stdexcept>
#include <cstring> #include <cstring>
skipping to change at line 70 skipping to change at line 70
IntPoint(long64 x = 0, long64 y = 0): X(x), Y(y) {}; IntPoint(long64 x = 0, long64 y = 0): X(x), Y(y) {};
friend std::ostream& operator <<(std::ostream &s, IntPoint &p); friend std::ostream& operator <<(std::ostream &s, IntPoint &p);
}; };
typedef std::vector< IntPoint > Polygon; typedef std::vector< IntPoint > Polygon;
typedef std::vector< Polygon > Polygons; typedef std::vector< Polygon > Polygons;
std::ostream& operator <<(std::ostream &s, Polygon &p); std::ostream& operator <<(std::ostream &s, Polygon &p);
std::ostream& operator <<(std::ostream &s, Polygons &p); std::ostream& operator <<(std::ostream &s, Polygons &p);
struct ExPolygon { class PolyNode;
Polygon outer; typedef std::vector< PolyNode* > PolyNodes;
Polygons holes;
class PolyNode
{
public:
Polygon Contour;
PolyNodes Childs;
PolyNode* Parent;
PolyNode* GetNext();
bool IsHole();
int ChildCount();
private:
PolyNode* GetNextSiblingUp();
unsigned Index; //node index in Parent.Childs
void AddChild(PolyNode& child);
friend class Clipper; //to access Index
};
class PolyTree: public PolyNode
{
public:
~PolyTree(){Clear();};
PolyNode* GetFirst();
void Clear();
int Total();
private:
PolyNodes AllNodes;
friend class Clipper; //to access AllNodes
}; };
typedef std::vector< ExPolygon > ExPolygons;
enum JoinType { jtSquare, jtRound, jtMiter }; enum JoinType { jtSquare, jtRound, jtMiter };
bool Orientation(const Polygon &poly); bool Orientation(const Polygon &poly);
double Area(const Polygon &poly); double Area(const Polygon &poly);
void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys, void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys,
double delta, JoinType jointype = jtSquare, double MiterLimit = 2, bool A utoFix = true); double delta, JoinType jointype = jtSquare, double MiterLimit = 2, bool A utoFix = true);
void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillT ype fillType = pftEvenOdd); void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillT ype fillType = pftEvenOdd);
void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys, PolyFi llType fillType = pftEvenOdd); void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys, PolyFi llType fillType = pftEvenOdd);
void SimplifyPolygons(Polygons &polys, PolyFillType fillType = pftEvenOdd); void SimplifyPolygons(Polygons &polys, PolyFillType fillType = pftEvenOdd);
void CleanPolygon(Polygon& in_poly, Polygon& out_poly, double distance = 1.
415);
void CleanPolygons(Polygons& in_polys, Polygons& out_polys, double distance
= 1.415);
void PolyTreeToPolygons(PolyTree& polytree, Polygons& polygons);
void ReversePolygon(Polygon& p); void ReversePolygon(Polygon& p);
void ReversePolygons(Polygons& p); void ReversePolygons(Polygons& p);
//used internally ... //used internally ...
enum EdgeSide { esLeft = 1, esRight = 2}; enum EdgeSide { esLeft = 1, esRight = 2};
enum IntersectProtects { ipNone = 0, ipLeft = 1, ipRight = 2, ipBoth = 3 }; enum IntersectProtects { ipNone = 0, ipLeft = 1, ipRight = 2, ipBoth = 3 };
struct TEdge { struct TEdge {
long64 xbot; long64 xbot;
long64 ybot; long64 ybot;
skipping to change at line 143 skipping to change at line 174
struct Scanbeam { struct Scanbeam {
long64 Y; long64 Y;
Scanbeam *next; Scanbeam *next;
}; };
struct OutPt; //forward declaration struct OutPt; //forward declaration
struct OutRec { struct OutRec {
int idx; int idx;
bool isHole; bool isHole;
OutRec *FirstLeft; OutRec *FirstLeft; //see comments in clipper.pas
OutRec *AppendLink; PolyNode *polyNode;
OutPt *pts; OutPt *pts;
OutPt *bottomPt; OutPt *bottomPt;
}; };
struct OutPt { struct OutPt {
int idx; int idx;
IntPoint pt; IntPoint pt;
OutPt *next; OutPt *next;
OutPt *prev; OutPt *prev;
}; };
skipping to change at line 207 skipping to change at line 238
bool m_UseFullRange; bool m_UseFullRange;
EdgeList m_edges; EdgeList m_edges;
}; };
class Clipper : public virtual ClipperBase class Clipper : public virtual ClipperBase
{ {
public: public:
Clipper(); Clipper();
~Clipper(); ~Clipper();
bool Execute(ClipType clipType, bool Execute(ClipType clipType,
Polygons &solution, Polygons &solution,
PolyFillType subjFillType = pftEvenOdd, PolyFillType subjFillType = pftEvenOdd,
PolyFillType clipFillType = pftEvenOdd); PolyFillType clipFillType = pftEvenOdd);
bool Execute(ClipType clipType, bool Execute(ClipType clipType,
ExPolygons &solution, PolyTree &polytree,
PolyFillType subjFillType = pftEvenOdd, PolyFillType subjFillType = pftEvenOdd,
PolyFillType clipFillType = pftEvenOdd); PolyFillType clipFillType = pftEvenOdd);
void Clear(); void Clear();
bool ReverseSolution() {return m_ReverseOutput;}; bool ReverseSolution() {return m_ReverseOutput;};
void ReverseSolution(bool value) {m_ReverseOutput = value;}; void ReverseSolution(bool value) {m_ReverseOutput = value;};
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;
HorzJoinList m_HorizJoins; HorzJoinList m_HorizJoins;
ClipType m_ClipType; ClipType m_ClipType;
Scanbeam *m_Scanbeam; Scanbeam *m_Scanbeam;
TEdge *m_ActiveEdges; TEdge *m_ActiveEdges;
TEdge *m_SortedEdges; TEdge *m_SortedEdges;
IntersectNode *m_IntersectNodes; 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_UsingExPolygons; bool m_UsingPolyTree;
void DisposeScanbeamList(); void DisposeScanbeamList();
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 long64 Y); void InsertScanbeam(const long64 Y);
long64 PopScanbeam(); long64 PopScanbeam();
void InsertLocalMinimaIntoAEL(const long64 botY); void InsertLocalMinimaIntoAEL(const long64 botY);
void InsertEdgeIntoAEL(TEdge *edge); void InsertEdgeIntoAEL(TEdge *edge);
void AddEdgeToSEL(TEdge *edge); void AddEdgeToSEL(TEdge *edge);
void CopyAELToSEL(); void CopyAELToSEL();
skipping to change at line 272 skipping to change at line 303
OutRec* CreateOutRec(); OutRec* CreateOutRec();
void AddOutPt(TEdge *e, const IntPoint &pt); void AddOutPt(TEdge *e, const IntPoint &pt);
void DisposeAllPolyPts(); void DisposeAllPolyPts();
void DisposeOutRec(PolyOutList::size_type index); void DisposeOutRec(PolyOutList::size_type index);
bool ProcessIntersections(const long64 botY, const long64 topY); bool ProcessIntersections(const long64 botY, const long64 topY);
void AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt); void AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt);
void BuildIntersectList(const long64 botY, const long64 topY); void BuildIntersectList(const long64 botY, const long64 topY);
void ProcessIntersectList(); void ProcessIntersectList();
void ProcessEdgesAtTopOfScanbeam(const long64 topY); void ProcessEdgesAtTopOfScanbeam(const long64 topY);
void BuildResult(Polygons& polys); void BuildResult(Polygons& polys);
void BuildResultEx(ExPolygons& polys); void BuildResult2(PolyTree& polytree);
void SetHoleState(TEdge *e, OutRec *OutRec); void SetHoleState(TEdge *e, OutRec *OutRec);
void DisposeIntersectNodes(); void DisposeIntersectNodes();
bool FixupIntersections(); bool FixupIntersections();
void FixupOutPolygon(OutRec &outRec); void FixupOutPolygon(OutRec &outRec);
bool IsHole(TEdge *e); bool IsHole(TEdge *e);
void FixHoleLinkage(OutRec *outRec); void FixHoleLinkage(OutRec &outRec);
void AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx = -1, int e2OutIdx = -1); void AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx = -1, int e2OutIdx = -1);
void ClearJoins(); void ClearJoins();
void AddHorzJoin(TEdge *e, int idx); void AddHorzJoin(TEdge *e, int idx);
void ClearHorzJoins(); void ClearHorzJoins();
bool JoinPoints(const JoinRec *j, OutPt *&p1, OutPt *&p2); bool JoinPoints(const JoinRec *j, OutPt *&p1, OutPt *&p2);
void FixupJoinRecs(JoinRec *j, OutPt *pt, unsigned startIdx); void FixupJoinRecs(JoinRec *j, OutPt *pt, unsigned startIdx);
void JoinCommonEdges(); void JoinCommonEdges();
void FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec);
void FixupFirstLefts2(OutRec* OldOutRec, OutRec* NewOutRec);
}; };
//------------------------------------------------------------------------- ----- //------------------------------------------------------------------------- -----
//------------------------------------------------------------------------- ----- //------------------------------------------------------------------------- -----
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() {}
 End of changes. 13 change blocks. 
25 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/