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#ifndef AGG_PATH_STORAGE_INCLUDED 17#define AGG_PATH_STORAGE_INCLUDED 18 19#include <string.h> 20#include <math.h> 21#include "agg_math.h" 22#include "agg_array.h" 23#include "agg_bezier_arc.h" 24 25namespace agg 26{ 27 28 29 //----------------------------------------------------vertex_block_storage 30 template<class T, unsigned BlockShift=8, unsigned BlockPool=256> 31 class vertex_block_storage 32 { 33 public: 34 // Allocation parameters 35 enum block_scale_e 36 { 37 block_shift = BlockShift, 38 block_size = 1 << block_shift, 39 block_mask = block_size - 1, 40 block_pool = BlockPool 41 }; 42 43 typedef T value_type; 44 typedef vertex_block_storage<T, BlockShift, BlockPool> self_type; 45 46 ~vertex_block_storage(); 47 vertex_block_storage(); 48 vertex_block_storage(const self_type& v); 49 const self_type& operator = (const self_type& ps); 50 51 void remove_all(); 52 void free_all(); 53 54 void add_vertex(double x, double y, unsigned cmd); 55 void modify_vertex(unsigned idx, double x, double y); 56 void modify_vertex(unsigned idx, double x, double y, unsigned cmd); 57 void modify_command(unsigned idx, unsigned cmd); 58 void swap_vertices(unsigned v1, unsigned v2); 59 60 unsigned last_command() const; 61 unsigned last_vertex(double* x, double* y) const; 62 unsigned prev_vertex(double* x, double* y) const; 63 64 double last_x() const; 65 double last_y() const; 66 67 unsigned total_vertices() const; 68 unsigned vertex(unsigned idx, double* x, double* y) const; 69 unsigned command(unsigned idx) const; 70 71 private: 72 void allocate_block(unsigned nb); 73 int8u* storage_ptrs(T** xy_ptr); 74 75 private: 76 unsigned m_total_vertices; 77 unsigned m_total_blocks; 78 unsigned m_max_blocks; 79 T** m_coord_blocks; 80 int8u** m_cmd_blocks; 81 }; 82 83 84 //------------------------------------------------------------------------ 85 template<class T, unsigned S, unsigned P> 86 void vertex_block_storage<T,S,P>::free_all() 87 { 88 if(m_total_blocks) 89 { 90 T** coord_blk = m_coord_blocks + m_total_blocks - 1; 91 while(m_total_blocks--) 92 { 93 pod_allocator<T>::deallocate( 94 *coord_blk, 95 block_size * 2 + 96 block_size / (sizeof(T) / sizeof(unsigned char))); 97 --coord_blk; 98 } 99 pod_allocator<T*>::deallocate(m_coord_blocks, m_max_blocks * 2); 100 m_total_blocks = 0; 101 m_max_blocks = 0; 102 m_coord_blocks = 0; 103 m_cmd_blocks = 0; 104 m_total_vertices = 0; 105 } 106 } 107 108 //------------------------------------------------------------------------ 109 template<class T, unsigned S, unsigned P> 110 vertex_block_storage<T,S,P>::~vertex_block_storage() 111 { 112 free_all(); 113 } 114 115 //------------------------------------------------------------------------ 116 template<class T, unsigned S, unsigned P> 117 vertex_block_storage<T,S,P>::vertex_block_storage() : 118 m_total_vertices(0), 119 m_total_blocks(0), 120 m_max_blocks(0), 121 m_coord_blocks(0), 122 m_cmd_blocks(0) 123 { 124 } 125 126 //------------------------------------------------------------------------ 127 template<class T, unsigned S, unsigned P> 128 vertex_block_storage<T,S,P>::vertex_block_storage(const vertex_block_storage<T,S,P>& v) : 129 m_total_vertices(0), 130 m_total_blocks(0), 131 m_max_blocks(0), 132 m_coord_blocks(0), 133 m_cmd_blocks(0) 134 { 135 *this = v; 136 } 137 138 //------------------------------------------------------------------------ 139 template<class T, unsigned S, unsigned P> 140 const vertex_block_storage<T,S,P>& 141 vertex_block_storage<T,S,P>::operator = (const vertex_block_storage<T,S,P>& v) 142 { 143 remove_all(); 144 unsigned i; 145 for(i = 0; i < v.total_vertices(); i++) 146 { 147 double x, y; 148 unsigned cmd = v.vertex(i, &x, &y); 149 add_vertex(x, y, cmd); 150 } 151 return *this; 152 } 153 154 //------------------------------------------------------------------------ 155 template<class T, unsigned S, unsigned P> 156 inline void vertex_block_storage<T,S,P>::remove_all() 157 { 158 m_total_vertices = 0; 159 } 160 161 //------------------------------------------------------------------------ 162 template<class T, unsigned S, unsigned P> 163 inline void vertex_block_storage<T,S,P>::add_vertex(double x, double y, 164 unsigned cmd) 165 { 166 T* coord_ptr = 0; 167 *storage_ptrs(&coord_ptr) = (int8u)cmd; 168 coord_ptr[0] = T(x); 169 coord_ptr[1] = T(y); 170 m_total_vertices++; 171 } 172 173 //------------------------------------------------------------------------ 174 template<class T, unsigned S, unsigned P> 175 inline void vertex_block_storage<T,S,P>::modify_vertex(unsigned idx, 176 double x, double y) 177 { 178 T* pv = m_coord_blocks[idx >> block_shift] + ((idx & block_mask) << 1); 179 pv[0] = T(x); 180 pv[1] = T(y); 181 } 182 183 //------------------------------------------------------------------------ 184 template<class T, unsigned S, unsigned P> 185 inline void vertex_block_storage<T,S,P>::modify_vertex(unsigned idx, 186 double x, double y, 187 unsigned cmd) 188 { 189 unsigned block = idx >> block_shift; 190 unsigned offset = idx & block_mask; 191 T* pv = m_coord_blocks[block] + (offset << 1); 192 pv[0] = T(x); 193 pv[1] = T(y); 194 m_cmd_blocks[block][offset] = (int8u)cmd; 195 } 196 197 //------------------------------------------------------------------------ 198 template<class T, unsigned S, unsigned P> 199 inline void vertex_block_storage<T,S,P>::modify_command(unsigned idx, 200 unsigned cmd) 201 { 202 m_cmd_blocks[idx >> block_shift][idx & block_mask] = (int8u)cmd; 203 } 204 205 //------------------------------------------------------------------------ 206 template<class T, unsigned S, unsigned P> 207 inline void vertex_block_storage<T,S,P>::swap_vertices(unsigned v1, unsigned v2) 208 { 209 unsigned b1 = v1 >> block_shift; 210 unsigned b2 = v2 >> block_shift; 211 unsigned o1 = v1 & block_mask; 212 unsigned o2 = v2 & block_mask; 213 T* pv1 = m_coord_blocks[b1] + (o1 << 1); 214 T* pv2 = m_coord_blocks[b2] + (o2 << 1); 215 T val; 216 val = pv1[0]; pv1[0] = pv2[0]; pv2[0] = val; 217 val = pv1[1]; pv1[1] = pv2[1]; pv2[1] = val; 218 int8u cmd = m_cmd_blocks[b1][o1]; 219 m_cmd_blocks[b1][o1] = m_cmd_blocks[b2][o2]; 220 m_cmd_blocks[b2][o2] = cmd; 221 } 222 223 //------------------------------------------------------------------------ 224 template<class T, unsigned S, unsigned P> 225 inline unsigned vertex_block_storage<T,S,P>::last_command() const 226 { 227 if(m_total_vertices) return command(m_total_vertices - 1); 228 return path_cmd_stop; 229 } 230 231 //------------------------------------------------------------------------ 232 template<class T, unsigned S, unsigned P> 233 inline unsigned vertex_block_storage<T,S,P>::last_vertex(double* x, double* y) const 234 { 235 if(m_total_vertices) return vertex(m_total_vertices - 1, x, y); 236 return path_cmd_stop; 237 } 238 239 //------------------------------------------------------------------------ 240 template<class T, unsigned S, unsigned P> 241 inline unsigned vertex_block_storage<T,S,P>::prev_vertex(double* x, double* y) const 242 { 243 if(m_total_vertices > 1) return vertex(m_total_vertices - 2, x, y); 244 return path_cmd_stop; 245 } 246 247 //------------------------------------------------------------------------ 248 template<class T, unsigned S, unsigned P> 249 inline double vertex_block_storage<T,S,P>::last_x() const 250 { 251 if(m_total_vertices) 252 { 253 unsigned idx = m_total_vertices - 1; 254 return m_coord_blocks[idx >> block_shift][(idx & block_mask) << 1]; 255 } 256 return 0.0; 257 } 258 259 //------------------------------------------------------------------------ 260 template<class T, unsigned S, unsigned P> 261 inline double vertex_block_storage<T,S,P>::last_y() const 262 { 263 if(m_total_vertices) 264 { 265 unsigned idx = m_total_vertices - 1; 266 return m_coord_blocks[idx >> block_shift][((idx & block_mask) << 1) + 1]; 267 } 268 return 0.0; 269 } 270 271 //------------------------------------------------------------------------ 272 template<class T, unsigned S, unsigned P> 273 inline unsigned vertex_block_storage<T,S,P>::total_vertices() const 274 { 275 return m_total_vertices; 276 } 277 278 //------------------------------------------------------------------------ 279 template<class T, unsigned S, unsigned P> 280 inline unsigned vertex_block_storage<T,S,P>::vertex(unsigned idx, 281 double* x, double* y) const 282 { 283 unsigned nb = idx >> block_shift; 284 const T* pv = m_coord_blocks[nb] + ((idx & block_mask) << 1); 285 *x = pv[0]; 286 *y = pv[1]; 287 return m_cmd_blocks[nb][idx & block_mask]; 288 } 289 290 //------------------------------------------------------------------------ 291 template<class T, unsigned S, unsigned P> 292 inline unsigned vertex_block_storage<T,S,P>::command(unsigned idx) const 293 { 294 return m_cmd_blocks[idx >> block_shift][idx & block_mask]; 295 } 296 297 //------------------------------------------------------------------------ 298 template<class T, unsigned S, unsigned P> 299 void vertex_block_storage<T,S,P>::allocate_block(unsigned nb) 300 { 301 if(nb >= m_max_blocks) 302 { 303 T** new_coords = 304 pod_allocator<T*>::allocate((m_max_blocks + block_pool) * 2); 305 306 unsigned char** new_cmds = 307 (unsigned char**)(new_coords + m_max_blocks + block_pool); 308 309 if(m_coord_blocks) 310 { 311 memcpy(new_coords, 312 m_coord_blocks, 313 m_max_blocks * sizeof(T*)); 314 315 memcpy(new_cmds, 316 m_cmd_blocks, 317 m_max_blocks * sizeof(unsigned char*)); 318 319 pod_allocator<T*>::deallocate(m_coord_blocks, m_max_blocks * 2); 320 } 321 m_coord_blocks = new_coords; 322 m_cmd_blocks = new_cmds; 323 m_max_blocks += block_pool; 324 } 325 m_coord_blocks[nb] = 326 pod_allocator<T>::allocate(block_size * 2 + 327 block_size / (sizeof(T) / sizeof(unsigned char))); 328 329 m_cmd_blocks[nb] = 330 (unsigned char*)(m_coord_blocks[nb] + block_size * 2); 331 332 m_total_blocks++; 333 } 334 335 //------------------------------------------------------------------------ 336 template<class T, unsigned S, unsigned P> 337 int8u* vertex_block_storage<T,S,P>::storage_ptrs(T** xy_ptr) 338 { 339 unsigned nb = m_total_vertices >> block_shift; 340 if(nb >= m_total_blocks) 341 { 342 allocate_block(nb); 343 } 344 *xy_ptr = m_coord_blocks[nb] + ((m_total_vertices & block_mask) << 1); 345 return m_cmd_blocks[nb] + (m_total_vertices & block_mask); 346 } 347 348 349 350 351 //-----------------------------------------------------poly_plain_adaptor 352 template<class T> class poly_plain_adaptor 353 { 354 public: 355 typedef T value_type; 356 357 poly_plain_adaptor() : 358 m_data(0), 359 m_ptr(0), 360 m_end(0), 361 m_closed(false), 362 m_stop(false) 363 {} 364 365 poly_plain_adaptor(const T* data, unsigned num_points, bool closed) : 366 m_data(data), 367 m_ptr(data), 368 m_end(data + num_points * 2), 369 m_closed(closed), 370 m_stop(false) 371 {} 372 373 void init(const T* data, unsigned num_points, bool closed) 374 { 375 m_data = data; 376 m_ptr = data; 377 m_end = data + num_points * 2; 378 m_closed = closed; 379 m_stop = false; 380 } 381 382 void rewind(unsigned) 383 { 384 m_ptr = m_data; 385 m_stop = false; 386 } 387 388 unsigned vertex(double* x, double* y) 389 { 390 if(m_ptr < m_end) 391 { 392 bool first = m_ptr == m_data; 393 *x = *m_ptr++; 394 *y = *m_ptr++; 395 return first ? path_cmd_move_to : path_cmd_line_to; 396 } 397 *x = *y = 0.0; 398 if(m_closed && !m_stop) 399 { 400 m_stop = true; 401 return path_cmd_end_poly | path_flags_close; 402 } 403 return path_cmd_stop; 404 } 405 406 private: 407 const T* m_data; 408 const T* m_ptr; 409 const T* m_end; 410 bool m_closed; 411 bool m_stop; 412 }; 413 414 415 416 417 418 //-------------------------------------------------poly_container_adaptor 419 template<class Container> class poly_container_adaptor 420 { 421 public: 422 typedef typename Container::value_type vertex_type; 423 424 poly_container_adaptor() : 425 m_container(0), 426 m_index(0), 427 m_closed(false), 428 m_stop(false) 429 {} 430 431 poly_container_adaptor(const Container& data, bool closed) : 432 m_container(&data), 433 m_index(0), 434 m_closed(closed), 435 m_stop(false) 436 {} 437 438 void init(const Container& data, bool closed) 439 { 440 m_container = &data; 441 m_index = 0; 442 m_closed = closed; 443 m_stop = false; 444 } 445 446 void rewind(unsigned) 447 { 448 m_index = 0; 449 m_stop = false; 450 } 451 452 unsigned vertex(double* x, double* y) 453 { 454 if(m_index < m_container->size()) 455 { 456 bool first = m_index == 0; 457 const vertex_type& v = (*m_container)[m_index++]; 458 *x = v.x; 459 *y = v.y; 460 return first ? path_cmd_move_to : path_cmd_line_to; 461 } 462 *x = *y = 0.0; 463 if(m_closed && !m_stop) 464 { 465 m_stop = true; 466 return path_cmd_end_poly | path_flags_close; 467 } 468 return path_cmd_stop; 469 } 470 471 private: 472 const Container* m_container; 473 unsigned m_index; 474 bool m_closed; 475 bool m_stop; 476 }; 477 478 479 480 //-----------------------------------------poly_container_reverse_adaptor 481 template<class Container> class poly_container_reverse_adaptor 482 { 483 public: 484 typedef typename Container::value_type vertex_type; 485 486 poly_container_reverse_adaptor() : 487 m_container(0), 488 m_index(-1), 489 m_closed(false), 490 m_stop(false) 491 {} 492 493 poly_container_reverse_adaptor(const Container& data, bool closed) : 494 m_container(&data), 495 m_index(-1), 496 m_closed(closed), 497 m_stop(false) 498 {} 499 500 void init(const Container& data, bool closed) 501 { 502 m_container = &data; 503 m_index = m_container->size() - 1; 504 m_closed = closed; 505 m_stop = false; 506 } 507 508 void rewind(unsigned) 509 { 510 m_index = m_container->size() - 1; 511 m_stop = false; 512 } 513 514 unsigned vertex(double* x, double* y) 515 { 516 if(m_index >= 0) 517 { 518 bool first = m_index == int(m_container->size() - 1); 519 const vertex_type& v = (*m_container)[m_index--]; 520 *x = v.x; 521 *y = v.y; 522 return first ? path_cmd_move_to : path_cmd_line_to; 523 } 524 *x = *y = 0.0; 525 if(m_closed && !m_stop) 526 { 527 m_stop = true; 528 return path_cmd_end_poly | path_flags_close; 529 } 530 return path_cmd_stop; 531 } 532 533 private: 534 const Container* m_container; 535 int m_index; 536 bool m_closed; 537 bool m_stop; 538 }; 539 540 541 542 543 544 //--------------------------------------------------------line_adaptor 545 class line_adaptor 546 { 547 public: 548 typedef double value_type; 549 550 line_adaptor() : m_line(m_coord, 2, false) {} 551 line_adaptor(double x1, double y1, double x2, double y2) : 552 m_line(m_coord, 2, false) 553 { 554 m_coord[0] = x1; 555 m_coord[1] = y1; 556 m_coord[2] = x2; 557 m_coord[3] = y2; 558 } 559 560 void init(double x1, double y1, double x2, double y2) 561 { 562 m_coord[0] = x1; 563 m_coord[1] = y1; 564 m_coord[2] = x2; 565 m_coord[3] = y2; 566 m_line.rewind(0); 567 } 568 569 void rewind(unsigned) 570 { 571 m_line.rewind(0); 572 } 573 574 unsigned vertex(double* x, double* y) 575 { 576 return m_line.vertex(x, y); 577 } 578 579 private: 580 double m_coord[4]; 581 poly_plain_adaptor<double> m_line; 582 }; 583 584 585 586 587 588 589 590 591 592 593 594 595 596 //---------------------------------------------------------------path_base 597 // A container to store vertices with their flags. 598 // A path consists of a number of contours separated with "move_to" 599 // commands. The path storage can keep and maintain more than one 600 // path. 601 // To navigate to the beginning of a particular path, use rewind(path_id); 602 // Where path_id is what start_new_path() returns. So, when you call 603 // start_new_path() you need to store its return value somewhere else 604 // to navigate to the path afterwards. 605 // 606 // See also: vertex_source concept 607 //------------------------------------------------------------------------ 608 template<class VertexContainer> class path_base 609 { 610 public: 611 typedef VertexContainer container_type; 612 typedef path_base<VertexContainer> self_type; 613 614 //-------------------------------------------------------------------- 615 path_base() : m_vertices(), m_iterator(0) {} 616 void remove_all() { m_vertices.remove_all(); m_iterator = 0; } 617 void free_all() { m_vertices.free_all(); m_iterator = 0; } 618 619 // Make path functions 620 //-------------------------------------------------------------------- 621 unsigned start_new_path(); 622 623 void move_to(double x, double y); 624 void move_rel(double dx, double dy); 625 626 void line_to(double x, double y); 627 void line_rel(double dx, double dy); 628 629 void hline_to(double x); 630 void hline_rel(double dx); 631 632 void vline_to(double y); 633 void vline_rel(double dy); 634 635 void arc_to(double rx, double ry, 636 double angle, 637 bool large_arc_flag, 638 bool sweep_flag, 639 double x, double y); 640 641 void arc_rel(double rx, double ry, 642 double angle, 643 bool large_arc_flag, 644 bool sweep_flag, 645 double dx, double dy); 646 647 void curve3(double x_ctrl, double y_ctrl, 648 double x_to, double y_to); 649 650 void curve3_rel(double dx_ctrl, double dy_ctrl, 651 double dx_to, double dy_to); 652 653 void curve3(double x_to, double y_to); 654 655 void curve3_rel(double dx_to, double dy_to); 656 657 void curve4(double x_ctrl1, double y_ctrl1, 658 double x_ctrl2, double y_ctrl2, 659 double x_to, double y_to); 660 661 void curve4_rel(double dx_ctrl1, double dy_ctrl1, 662 double dx_ctrl2, double dy_ctrl2, 663 double dx_to, double dy_to); 664 665 void curve4(double x_ctrl2, double y_ctrl2, 666 double x_to, double y_to); 667 668 void curve4_rel(double x_ctrl2, double y_ctrl2, 669 double x_to, double y_to); 670 671 672 void end_poly(unsigned flags = path_flags_close); 673 void close_polygon(unsigned flags = path_flags_none); 674 675 // Accessors 676 //-------------------------------------------------------------------- 677 const container_type& vertices() const { return m_vertices; } 678 container_type& vertices() { return m_vertices; } 679 680 unsigned total_vertices() const; 681 682 void rel_to_abs(double* x, double* y) const; 683 684 unsigned last_vertex(double* x, double* y) const; 685 unsigned prev_vertex(double* x, double* y) const; 686 687 double last_x() const; 688 double last_y() const; 689 690 unsigned vertex(unsigned idx, double* x, double* y) const; 691 unsigned command(unsigned idx) const; 692 693 void modify_vertex(unsigned idx, double x, double y); 694 void modify_vertex(unsigned idx, double x, double y, unsigned cmd); 695 void modify_command(unsigned idx, unsigned cmd); 696 697 // VertexSource interface 698 //-------------------------------------------------------------------- 699 void rewind(unsigned path_id); 700 unsigned vertex(double* x, double* y); 701 702 // Arrange the orientation of a polygon, all polygons in a path, 703 // or in all paths. After calling arrange_orientations() or 704 // arrange_orientations_all_paths(), all the polygons will have 705 // the same orientation, i.e. path_flags_cw or path_flags_ccw 706 //-------------------------------------------------------------------- 707 unsigned arrange_polygon_orientation(unsigned start, path_flags_e orientation); 708 unsigned arrange_orientations(unsigned path_id, path_flags_e orientation); 709 void arrange_orientations_all_paths(path_flags_e orientation); 710 void invert_polygon(unsigned start); 711 712 // Flip all vertices horizontally or vertically, 713 // between x1 and x2, or between y1 and y2 respectively 714 //-------------------------------------------------------------------- 715 void flip_x(double x1, double x2); 716 void flip_y(double y1, double y2); 717 718 // Concatenate path. The path is added as is. 719 //-------------------------------------------------------------------- 720 template<class VertexSource> 721 void concat_path(VertexSource& vs, unsigned path_id = 0) 722 { 723 double x, y; 724 unsigned cmd; 725 vs.rewind(path_id); 726 while(!is_stop(cmd = vs.vertex(&x, &y))) 727 { 728 m_vertices.add_vertex(x, y, cmd); 729 } 730 } 731 732 //-------------------------------------------------------------------- 733 // Join path. The path is joined with the existing one, that is, 734 // it behaves as if the pen of a plotter was always down (drawing) 735 template<class VertexSource> 736 void join_path(VertexSource& vs, unsigned path_id = 0) 737 { 738 double x, y; 739 unsigned cmd; 740 vs.rewind(path_id); 741 cmd = vs.vertex(&x, &y); 742 if(!is_stop(cmd)) 743 { 744 if(is_vertex(cmd)) 745 { 746 double x0, y0; 747 unsigned cmd0 = last_vertex(&x0, &y0); 748 if(is_vertex(cmd0)) 749 { 750 if(calc_distance(x, y, x0, y0) > vertex_dist_epsilon) 751 { 752 if(is_move_to(cmd)) cmd = path_cmd_line_to; 753 m_vertices.add_vertex(x, y, cmd); 754 } 755 } 756 else 757 { 758 if(is_stop(cmd0)) 759 { 760 cmd = path_cmd_move_to; 761 } 762 else 763 { 764 if(is_move_to(cmd)) cmd = path_cmd_line_to; 765 } 766 m_vertices.add_vertex(x, y, cmd); 767 } 768 } 769 while(!is_stop(cmd = vs.vertex(&x, &y))) 770 { 771 m_vertices.add_vertex(x, y, is_move_to(cmd) ? 772 path_cmd_line_to : 773 cmd); 774 } 775 } 776 } 777 778 // Concatenate polygon/polyline. 779 //-------------------------------------------------------------------- 780 template<class T> void concat_poly(const T* data, 781 unsigned num_points, 782 bool closed) 783 { 784 poly_plain_adaptor<T> poly(data, num_points, closed); 785 concat_path(poly); 786 } 787 788 // Join polygon/polyline continuously. 789 //-------------------------------------------------------------------- 790 template<class T> void join_poly(const T* data, 791 unsigned num_points, 792 bool closed) 793 { 794 poly_plain_adaptor<T> poly(data, num_points, closed); 795 join_path(poly); 796 } 797 798 799 private: 800 unsigned perceive_polygon_orientation(unsigned start, unsigned end); 801 void invert_polygon(unsigned start, unsigned end); 802 803 VertexContainer m_vertices; 804 unsigned m_iterator; 805 }; 806 807 //------------------------------------------------------------------------ 808 template<class VC> 809 unsigned path_base<VC>::start_new_path() 810 { 811 if(!is_stop(m_vertices.last_command())) 812 { 813 m_vertices.add_vertex(0.0, 0.0, path_cmd_stop); 814 } 815 return m_vertices.total_vertices(); 816 } 817 818 819 //------------------------------------------------------------------------ 820 template<class VC> 821 inline void path_base<VC>::rel_to_abs(double* x, double* y) const 822 { 823 if(m_vertices.total_vertices()) 824 { 825 double x2; 826 double y2; 827 if(is_vertex(m_vertices.last_vertex(&x2, &y2))) 828 { 829 *x += x2; 830 *y += y2; 831 } 832 } 833 } 834 835 //------------------------------------------------------------------------ 836 template<class VC> 837 inline void path_base<VC>::move_to(double x, double y) 838 { 839 m_vertices.add_vertex(x, y, path_cmd_move_to); 840 } 841 842 //------------------------------------------------------------------------ 843 template<class VC> 844 inline void path_base<VC>::move_rel(double dx, double dy) 845 { 846 rel_to_abs(&dx, &dy); 847 m_vertices.add_vertex(dx, dy, path_cmd_move_to); 848 } 849 850 //------------------------------------------------------------------------ 851 template<class VC> 852 inline void path_base<VC>::line_to(double x, double y) 853 { 854 m_vertices.add_vertex(x, y, path_cmd_line_to); 855 } 856 857 //------------------------------------------------------------------------ 858 template<class VC> 859 inline void path_base<VC>::line_rel(double dx, double dy) 860 { 861 rel_to_abs(&dx, &dy); 862 m_vertices.add_vertex(dx, dy, path_cmd_line_to); 863 } 864 865 //------------------------------------------------------------------------ 866 template<class VC> 867 inline void path_base<VC>::hline_to(double x) 868 { 869 m_vertices.add_vertex(x, last_y(), path_cmd_line_to); 870 } 871 872 //------------------------------------------------------------------------ 873 template<class VC> 874 inline void path_base<VC>::hline_rel(double dx) 875 { 876 double dy = 0; 877 rel_to_abs(&dx, &dy); 878 m_vertices.add_vertex(dx, dy, path_cmd_line_to); 879 } 880 881 //------------------------------------------------------------------------ 882 template<class VC> 883 inline void path_base<VC>::vline_to(double y) 884 { 885 m_vertices.add_vertex(last_x(), y, path_cmd_line_to); 886 } 887 888 //------------------------------------------------------------------------ 889 template<class VC> 890 inline void path_base<VC>::vline_rel(double dy) 891 { 892 double dx = 0; 893 rel_to_abs(&dx, &dy); 894 m_vertices.add_vertex(dx, dy, path_cmd_line_to); 895 } 896 897 //------------------------------------------------------------------------ 898 template<class VC> 899 void path_base<VC>::arc_to(double rx, double ry, 900 double angle, 901 bool large_arc_flag, 902 bool sweep_flag, 903 double x, double y) 904 { 905 if(m_vertices.total_vertices() && is_vertex(m_vertices.last_command())) 906 { 907 const double epsilon = 1e-30; 908 double x0 = 0.0; 909 double y0 = 0.0; 910 m_vertices.last_vertex(&x0, &y0); 911 912 rx = fabs(rx); 913 ry = fabs(ry); 914 915 // Ensure radii are valid 916 //------------------------- 917 if(rx < epsilon || ry < epsilon) 918 { 919 line_to(x, y); 920 return; 921 } 922 923 if(calc_distance(x0, y0, x, y) < epsilon) 924 { 925 // If the endpoints (x, y) and (x0, y0) are identical, then this 926 // is equivalent to omitting the elliptical arc segment entirely. 927 return; 928 } 929 bezier_arc_svg a(x0, y0, rx, ry, angle, large_arc_flag, sweep_flag, x, y); 930 if(a.radii_ok()) 931 { 932 join_path(a); 933 } 934 else 935 { 936 line_to(x, y); 937 } 938 } 939 else 940 { 941 move_to(x, y); 942 } 943 } 944 945 //------------------------------------------------------------------------ 946 template<class VC> 947 void path_base<VC>::arc_rel(double rx, double ry, 948 double angle, 949 bool large_arc_flag, 950 bool sweep_flag, 951 double dx, double dy) 952 { 953 rel_to_abs(&dx, &dy); 954 arc_to(rx, ry, angle, large_arc_flag, sweep_flag, dx, dy); 955 } 956 957 //------------------------------------------------------------------------ 958 template<class VC> 959 void path_base<VC>::curve3(double x_ctrl, double y_ctrl, 960 double x_to, double y_to) 961 { 962 m_vertices.add_vertex(x_ctrl, y_ctrl, path_cmd_curve3); 963 m_vertices.add_vertex(x_to, y_to, path_cmd_curve3); 964 } 965 966 //------------------------------------------------------------------------ 967 template<class VC> 968 void path_base<VC>::curve3_rel(double dx_ctrl, double dy_ctrl, 969 double dx_to, double dy_to) 970 { 971 rel_to_abs(&dx_ctrl, &dy_ctrl); 972 rel_to_abs(&dx_to, &dy_to); 973 m_vertices.add_vertex(dx_ctrl, dy_ctrl, path_cmd_curve3); 974 m_vertices.add_vertex(dx_to, dy_to, path_cmd_curve3); 975 } 976 977 //------------------------------------------------------------------------ 978 template<class VC> 979 void path_base<VC>::curve3(double x_to, double y_to) 980 { 981 double x0; 982 double y0; 983 if(is_vertex(m_vertices.last_vertex(&x0, &y0))) 984 { 985 double x_ctrl; 986 double y_ctrl; 987 unsigned cmd = m_vertices.prev_vertex(&x_ctrl, &y_ctrl); 988 if(is_curve(cmd)) 989 { 990 x_ctrl = x0 + x0 - x_ctrl; 991 y_ctrl = y0 + y0 - y_ctrl; 992 } 993 else 994 { 995 x_ctrl = x0; 996 y_ctrl = y0; 997 } 998 curve3(x_ctrl, y_ctrl, x_to, y_to); 999 } 1000 } 1001 1002 //------------------------------------------------------------------------ 1003 template<class VC> 1004 void path_base<VC>::curve3_rel(double dx_to, double dy_to) 1005 { 1006 rel_to_abs(&dx_to, &dy_to); 1007 curve3(dx_to, dy_to); 1008 } 1009 1010 //------------------------------------------------------------------------ 1011 template<class VC> 1012 void path_base<VC>::curve4(double x_ctrl1, double y_ctrl1, 1013 double x_ctrl2, double y_ctrl2, 1014 double x_to, double y_to) 1015 { 1016 m_vertices.add_vertex(x_ctrl1, y_ctrl1, path_cmd_curve4); 1017 m_vertices.add_vertex(x_ctrl2, y_ctrl2, path_cmd_curve4); 1018 m_vertices.add_vertex(x_to, y_to, path_cmd_curve4); 1019 } 1020 1021 //------------------------------------------------------------------------ 1022 template<class VC> 1023 void path_base<VC>::curve4_rel(double dx_ctrl1, double dy_ctrl1, 1024 double dx_ctrl2, double dy_ctrl2, 1025 double dx_to, double dy_to) 1026 { 1027 rel_to_abs(&dx_ctrl1, &dy_ctrl1); 1028 rel_to_abs(&dx_ctrl2, &dy_ctrl2); 1029 rel_to_abs(&dx_to, &dy_to); 1030 m_vertices.add_vertex(dx_ctrl1, dy_ctrl1, path_cmd_curve4); 1031 m_vertices.add_vertex(dx_ctrl2, dy_ctrl2, path_cmd_curve4); 1032 m_vertices.add_vertex(dx_to, dy_to, path_cmd_curve4); 1033 } 1034 1035 //------------------------------------------------------------------------ 1036 template<class VC> 1037 void path_base<VC>::curve4(double x_ctrl2, double y_ctrl2, 1038 double x_to, double y_to) 1039 { 1040 double x0; 1041 double y0; 1042 if(is_vertex(last_vertex(&x0, &y0))) 1043 { 1044 double x_ctrl1; 1045 double y_ctrl1; 1046 unsigned cmd = prev_vertex(&x_ctrl1, &y_ctrl1); 1047 if(is_curve(cmd)) 1048 { 1049 x_ctrl1 = x0 + x0 - x_ctrl1; 1050 y_ctrl1 = y0 + y0 - y_ctrl1; 1051 } 1052 else 1053 { 1054 x_ctrl1 = x0; 1055 y_ctrl1 = y0; 1056 } 1057 curve4(x_ctrl1, y_ctrl1, x_ctrl2, y_ctrl2, x_to, y_to); 1058 } 1059 } 1060 1061 //------------------------------------------------------------------------ 1062 template<class VC> 1063 void path_base<VC>::curve4_rel(double dx_ctrl2, double dy_ctrl2, 1064 double dx_to, double dy_to) 1065 { 1066 rel_to_abs(&dx_ctrl2, &dy_ctrl2); 1067 rel_to_abs(&dx_to, &dy_to); 1068 curve4(dx_ctrl2, dy_ctrl2, dx_to, dy_to); 1069 } 1070 1071 //------------------------------------------------------------------------ 1072 template<class VC> 1073 inline void path_base<VC>::end_poly(unsigned flags) 1074 { 1075 if(is_vertex(m_vertices.last_command())) 1076 { 1077 m_vertices.add_vertex(0.0, 0.0, path_cmd_end_poly | flags); 1078 } 1079 } 1080 1081 //------------------------------------------------------------------------ 1082 template<class VC> 1083 inline void path_base<VC>::close_polygon(unsigned flags) 1084 { 1085 end_poly(path_flags_close | flags); 1086 } 1087 1088 //------------------------------------------------------------------------ 1089 template<class VC> 1090 inline unsigned path_base<VC>::total_vertices() const 1091 { 1092 return m_vertices.total_vertices(); 1093 } 1094 1095 //------------------------------------------------------------------------ 1096 template<class VC> 1097 inline unsigned path_base<VC>::last_vertex(double* x, double* y) const 1098 { 1099 return m_vertices.last_vertex(x, y); 1100 } 1101 1102 //------------------------------------------------------------------------ 1103 template<class VC> 1104 inline unsigned path_base<VC>::prev_vertex(double* x, double* y) const 1105 { 1106 return m_vertices.prev_vertex(x, y); 1107 } 1108 1109 //------------------------------------------------------------------------ 1110 template<class VC> 1111 inline double path_base<VC>::last_x() const 1112 { 1113 return m_vertices.last_x(); 1114 } 1115 1116 //------------------------------------------------------------------------ 1117 template<class VC> 1118 inline double path_base<VC>::last_y() const 1119 { 1120 return m_vertices.last_y(); 1121 } 1122 1123 //------------------------------------------------------------------------ 1124 template<class VC> 1125 inline unsigned path_base<VC>::vertex(unsigned idx, double* x, double* y) const 1126 { 1127 return m_vertices.vertex(idx, x, y); 1128 } 1129 1130 //------------------------------------------------------------------------ 1131 template<class VC> 1132 inline unsigned path_base<VC>::command(unsigned idx) const 1133 { 1134 return m_vertices.command(idx); 1135 } 1136 1137 //------------------------------------------------------------------------ 1138 template<class VC> 1139 void path_base<VC>::modify_vertex(unsigned idx, double x, double y) 1140 { 1141 m_vertices.modify_vertex(idx, x, y); 1142 } 1143 1144 //------------------------------------------------------------------------ 1145 template<class VC> 1146 void path_base<VC>::modify_vertex(unsigned idx, double x, double y, unsigned cmd) 1147 { 1148 m_vertices.modify_vertex(idx, x, y, cmd); 1149 } 1150 1151 //------------------------------------------------------------------------ 1152 template<class VC> 1153 void path_base<VC>::modify_command(unsigned idx, unsigned cmd) 1154 { 1155 m_vertices.modify_command(idx, cmd); 1156 } 1157 1158 //------------------------------------------------------------------------ 1159 template<class VC> 1160 inline void path_base<VC>::rewind(unsigned path_id) 1161 { 1162 m_iterator = path_id; 1163 } 1164 1165 //------------------------------------------------------------------------ 1166 template<class VC> 1167 inline unsigned path_base<VC>::vertex(double* x, double* y) 1168 { 1169 if(m_iterator >= m_vertices.total_vertices()) return path_cmd_stop; 1170 return m_vertices.vertex(m_iterator++, x, y); 1171 } 1172 1173 1174 //------------------------------------------------------------------------ 1175 template<class VC> 1176 unsigned path_base<VC>::perceive_polygon_orientation(unsigned start, 1177 unsigned end) 1178 { 1179 // Calculate signed area (double area to be exact) 1180 //--------------------- 1181 unsigned np = end - start; 1182 double area = 0.0; 1183 unsigned i; 1184 for(i = 0; i < np; i++) 1185 { 1186 double x1, y1, x2, y2; 1187 m_vertices.vertex(start + i, &x1, &y1); 1188 m_vertices.vertex(start + (i + 1) % np, &x2, &y2); 1189 area += x1 * y2 - y1 * x2; 1190 } 1191 return (area < 0.0) ? path_flags_cw : path_flags_ccw; 1192 } 1193 1194 1195 //------------------------------------------------------------------------ 1196 template<class VC> 1197 void path_base<VC>::invert_polygon(unsigned start, unsigned end) 1198 { 1199 unsigned i; 1200 unsigned tmp_cmd = m_vertices.command(start); 1201 1202 --end; // Make "end" inclusive 1203 1204 // Shift all commands to one position 1205 for(i = start; i < end; i++) 1206 { 1207 m_vertices.modify_command(i, m_vertices.command(i + 1)); 1208 } 1209 1210 // Assign starting command to the ending command 1211 m_vertices.modify_command(end, tmp_cmd); 1212 1213 // Reverse the polygon 1214 while(end > start) 1215 { 1216 m_vertices.swap_vertices(start++, end--); 1217 } 1218 } 1219 1220 //------------------------------------------------------------------------ 1221 template<class VC> 1222 void path_base<VC>::invert_polygon(unsigned start) 1223 { 1224 // Skip all non-vertices at the beginning 1225 while(start < m_vertices.total_vertices() && 1226 !is_vertex(m_vertices.command(start))) ++start; 1227 1228 // Skip all insignificant move_to 1229 while(start+1 < m_vertices.total_vertices() && 1230 is_move_to(m_vertices.command(start)) && 1231 is_move_to(m_vertices.command(start+1))) ++start; 1232 1233 // Find the last vertex 1234 unsigned end = start + 1; 1235 while(end < m_vertices.total_vertices() && 1236 !is_next_poly(m_vertices.command(end))) ++end; 1237 1238 invert_polygon(start, end); 1239 } 1240 1241 //------------------------------------------------------------------------ 1242 template<class VC> 1243 unsigned path_base<VC>::arrange_polygon_orientation(unsigned start, 1244 path_flags_e orientation) 1245 { 1246 if(orientation == path_flags_none) return start; 1247 1248 // Skip all non-vertices at the beginning 1249 while(start < m_vertices.total_vertices() && 1250 !is_vertex(m_vertices.command(start))) ++start; 1251 1252 // Skip all insignificant move_to 1253 while(start+1 < m_vertices.total_vertices() && 1254 is_move_to(m_vertices.command(start)) && 1255 is_move_to(m_vertices.command(start+1))) ++start; 1256 1257 // Find the last vertex 1258 unsigned end = start + 1; 1259 while(end < m_vertices.total_vertices() && 1260 !is_next_poly(m_vertices.command(end))) ++end; 1261 1262 if(end - start > 2) 1263 { 1264 if(perceive_polygon_orientation(start, end) != unsigned(orientation)) 1265 { 1266 // Invert polygon, set orientation flag, and skip all end_poly 1267 invert_polygon(start, end); 1268 unsigned cmd; 1269 while(end < m_vertices.total_vertices() && 1270 is_end_poly(cmd = m_vertices.command(end))) 1271 { 1272 m_vertices.modify_command(end++, set_orientation(cmd, orientation)); 1273 } 1274 } 1275 } 1276 return end; 1277 } 1278 1279 1280 //------------------------------------------------------------------------ 1281 template<class VC> 1282 unsigned path_base<VC>::arrange_orientations(unsigned start, 1283 path_flags_e orientation) 1284 { 1285 if(orientation != path_flags_none) 1286 { 1287 while(start < m_vertices.total_vertices()) 1288 { 1289 start = arrange_polygon_orientation(start, orientation); 1290 if(is_stop(m_vertices.command(start))) 1291 { 1292 ++start; 1293 break; 1294 } 1295 } 1296 } 1297 return start; 1298 } 1299 1300 1301 //------------------------------------------------------------------------ 1302 template<class VC> 1303 void path_base<VC>::arrange_orientations_all_paths(path_flags_e orientation) 1304 { 1305 if(orientation != path_flags_none) 1306 { 1307 unsigned start = 0; 1308 while(start < m_vertices.total_vertices()) 1309 { 1310 start = arrange_orientations(start, orientation); 1311 } 1312 } 1313 } 1314 1315 1316 //------------------------------------------------------------------------ 1317 template<class VC> 1318 void path_base<VC>::flip_x(double x1, double x2) 1319 { 1320 unsigned i; 1321 double x, y; 1322 for(i = 0; i < m_vertices.total_vertices(); i++) 1323 { 1324 unsigned cmd = m_vertices.vertex(i, &x, &y); 1325 if(is_vertex(cmd)) 1326 { 1327 m_vertices.modify_vertex(i, x2 - x + x1, y); 1328 } 1329 } 1330 } 1331 1332 1333 //------------------------------------------------------------------------ 1334 template<class VC> 1335 void path_base<VC>::flip_y(double y1, double y2) 1336 { 1337 unsigned i; 1338 double x, y; 1339 for(i = 0; i < m_vertices.total_vertices(); i++) 1340 { 1341 unsigned cmd = m_vertices.vertex(i, &x, &y); 1342 if(is_vertex(cmd)) 1343 { 1344 m_vertices.modify_vertex(i, x, y2 - y + y1); 1345 } 1346 } 1347 } 1348 1349 1350 1351 1352 1353 //-----------------------------------------------------vertex_stl_storage 1354 template<class Container> class vertex_stl_storage 1355 { 1356 public: 1357 typedef typename Container::value_type vertex_type; 1358 typedef typename vertex_type::value_type value_type; 1359 1360 void remove_all() { m_vertices.clear(); } 1361 void free_all() { m_vertices.clear(); } 1362 1363 void add_vertex(double x, double y, unsigned cmd) 1364 { 1365 m_vertices.push_back(vertex_type(value_type(x), 1366 value_type(y), 1367 int8u(cmd))); 1368 } 1369 1370 void modify_vertex(unsigned idx, double x, double y) 1371 { 1372 vertex_type& v = m_vertices[idx]; 1373 v.x = value_type(x); 1374 v.y = value_type(y); 1375 } 1376 1377 void modify_vertex(unsigned idx, double x, double y, unsigned cmd) 1378 { 1379 vertex_type& v = m_vertices[idx]; 1380 v.x = value_type(x); 1381 v.y = value_type(y); 1382 v.cmd = int8u(cmd); 1383 } 1384 1385 void modify_command(unsigned idx, unsigned cmd) 1386 { 1387 m_vertices[idx].cmd = int8u(cmd); 1388 } 1389 1390 void swap_vertices(unsigned v1, unsigned v2) 1391 { 1392 vertex_type t = m_vertices[v1]; 1393 m_vertices[v1] = m_vertices[v2]; 1394 m_vertices[v2] = t; 1395 } 1396 1397 unsigned last_command() const 1398 { 1399 return m_vertices.size() ? 1400 m_vertices[m_vertices.size() - 1].cmd : 1401 path_cmd_stop; 1402 } 1403 1404 unsigned last_vertex(double* x, double* y) const 1405 { 1406 if(m_vertices.size() == 0) 1407 { 1408 *x = *y = 0.0; 1409 return path_cmd_stop; 1410 } 1411 return vertex(m_vertices.size() - 1, x, y); 1412 } 1413 1414 unsigned prev_vertex(double* x, double* y) const 1415 { 1416 if(m_vertices.size() < 2) 1417 { 1418 *x = *y = 0.0; 1419 return path_cmd_stop; 1420 } 1421 return vertex(m_vertices.size() - 2, x, y); 1422 } 1423 1424 double last_x() const 1425 { 1426 return m_vertices.size() ? m_vertices[m_vertices.size() - 1].x : 0.0; 1427 } 1428 1429 double last_y() const 1430 { 1431 return m_vertices.size() ? m_vertices[m_vertices.size() - 1].y : 0.0; 1432 } 1433 1434 unsigned total_vertices() const 1435 { 1436 return m_vertices.size(); 1437 } 1438 1439 unsigned vertex(unsigned idx, double* x, double* y) const 1440 { 1441 const vertex_type& v = m_vertices[idx]; 1442 *x = v.x; 1443 *y = v.y; 1444 return v.cmd; 1445 } 1446 1447 unsigned command(unsigned idx) const 1448 { 1449 return m_vertices[idx].cmd; 1450 } 1451 1452 private: 1453 Container m_vertices; 1454 }; 1455 1456 //-----------------------------------------------------------path_storage 1457 typedef path_base<vertex_block_storage<double> > path_storage; 1458 1459 // Example of declarations path_storage with pod_bvector as a container 1460 //----------------------------------------------------------------------- 1461 //typedef path_base<vertex_stl_storage<pod_bvector<vertex_d> > > path_storage; 1462 1463} 1464 1465 1466 1467// Example of declarations path_storage with std::vector as a container 1468//--------------------------------------------------------------------------- 1469//#include <vector> 1470//namespace agg 1471//{ 1472// typedef path_base<vertex_stl_storage<std::vector<vertex_d> > > stl_path_storage; 1473//} 1474 1475 1476 1477 1478#endif 1479