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 
65         typedef pod_bvector<gpc_vertex, 8>          vertex_array_type;
66         typedef pod_bvector<contour_header_type, 6> contour_header_array_type;
67 
68 
69     public:
70         typedef VSA source_a_type;
71         typedef VSB source_b_type;
72         typedef conv_gpc<source_a_type, source_b_type> self_type;
73 
~conv_gpc()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 
attach1(VSA & source)92         void attach1(VSA& source) { m_src_a = &source; }
attach2(VSB & source)93         void attach2(VSB& source) { m_src_b = &source; }
94 
operation(gpc_op_e v)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:
102         conv_gpc(const conv_gpc<VSA, VSB>&);
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         //--------------------------------------------------------------------
add(VS & src,gpc_polygon & p)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>
free_polygon(gpc_polygon & p)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>
free_result()204     void conv_gpc<VSA, VSB>::free_result()
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>
free_gpc_data()216     void conv_gpc<VSA, VSB>::free_gpc_data()
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>
start_contour()226     void conv_gpc<VSA, VSB>::start_contour()
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>
add_vertex(double x,double y)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>
end_contour(unsigned)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>
make_polygon(gpc_polygon & p)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>
start_extracting()309     void conv_gpc<VSA, VSB>::start_extracting()
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>
next_contour()319     bool conv_gpc<VSA, VSB>::next_contour()
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>
next_vertex(double * x,double * y)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>
rewind(unsigned path_id)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>
vertex(double * x,double * y)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
433