37 #define CLIPPER_VERSION "6.2.6"
62 namespace ClipperLib {
64 enum ClipType { ctIntersection, ctUnion, ctDifference, ctXor };
65 enum PolyType { ptSubject, ptClip };
70 enum PolyFillType { pftEvenOdd, pftNonZero, pftPositive, pftNegative };
74 static cInt
const loRange = 0x7FFF;
75 static cInt
const hiRange = 0x7FFF;
77 typedef signed long long cInt;
78 static cInt
const loRange = 0x3FFFFFFF;
79 static cInt
const hiRange = 0x3FFFFFFFFFFFFFFFLL;
80 typedef signed long long long64;
81 typedef unsigned long long ulong64;
90 IntPoint(cInt x = 0, cInt y = 0, cInt z = 0): X(x), Y(y), Z(z) {};
92 IntPoint(cInt x = 0, cInt y = 0): X(x), Y(y) {};
95 friend inline bool operator== (
const IntPoint& a,
const IntPoint& b)
97 return a.X == b.X && a.Y == b.Y;
99 friend inline bool operator!= (
const IntPoint& a,
const IntPoint& b)
101 return a.X != b.X || a.Y != b.Y;
106 typedef std::vector< IntPoint > Path;
107 typedef std::vector< Path > Paths;
109 inline Path& operator <<(Path& poly,
const IntPoint& p) {poly.push_back(p);
return poly;}
110 inline Paths& operator <<(Paths& polys,
const Path& p) {polys.push_back(p);
return polys;}
112 std::ostream& operator <<(std::ostream &s,
const IntPoint &p);
113 std::ostream& operator <<(std::ostream &s,
const Path &p);
114 std::ostream& operator <<(std::ostream &s,
const Paths &p);
120 DoublePoint(
double x = 0,
double y = 0) : X(x), Y(y) {}
121 DoublePoint(IntPoint ip) : X((double)ip.X), Y((double)ip.Y) {}
126 typedef void (*ZFillCallback)(IntPoint& e1bot, IntPoint& e1top, IntPoint& e2bot, IntPoint& e2top, IntPoint& pt);
129 enum InitOptions {ioReverseSolution = 1, ioStrictlySimple = 2, ioPreserveCollinear = 4};
130 enum JoinType {jtSquare, jtRound, jtMiter};
131 enum EndType {etClosedPolygon, etClosedLine, etOpenButt, etOpenSquare, etOpenRound};
134 typedef std::vector< PolyNode* > PolyNodes;
140 virtual ~PolyNode(){};
144 PolyNode* GetNext()
const;
147 int ChildCount()
const;
153 PolyNode* GetNextSiblingUp()
const;
154 void AddChild(PolyNode& child);
155 friend class Clipper;
156 friend class ClipperOffset;
159 class PolyTree:
public PolyNode
162 ~PolyTree(){Clear();};
163 PolyNode* GetFirst()
const;
168 friend class Clipper;
171 bool Orientation(
const Path &poly);
172 double Area(
const Path &poly);
173 int PointInPolygon(
const IntPoint &pt,
const Path &path);
175 void SimplifyPolygon(
const Path &in_poly, Paths &out_polys, PolyFillType fillType = pftEvenOdd);
176 void SimplifyPolygons(
const Paths &in_polys, Paths &out_polys, PolyFillType fillType = pftEvenOdd);
177 void SimplifyPolygons(Paths &polys, PolyFillType fillType = pftEvenOdd);
179 void CleanPolygon(
const Path& in_poly, Path& out_poly,
double distance = 1.415);
180 void CleanPolygon(Path& poly,
double distance = 1.415);
181 void CleanPolygons(
const Paths& in_polys, Paths& out_polys,
double distance = 1.415);
182 void CleanPolygons(Paths& polys,
double distance = 1.415);
184 void MinkowskiSum(
const Path& pattern,
const Path& path, Paths& solution,
bool pathIsClosed);
185 void MinkowskiSum(
const Path& pattern,
const Paths& paths, Paths& solution,
bool pathIsClosed);
186 void MinkowskiDiff(
const Path& poly1,
const Path& poly2, Paths& solution);
188 void PolyTreeToPaths(
const PolyTree& polytree, Paths& paths);
189 void ClosedPathsFromPolyTree(
const PolyTree& polytree, Paths& paths);
190 void OpenPathsFromPolyTree(PolyTree& polytree, Paths& paths);
192 void ReversePath(Path& p);
193 void ReversePaths(Paths& p);
195 struct IntRect { cInt left; cInt top; cInt right; cInt bottom; };
198 enum EdgeSide { esLeft = 1, esRight = 2};
202 struct IntersectNode;
208 typedef std::vector < OutRec* > PolyOutList;
209 typedef std::vector < TEdge* > EdgeList;
210 typedef std::vector < Join* > JoinList;
211 typedef std::vector < IntersectNode* > IntersectList;
222 virtual ~ClipperBase();
223 virtual bool AddPath(
const Path &pg, PolyType PolyTyp,
bool Closed);
224 bool AddPaths(
const Paths &ppg, PolyType PolyTyp,
bool Closed);
225 virtual void Clear();
227 bool PreserveCollinear() {
return m_PreserveCollinear;};
228 void PreserveCollinear(
bool value) {m_PreserveCollinear = value;};
230 void DisposeLocalMinimaList();
231 TEdge* AddBoundsToLML(TEdge *e,
bool IsClosed);
232 virtual void Reset();
233 TEdge* ProcessBound(TEdge* E,
bool IsClockwise);
234 void InsertScanbeam(
const cInt Y);
235 bool PopScanbeam(cInt &Y);
236 bool LocalMinimaPending();
237 bool PopLocalMinima(cInt Y,
const LocalMinimum *&locMin);
238 OutRec* CreateOutRec();
239 void DisposeAllOutRecs();
240 void DisposeOutRec(PolyOutList::size_type index);
241 void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2);
242 void DeleteFromAEL(TEdge *e);
243 void UpdateEdgeIntoAEL(TEdge *&e);
245 typedef std::vector<LocalMinimum> MinimaList;
246 MinimaList::iterator m_CurrentLM;
247 MinimaList m_MinimaList;
251 bool m_PreserveCollinear;
253 PolyOutList m_PolyOuts;
254 TEdge *m_ActiveEdges;
256 typedef std::priority_queue<cInt> ScanbeamList;
257 ScanbeamList m_Scanbeam;
261 class Clipper :
public virtual ClipperBase
264 Clipper(
int initOptions = 0);
265 bool Execute(ClipType clipType,
267 PolyFillType fillType = pftEvenOdd);
268 bool Execute(ClipType clipType,
270 PolyFillType subjFillType,
271 PolyFillType clipFillType);
272 bool Execute(ClipType clipType,
274 PolyFillType fillType = pftEvenOdd);
275 bool Execute(ClipType clipType,
277 PolyFillType subjFillType,
278 PolyFillType clipFillType);
279 bool ReverseSolution() {
return m_ReverseOutput; };
280 void ReverseSolution(
bool value) {m_ReverseOutput = value;};
281 bool StrictlySimple() {
return m_StrictSimple;};
282 void StrictlySimple(
bool value) {m_StrictSimple = value;};
285 void ZFillFunction(ZFillCallback zFillFunc);
288 virtual bool ExecuteInternal();
291 JoinList m_GhostJoins;
292 IntersectList m_IntersectList;
294 typedef std::list<cInt> MaximaList;
296 TEdge *m_SortedEdges;
297 bool m_ExecuteLocked;
298 PolyFillType m_ClipFillType;
299 PolyFillType m_SubjFillType;
300 bool m_ReverseOutput;
301 bool m_UsingPolyTree;
304 ZFillCallback m_ZFill;
306 void SetWindingCount(TEdge& edge);
307 bool IsEvenOddFillType(
const TEdge& edge)
const;
308 bool IsEvenOddAltFillType(
const TEdge& edge)
const;
309 void InsertLocalMinimaIntoAEL(
const cInt botY);
310 void InsertEdgeIntoAEL(TEdge *edge, TEdge* startEdge);
311 void AddEdgeToSEL(TEdge *edge);
312 bool PopEdgeFromSEL(TEdge *&edge);
314 void DeleteFromSEL(TEdge *e);
315 void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2);
316 bool IsContributing(
const TEdge& edge)
const;
317 bool IsTopHorz(
const cInt XPos);
318 void DoMaxima(TEdge *e);
319 void ProcessHorizontals();
320 void ProcessHorizontal(TEdge *horzEdge);
321 void AddLocalMaxPoly(TEdge *e1, TEdge *e2,
const IntPoint &pt);
322 OutPt* AddLocalMinPoly(TEdge *e1, TEdge *e2,
const IntPoint &pt);
323 OutRec* GetOutRec(
int idx);
324 void AppendPolygon(TEdge *e1, TEdge *e2);
325 void IntersectEdges(TEdge *e1, TEdge *e2, IntPoint &pt);
326 OutPt* AddOutPt(TEdge *e,
const IntPoint &pt);
327 OutPt* GetLastOutPt(TEdge *e);
328 bool ProcessIntersections(
const cInt topY);
329 void BuildIntersectList(
const cInt topY);
330 void ProcessIntersectList();
331 void ProcessEdgesAtTopOfScanbeam(
const cInt topY);
332 void BuildResult(Paths& polys);
333 void BuildResult2(PolyTree& polytree);
334 void SetHoleState(TEdge *e, OutRec *outrec);
335 void DisposeIntersectNodes();
336 bool FixupIntersectionOrder();
337 void FixupOutPolygon(OutRec &outrec);
338 void FixupOutPolyline(OutRec &outrec);
339 bool IsHole(TEdge *e);
340 bool FindOwnerFromSplitRecs(OutRec &outRec, OutRec *&currOrfl);
341 void FixHoleLinkage(OutRec &outrec);
342 void AddJoin(OutPt *op1, OutPt *op2,
const IntPoint offPt);
344 void ClearGhostJoins();
345 void AddGhostJoin(OutPt *op,
const IntPoint offPt);
346 bool JoinPoints(Join *j, OutRec* outRec1, OutRec* outRec2);
347 void JoinCommonEdges();
348 void DoSimplePolygons();
349 void FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec);
350 void FixupFirstLefts2(OutRec* InnerOutRec, OutRec* OuterOutRec);
351 void FixupFirstLefts3(OutRec* OldOutRec, OutRec* NewOutRec);
353 void SetZ(IntPoint& pt, TEdge& e1, TEdge& e2);
361 ClipperOffset(
double miterLimit = 2.0,
double roundPrecision = 0.25);
363 void AddPath(
const Path& path, JoinType joinType, EndType endType);
364 void AddPaths(
const Paths& paths, JoinType joinType, EndType endType);
365 void Execute(Paths& solution,
double delta);
366 void Execute(PolyTree& solution,
double delta);
374 std::vector<DoublePoint> m_normals;
375 double m_delta, m_sinA, m_sin, m_cos;
376 double m_miterLim, m_StepsPerRad;
378 PolyNode m_polyNodes;
380 void FixOrientations();
381 void DoOffset(
double delta);
382 void OffsetPoint(
int j,
int& k, JoinType jointype);
383 void DoSquare(
int j,
int k);
384 void DoMiter(
int j,
int k,
double r);
385 void DoRound(
int j,
int k);
389 class clipperException :
public std::exception
392 clipperException(
const char* description): m_descr(description) {}
393 virtual ~clipperException() throw() {}
394 virtual const char* what()
const throw() {
return m_descr.c_str();}