/*******************************************************************************
* *
* Author : Angus Johnson *
* Version : 4.10.0 *
* Date : 25 December 2012 *
* Website : http://www.angusj.com *
* Copyright : Angus Johnson 2010-2012 *
* *
* 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 2428, 2005 , Long Beach, California, USA *
* http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf *
* *
*******************************************************************************/
#ifndef clipper_hpp
#define clipper_hpp
#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, jtRound, jtMiter };
bool Orientation(const Polygon &poly);
double Area(const Polygon &poly);
void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys,
double delta, JoinType jointype = jtSquare, double MiterLimit = 2, bool CheckInputs = true);
void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillType fillType = pftEvenOdd);
void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys, PolyFillType fillType = pftEvenOdd);
void SimplifyPolygons(Polygons &polys, PolyFillType fillType = pftEvenOdd);
void ReversePolygon(Polygon& p);
void ReversePolygons(Polygons& p);
//used internally ...
enum EdgeSide { esLeft = 1, esRight = 2};
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 deltaX;
long64 deltaY;
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;
};
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 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 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();
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;
bool m_UsingExPolygons;
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, const IntersectProtects protects);
OutRec* CreateOutRec();
void AddOutPt(TEdge *e, const IntPoint &pt);
void DisposeAllPolyPts();
void DisposeOutRec(PolyOutList::size_type index);
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 AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx = -1, int e2OutIdx = -1);
void ClearJoins();
void AddHorzJoin(TEdge *e, int idx);
void ClearHorzJoins();
bool JoinPoints(const JoinRec *j, OutPt *&p1, OutPt *&p2);
void FixupJoinRecs(JoinRec *j, OutPt *pt, unsigned startIdx);
void JoinCommonEdges();
};
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
class clipperException : public std::exception
{
public:
clipperException(const char* description): m_descr(description) {}
virtual ~clipperException() throw() {}
virtual const char* what() const throw() {return m_descr.c_str();}
private:
std::string m_descr;
};
//------------------------------------------------------------------------------
} //ClipperLib namespace
#endif //clipper_hpp