vfs: check userland buffers before reading them.
[haiku.git] / headers / libs / agg / agg_path_storage.h
blob141d70466a092e9e360b5e085a7219885b102551
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 //----------------------------------------------------------------------------
16 #ifndef AGG_PATH_STORAGE_INCLUDED
17 #define AGG_PATH_STORAGE_INCLUDED
19 #include <string.h>
20 #include <math.h>
21 #include "agg_math.h"
22 #include "agg_array.h"
23 #include "agg_bezier_arc.h"
25 namespace agg
29 //----------------------------------------------------vertex_block_storage
30 template<class T, unsigned BlockShift=8, unsigned BlockPool=256>
31 class vertex_block_storage
33 public:
34 // Allocation parameters
35 enum block_scale_e
37 block_shift = BlockShift,
38 block_size = 1 << block_shift,
39 block_mask = block_size - 1,
40 block_pool = BlockPool
43 typedef T value_type;
44 typedef vertex_block_storage<T, BlockShift, BlockPool> self_type;
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);
51 void remove_all();
52 void free_all();
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);
60 unsigned last_command() const;
61 unsigned last_vertex(double* x, double* y) const;
62 unsigned prev_vertex(double* x, double* y) const;
64 double last_x() const;
65 double last_y() const;
67 unsigned total_vertices() const;
68 unsigned vertex(unsigned idx, double* x, double* y) const;
69 unsigned command(unsigned idx) const;
71 private:
72 void allocate_block(unsigned nb);
73 int8u* storage_ptrs(T** xy_ptr);
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;
84 //------------------------------------------------------------------------
85 template<class T, unsigned S, unsigned P>
86 void vertex_block_storage<T,S,P>::free_all()
88 if(m_total_blocks)
90 T** coord_blk = m_coord_blocks + m_total_blocks - 1;
91 while(m_total_blocks--)
93 pod_allocator<T>::deallocate(
94 *coord_blk,
95 block_size * 2 +
96 block_size / (sizeof(T) / sizeof(unsigned char)));
97 --coord_blk;
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;
108 //------------------------------------------------------------------------
109 template<class T, unsigned S, unsigned P>
110 vertex_block_storage<T,S,P>::~vertex_block_storage()
112 free_all();
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)
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)
135 *this = v;
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)
143 remove_all();
144 unsigned i;
145 for(i = 0; i < v.total_vertices(); i++)
147 double x, y;
148 unsigned cmd = v.vertex(i, &x, &y);
149 add_vertex(x, y, cmd);
151 return *this;
154 //------------------------------------------------------------------------
155 template<class T, unsigned S, unsigned P>
156 inline void vertex_block_storage<T,S,P>::remove_all()
158 m_total_vertices = 0;
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)
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++;
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)
178 T* pv = m_coord_blocks[idx >> block_shift] + ((idx & block_mask) << 1);
179 pv[0] = T(x);
180 pv[1] = T(y);
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)
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;
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)
202 m_cmd_blocks[idx >> block_shift][idx & block_mask] = (int8u)cmd;
205 //------------------------------------------------------------------------
206 template<class T, unsigned S, unsigned P>
207 inline void vertex_block_storage<T,S,P>::swap_vertices(unsigned v1, unsigned v2)
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;
223 //------------------------------------------------------------------------
224 template<class T, unsigned S, unsigned P>
225 inline unsigned vertex_block_storage<T,S,P>::last_command() const
227 if(m_total_vertices) return command(m_total_vertices - 1);
228 return path_cmd_stop;
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
235 if(m_total_vertices) return vertex(m_total_vertices - 1, x, y);
236 return path_cmd_stop;
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
243 if(m_total_vertices > 1) return vertex(m_total_vertices - 2, x, y);
244 return path_cmd_stop;
247 //------------------------------------------------------------------------
248 template<class T, unsigned S, unsigned P>
249 inline double vertex_block_storage<T,S,P>::last_x() const
251 if(m_total_vertices)
253 unsigned idx = m_total_vertices - 1;
254 return m_coord_blocks[idx >> block_shift][(idx & block_mask) << 1];
256 return 0.0;
259 //------------------------------------------------------------------------
260 template<class T, unsigned S, unsigned P>
261 inline double vertex_block_storage<T,S,P>::last_y() const
263 if(m_total_vertices)
265 unsigned idx = m_total_vertices - 1;
266 return m_coord_blocks[idx >> block_shift][((idx & block_mask) << 1) + 1];
268 return 0.0;
271 //------------------------------------------------------------------------
272 template<class T, unsigned S, unsigned P>
273 inline unsigned vertex_block_storage<T,S,P>::total_vertices() const
275 return m_total_vertices;
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
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];
290 //------------------------------------------------------------------------
291 template<class T, unsigned S, unsigned P>
292 inline unsigned vertex_block_storage<T,S,P>::command(unsigned idx) const
294 return m_cmd_blocks[idx >> block_shift][idx & block_mask];
297 //------------------------------------------------------------------------
298 template<class T, unsigned S, unsigned P>
299 void vertex_block_storage<T,S,P>::allocate_block(unsigned nb)
301 if(nb >= m_max_blocks)
303 T** new_coords =
304 pod_allocator<T*>::allocate((m_max_blocks + block_pool) * 2);
306 unsigned char** new_cmds =
307 (unsigned char**)(new_coords + m_max_blocks + block_pool);
309 if(m_coord_blocks)
311 memcpy(new_coords,
312 m_coord_blocks,
313 m_max_blocks * sizeof(T*));
315 memcpy(new_cmds,
316 m_cmd_blocks,
317 m_max_blocks * sizeof(unsigned char*));
319 pod_allocator<T*>::deallocate(m_coord_blocks, m_max_blocks * 2);
321 m_coord_blocks = new_coords;
322 m_cmd_blocks = new_cmds;
323 m_max_blocks += block_pool;
325 m_coord_blocks[nb] =
326 pod_allocator<T>::allocate(block_size * 2 +
327 block_size / (sizeof(T) / sizeof(unsigned char)));
329 m_cmd_blocks[nb] =
330 (unsigned char*)(m_coord_blocks[nb] + block_size * 2);
332 m_total_blocks++;
335 //------------------------------------------------------------------------
336 template<class T, unsigned S, unsigned P>
337 int8u* vertex_block_storage<T,S,P>::storage_ptrs(T** xy_ptr)
339 unsigned nb = m_total_vertices >> block_shift;
340 if(nb >= m_total_blocks)
342 allocate_block(nb);
344 *xy_ptr = m_coord_blocks[nb] + ((m_total_vertices & block_mask) << 1);
345 return m_cmd_blocks[nb] + (m_total_vertices & block_mask);
351 //-----------------------------------------------------poly_plain_adaptor
352 template<class T> class poly_plain_adaptor
354 public:
355 typedef T value_type;
357 poly_plain_adaptor() :
358 m_data(0),
359 m_ptr(0),
360 m_end(0),
361 m_closed(false),
362 m_stop(false)
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)
373 void init(const T* data, unsigned num_points, bool closed)
375 m_data = data;
376 m_ptr = data;
377 m_end = data + num_points * 2;
378 m_closed = closed;
379 m_stop = false;
382 void rewind(unsigned)
384 m_ptr = m_data;
385 m_stop = false;
388 unsigned vertex(double* x, double* y)
390 if(m_ptr < m_end)
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;
397 *x = *y = 0.0;
398 if(m_closed && !m_stop)
400 m_stop = true;
401 return path_cmd_end_poly | path_flags_close;
403 return path_cmd_stop;
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;
418 //-------------------------------------------------poly_container_adaptor
419 template<class Container> class poly_container_adaptor
421 public:
422 typedef typename Container::value_type vertex_type;
424 poly_container_adaptor() :
425 m_container(0),
426 m_index(0),
427 m_closed(false),
428 m_stop(false)
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)
438 void init(const Container& data, bool closed)
440 m_container = &data;
441 m_index = 0;
442 m_closed = closed;
443 m_stop = false;
446 void rewind(unsigned)
448 m_index = 0;
449 m_stop = false;
452 unsigned vertex(double* x, double* y)
454 if(m_index < m_container->size())
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;
462 *x = *y = 0.0;
463 if(m_closed && !m_stop)
465 m_stop = true;
466 return path_cmd_end_poly | path_flags_close;
468 return path_cmd_stop;
471 private:
472 const Container* m_container;
473 unsigned m_index;
474 bool m_closed;
475 bool m_stop;
480 //-----------------------------------------poly_container_reverse_adaptor
481 template<class Container> class poly_container_reverse_adaptor
483 public:
484 typedef typename Container::value_type vertex_type;
486 poly_container_reverse_adaptor() :
487 m_container(0),
488 m_index(-1),
489 m_closed(false),
490 m_stop(false)
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)
500 void init(const Container& data, bool closed)
502 m_container = &data;
503 m_index = m_container->size() - 1;
504 m_closed = closed;
505 m_stop = false;
508 void rewind(unsigned)
510 m_index = m_container->size() - 1;
511 m_stop = false;
514 unsigned vertex(double* x, double* y)
516 if(m_index >= 0)
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;
524 *x = *y = 0.0;
525 if(m_closed && !m_stop)
527 m_stop = true;
528 return path_cmd_end_poly | path_flags_close;
530 return path_cmd_stop;
533 private:
534 const Container* m_container;
535 int m_index;
536 bool m_closed;
537 bool m_stop;
544 //--------------------------------------------------------line_adaptor
545 class line_adaptor
547 public:
548 typedef double value_type;
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)
554 m_coord[0] = x1;
555 m_coord[1] = y1;
556 m_coord[2] = x2;
557 m_coord[3] = y2;
560 void init(double x1, double y1, double x2, double y2)
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);
569 void rewind(unsigned)
571 m_line.rewind(0);
574 unsigned vertex(double* x, double* y)
576 return m_line.vertex(x, y);
579 private:
580 double m_coord[4];
581 poly_plain_adaptor<double> m_line;
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.
606 // See also: vertex_source concept
607 //------------------------------------------------------------------------
608 template<class VertexContainer> class path_base
610 public:
611 typedef VertexContainer container_type;
612 typedef path_base<VertexContainer> self_type;
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; }
619 // Make path functions
620 //--------------------------------------------------------------------
621 unsigned start_new_path();
623 void move_to(double x, double y);
624 void move_rel(double dx, double dy);
626 void line_to(double x, double y);
627 void line_rel(double dx, double dy);
629 void hline_to(double x);
630 void hline_rel(double dx);
632 void vline_to(double y);
633 void vline_rel(double dy);
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);
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);
647 void curve3(double x_ctrl, double y_ctrl,
648 double x_to, double y_to);
650 void curve3_rel(double dx_ctrl, double dy_ctrl,
651 double dx_to, double dy_to);
653 void curve3(double x_to, double y_to);
655 void curve3_rel(double dx_to, double dy_to);
657 void curve4(double x_ctrl1, double y_ctrl1,
658 double x_ctrl2, double y_ctrl2,
659 double x_to, double y_to);
661 void curve4_rel(double dx_ctrl1, double dy_ctrl1,
662 double dx_ctrl2, double dy_ctrl2,
663 double dx_to, double dy_to);
665 void curve4(double x_ctrl2, double y_ctrl2,
666 double x_to, double y_to);
668 void curve4_rel(double x_ctrl2, double y_ctrl2,
669 double x_to, double y_to);
672 void end_poly(unsigned flags = path_flags_close);
673 void close_polygon(unsigned flags = path_flags_none);
675 // Accessors
676 //--------------------------------------------------------------------
677 const container_type& vertices() const { return m_vertices; }
678 container_type& vertices() { return m_vertices; }
680 unsigned total_vertices() const;
682 void rel_to_abs(double* x, double* y) const;
684 unsigned last_vertex(double* x, double* y) const;
685 unsigned prev_vertex(double* x, double* y) const;
687 double last_x() const;
688 double last_y() const;
690 unsigned vertex(unsigned idx, double* x, double* y) const;
691 unsigned command(unsigned idx) const;
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);
697 // VertexSource interface
698 //--------------------------------------------------------------------
699 void rewind(unsigned path_id);
700 unsigned vertex(double* x, double* y);
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);
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);
718 // Concatenate path. The path is added as is.
719 //--------------------------------------------------------------------
720 template<class VertexSource>
721 void concat_path(VertexSource& vs, unsigned path_id = 0)
723 double x, y;
724 unsigned cmd;
725 vs.rewind(path_id);
726 while(!is_stop(cmd = vs.vertex(&x, &y)))
728 m_vertices.add_vertex(x, y, cmd);
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)
738 double x, y;
739 unsigned cmd;
740 vs.rewind(path_id);
741 cmd = vs.vertex(&x, &y);
742 if(!is_stop(cmd))
744 if(is_vertex(cmd))
746 double x0, y0;
747 unsigned cmd0 = last_vertex(&x0, &y0);
748 if(is_vertex(cmd0))
750 if(calc_distance(x, y, x0, y0) > vertex_dist_epsilon)
752 if(is_move_to(cmd)) cmd = path_cmd_line_to;
753 m_vertices.add_vertex(x, y, cmd);
756 else
758 if(is_stop(cmd0))
760 cmd = path_cmd_move_to;
762 else
764 if(is_move_to(cmd)) cmd = path_cmd_line_to;
766 m_vertices.add_vertex(x, y, cmd);
769 while(!is_stop(cmd = vs.vertex(&x, &y)))
771 m_vertices.add_vertex(x, y, is_move_to(cmd) ?
772 path_cmd_line_to :
773 cmd);
778 // Concatenate polygon/polyline.
779 //--------------------------------------------------------------------
780 template<class T> void concat_poly(const T* data,
781 unsigned num_points,
782 bool closed)
784 poly_plain_adaptor<T> poly(data, num_points, closed);
785 concat_path(poly);
788 // Join polygon/polyline continuously.
789 //--------------------------------------------------------------------
790 template<class T> void join_poly(const T* data,
791 unsigned num_points,
792 bool closed)
794 poly_plain_adaptor<T> poly(data, num_points, closed);
795 join_path(poly);
799 private:
800 unsigned perceive_polygon_orientation(unsigned start, unsigned end);
801 void invert_polygon(unsigned start, unsigned end);
803 VertexContainer m_vertices;
804 unsigned m_iterator;
807 //------------------------------------------------------------------------
808 template<class VC>
809 unsigned path_base<VC>::start_new_path()
811 if(!is_stop(m_vertices.last_command()))
813 m_vertices.add_vertex(0.0, 0.0, path_cmd_stop);
815 return m_vertices.total_vertices();
819 //------------------------------------------------------------------------
820 template<class VC>
821 inline void path_base<VC>::rel_to_abs(double* x, double* y) const
823 if(m_vertices.total_vertices())
825 double x2;
826 double y2;
827 if(is_vertex(m_vertices.last_vertex(&x2, &y2)))
829 *x += x2;
830 *y += y2;
835 //------------------------------------------------------------------------
836 template<class VC>
837 inline void path_base<VC>::move_to(double x, double y)
839 m_vertices.add_vertex(x, y, path_cmd_move_to);
842 //------------------------------------------------------------------------
843 template<class VC>
844 inline void path_base<VC>::move_rel(double dx, double dy)
846 rel_to_abs(&dx, &dy);
847 m_vertices.add_vertex(dx, dy, path_cmd_move_to);
850 //------------------------------------------------------------------------
851 template<class VC>
852 inline void path_base<VC>::line_to(double x, double y)
854 m_vertices.add_vertex(x, y, path_cmd_line_to);
857 //------------------------------------------------------------------------
858 template<class VC>
859 inline void path_base<VC>::line_rel(double dx, double dy)
861 rel_to_abs(&dx, &dy);
862 m_vertices.add_vertex(dx, dy, path_cmd_line_to);
865 //------------------------------------------------------------------------
866 template<class VC>
867 inline void path_base<VC>::hline_to(double x)
869 m_vertices.add_vertex(x, last_y(), path_cmd_line_to);
872 //------------------------------------------------------------------------
873 template<class VC>
874 inline void path_base<VC>::hline_rel(double dx)
876 double dy = 0;
877 rel_to_abs(&dx, &dy);
878 m_vertices.add_vertex(dx, dy, path_cmd_line_to);
881 //------------------------------------------------------------------------
882 template<class VC>
883 inline void path_base<VC>::vline_to(double y)
885 m_vertices.add_vertex(last_x(), y, path_cmd_line_to);
888 //------------------------------------------------------------------------
889 template<class VC>
890 inline void path_base<VC>::vline_rel(double dy)
892 double dx = 0;
893 rel_to_abs(&dx, &dy);
894 m_vertices.add_vertex(dx, dy, path_cmd_line_to);
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)
905 if(m_vertices.total_vertices() && is_vertex(m_vertices.last_command()))
907 const double epsilon = 1e-30;
908 double x0 = 0.0;
909 double y0 = 0.0;
910 m_vertices.last_vertex(&x0, &y0);
912 rx = fabs(rx);
913 ry = fabs(ry);
915 // Ensure radii are valid
916 //-------------------------
917 if(rx < epsilon || ry < epsilon)
919 line_to(x, y);
920 return;
923 if(calc_distance(x0, y0, x, y) < epsilon)
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;
929 bezier_arc_svg a(x0, y0, rx, ry, angle, large_arc_flag, sweep_flag, x, y);
930 if(a.radii_ok())
932 join_path(a);
934 else
936 line_to(x, y);
939 else
941 move_to(x, y);
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)
953 rel_to_abs(&dx, &dy);
954 arc_to(rx, ry, angle, large_arc_flag, sweep_flag, dx, dy);
957 //------------------------------------------------------------------------
958 template<class VC>
959 void path_base<VC>::curve3(double x_ctrl, double y_ctrl,
960 double x_to, double y_to)
962 m_vertices.add_vertex(x_ctrl, y_ctrl, path_cmd_curve3);
963 m_vertices.add_vertex(x_to, y_to, path_cmd_curve3);
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)
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);
977 //------------------------------------------------------------------------
978 template<class VC>
979 void path_base<VC>::curve3(double x_to, double y_to)
981 double x0;
982 double y0;
983 if(is_vertex(m_vertices.last_vertex(&x0, &y0)))
985 double x_ctrl;
986 double y_ctrl;
987 unsigned cmd = m_vertices.prev_vertex(&x_ctrl, &y_ctrl);
988 if(is_curve(cmd))
990 x_ctrl = x0 + x0 - x_ctrl;
991 y_ctrl = y0 + y0 - y_ctrl;
993 else
995 x_ctrl = x0;
996 y_ctrl = y0;
998 curve3(x_ctrl, y_ctrl, x_to, y_to);
1002 //------------------------------------------------------------------------
1003 template<class VC>
1004 void path_base<VC>::curve3_rel(double dx_to, double dy_to)
1006 rel_to_abs(&dx_to, &dy_to);
1007 curve3(dx_to, dy_to);
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)
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);
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)
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);
1035 //------------------------------------------------------------------------
1036 template<class VC>
1037 void path_base<VC>::curve4(double x_ctrl2, double y_ctrl2,
1038 double x_to, double y_to)
1040 double x0;
1041 double y0;
1042 if(is_vertex(last_vertex(&x0, &y0)))
1044 double x_ctrl1;
1045 double y_ctrl1;
1046 unsigned cmd = prev_vertex(&x_ctrl1, &y_ctrl1);
1047 if(is_curve(cmd))
1049 x_ctrl1 = x0 + x0 - x_ctrl1;
1050 y_ctrl1 = y0 + y0 - y_ctrl1;
1052 else
1054 x_ctrl1 = x0;
1055 y_ctrl1 = y0;
1057 curve4(x_ctrl1, y_ctrl1, x_ctrl2, y_ctrl2, x_to, y_to);
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)
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);
1071 //------------------------------------------------------------------------
1072 template<class VC>
1073 inline void path_base<VC>::end_poly(unsigned flags)
1075 if(is_vertex(m_vertices.last_command()))
1077 m_vertices.add_vertex(0.0, 0.0, path_cmd_end_poly | flags);
1081 //------------------------------------------------------------------------
1082 template<class VC>
1083 inline void path_base<VC>::close_polygon(unsigned flags)
1085 end_poly(path_flags_close | flags);
1088 //------------------------------------------------------------------------
1089 template<class VC>
1090 inline unsigned path_base<VC>::total_vertices() const
1092 return m_vertices.total_vertices();
1095 //------------------------------------------------------------------------
1096 template<class VC>
1097 inline unsigned path_base<VC>::last_vertex(double* x, double* y) const
1099 return m_vertices.last_vertex(x, y);
1102 //------------------------------------------------------------------------
1103 template<class VC>
1104 inline unsigned path_base<VC>::prev_vertex(double* x, double* y) const
1106 return m_vertices.prev_vertex(x, y);
1109 //------------------------------------------------------------------------
1110 template<class VC>
1111 inline double path_base<VC>::last_x() const
1113 return m_vertices.last_x();
1116 //------------------------------------------------------------------------
1117 template<class VC>
1118 inline double path_base<VC>::last_y() const
1120 return m_vertices.last_y();
1123 //------------------------------------------------------------------------
1124 template<class VC>
1125 inline unsigned path_base<VC>::vertex(unsigned idx, double* x, double* y) const
1127 return m_vertices.vertex(idx, x, y);
1130 //------------------------------------------------------------------------
1131 template<class VC>
1132 inline unsigned path_base<VC>::command(unsigned idx) const
1134 return m_vertices.command(idx);
1137 //------------------------------------------------------------------------
1138 template<class VC>
1139 void path_base<VC>::modify_vertex(unsigned idx, double x, double y)
1141 m_vertices.modify_vertex(idx, x, y);
1144 //------------------------------------------------------------------------
1145 template<class VC>
1146 void path_base<VC>::modify_vertex(unsigned idx, double x, double y, unsigned cmd)
1148 m_vertices.modify_vertex(idx, x, y, cmd);
1151 //------------------------------------------------------------------------
1152 template<class VC>
1153 void path_base<VC>::modify_command(unsigned idx, unsigned cmd)
1155 m_vertices.modify_command(idx, cmd);
1158 //------------------------------------------------------------------------
1159 template<class VC>
1160 inline void path_base<VC>::rewind(unsigned path_id)
1162 m_iterator = path_id;
1165 //------------------------------------------------------------------------
1166 template<class VC>
1167 inline unsigned path_base<VC>::vertex(double* x, double* y)
1169 if(m_iterator >= m_vertices.total_vertices()) return path_cmd_stop;
1170 return m_vertices.vertex(m_iterator++, x, y);
1174 //------------------------------------------------------------------------
1175 template<class VC>
1176 unsigned path_base<VC>::perceive_polygon_orientation(unsigned start,
1177 unsigned end)
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++)
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;
1191 return (area < 0.0) ? path_flags_cw : path_flags_ccw;
1195 //------------------------------------------------------------------------
1196 template<class VC>
1197 void path_base<VC>::invert_polygon(unsigned start, unsigned end)
1199 unsigned i;
1200 unsigned tmp_cmd = m_vertices.command(start);
1202 --end; // Make "end" inclusive
1204 // Shift all commands to one position
1205 for(i = start; i < end; i++)
1207 m_vertices.modify_command(i, m_vertices.command(i + 1));
1210 // Assign starting command to the ending command
1211 m_vertices.modify_command(end, tmp_cmd);
1213 // Reverse the polygon
1214 while(end > start)
1216 m_vertices.swap_vertices(start++, end--);
1220 //------------------------------------------------------------------------
1221 template<class VC>
1222 void path_base<VC>::invert_polygon(unsigned start)
1224 // Skip all non-vertices at the beginning
1225 while(start < m_vertices.total_vertices() &&
1226 !is_vertex(m_vertices.command(start))) ++start;
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;
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;
1238 invert_polygon(start, end);
1241 //------------------------------------------------------------------------
1242 template<class VC>
1243 unsigned path_base<VC>::arrange_polygon_orientation(unsigned start,
1244 path_flags_e orientation)
1246 if(orientation == path_flags_none) return start;
1248 // Skip all non-vertices at the beginning
1249 while(start < m_vertices.total_vertices() &&
1250 !is_vertex(m_vertices.command(start))) ++start;
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;
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;
1262 if(end - start > 2)
1264 if(perceive_polygon_orientation(start, end) != unsigned(orientation))
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)))
1272 m_vertices.modify_command(end++, set_orientation(cmd, orientation));
1276 return end;
1280 //------------------------------------------------------------------------
1281 template<class VC>
1282 unsigned path_base<VC>::arrange_orientations(unsigned start,
1283 path_flags_e orientation)
1285 if(orientation != path_flags_none)
1287 while(start < m_vertices.total_vertices())
1289 start = arrange_polygon_orientation(start, orientation);
1290 if(is_stop(m_vertices.command(start)))
1292 ++start;
1293 break;
1297 return start;
1301 //------------------------------------------------------------------------
1302 template<class VC>
1303 void path_base<VC>::arrange_orientations_all_paths(path_flags_e orientation)
1305 if(orientation != path_flags_none)
1307 unsigned start = 0;
1308 while(start < m_vertices.total_vertices())
1310 start = arrange_orientations(start, orientation);
1316 //------------------------------------------------------------------------
1317 template<class VC>
1318 void path_base<VC>::flip_x(double x1, double x2)
1320 unsigned i;
1321 double x, y;
1322 for(i = 0; i < m_vertices.total_vertices(); i++)
1324 unsigned cmd = m_vertices.vertex(i, &x, &y);
1325 if(is_vertex(cmd))
1327 m_vertices.modify_vertex(i, x2 - x + x1, y);
1333 //------------------------------------------------------------------------
1334 template<class VC>
1335 void path_base<VC>::flip_y(double y1, double y2)
1337 unsigned i;
1338 double x, y;
1339 for(i = 0; i < m_vertices.total_vertices(); i++)
1341 unsigned cmd = m_vertices.vertex(i, &x, &y);
1342 if(is_vertex(cmd))
1344 m_vertices.modify_vertex(i, x, y2 - y + y1);
1353 //-----------------------------------------------------vertex_stl_storage
1354 template<class Container> class vertex_stl_storage
1356 public:
1357 typedef typename Container::value_type vertex_type;
1358 typedef typename vertex_type::value_type value_type;
1360 void remove_all() { m_vertices.clear(); }
1361 void free_all() { m_vertices.clear(); }
1363 void add_vertex(double x, double y, unsigned cmd)
1365 m_vertices.push_back(vertex_type(value_type(x),
1366 value_type(y),
1367 int8u(cmd)));
1370 void modify_vertex(unsigned idx, double x, double y)
1372 vertex_type& v = m_vertices[idx];
1373 v.x = value_type(x);
1374 v.y = value_type(y);
1377 void modify_vertex(unsigned idx, double x, double y, unsigned cmd)
1379 vertex_type& v = m_vertices[idx];
1380 v.x = value_type(x);
1381 v.y = value_type(y);
1382 v.cmd = int8u(cmd);
1385 void modify_command(unsigned idx, unsigned cmd)
1387 m_vertices[idx].cmd = int8u(cmd);
1390 void swap_vertices(unsigned v1, unsigned v2)
1392 vertex_type t = m_vertices[v1];
1393 m_vertices[v1] = m_vertices[v2];
1394 m_vertices[v2] = t;
1397 unsigned last_command() const
1399 return m_vertices.size() ?
1400 m_vertices[m_vertices.size() - 1].cmd :
1401 path_cmd_stop;
1404 unsigned last_vertex(double* x, double* y) const
1406 if(m_vertices.size() == 0)
1408 *x = *y = 0.0;
1409 return path_cmd_stop;
1411 return vertex(m_vertices.size() - 1, x, y);
1414 unsigned prev_vertex(double* x, double* y) const
1416 if(m_vertices.size() < 2)
1418 *x = *y = 0.0;
1419 return path_cmd_stop;
1421 return vertex(m_vertices.size() - 2, x, y);
1424 double last_x() const
1426 return m_vertices.size() ? m_vertices[m_vertices.size() - 1].x : 0.0;
1429 double last_y() const
1431 return m_vertices.size() ? m_vertices[m_vertices.size() - 1].y : 0.0;
1434 unsigned total_vertices() const
1436 return m_vertices.size();
1439 unsigned vertex(unsigned idx, double* x, double* y) const
1441 const vertex_type& v = m_vertices[idx];
1442 *x = v.x;
1443 *y = v.y;
1444 return v.cmd;
1447 unsigned command(unsigned idx) const
1449 return m_vertices[idx].cmd;
1452 private:
1453 Container m_vertices;
1456 //-----------------------------------------------------------path_storage
1457 typedef path_base<vertex_block_storage<double> > path_storage;
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;
1467 // Example of declarations path_storage with std::vector as a container
1468 //---------------------------------------------------------------------------
1469 //#include <vector>
1470 //namespace agg
1472 // typedef path_base<vertex_stl_storage<std::vector<vertex_d> > > stl_path_storage;
1478 #endif