switched to inline heaps
[swftools.git] / lib / art / art_vpath.c
1 /* Libart_LGPL - library of basic graphic primitives
2  * Copyright (C) 1998-2000 Raph Levien
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Library General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Library General Public License for more details.
13  *
14  * You should have received a copy of the GNU Library General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19
20 /* Basic constructors and operations for vector paths */
21
22 #include "config.h"
23 #include "art_vpath.h"
24
25 #include <math.h>
26 #include <stdlib.h>
27
28 #include "art_misc.h"
29
30 #include "art_rect.h"
31
32 /**
33  * art_vpath_add_point: Add point to vpath.
34  * @p_vpath: Where the pointer to the #ArtVpath structure is stored.
35  * @pn_points: Pointer to the number of points in *@p_vpath.
36  * @pn_points_max: Pointer to the number of points allocated.
37  * @code: The pathcode for the new point.
38  * @x: The X coordinate of the new point.
39  * @y: The Y coordinate of the new point.
40  *
41  * Adds a new point to *@p_vpath, reallocating and updating *@p_vpath
42  * and *@pn_points_max as necessary. *@pn_points is incremented.
43  *
44  * This routine always adds the point after all points already in the
45  * vpath. Thus, it should be called in the order the points are
46  * desired.
47  **/
48 void
49 art_vpath_add_point (ArtVpath **p_vpath, int *pn_points, int *pn_points_max,
50                      ArtPathcode code, double x, double y)
51 {
52   int i;
53
54   i = (*pn_points)++;
55   if (i == *pn_points_max)
56     art_expand (*p_vpath, ArtVpath, *pn_points_max);
57   (*p_vpath)[i].code = code;
58   (*p_vpath)[i].x = x;
59   (*p_vpath)[i].y = y;
60 }
61
62 /* number of steps should really depend on radius. */
63 #define CIRCLE_STEPS 128
64
65 /**
66  * art_vpath_new_circle: Create a new circle.
67  * @x: X coordinate of center.
68  * @y: Y coordinate of center.
69  * @r: radius.
70  *
71  * Creates a new polygon closely approximating a circle with center
72  * (@x, @y) and radius @r. Currently, the number of points used in the
73  * approximation is fixed, but that will probably change.
74  *
75  * Return value: The newly created #ArtVpath.
76  **/
77 ArtVpath *
78 art_vpath_new_circle (double x, double y, double r)
79 {
80   int i;
81   ArtVpath *vec;
82   double theta;
83
84   vec = (ArtVpath*)art_new (ArtVpath, CIRCLE_STEPS + 2);
85
86   for (i = 0; i < CIRCLE_STEPS + 1; i++)
87     {
88       vec[i].code = i ? ART_LINETO : ART_MOVETO;
89       theta = (i & (CIRCLE_STEPS - 1)) * (M_PI * 2.0 / CIRCLE_STEPS);
90       vec[i].x = x + r * cos (theta);
91       vec[i].y = y - r * sin (theta);
92     }
93   vec[i].code = ART_END;
94
95   return vec;
96 }
97
98 /**
99  * art_vpath_affine_transform: Affine transform a vpath.
100  * @src: Source vpath to transform.
101  * @matrix: Affine transform.
102  *
103  * Computes the affine transform of the vpath, using @matrix as the
104  * transform. @matrix is stored in the same format as PostScript, ie.
105  * x' = @matrix[0] * x + @matrix[2] * y + @matrix[4]
106  * y' = @matrix[1] * x + @matrix[3] * y + @matrix[5]
107  *
108  * Return value: the newly allocated vpath resulting from the transform.
109 **/
110 ArtVpath *
111 art_vpath_affine_transform (const ArtVpath *src, const double matrix[6])
112 {
113   int i;
114   int size;
115   ArtVpath *xnew;
116   double x, y;
117
118   for (i = 0; src[i].code != ART_END; i++);
119   size = i;
120
121   xnew = (ArtVpath*)art_new (ArtVpath, size + 1);
122
123   for (i = 0; i < size; i++)
124     {
125       xnew[i].code = src[i].code;
126       x = src[i].x;
127       y = src[i].y;
128       xnew[i].x = matrix[0] * x + matrix[2] * y + matrix[4];
129       xnew[i].y = matrix[1] * x + matrix[3] * y + matrix[5];
130     }
131   xnew[i].code = ART_END;
132
133   return xnew;
134 }
135
136 /**
137  * art_vpath_bbox_drect: Determine bounding box of vpath.
138  * @vec: Source vpath.
139  * @drect: Where to store bounding box.
140  *
141  * Determines bounding box of @vec, and stores it in @drect.
142  **/
143 void
144 art_vpath_bbox_drect (const ArtVpath *vec, ArtDRect *drect)
145 {
146   int i;
147   double x0, y0, x1, y1;
148
149   if (vec[0].code == ART_END)
150     {
151       x0 = y0 = x1 = y1 = 0;
152     }
153   else
154     {
155       x0 = x1 = vec[0].x;
156       y0 = y1 = vec[0].y;
157       for (i = 1; vec[i].code != ART_END; i++)
158         {
159           if (vec[i].x < x0) x0 = vec[i].x;
160           if (vec[i].x > x1) x1 = vec[i].x;
161           if (vec[i].y < y0) y0 = vec[i].y;
162           if (vec[i].y > y1) y1 = vec[i].y;
163         }
164     }
165   drect->x0 = x0;
166   drect->y0 = y0;
167   drect->x1 = x1;
168   drect->y1 = y1;
169 }
170
171 /**
172  * art_vpath_bbox_irect: Determine integer bounding box of vpath.
173  * @vec: Source vpath.
174  * idrect: Where to store bounding box.
175  *
176  * Determines integer bounding box of @vec, and stores it in @irect.
177  **/
178 void
179 art_vpath_bbox_irect (const ArtVpath *vec, ArtIRect *irect)
180 {
181   ArtDRect drect;
182
183   art_vpath_bbox_drect (vec, &drect);
184   art_drect_to_irect (irect, &drect);
185 }
186
187 #define PERTURBATION 2e-3
188
189 /**
190  * art_vpath_perturb: Perturb each point in vpath by small random amount.
191  * @src: Source vpath.
192  *
193  * Perturbs each of the points by a small random amount. This is
194  * helpful for cheating in cases when algorithms haven't attained
195  * numerical stability yet.
196  *
197  * Return value: Newly allocated vpath containing perturbed @src.
198  **/ 
199 ArtVpath *
200 art_vpath_perturb (ArtVpath *src)
201 {
202   int i;
203   int size;
204   ArtVpath *xnew;
205   double x, y;
206   double x_start, y_start;
207   int open;
208
209   for (i = 0; src[i].code != ART_END; i++);
210   size = i;
211
212   xnew = (ArtVpath*)art_new (ArtVpath, size + 1);
213
214   x_start = 0;
215   y_start = 0;
216   open = 0;
217   for (i = 0; i < size; i++)
218     {
219       xnew[i].code = src[i].code;
220       x = src[i].x + (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
221       y = src[i].y + (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
222       if (src[i].code == ART_MOVETO)
223         {
224           x_start = x;
225           y_start = y;
226           open = 0;
227         }
228       else if (src[i].code == ART_MOVETO_OPEN)
229         open = 1;
230       if (!open && (i + 1 == size || src[i + 1].code != ART_LINETO))
231         {
232           x = x_start;
233           y = y_start;
234         }
235       xnew[i].x = x;
236       xnew[i].y = y;
237     }
238   xnew[i].code = ART_END;
239
240   return xnew;
241 }