agg/inc/agg_conv_gpc.h

   1 //----------------------------------------------------------------------------
   2 // Anti-Grain Geometry - Version 2.3
   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 <math.h>
  28 #include "agg_basics.h"
  29 #include "agg_array.h"
  30 #include "agg_vertex_iterator.h"
  31
  32 extern "C"
  33 {
  34 #include "gpc.h"
  35 }
  36
  37 namespace agg
  38 {
  39     enum gpc_op_e
  40     {
  41         gpc_or,
  42         gpc_and,
  43         gpc_xor,
  44         gpc_a_minus_b,
  45         gpc_b_minus_a
  46     };
  47
  48
  49     //================================================================conv_gpc
  50     template<class VSA, class VSB> class conv_gpc
  51     {
  52         enum status
  53         {
  54             status_move_to,
  55             status_line_to,
  56             status_stop
  57         };
  58
  59         struct contour_header_type
  60         {
  61             int num_vertices;
  62             int hole_flag;
  63             gpc_vertex* vertices;
  64         };
  65
  66         typedef pod_deque<gpc_vertex, 8>          vertex_array_type;
  67         typedef pod_deque<contour_header_type, 6> contour_header_array_type;
  68
  69
  70     public:
  71         typedef VSA source_a_type;
  72         typedef VSB source_b_type;
  73         typedef conv_gpc<source_a_type, source_b_type> self_type;
  74
  75         ~conv_gpc()
  76         {
  77             free_gpc_data();
  78         }
  79
  80         conv_gpc(source_a_type& a, source_b_type& b, gpc_op_e op = gpc_or) :
  81             m_src_a(&a),
  82             m_src_b(&b),
  83             m_status(status_move_to),
  84             m_vertex(-1),
  85             m_contour(-1),
  86             m_operation(op)
  87         {
  88             memset(&m_poly_a, 0, sizeof(m_poly_a));
  89             memset(&m_poly_b, 0, sizeof(m_poly_b));
  90             memset(&m_result, 0, sizeof(m_result));
  91         }
  92
  93         void set_source1(VSA& source) { m_src_a = &source; }
  94         void set_source2(VSB& source) { m_src_b = &source; }
  95
  96         void operation(gpc_op_e v) { m_operation = v; }
  97
  98         // Vertex Source Interface
  99         void     rewind(unsigned id);
 100         unsigned vertex(double* x, double* y);
 101
 102         // Iterator
 103         typedef vertex_iterator<self_type> iterator;
 104         iterator begin(unsigned id) { return iterator(*this, id); }
 105         iterator end() { return iterator(path_cmd_stop); }
 106
 107     private:
 108         conv_gpc(const conv_gpc<VSA, VSB>&);
 109         const conv_gpc<VSA, VSB>& operator = (const conv_gpc<VSA, VSB>&);
 110
 111         //--------------------------------------------------------------------
 112         void free_polygon(gpc_polygon& p);
 113         void free_result();
 114         void free_gpc_data();
 115         void start_contour();
 116         void add_vertex(double x, double y);
 117         void end_contour(unsigned orientation);
 118         void make_polygon(gpc_polygon& p);
 119         void start_extracting();
 120         bool next_contour();
 121         bool next_vertex(double* x, double* y);
 122
 123
 124         //--------------------------------------------------------------------
 125         template<class VS> void add(VS& src, gpc_polygon& p)
 126         {
 127             unsigned cmd;
 128             double x, y;
 129             double start_x = 0.0;
 130             double start_y = 0.0;
 131             bool line_to = false;
 132             unsigned orientation = 0;
 133
 134             m_contour_accumulator.remove_all();
 135
 136             while(!is_stop(cmd = src.vertex(&x, &y)))
 137             {
 138                 if(is_vertex(cmd))
 139                 {
 140                     if(is_move_to(cmd))
 141                     {
 142                         if(line_to)
 143                         {
 144                             end_contour(orientation);
 145                             orientation = 0;
 146                         }
 147                         start_contour();
 148                         start_x = x;
 149                         start_y = y;
 150                     }
 151                     add_vertex(x, y);
 152                     line_to = true;
 153                 }
 154                 else
 155                 {
 156                     if(is_end_poly(cmd))
 157                     {
 158                         orientation = get_orientation(cmd);
 159                         if(line_to && is_closed(cmd))
 160                         {
 161                             add_vertex(start_x, start_y);
 162                         }
 163                     }
 164                 }
 165             }
 166             if(line_to)
 167             {
 168                 end_contour(orientation);
 169             }
 170             make_polygon(p);
 171         }
 172
 173
 174     private:
 175         //--------------------------------------------------------------------
 176         source_a_type*             m_src_a;
 177         source_b_type*             m_src_b;
 178         status                     m_status;
 179         int                        m_vertex;
 180         int                        m_contour;
 181         gpc_op_e                   m_operation;
 182         vertex_array_type          m_vertex_accumulator;
 183         contour_header_array_type  m_contour_accumulator;
 184         gpc_polygon                m_poly_a;
 185         gpc_polygon                m_poly_b;
 186         gpc_polygon                m_result;
 187     };
 188
 189
 190
 191
 192
 193     //------------------------------------------------------------------------
 194     template<class VSA, class VSB>
 195     void conv_gpc<VSA, VSB>::free_polygon(gpc_polygon& p)
 196     {
 197         int i;
 198         for(i = 0; i < p.num_contours; i++)
 199         {
 200             delete [] p.contour[i].vertex;
 201         }
 202         delete [] p.hole;
 203         delete [] p.contour;
 204         memset(&p, 0, sizeof(gpc_polygon));
 205     }
 206
 207
 208     //------------------------------------------------------------------------
 209     template<class VSA, class VSB>
 210     void conv_gpc<VSA, VSB>::free_result()
 211     {
 212         if(m_result.contour)
 213         {
 214             gpc_free_polygon(&m_result);
 215         }
 216         memset(&m_result, 0, sizeof(m_result));
 217     }
 218
 219
 220     //------------------------------------------------------------------------
 221     template<class VSA, class VSB>
 222     void conv_gpc<VSA, VSB>::free_gpc_data()
 223     {
 224         free_polygon(m_poly_a);
 225         free_polygon(m_poly_b);
 226         free_result();
 227     }
 228
 229
 230     //------------------------------------------------------------------------
 231     template<class VSA, class VSB>
 232     void conv_gpc<VSA, VSB>::start_contour()
 233     {
 234         contour_header_type h;
 235         memset(&h, 0, sizeof(h));
 236         m_contour_accumulator.add(h);
 237         m_vertex_accumulator.remove_all();
 238     }
 239
 240
 241     //------------------------------------------------------------------------
 242     template<class VSA, class VSB>
 243     inline void conv_gpc<VSA, VSB>::add_vertex(double x, double y)
 244     {
 245         gpc_vertex v;
 246         v.x = x;
 247         v.y = y;
 248         m_vertex_accumulator.add(v);
 249     }
 250
 251
 252     //------------------------------------------------------------------------
 253     template<class VSA, class VSB>
 254     void conv_gpc<VSA, VSB>::end_contour(unsigned orientation)
 255     {
 256         if(m_contour_accumulator.size())
 257         {
 258             if(m_vertex_accumulator.size() > 2)
 259             {
 260                 contour_header_type& h =
 261                     m_contour_accumulator[m_contour_accumulator.size() - 1];
 262
 263                 h.num_vertices = m_vertex_accumulator.size();
 264                 h.hole_flag = 0;
 265
 266                 // TO DO: Clarify the "holes"
 267                 //if(is_cw(orientation)) h.hole_flag = 1;
 268
 269                 h.vertices = new gpc_vertex [h.num_vertices];
 270                 gpc_vertex* d = h.vertices;
 271                 int i;
 272                 for(i = 0; i < h.num_vertices; i++)
 273                 {
 274                     const gpc_vertex& s = m_vertex_accumulator[i];
 275                     d->x = s.x;
 276                     d->y = s.y;
 277                     ++d;
 278                 }
 279             }
 280             else
 281             {
 282                 m_vertex_accumulator.remove_last();
 283             }
 284         }
 285     }
 286
 287
 288     //------------------------------------------------------------------------
 289     template<class VSA, class VSB>
 290     void conv_gpc<VSA, VSB>::make_polygon(gpc_polygon& p)
 291     {
 292         free_polygon(p);
 293         if(m_contour_accumulator.size())
 294         {
 295             p.num_contours = m_contour_accumulator.size();
 296
 297             // TO DO: Clarify the "holes"
 298             //p.hole = new int[p.num_contours];
 299             p.hole = 0;
 300
 301             p.contour = new gpc_vertex_list[p.num_contours];
 302
 303             int i;
 304             //int* ph = p.hole;
 305             gpc_vertex_list* pv = p.contour;
 306             for(i = 0; i < p.num_contours; i++)
 307             {
 308                 const contour_header_type& h = m_contour_accumulator[i];
 309                 // *ph++ = h.hole_flag;
 310                 pv->num_vertices = h.num_vertices;
 311                 pv->vertex = h.vertices;
 312                 ++pv;
 313             }
 314         }
 315     }
 316
 317
 318     //------------------------------------------------------------------------
 319     template<class VSA, class VSB>
 320     void conv_gpc<VSA, VSB>::start_extracting()
 321     {
 322         m_status = status_move_to;
 323         m_contour = -1;
 324         m_vertex = -1;
 325     }
 326
 327
 328     //------------------------------------------------------------------------
 329     template<class VSA, class VSB>
 330     bool conv_gpc<VSA, VSB>::next_contour()
 331     {
 332         if(++m_contour < m_result.num_contours)
 333         {
 334             m_vertex = -1;
 335             return true;
 336         }
 337         return false;
 338     }
 339
 340
 341     //------------------------------------------------------------------------
 342     template<class VSA, class VSB>
 343     inline bool conv_gpc<VSA, VSB>::next_vertex(double* x, double* y)
 344     {
 345         const gpc_vertex_list& vlist = m_result.contour[m_contour];
 346         if(++m_vertex < vlist.num_vertices)
 347         {
 348             const gpc_vertex& v = vlist.vertex[m_vertex];
 349             *x = v.x;
 350             *y = v.y;
 351             return true;
 352         }
 353         return false;
 354     }
 355
 356
 357     //------------------------------------------------------------------------
 358     template<class VSA, class VSB>
 359     void conv_gpc<VSA, VSB>::rewind(unsigned id)
 360     {
 361         free_result();
 362         m_src_a->rewind(id);
 363         m_src_b->rewind(id);
 364         add(*m_src_a, m_poly_a);
 365         add(*m_src_b, m_poly_b);
 366         switch(m_operation)
 367         {
 368            case gpc_or:
 369                 gpc_polygon_clip(GPC_UNION,
 370                                  &m_poly_a,
 371                                  &m_poly_b,
 372                                  &m_result);
 373                break;
 374
 375            case gpc_and:
 376                 gpc_polygon_clip(GPC_INT,
 377                                  &m_poly_a,
 378                                  &m_poly_b,
 379                                  &m_result);
 380                break;
 381
 382            case gpc_xor:
 383                 gpc_polygon_clip(GPC_XOR,
 384                                  &m_poly_a,
 385                                  &m_poly_b,
 386                                  &m_result);
 387                break;
 388
 389            case gpc_a_minus_b:
 390                 gpc_polygon_clip(GPC_DIFF,
 391                                  &m_poly_a,
 392                                  &m_poly_b,
 393                                  &m_result);
 394                break;
 395
 396            case gpc_b_minus_a:
 397                 gpc_polygon_clip(GPC_DIFF,
 398                                  &m_poly_b,
 399                                  &m_poly_a,
 400                                  &m_result);
 401                break;
 402         }
 403         start_extracting();
 404     }
 405
 406
 407     //------------------------------------------------------------------------
 408     template<class VSA, class VSB>
 409     unsigned conv_gpc<VSA, VSB>::vertex(double* x, double* y)
 410     {
 411         if(m_status == status_move_to)
 412         {
 413             if(next_contour())
 414             {
 415                 if(next_vertex(x, y))
 416                 {
 417                     m_status = status_line_to;
 418                     return path_cmd_move_to;
 419                 }
 420                 m_status = status_stop;
 421                 return path_cmd_end_poly | path_flags_close;
 422             }
 423         }
 424         else
 425         {
 426             if(next_vertex(x, y))
 427             {
 428                 return path_cmd_line_to;
 429             }
 430             else
 431             {
 432                 m_status = status_move_to;
 433             }
 434             return path_cmd_end_poly | path_flags_close;
 435         }
 436         return path_cmd_stop;
 437     }
 438
 439
 440 }
 441
 442
 443 #endif