1 /******************************************************************************* 2 * * 3 * Author : Angus Johnson * 4 * Version : 4.6.3 * 5 * Date : 11 November 2011 * 6 * Website : http://www.angusj.com * 7 * Copyright : Angus Johnson 2010-2011 * 8 * * 9 * License: * 10 * Use, modification & distribution is subject to Boost Software License Ver 1. * 11 * http://www.boost.org/LICENSE_1_0.txt * 12 * * 13 * Attributions: * 14 * The code in this library is an extension of Bala Vatti's clipping algorithm: * 15 * "A generic solution to polygon clipping" * 16 * Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63. * 17 * http://portal.acm.org/citation.cfm?id=129906 * 18 * * 19 * Computer graphics and geometric modeling: implementation and algorithms * 20 * By Max K. Agoston * 21 * Springer; 1 edition (January 4, 2005) * 22 * http://books.google.com/books?q=vatti+clipping+agoston * 23 * * 24 * See also: * 25 * "Polygon Offsetting by Computing Winding Numbers" * 26 * Paper no. DETC2005-85513 pp. 565-575 * 27 * ASME 2005 International Design Engineering Technical Conferences * 28 * and Computers and Information in Engineering Conference (IDETC/CIE2005) * 29 * September 24-28, 2005 , Long Beach, California, USA * 30 * http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf * 31 * * 32 *******************************************************************************/ 33 34 #ifndef clipper_hpp 35 #define clipper_hpp 36 37 #include <vector> 38 #include <stdexcept> 39 #include <cstring> 40 #include <cstdlib> 41 #include <ostream> 42 43 namespace ClipperLib { 44 45 enum ClipType { ctIntersection, ctUnion, ctDifference, ctXor }; 46 enum PolyType { ptSubject, ptClip }; 47 //By far the most widely used winding rules for polygon filling are 48 //EvenOdd & NonZero (GDI, GDI+, XLib, OpenGL, Cairo, AGG, Quartz, SVG, Gr32) 49 //Others rules include Positive, Negative and ABS_GTR_EQ_TWO (only in OpenGL) 50 //see http://glprogramming.com/red/chapter11.html 51 enum PolyFillType { pftEvenOdd, pftNonZero, pftPositive, pftNegative }; 52 53 typedef signed long long long64; 54 typedef unsigned long long ulong64; 55 56 struct IntPoint { 57 public: 58 long64 X; 59 long64 Y; IntPointClipperLib::IntPoint60 IntPoint(long64 x = 0, long64 y = 0): X(x), Y(y) {}; 61 friend std::ostream& operator <<(std::ostream &s, IntPoint &p); 62 }; 63 64 typedef std::vector< IntPoint > Polygon; 65 typedef std::vector< Polygon > Polygons; 66 67 std::ostream& operator <<(std::ostream &s, Polygon &p); 68 std::ostream& operator <<(std::ostream &s, Polygons &p); 69 70 struct ExPolygon { 71 Polygon outer; 72 Polygons holes; 73 }; 74 typedef std::vector< ExPolygon > ExPolygons; 75 76 enum JoinType { jtSquare, jtMiter, jtRound }; 77 78 bool Orientation(const Polygon &poly); 79 double Area(const Polygon &poly); 80 void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys, 81 double delta, JoinType jointype = jtSquare, double MiterLimit = 2); 82 83 void ReversePoints(Polygon& p); 84 void ReversePoints(Polygons& p); 85 86 //used internally ... 87 enum EdgeSide { esLeft, esRight }; 88 enum IntersectProtects { ipNone = 0, ipLeft = 1, ipRight = 2, ipBoth = 3 }; 89 90 struct TEdge { 91 long64 xbot; 92 long64 ybot; 93 long64 xcurr; 94 long64 ycurr; 95 long64 xtop; 96 long64 ytop; 97 double dx; 98 long64 tmpX; 99 PolyType polyType; 100 EdgeSide side; 101 int windDelta; //1 or -1 depending on winding direction 102 int windCnt; 103 int windCnt2; //winding count of the opposite polytype 104 int outIdx; 105 TEdge *next; 106 TEdge *prev; 107 TEdge *nextInLML; 108 TEdge *nextInAEL; 109 TEdge *prevInAEL; 110 TEdge *nextInSEL; 111 TEdge *prevInSEL; 112 }; 113 114 struct IntersectNode { 115 TEdge *edge1; 116 TEdge *edge2; 117 IntPoint pt; 118 IntersectNode *next; 119 }; 120 121 struct LocalMinima { 122 long64 Y; 123 TEdge *leftBound; 124 TEdge *rightBound; 125 LocalMinima *next; 126 }; 127 128 struct Scanbeam { 129 long64 Y; 130 Scanbeam *next; 131 }; 132 133 struct OutPt; //forward declaration 134 135 struct OutRec { 136 int idx; 137 bool isHole; 138 OutRec *FirstLeft; 139 OutRec *AppendLink; 140 OutPt *pts; 141 OutPt *bottomPt; 142 TEdge *bottomE1; 143 TEdge *bottomE2; 144 }; 145 146 struct OutPt { 147 int idx; 148 IntPoint pt; 149 OutPt *next; 150 OutPt *prev; 151 }; 152 153 struct JoinRec { 154 IntPoint pt1a; 155 IntPoint pt1b; 156 int poly1Idx; 157 IntPoint pt2a; 158 IntPoint pt2b; 159 int poly2Idx; 160 }; 161 162 struct HorzJoinRec { 163 TEdge *edge; 164 int savedIdx; 165 }; 166 167 struct IntRect { long64 left; long64 top; long64 right; long64 bottom; }; 168 169 typedef std::vector < OutRec* > PolyOutList; 170 typedef std::vector < TEdge* > EdgeList; 171 typedef std::vector < JoinRec* > JoinList; 172 typedef std::vector < HorzJoinRec* > HorzJoinList; 173 174 //ClipperBase is the ancestor to the Clipper class. It should not be 175 //instantiated directly. This class simply abstracts the conversion of sets of 176 //polygon coordinates into edge objects that are stored in a LocalMinima list. 177 class ClipperBase 178 { 179 public: 180 ClipperBase(); 181 virtual ~ClipperBase(); 182 bool AddPolygon(const Polygon &pg, PolyType polyType); 183 bool AddPolygons( const Polygons &ppg, PolyType polyType); 184 virtual void Clear(); 185 IntRect GetBounds(); 186 protected: 187 void DisposeLocalMinimaList(); 188 TEdge* AddBoundsToLML(TEdge *e); 189 void PopLocalMinima(); 190 virtual void Reset(); 191 void InsertLocalMinima(LocalMinima *newLm); 192 LocalMinima *m_CurrentLM; 193 LocalMinima *m_MinimaList; 194 bool m_UseFullRange; 195 EdgeList m_edges; 196 }; 197 198 class Clipper : public virtual ClipperBase 199 { 200 public: 201 Clipper(); 202 ~Clipper(); 203 bool Execute(ClipType clipType, 204 Polygons &solution, 205 PolyFillType subjFillType = pftEvenOdd, 206 PolyFillType clipFillType = pftEvenOdd); 207 bool Execute(ClipType clipType, 208 ExPolygons &solution, 209 PolyFillType subjFillType = pftEvenOdd, 210 PolyFillType clipFillType = pftEvenOdd); 211 void Clear(); ReverseSolution()212 bool ReverseSolution() {return m_ReverseOutput;}; ReverseSolution(bool value)213 void ReverseSolution(bool value) {m_ReverseOutput = value;}; 214 protected: 215 void Reset(); 216 virtual bool ExecuteInternal(bool fixHoleLinkages); 217 private: 218 PolyOutList m_PolyOuts; 219 JoinList m_Joins; 220 HorzJoinList m_HorizJoins; 221 ClipType m_ClipType; 222 Scanbeam *m_Scanbeam; 223 TEdge *m_ActiveEdges; 224 TEdge *m_SortedEdges; 225 IntersectNode *m_IntersectNodes; 226 bool m_ExecuteLocked; 227 PolyFillType m_ClipFillType; 228 PolyFillType m_SubjFillType; 229 bool m_ReverseOutput; 230 void DisposeScanbeamList(); 231 void SetWindingCount(TEdge& edge); 232 bool IsEvenOddFillType(const TEdge& edge) const; 233 bool IsEvenOddAltFillType(const TEdge& edge) const; 234 void InsertScanbeam(const long64 Y); 235 long64 PopScanbeam(); 236 void InsertLocalMinimaIntoAEL(const long64 botY); 237 void InsertEdgeIntoAEL(TEdge *edge); 238 void AddEdgeToSEL(TEdge *edge); 239 void CopyAELToSEL(); 240 void DeleteFromSEL(TEdge *e); 241 void DeleteFromAEL(TEdge *e); 242 void UpdateEdgeIntoAEL(TEdge *&e); 243 void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2); 244 bool IsContributing(const TEdge& edge) const; 245 bool IsTopHorz(const long64 XPos); 246 void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2); 247 void DoMaxima(TEdge *e, long64 topY); 248 void ProcessHorizontals(); 249 void ProcessHorizontal(TEdge *horzEdge); 250 void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); 251 void AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); 252 void AppendPolygon(TEdge *e1, TEdge *e2); 253 void DoEdge1(TEdge *edge1, TEdge *edge2, const IntPoint &pt); 254 void DoEdge2(TEdge *edge1, TEdge *edge2, const IntPoint &pt); 255 void DoBothEdges(TEdge *edge1, TEdge *edge2, const IntPoint &pt); 256 void IntersectEdges(TEdge *e1, TEdge *e2, 257 const IntPoint &pt, IntersectProtects protects); 258 OutRec* CreateOutRec(); 259 void AddOutPt(TEdge *e, TEdge *altE, const IntPoint &pt); 260 void DisposeAllPolyPts(); 261 void DisposeOutRec(PolyOutList::size_type index, bool ignorePts = false); 262 bool ProcessIntersections(const long64 botY, const long64 topY); 263 void AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt); 264 void BuildIntersectList(const long64 botY, const long64 topY); 265 void ProcessIntersectList(); 266 void ProcessEdgesAtTopOfScanbeam(const long64 topY); 267 void BuildResult(Polygons& polys); 268 void BuildResultEx(ExPolygons& polys); 269 void SetHoleState(TEdge *e, OutRec *OutRec); 270 void DisposeIntersectNodes(); 271 bool FixupIntersections(); 272 void FixupOutPolygon(OutRec &outRec); 273 bool IsHole(TEdge *e); 274 void FixHoleLinkage(OutRec *outRec); 275 void CheckHoleLinkages1(OutRec *outRec1, OutRec *outRec2); 276 void CheckHoleLinkages2(OutRec *outRec1, OutRec *outRec2); 277 void AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx = -1, int e2OutIdx = -1); 278 void ClearJoins(); 279 void AddHorzJoin(TEdge *e, int idx); 280 void ClearHorzJoins(); 281 void JoinCommonEdges(bool fixHoleLinkages); 282 }; 283 284 //------------------------------------------------------------------------------ 285 //------------------------------------------------------------------------------ 286 287 class clipperException : public std::exception 288 { 289 public: clipperException(const char * description)290 clipperException(const char* description): m_descr(description) {} ~clipperException()291 virtual ~clipperException() throw() {} what() const292 virtual const char* what() const throw() {return m_descr.c_str();} 293 private: 294 std::string m_descr; 295 }; 296 //------------------------------------------------------------------------------ 297 298 } //ClipperLib namespace 299 300 #endif //clipper_hpp 301 302 303