← Back to branch summary

~ubuntu-branches/ubuntu/trusty/repsnapper/trusty

« back to all changes in this revision

Viewing changes to libraries/clipper/clipper/polyclipping/trunk/cpp/clipper.hpp

  • Committer: Package Import Robot
  • Author(s): Ying-Chun Liu (PaulLiu)
  • Date: 2013-06-24 01:37:09 UTC
  • mfrom: (1.1.1)
  • Revision ID: package-import@ubuntu.com-20130624013709-2ip9tub008d6nhft
Tags: 0+git20130603.7c690471-1
http://bugs.debian.org/709554
http://bugs.debian.org/713244
* New upstream release
* Drop 02_add_desktop_main_category.patch: in upstream already.
* Add Build-Depends to libgtkglextmm-x11-1.2-dev, libpangox-1.0-dev
  (Closes: #709554, #713244)
* Bump Standards-Version to 3.9.4: nothing needs to be changed.

Show diffs side-by-side

added added

removed removed

Lines of Context:
libraries/clipper/clipper/polyclipping/trunk/cpp/clipper.hpp
1
 
/*******************************************************************************
2
 
*                                                                              *
3
 
* Author    :  Angus Johnson                                                   *
4
 
* Version   :  4.8.8                                                           *
5
 
* Date      :  30 August 2012                                                  *
6
 
* Website   :  http://www.angusj.com                                           *
7
 
* Copyright :  Angus Johnson 2010-2012                                         *
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;
60
 
  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, jtRound, jtMiter };
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
 
void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillType fillType = pftEvenOdd);
83
 
void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys, PolyFillType fillType = pftEvenOdd);
84
 
void SimplifyPolygons(Polygons &polys, PolyFillType fillType = pftEvenOdd);
85
 
 
86
 
void ReversePolygon(Polygon& p);
87
 
void ReversePolygons(Polygons& p);
88
 
 
89
 
//used internally ...
90
 
enum EdgeSide { esNeither = 0, esLeft = 1, esRight = 2, esBoth = 3 };
91
 
enum IntersectProtects { ipNone = 0, ipLeft = 1, ipRight = 2, ipBoth = 3 };
92
 
 
93
 
struct TEdge {
94
 
  long64 xbot;
95
 
  long64 ybot;
96
 
  long64 xcurr;
97
 
  long64 ycurr;
98
 
  long64 xtop;
99
 
  long64 ytop;
100
 
  double dx;
101
 
  long64 tmpX;
102
 
  PolyType polyType;
103
 
  EdgeSide side;
104
 
  int windDelta; //1 or -1 depending on winding direction
105
 
  int windCnt;
106
 
  int windCnt2; //winding count of the opposite polytype
107
 
  int outIdx;
108
 
  TEdge *next;
109
 
  TEdge *prev;
110
 
  TEdge *nextInLML;
111
 
  TEdge *nextInAEL;
112
 
  TEdge *prevInAEL;
113
 
  TEdge *nextInSEL;
114
 
  TEdge *prevInSEL;
115
 
};
116
 
 
117
 
struct IntersectNode {
118
 
  TEdge          *edge1;
119
 
  TEdge          *edge2;
120
 
  IntPoint        pt;
121
 
  IntersectNode  *next;
122
 
};
123
 
 
124
 
struct LocalMinima {
125
 
  long64        Y;
126
 
  TEdge        *leftBound;
127
 
  TEdge        *rightBound;
128
 
  LocalMinima  *next;
129
 
};
130
 
 
131
 
struct Scanbeam {
132
 
  long64    Y;
133
 
  Scanbeam *next;
134
 
};
135
 
 
136
 
struct OutPt; //forward declaration
137
 
 
138
 
struct OutRec {
139
 
  int     idx;
140
 
  bool    isHole;
141
 
  OutRec *FirstLeft;
142
 
  OutRec *AppendLink;
143
 
  OutPt  *pts;
144
 
  OutPt  *bottomPt;
145
 
  OutPt  *bottomFlag;
146
 
  EdgeSide sides;
147
 
};
148
 
 
149
 
struct OutPt {
150
 
  int     idx;
151
 
  IntPoint pt;
152
 
  OutPt   *next;
153
 
  OutPt   *prev;
154
 
};
155
 
 
156
 
struct JoinRec {
157
 
  IntPoint  pt1a;
158
 
  IntPoint  pt1b;
159
 
  int       poly1Idx;
160
 
  IntPoint  pt2a;
161
 
  IntPoint  pt2b;
162
 
  int       poly2Idx;
163
 
};
164
 
 
165
 
struct HorzJoinRec {
166
 
  TEdge    *edge;
167
 
  int       savedIdx;
168
 
};
169
 
 
170
 
struct IntRect { long64 left; long64 top; long64 right; long64 bottom; };
171
 
 
172
 
typedef std::vector < OutRec* > PolyOutList;
173
 
typedef std::vector < TEdge* > EdgeList;
174
 
typedef std::vector < JoinRec* > JoinList;
175
 
typedef std::vector < HorzJoinRec* > HorzJoinList;
176
 
 
177
 
//ClipperBase is the ancestor to the Clipper class. It should not be
178
 
//instantiated directly. This class simply abstracts the conversion of sets of
179
 
//polygon coordinates into edge objects that are stored in a LocalMinima list.
180
 
class ClipperBase
181
 
{
182
 
public:
183
 
  ClipperBase();
184
 
  virtual ~ClipperBase();
185
 
  bool AddPolygon(const Polygon &pg, PolyType polyType);
186
 
  bool AddPolygons( const Polygons &ppg, PolyType polyType);
187
 
  virtual void Clear();
188
 
  IntRect GetBounds();
189
 
protected:
190
 
  void DisposeLocalMinimaList();
191
 
  TEdge* AddBoundsToLML(TEdge *e);
192
 
  void PopLocalMinima();
193
 
  virtual void Reset();
194
 
  void InsertLocalMinima(LocalMinima *newLm);
195
 
  LocalMinima      *m_CurrentLM;
196
 
  LocalMinima      *m_MinimaList;
197
 
  bool              m_UseFullRange;
198
 
  EdgeList          m_edges;
199
 
};
200
 
 
201
 
class Clipper : public virtual ClipperBase
202
 
{
203
 
public:
204
 
  Clipper();
205
 
  ~Clipper();
206
 
  bool Execute(ClipType clipType,
207
 
  Polygons &solution,
208
 
  PolyFillType subjFillType = pftEvenOdd,
209
 
  PolyFillType clipFillType = pftEvenOdd);
210
 
  bool Execute(ClipType clipType,
211
 
  ExPolygons &solution,
212
 
  PolyFillType subjFillType = pftEvenOdd,
213
 
  PolyFillType clipFillType = pftEvenOdd);
214
 
  void Clear();
215
 
  bool ReverseSolution() {return m_ReverseOutput;};
216
 
  void ReverseSolution(bool value) {m_ReverseOutput = value;};
217
 
protected:
218
 
  void Reset();
219
 
  virtual bool ExecuteInternal(bool fixHoleLinkages);
220
 
private:
221
 
  PolyOutList       m_PolyOuts;
222
 
  JoinList          m_Joins;
223
 
  HorzJoinList      m_HorizJoins;
224
 
  ClipType          m_ClipType;
225
 
  Scanbeam         *m_Scanbeam;
226
 
  TEdge           *m_ActiveEdges;
227
 
  TEdge           *m_SortedEdges;
228
 
  IntersectNode    *m_IntersectNodes;
229
 
  bool              m_ExecuteLocked;
230
 
  PolyFillType      m_ClipFillType;
231
 
  PolyFillType      m_SubjFillType;
232
 
  bool              m_ReverseOutput;
233
 
  void DisposeScanbeamList();
234
 
  void SetWindingCount(TEdge& edge);
235
 
  bool IsEvenOddFillType(const TEdge& edge) const;
236
 
  bool IsEvenOddAltFillType(const TEdge& edge) const;
237
 
  void InsertScanbeam(const long64 Y);
238
 
  long64 PopScanbeam();
239
 
  void InsertLocalMinimaIntoAEL(const long64 botY);
240
 
  void InsertEdgeIntoAEL(TEdge *edge);
241
 
  void AddEdgeToSEL(TEdge *edge);
242
 
  void CopyAELToSEL();
243
 
  void DeleteFromSEL(TEdge *e);
244
 
  void DeleteFromAEL(TEdge *e);
245
 
  void UpdateEdgeIntoAEL(TEdge *&e);
246
 
  void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2);
247
 
  bool IsContributing(const TEdge& edge) const;
248
 
  bool IsTopHorz(const long64 XPos);
249
 
  void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2);
250
 
  void DoMaxima(TEdge *e, long64 topY);
251
 
  void ProcessHorizontals();
252
 
  void ProcessHorizontal(TEdge *horzEdge);
253
 
  void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
254
 
  void AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
255
 
  void AppendPolygon(TEdge *e1, TEdge *e2);
256
 
  void DoEdge1(TEdge *edge1, TEdge *edge2, const IntPoint &pt);
257
 
  void DoEdge2(TEdge *edge1, TEdge *edge2, const IntPoint &pt);
258
 
  void DoBothEdges(TEdge *edge1, TEdge *edge2, const IntPoint &pt);
259
 
  void IntersectEdges(TEdge *e1, TEdge *e2,
260
 
    const IntPoint &pt, IntersectProtects protects);
261
 
  OutRec* CreateOutRec();
262
 
  void AddOutPt(TEdge *e, const IntPoint &pt);
263
 
  void DisposeBottomPt(OutRec &outRec);
264
 
  void DisposeAllPolyPts();
265
 
  void DisposeOutRec(PolyOutList::size_type index);
266
 
  bool ProcessIntersections(const long64 botY, const long64 topY);
267
 
  void AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt);
268
 
  void BuildIntersectList(const long64 botY, const long64 topY);
269
 
  void ProcessIntersectList();
270
 
  void ProcessEdgesAtTopOfScanbeam(const long64 topY);
271
 
  void BuildResult(Polygons& polys);
272
 
  void BuildResultEx(ExPolygons& polys);
273
 
  void SetHoleState(TEdge *e, OutRec *OutRec);
274
 
  void DisposeIntersectNodes();
275
 
  bool FixupIntersections();
276
 
  void FixupOutPolygon(OutRec &outRec);
277
 
  bool IsHole(TEdge *e);
278
 
  void FixHoleLinkage(OutRec *outRec);
279
 
  void CheckHoleLinkages1(OutRec *outRec1, OutRec *outRec2);
280
 
  void CheckHoleLinkages2(OutRec *outRec1, OutRec *outRec2);
281
 
  void AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx = -1, int e2OutIdx = -1);
282
 
  void ClearJoins();
283
 
  void AddHorzJoin(TEdge *e, int idx);
284
 
  void ClearHorzJoins();
285
 
  void JoinCommonEdges(bool fixHoleLinkages);
286
 
};
287
 
 
288
 
//------------------------------------------------------------------------------
289
 
//------------------------------------------------------------------------------
290
 
 
291
 
class clipperException : public std::exception
292
 
{
293
 
  public:
294
 
    clipperException(const char* description): m_descr(description) {}
295
 
    virtual ~clipperException() throw() {}
296
 
    virtual const char* what() const throw() {return m_descr.c_str();}
297
 
  private:
298
 
    std::string m_descr;
299
 
};
300
 
//------------------------------------------------------------------------------
301
 
 
302
 
} //ClipperLib namespace
303
 
 
304
 
#endif //clipper_hpp
305
 
 
306