2 * Copyright (c) 1987, 1988, 1989 Stanford University
4 * Permission to use, copy, modify, distribute, and sell this software and its
5 * documentation for any purpose is hereby granted without fee, provided
6 * that the above copyright notice appear in all copies and that both that
7 * copyright notice and this permission notice appear in supporting
8 * documentation, and that the name of Stanford not be used in advertising or
9 * publicity pertaining to distribution of the software without specific,
10 * written prior permission. Stanford makes no representations about
11 * the suitability of this software for any purpose. It is provided "as is"
12 * without express or implied warranty.
14 * STANFORD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
15 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
16 * IN NO EVENT SHALL STANFORD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
17 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
18 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
19 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
20 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
23 /* This code came with the InterViews distribution, and was translated
24 from C++ to C by Matthieu Devin <devin@lucid.com> some time in 1992.
34 /* Lifted from InterViews */
35 #define SMOOTHNESS 1.0
38 static void no_more_memory (void);
39 static void grow_spline_points (spline* s);
40 static void mid_point (double x0, double y0, double x1, double y1,
41 double *mx, double *my);
42 static int can_approx_with_line (double x0, double y0, double x2,
43 double y2, double x3, double y3);
44 static void add_line (spline* s, double x0, double y0, double x1, double y1);
45 static void add_bezier_arc (spline* s,
46 double x0, double y0, double x1, double y1,
47 double x2, double y2, double x3, double y3);
48 static void third_point (double x0, double y0, double x1, double y1,
49 double *tx, double *ty);
50 static void calc_section (spline* s, double cminus1x, double cminus1y,
51 double cx, double cy, double cplus1x, double cplus1y,
52 double cplus2x, double cplus2y);
59 fprintf (stderr, "No more memory\n");
67 spline* s = (spline*)calloc (1, sizeof (spline));
71 s->control_x = (double*)calloc (s->n_controls, sizeof (double));
72 s->control_y = (double*)calloc (s->n_controls, sizeof (double));
75 s->allocated_points = s->n_controls;
76 s->points = (XPoint*)calloc (s->allocated_points, sizeof (XPoint));
78 if (!s->control_x || !s->control_y || !s->points)
85 grow_spline_points (s)
88 s->allocated_points *= 2;
90 (XPoint*)realloc (s->points, s->allocated_points * sizeof (XPoint));
97 mid_point (x0, y0, x1, y1, mx, my)
98 double x0, y0, x1, y1, *mx, *my;
100 *mx = (x0 + x1) / 2.0;
101 *my = (y0 + y1) / 2.0;
105 third_point (x0, y0, x1, y1, tx, ty)
106 double x0, y0, x1, y1, *tx, *ty;
108 *tx = (2 * x0 + x1) / 3.0;
109 *ty = (2 * y0 + y1) / 3.0;
113 can_approx_with_line (x0, y0, x2, y2, x3, y3)
114 double x0, y0, x2, y2, x3, y3;
116 double triangle_area, side_squared, dx, dy;
118 triangle_area = x0 * y2 - x2 * y0 + x2 * y3 - x3 * y2 + x3 * y0 - x0 * y3;
119 /* actually 4 times the area. */
120 triangle_area *= triangle_area;
123 side_squared = dx * dx + dy * dy;
124 return triangle_area <= SMOOTHNESS * side_squared;
128 add_line (s, x0, y0, x1, y1)
130 double x0, y0, x1, y1;
132 if (s->n_points >= s->allocated_points)
133 grow_spline_points (s);
135 if (s->n_points == 0)
137 s->points [s->n_points].x = x0;
138 s->points [s->n_points].y = y0;
141 s->points [s->n_points].x = x1;
142 s->points [s->n_points].y = y1;
147 add_bezier_arc (s, x0, y0, x1, y1, x2, y2, x3, y3)
149 double x0, y0, x1, y1, x2, y2, x3, y3;
151 double midx01, midx12, midx23, midlsegx, midrsegx, cx,
152 midy01, midy12, midy23, midlsegy, midrsegy, cy;
154 mid_point (x0, y0, x1, y1, &midx01, &midy01);
155 mid_point (x1, y1, x2, y2, &midx12, &midy12);
156 mid_point (x2, y2, x3, y3, &midx23, &midy23);
157 mid_point (midx01, midy01, midx12, midy12, &midlsegx, &midlsegy);
158 mid_point (midx12, midy12, midx23, midy23, &midrsegx, &midrsegy);
159 mid_point (midlsegx, midlsegy, midrsegx, midrsegy, &cx, &cy);
161 if (can_approx_with_line (x0, y0, midlsegx, midlsegy, cx, cy))
162 add_line (s, x0, y0, cx, cy);
163 else if ((midx01 != x1) || (midy01 != y1) || (midlsegx != x2)
164 || (midlsegy != y2) || (cx != x3) || (cy != y3))
165 add_bezier_arc (s, x0, y0, midx01, midy01, midlsegx, midlsegy, cx, cy);
167 if (can_approx_with_line (cx, cy, midx23, midy23, x3, y3))
168 add_line (s, cx, cy, x3, y3);
169 else if ((cx != x0) || (cy != y0) || (midrsegx != x1) || (midrsegy != y1)
170 || (midx23 != x2) || (midy23 != y2))
171 add_bezier_arc (s, cx, cy, midrsegx, midrsegy, midx23, midy23, x3, y3);
175 calc_section (s, cminus1x, cminus1y, cx, cy, cplus1x, cplus1y,
178 double cminus1x, cminus1y, cx, cy, cplus1x, cplus1y, cplus2x, cplus2y;
180 double p0x, p1x, p2x, p3x, tempx,
181 p0y, p1y, p2y, p3y, tempy;
183 third_point (cx, cy, cplus1x, cplus1y, &p1x, &p1y);
184 third_point (cplus1x, cplus1y, cx, cy, &p2x, &p2y);
185 third_point (cx, cy, cminus1x, cminus1y, &tempx, &tempy);
186 mid_point (tempx, tempy, p1x, p1y, &p0x, &p0y);
187 third_point (cplus1x, cplus1y, cplus2x, cplus2y, &tempx, &tempy);
188 mid_point (tempx, tempy, p2x, p2y, &p3x, &p3y);
189 add_bezier_arc (s, p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y);
199 if (s->n_controls < 3)
202 calc_section (s, s->control_x [0], s->control_y [0], s->control_x [0],
203 s->control_y [0], s->control_x [0], s->control_y [0],
204 s->control_x [1], s->control_y [1]);
205 calc_section (s, s->control_x [0], s->control_y [0], s->control_x [0],
206 s->control_y [0], s->control_x [1], s->control_y [1],
207 s->control_x [2], s->control_y [2]);
209 for (i = 1; i < s->n_controls - 2; i++)
210 calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
211 s->control_x [i], s->control_y [i],
212 s->control_x [i + 1], s->control_y [i + 1],
213 s->control_x [i + 2], s->control_y [i + 2]);
215 calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
216 s->control_x [i], s->control_y [i],
217 s->control_x [i + 1], s->control_y [i + 1],
218 s->control_x [i + 1], s->control_y [i + 1]);
219 calc_section (s, s->control_x [i], s->control_y [i],
220 s->control_x [i + 1], s->control_y [i + 1],
221 s->control_x [i + 1], s->control_y [i + 1],
222 s->control_x [i + 1], s->control_y [i + 1]);
226 compute_closed_spline (s)
232 if (s->n_controls < 3)
236 s->control_x [s->n_controls - 1],
237 s->control_y [s->n_controls - 1],
238 s->control_x [0], s->control_y [0],
239 s->control_x [1], s->control_y [1],
240 s->control_x [2], s->control_y [2]);
242 for (i = 1; i < s->n_controls - 2; i++)
243 calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
244 s->control_x [i], s->control_y [i],
245 s->control_x [i + 1], s->control_y [i + 1],
246 s->control_x [i + 2], s->control_y [i + 2]);
248 calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
249 s->control_x [i], s->control_y [i],
250 s->control_x [i + 1], s->control_y [i + 1],
251 s->control_x [0], s->control_y [0]);
252 calc_section (s, s->control_x [i], s->control_y [i],
253 s->control_x [i + 1], s->control_y [i + 1],
254 s->control_x [0], s->control_y [0],
255 s->control_x [1], s->control_y [1]);
264 while (s->allocated_points < s->n_controls + 1)
265 grow_spline_points (s);
267 for (i = 0; i < s->n_controls; i++)
269 s->points [i].x = s->control_x [i];
270 s->points [i].y = s->control_y [i];
272 s->points [s->n_controls].x = s->control_x [0];
273 s->points [s->n_controls].y = s->control_y [0];
274 s->n_points = s->n_controls + 1;
278 append_spline_points (s1, s2)
282 while (s1->allocated_points < s1->n_points + s2->n_points)
283 grow_spline_points (s1);
284 for (i = s1->n_points; i < s1->n_points + s2->n_points; i++)
286 s1->points [i].x = s2->points [i - s1->n_points].x;
287 s1->points [i].y = s2->points [i - s1->n_points].y;
289 s1->n_points = s1->n_points + s2->n_points;
293 spline_bounding_box (s, rectangle_out)
295 XRectangle* rectangle_out;
303 if (s->n_points == 0)
305 rectangle_out->x = 0;
306 rectangle_out->y = 0;
307 rectangle_out->width = 0;
308 rectangle_out->height = 0;
311 min_x = s->points [0].x;
313 min_y = s->points [0].y;
316 for (i = 1; i < s->n_points; i++)
318 if (s->points [i].x < min_x)
319 min_x = s->points [i].x;
320 if (s->points [i].x > max_x)
321 max_x = s->points [i].x;
322 if (s->points [i].y < min_y)
323 min_y = s->points [i].y;
324 if (s->points [i].y > max_y)
325 max_y = s->points [i].y;
327 rectangle_out->x = min_x;
328 rectangle_out->y = min_y;
329 rectangle_out->width = max_x - min_x;
330 rectangle_out->height = max_y - min_y;