/*******************************************************************************

*                                                                              *

* Author    :  Angus Johnson                                                   *

* Version   :  4.6.3                                                           *

* Date      :  11 November 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-28, 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, jtMiter, jtRound };

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);

void ReversePoints(Polygon& p);

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 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(bool fixHoleLinkages);

private:

  PolyOutList       m_PolyOuts;

  JoinList          m_Joins;

  HorzJoinList      m_HorizJoins;

  ClipType          m_ClipType = ctIntersection;

  Scanbeam         *m_Scanbeam;

  TEdge           *m_ActiveEdges;

  TEdge           *m_SortedEdges;

  IntersectNode    *m_IntersectNodes;

  bool              m_ExecuteLocked;

  PolyFillType      m_ClipFillType = pftEvenOdd;

  PolyFillType      m_SubjFillType = pftEvenOdd;

  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 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