clipper.hpp
Go to the documentation of this file.
00001 /*******************************************************************************
00002 *                                                                              *
00003 * Author    :  Angus Johnson                                                   *
00004 * Version   :  4.8.8                                                           *
00005 * Date      :  30 August 2012                                                  *
00006 * Website   :  http://www.angusj.com                                           *
00007 * Copyright :  Angus Johnson 2010-2012                                         *
00008 *                                                                              *
00009 * License:                                                                     *
00010 * Use, modification & distribution is subject to Boost Software License Ver 1. *
00011 * http://www.boost.org/LICENSE_1_0.txt                                         *
00012 *                                                                              *
00013 * Attributions:                                                                *
00014 * The code in this library is an extension of Bala Vatti's clipping algorithm: *
00015 * "A generic solution to polygon clipping"                                     *
00016 * Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63.             *
00017 * http://portal.acm.org/citation.cfm?id=129906                                 *
00018 *                                                                              *
00019 * Computer graphics and geometric modeling: implementation and algorithms      *
00020 * By Max K. Agoston                                                            *
00021 * Springer; 1 edition (January 4, 2005)                                        *
00022 * http://books.google.com/books?q=vatti+clipping+agoston                       *
00023 *                                                                              *
00024 * See also:                                                                    *
00025 * "Polygon Offsetting by Computing Winding Numbers"                            *
00026 * Paper no. DETC2005-85513 pp. 565-575                                         *
00027 * ASME 2005 International Design Engineering Technical Conferences             *
00028 * and Computers and Information in Engineering Conference (IDETC/CIE2005)      *
00029 * September 24�28, 2005 , Long Beach, California, USA                          *
00030 * http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf              *
00031 *                                                                              *
00032 *******************************************************************************/
00033 
00034 #ifndef clipper_hpp
00035 #define clipper_hpp
00036 
00037 #include <vector>
00038 #include <stdexcept>
00039 #include <cstring>
00040 #include <cstdlib>
00041 #include <ostream>
00042 
00043 namespace ClipperLib {
00044 
00045 enum ClipType { ctIntersection, ctUnion, ctDifference, ctXor };
00046 enum PolyType { ptSubject, ptClip };
00047 //By far the most widely used winding rules for polygon filling are
00048 //EvenOdd & NonZero (GDI, GDI+, XLib, OpenGL, Cairo, AGG, Quartz, SVG, Gr32)
00049 //Others rules include Positive, Negative and ABS_GTR_EQ_TWO (only in OpenGL)
00050 //see http://glprogramming.com/red/chapter11.html
00051 enum PolyFillType { pftEvenOdd, pftNonZero, pftPositive, pftNegative };
00052 
00053 typedef signed long long long64;
00054 typedef unsigned long long ulong64;
00055 
00056 struct IntPoint {
00057 public:
00058   long64 X;
00059   long64 Y;
00060   int ID;
00061   IntPoint(long64 x = 0, long64 y = 0): X(x), Y(y), ID(0) {};
00062   friend std::ostream& operator <<(std::ostream &s, IntPoint &p);
00063 };
00064 
00065 typedef std::vector< IntPoint > Polygon;
00066 typedef std::vector< Polygon > Polygons;
00067 
00068 std::ostream& operator <<(std::ostream &s, Polygon &p);
00069 std::ostream& operator <<(std::ostream &s, Polygons &p);
00070 
00071 struct ExPolygon {
00072   Polygon  outer;
00073   Polygons holes;
00074 };
00075 typedef std::vector< ExPolygon > ExPolygons;
00076 
00077 enum JoinType { jtSquare, jtRound, jtMiter };
00078 
00079 bool Orientation(const Polygon &poly);
00080 double Area(const Polygon &poly);
00081 void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys,
00082   double delta, JoinType jointype = jtSquare, double MiterLimit = 2);
00083 void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillType fillType = pftEvenOdd);
00084 void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys, PolyFillType fillType = pftEvenOdd);
00085 void SimplifyPolygons(Polygons &polys, PolyFillType fillType = pftEvenOdd);
00086 
00087 void ReversePolygon(Polygon& p);
00088 void ReversePolygons(Polygons& p);
00089 
00090 //used internally ...
00091 enum EdgeSide { esNeither = 0, esLeft = 1, esRight = 2, esBoth = 3 };
00092 enum IntersectProtects { ipNone = 0, ipLeft = 1, ipRight = 2, ipBoth = 3 };
00093 
00094 struct TEdge {
00095   long64 xbot;
00096   long64 ybot;
00097   long64 xcurr;
00098   long64 ycurr;
00099   long64 xtop;
00100   long64 ytop;
00101   double dx;
00102   long64 tmpX;
00103   PolyType polyType;
00104   EdgeSide side;
00105   int windDelta; //1 or -1 depending on winding direction
00106   int windCnt;
00107   int windCnt2; //winding count of the opposite polytype
00108   int outIdx;
00109   TEdge *next;
00110   TEdge *prev;
00111   TEdge *nextInLML;
00112   TEdge *nextInAEL;
00113   TEdge *prevInAEL;
00114   TEdge *nextInSEL;
00115   TEdge *prevInSEL;
00116 };
00117 
00118 struct IntersectNode {
00119   TEdge          *edge1;
00120   TEdge          *edge2;
00121   IntPoint        pt;
00122   IntersectNode  *next;
00123 };
00124 
00125 struct LocalMinima {
00126   long64        Y;
00127   TEdge        *leftBound;
00128   TEdge        *rightBound;
00129   LocalMinima  *next;
00130 };
00131 
00132 struct Scanbeam {
00133   long64    Y;
00134   Scanbeam *next;
00135 };
00136 
00137 struct OutPt; //forward declaration
00138 
00139 struct OutRec {
00140   int     idx;
00141   bool    isHole;
00142   OutRec *FirstLeft;
00143   OutRec *AppendLink;
00144   OutPt  *pts;
00145   OutPt  *bottomPt;
00146   OutPt  *bottomFlag;
00147   EdgeSide sides;
00148 };
00149 
00150 struct OutPt {
00151   int     idx;
00152   IntPoint pt;
00153   OutPt   *next;
00154   OutPt   *prev;
00155 };
00156 
00157 struct JoinRec {
00158   IntPoint  pt1a;
00159   IntPoint  pt1b;
00160   int       poly1Idx;
00161   IntPoint  pt2a;
00162   IntPoint  pt2b;
00163   int       poly2Idx;
00164 };
00165 
00166 struct HorzJoinRec {
00167   TEdge    *edge;
00168   int       savedIdx;
00169 };
00170 
00171 struct IntRect { long64 left; long64 top; long64 right; long64 bottom; };
00172 
00173 typedef std::vector < OutRec* > PolyOutList;
00174 typedef std::vector < TEdge* > EdgeList;
00175 typedef std::vector < JoinRec* > JoinList;
00176 typedef std::vector < HorzJoinRec* > HorzJoinList;
00177 
00178 //ClipperBase is the ancestor to the Clipper class. It should not be
00179 //instantiated directly. This class simply abstracts the conversion of sets of
00180 //polygon coordinates into edge objects that are stored in a LocalMinima list.
00181 class ClipperBase
00182 {
00183 public:
00184   ClipperBase();
00185   virtual ~ClipperBase();
00186   bool AddPolygon(const Polygon &pg, PolyType polyType);
00187   bool AddPolygons( const Polygons &ppg, PolyType polyType);
00188   virtual void Clear();
00189   IntRect GetBounds();
00190 protected:
00191   void DisposeLocalMinimaList();
00192   TEdge* AddBoundsToLML(TEdge *e);
00193   void PopLocalMinima();
00194   virtual void Reset();
00195   void InsertLocalMinima(LocalMinima *newLm);
00196   LocalMinima      *m_CurrentLM;
00197   LocalMinima      *m_MinimaList;
00198   bool              m_UseFullRange;
00199   EdgeList          m_edges;
00200 };
00201 
00202 class Clipper : public virtual ClipperBase
00203 {
00204 public:
00205   Clipper();
00206   ~Clipper();
00207   bool Execute(ClipType clipType,
00208   Polygons &solution,
00209   PolyFillType subjFillType = pftEvenOdd,
00210   PolyFillType clipFillType = pftEvenOdd);
00211   bool Execute(ClipType clipType,
00212   ExPolygons &solution,
00213   PolyFillType subjFillType = pftEvenOdd,
00214   PolyFillType clipFillType = pftEvenOdd);
00215   void Clear();
00216   bool ReverseSolution() {return m_ReverseOutput;};
00217   void ReverseSolution(bool value) {m_ReverseOutput = value;};
00218 protected:
00219   void Reset();
00220   virtual bool ExecuteInternal(bool fixHoleLinkages);
00221 private:
00222   PolyOutList       m_PolyOuts;
00223   JoinList          m_Joins;
00224   HorzJoinList      m_HorizJoins;
00225   ClipType          m_ClipType;
00226   Scanbeam         *m_Scanbeam;
00227   TEdge           *m_ActiveEdges;
00228   TEdge           *m_SortedEdges;
00229   IntersectNode    *m_IntersectNodes;
00230   bool              m_ExecuteLocked;
00231   PolyFillType      m_ClipFillType;
00232   PolyFillType      m_SubjFillType;
00233   bool              m_ReverseOutput;
00234   void DisposeScanbeamList();
00235   void SetWindingCount(TEdge& edge);
00236   bool IsEvenOddFillType(const TEdge& edge) const;
00237   bool IsEvenOddAltFillType(const TEdge& edge) const;
00238   void InsertScanbeam(const long64 Y);
00239   long64 PopScanbeam();
00240   void InsertLocalMinimaIntoAEL(const long64 botY);
00241   void InsertEdgeIntoAEL(TEdge *edge);
00242   void AddEdgeToSEL(TEdge *edge);
00243   void CopyAELToSEL();
00244   void DeleteFromSEL(TEdge *e);
00245   void DeleteFromAEL(TEdge *e);
00246   void UpdateEdgeIntoAEL(TEdge *&e);
00247   void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2);
00248   bool IsContributing(const TEdge& edge) const;
00249   bool IsTopHorz(const long64 XPos);
00250   void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2);
00251   void DoMaxima(TEdge *e, long64 topY);
00252   void ProcessHorizontals();
00253   void ProcessHorizontal(TEdge *horzEdge);
00254   void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
00255   void AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
00256   void AppendPolygon(TEdge *e1, TEdge *e2);
00257   void DoEdge1(TEdge *edge1, TEdge *edge2, const IntPoint &pt);
00258   void DoEdge2(TEdge *edge1, TEdge *edge2, const IntPoint &pt);
00259   void DoBothEdges(TEdge *edge1, TEdge *edge2, const IntPoint &pt);
00260   void IntersectEdges(TEdge *e1, TEdge *e2,
00261     const IntPoint &pt, IntersectProtects protects);
00262   OutRec* CreateOutRec();
00263   void AddOutPt(TEdge *e, const IntPoint &pt);
00264   void DisposeBottomPt(OutRec &outRec);
00265   void DisposeAllPolyPts();
00266   void DisposeOutRec(PolyOutList::size_type index);
00267   bool ProcessIntersections(const long64 botY, const long64 topY);
00268   void AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt);
00269   void BuildIntersectList(const long64 botY, const long64 topY);
00270   void ProcessIntersectList();
00271   void ProcessEdgesAtTopOfScanbeam(const long64 topY);
00272   void BuildResult(Polygons& polys);
00273   void BuildResultEx(ExPolygons& polys);
00274   void SetHoleState(TEdge *e, OutRec *OutRec);
00275   void DisposeIntersectNodes();
00276   bool FixupIntersections();
00277   void FixupOutPolygon(OutRec &outRec);
00278   bool IsHole(TEdge *e);
00279   void FixHoleLinkage(OutRec *outRec);
00280   void CheckHoleLinkages1(OutRec *outRec1, OutRec *outRec2);
00281   void CheckHoleLinkages2(OutRec *outRec1, OutRec *outRec2);
00282   void AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx = -1, int e2OutIdx = -1);
00283   void ClearJoins();
00284   void AddHorzJoin(TEdge *e, int idx);
00285   void ClearHorzJoins();
00286   void JoinCommonEdges(bool fixHoleLinkages);
00287 };
00288 
00289 //------------------------------------------------------------------------------
00290 //------------------------------------------------------------------------------
00291 
00292 class clipperException : public std::exception
00293 {
00294   public:
00295     clipperException(const char* description): m_descr(description) {}
00296     virtual ~clipperException() throw() {}
00297     virtual const char* what() const throw() {return m_descr.c_str();}
00298   private:
00299     std::string m_descr;
00300 };
00301 //------------------------------------------------------------------------------
00302 
00303 } //ClipperLib namespace
00304 
00305 #endif //clipper_hpp
00306 
00307 


srs_env_model_percp
Author(s): Rostislav Hulik (ihulik@fit.vutbr.cz), Tomas Hodan, Michal Spanel (spanel@fit.vutbr.cz)
autogenerated on Sun Jan 5 2014 11:51:56