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