Anti-Grain Geometry Tutorial
agg_conv_gpc.h
1 //----------------------------------------------------------------------------
2 // Anti-Grain Geometry - Version 2.4
3 // Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com)
4 //
5 // Permission to copy, use, modify, sell and distribute this software
6 // is granted provided this copyright notice appears in all copies.
7 // This software is provided "as is" without express or implied
8 // warranty, and with no claim as to its suitability for any purpose.
9 //
10 //----------------------------------------------------------------------------
11 // Contact: mcseem@antigrain.com
12 // mcseemagg@yahoo.com
13 // http://www.antigrain.com
14 //----------------------------------------------------------------------------
15 //
16 // General Polygon Clipper based on the GPC library by Alan Murta
17 // Union, Intersection, XOR, A-B, B-A
18 // Contact the author if you intend to use it in commercial applications!
19 // http://www.cs.man.ac.uk/aig/staff/alan/software/
20 // Alan Murta (email: gpc@cs.man.ac.uk)
21 //
22 //----------------------------------------------------------------------------
23 
24 #ifndef AGG_CONV_GPC_INCLUDED
25 #define AGG_CONV_GPC_INCLUDED
26 
27 #include <cstring>
28 #include "agg_basics.h"
29 #include "agg_array.h"
30 
31 extern "C"
32 {
33 #include "gpc.h"
34 }
35 
36 namespace agg
37 {
38  enum gpc_op_e
39  {
40  gpc_or,
41  gpc_and,
42  gpc_xor,
43  gpc_a_minus_b,
44  gpc_b_minus_a
45  };
46 
47 
48  //================================================================conv_gpc
49  template<class VSA, class VSB> class conv_gpc
50  {
51  enum status
52  {
53  status_move_to,
54  status_line_to,
55  status_stop
56  };
57 
58  struct contour_header_type
59  {
60  int num_vertices;
61  int hole_flag;
62  gpc_vertex* vertices;
63  };
64 
67 
68 
69  public:
70  typedef VSA source_a_type;
71  typedef VSB source_b_type;
73 
74  ~conv_gpc()
75  {
76  free_gpc_data();
77  }
78 
79  conv_gpc(source_a_type& a, source_b_type& b, gpc_op_e op = gpc_or) :
80  m_src_a(&a),
81  m_src_b(&b),
82  m_status(status_move_to),
83  m_vertex(-1),
84  m_contour(-1),
85  m_operation(op)
86  {
87  std::memset(&m_poly_a, 0, sizeof(m_poly_a));
88  std::memset(&m_poly_b, 0, sizeof(m_poly_b));
89  std::memset(&m_result, 0, sizeof(m_result));
90  }
91 
92  void attach1(VSA& source) { m_src_a = &source; }
93  void attach2(VSB& source) { m_src_b = &source; }
94 
95  void operation(gpc_op_e v) { m_operation = v; }
96 
97  // Vertex Source Interface
98  void rewind(unsigned path_id);
99  unsigned vertex(double* x, double* y);
100 
101  private:
103  const conv_gpc<VSA, VSB>& operator = (const conv_gpc<VSA, VSB>&);
104 
105  //--------------------------------------------------------------------
106  void free_polygon(gpc_polygon& p);
107  void free_result();
108  void free_gpc_data();
109  void start_contour();
110  void add_vertex(double x, double y);
111  void end_contour(unsigned orientation);
112  void make_polygon(gpc_polygon& p);
113  void start_extracting();
114  bool next_contour();
115  bool next_vertex(double* x, double* y);
116 
117 
118  //--------------------------------------------------------------------
119  template<class VS> void add(VS& src, gpc_polygon& p)
120  {
121  unsigned cmd;
122  double x, y;
123  double start_x = 0.0;
124  double start_y = 0.0;
125  bool line_to = false;
126  unsigned orientation = 0;
127 
128  m_contour_accumulator.remove_all();
129 
130  while(!is_stop(cmd = src.vertex(&x, &y)))
131  {
132  if(is_vertex(cmd))
133  {
134  if(is_move_to(cmd))
135  {
136  if(line_to)
137  {
138  end_contour(orientation);
139  orientation = 0;
140  }
141  start_contour();
142  start_x = x;
143  start_y = y;
144  }
145  add_vertex(x, y);
146  line_to = true;
147  }
148  else
149  {
150  if(is_end_poly(cmd))
151  {
152  orientation = get_orientation(cmd);
153  if(line_to && is_closed(cmd))
154  {
155  add_vertex(start_x, start_y);
156  }
157  }
158  }
159  }
160  if(line_to)
161  {
162  end_contour(orientation);
163  }
164  make_polygon(p);
165  }
166 
167 
168  private:
169  //--------------------------------------------------------------------
170  source_a_type* m_src_a;
171  source_b_type* m_src_b;
172  status m_status;
173  int m_vertex;
174  int m_contour;
175  gpc_op_e m_operation;
176  vertex_array_type m_vertex_accumulator;
177  contour_header_array_type m_contour_accumulator;
178  gpc_polygon m_poly_a;
179  gpc_polygon m_poly_b;
180  gpc_polygon m_result;
181  };
182 
183 
184 
185 
186 
187  //------------------------------------------------------------------------
188  template<class VSA, class VSB>
189  void conv_gpc<VSA, VSB>::free_polygon(gpc_polygon& p)
190  {
191  int i;
192  for(i = 0; i < p.num_contours; i++)
193  {
194  pod_allocator<gpc_vertex>::deallocate(p.contour[i].vertex,
195  p.contour[i].num_vertices);
196  }
197  pod_allocator<gpc_vertex_list>::deallocate(p.contour, p.num_contours);
198  std::memset(&p, 0, sizeof(gpc_polygon));
199  }
200 
201 
202  //------------------------------------------------------------------------
203  template<class VSA, class VSB>
205  {
206  if(m_result.contour)
207  {
208  gpc_free_polygon(&m_result);
209  }
210  std::memset(&m_result, 0, sizeof(m_result));
211  }
212 
213 
214  //------------------------------------------------------------------------
215  template<class VSA, class VSB>
217  {
218  free_polygon(m_poly_a);
219  free_polygon(m_poly_b);
220  free_result();
221  }
222 
223 
224  //------------------------------------------------------------------------
225  template<class VSA, class VSB>
227  {
228  contour_header_type h;
229  std::memset(&h, 0, sizeof(h));
230  m_contour_accumulator.add(h);
231  m_vertex_accumulator.remove_all();
232  }
233 
234 
235  //------------------------------------------------------------------------
236  template<class VSA, class VSB>
237  inline void conv_gpc<VSA, VSB>::add_vertex(double x, double y)
238  {
239  gpc_vertex v;
240  v.x = x;
241  v.y = y;
242  m_vertex_accumulator.add(v);
243  }
244 
245 
246  //------------------------------------------------------------------------
247  template<class VSA, class VSB>
248  void conv_gpc<VSA, VSB>::end_contour(unsigned /*orientation*/)
249  {
250  if(m_contour_accumulator.size())
251  {
252  if(m_vertex_accumulator.size() > 2)
253  {
254  contour_header_type& h =
255  m_contour_accumulator[m_contour_accumulator.size() - 1];
256 
257  h.num_vertices = m_vertex_accumulator.size();
258  h.hole_flag = 0;
259 
260  // TO DO: Clarify the "holes"
261  //if(is_cw(orientation)) h.hole_flag = 1;
262 
263  h.vertices = pod_allocator<gpc_vertex>::allocate(h.num_vertices);
264  gpc_vertex* d = h.vertices;
265  int i;
266  for(i = 0; i < h.num_vertices; i++)
267  {
268  const gpc_vertex& s = m_vertex_accumulator[i];
269  d->x = s.x;
270  d->y = s.y;
271  ++d;
272  }
273  }
274  else
275  {
276  m_vertex_accumulator.remove_last();
277  }
278  }
279  }
280 
281 
282  //------------------------------------------------------------------------
283  template<class VSA, class VSB>
284  void conv_gpc<VSA, VSB>::make_polygon(gpc_polygon& p)
285  {
286  free_polygon(p);
287  if(m_contour_accumulator.size())
288  {
289  p.num_contours = m_contour_accumulator.size();
290 
291  p.hole = 0;
292  p.contour = pod_allocator<gpc_vertex_list>::allocate(p.num_contours);
293 
294  int i;
295  gpc_vertex_list* pv = p.contour;
296  for(i = 0; i < p.num_contours; i++)
297  {
298  const contour_header_type& h = m_contour_accumulator[i];
299  pv->num_vertices = h.num_vertices;
300  pv->vertex = h.vertices;
301  ++pv;
302  }
303  }
304  }
305 
306 
307  //------------------------------------------------------------------------
308  template<class VSA, class VSB>
310  {
311  m_status = status_move_to;
312  m_contour = -1;
313  m_vertex = -1;
314  }
315 
316 
317  //------------------------------------------------------------------------
318  template<class VSA, class VSB>
320  {
321  if(++m_contour < m_result.num_contours)
322  {
323  m_vertex = -1;
324  return true;
325  }
326  return false;
327  }
328 
329 
330  //------------------------------------------------------------------------
331  template<class VSA, class VSB>
332  inline bool conv_gpc<VSA, VSB>::next_vertex(double* x, double* y)
333  {
334  const gpc_vertex_list& vlist = m_result.contour[m_contour];
335  if(++m_vertex < vlist.num_vertices)
336  {
337  const gpc_vertex& v = vlist.vertex[m_vertex];
338  *x = v.x;
339  *y = v.y;
340  return true;
341  }
342  return false;
343  }
344 
345 
346  //------------------------------------------------------------------------
347  template<class VSA, class VSB>
348  void conv_gpc<VSA, VSB>::rewind(unsigned path_id)
349  {
350  free_result();
351  m_src_a->rewind(path_id);
352  m_src_b->rewind(path_id);
353  add(*m_src_a, m_poly_a);
354  add(*m_src_b, m_poly_b);
355  switch(m_operation)
356  {
357  case gpc_or:
358  gpc_polygon_clip(GPC_UNION,
359  &m_poly_a,
360  &m_poly_b,
361  &m_result);
362  break;
363 
364  case gpc_and:
365  gpc_polygon_clip(GPC_INT,
366  &m_poly_a,
367  &m_poly_b,
368  &m_result);
369  break;
370 
371  case gpc_xor:
372  gpc_polygon_clip(GPC_XOR,
373  &m_poly_a,
374  &m_poly_b,
375  &m_result);
376  break;
377 
378  case gpc_a_minus_b:
379  gpc_polygon_clip(GPC_DIFF,
380  &m_poly_a,
381  &m_poly_b,
382  &m_result);
383  break;
384 
385  case gpc_b_minus_a:
386  gpc_polygon_clip(GPC_DIFF,
387  &m_poly_b,
388  &m_poly_a,
389  &m_result);
390  break;
391  }
392  start_extracting();
393  }
394 
395 
396  //------------------------------------------------------------------------
397  template<class VSA, class VSB>
398  unsigned conv_gpc<VSA, VSB>::vertex(double* x, double* y)
399  {
400  if(m_status == status_move_to)
401  {
402  if(next_contour())
403  {
404  if(next_vertex(x, y))
405  {
406  m_status = status_line_to;
407  return path_cmd_move_to;
408  }
409  m_status = status_stop;
410  return path_cmd_end_poly | path_flags_close;
411  }
412  }
413  else
414  {
415  if(next_vertex(x, y))
416  {
417  return path_cmd_line_to;
418  }
419  else
420  {
421  m_status = status_move_to;
422  }
423  return path_cmd_end_poly | path_flags_close;
424  }
425  return path_cmd_stop;
426  }
427 
428 
429 }
430 
431 
432 #endif
Definition: agg_arc.cpp:24