00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
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
00048
00049
00050
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
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;
00106 int windCnt;
00107 int windCnt2;
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;
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
00179
00180
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 }
00304
00305 #endif //clipper_hpp
00306
00307