1 /* Copyright (C) 2001-2017 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5 /* figure out the true bounding box of a vector image */
6
7 #ifdef HAVE_CONFIG_H
8 #include <config.h>
9 #endif
10
11 #include <math.h>
12 #include <stdlib.h>
13
14 #include "bbox.h"
15 #include "potracelib.h"
16 #include "lists.h"
17
18 /* ---------------------------------------------------------------------- */
19 /* intervals */
20
21 /* initialize the interval to [min, max] */
interval(interval_t * i,double min,double max)22 static void interval(interval_t *i, double min, double max) {
23 i->min = min;
24 i->max = max;
25 }
26
27 /* initialize the interval to [x, x] */
singleton(interval_t * i,double x)28 static inline void singleton(interval_t *i, double x) {
29 interval(i, x, x);
30 }
31
32 /* extend the interval to include the number x */
extend(interval_t * i,double x)33 static inline void extend(interval_t *i, double x) {
34 if (x < i->min) {
35 i->min = x;
36 } else if (x > i->max) {
37 i->max = x;
38 }
39 }
40
in_interval(interval_t * i,double x)41 static inline int in_interval(interval_t *i, double x) {
42 return i->min <= x && x <= i->max;
43 }
44
45 /* ---------------------------------------------------------------------- */
46 /* inner product */
47
48 typedef potrace_dpoint_t dpoint_t;
49
iprod(dpoint_t a,dpoint_t b)50 static double iprod(dpoint_t a, dpoint_t b) {
51 return a.x * b.x + a.y * b.y;
52 }
53
54 /* ---------------------------------------------------------------------- */
55 /* linear Bezier segments */
56
57 /* return a point on a 1-dimensional Bezier segment */
bezier(double t,double x0,double x1,double x2,double x3)58 static inline double bezier(double t, double x0, double x1, double x2, double x3) {
59 double s = 1-t;
60 return s*s*s*x0 + 3*(s*s*t)*x1 + 3*(t*t*s)*x2 + t*t*t*x3;
61 }
62
63 /* Extend the interval i to include the minimum and maximum of a
64 1-dimensional Bezier segment given by control points x0..x3. For
65 efficiency, x0 in i is assumed as a precondition. */
bezier_limits(double x0,double x1,double x2,double x3,interval_t * i)66 static void bezier_limits(double x0, double x1, double x2, double x3, interval_t *i) {
67 double a, b, c, d, r;
68 double t, x;
69
70 /* the min and max of a cubic curve segment are attained at one of
71 at most 4 critical points: the 2 endpoints and at most 2 local
72 extrema. We don't check the first endpoint, because all our
73 curves are cyclic so it's more efficient not to check endpoints
74 twice. */
75
76 /* endpoint */
77 extend(i, x3);
78
79 /* optimization: don't bother calculating extrema if all control
80 points are already in i */
81 if (in_interval(i, x1) && in_interval(i, x2)) {
82 return;
83 }
84
85 /* solve for extrema. at^2 + bt + c = 0 */
86 a = -3*x0 + 9*x1 - 9*x2 + 3*x3;
87 b = 6*x0 - 12*x1 + 6*x2;
88 c = -3*x0 + 3*x1;
89 d = b*b - 4*a*c;
90 if (d > 0) {
91 r = sqrt(d);
92 t = (-b-r)/(2*a);
93 if (t > 0 && t < 1) {
94 x = bezier(t, x0, x1, x2, x3);
95 extend(i, x);
96 }
97 t = (-b+r)/(2*a);
98 if (t > 0 && t < 1) {
99 x = bezier(t, x0, x1, x2, x3);
100 extend(i, x);
101 }
102 }
103 return;
104 }
105
106 /* ---------------------------------------------------------------------- */
107 /* Potrace segments, curves, and pathlists */
108
109 /* extend the interval i to include the inner product <v | dir> for
110 all points v on the segment. Assume precondition a in i. */
segment_limits(int tag,dpoint_t a,dpoint_t c[3],dpoint_t dir,interval_t * i)111 static inline void segment_limits(int tag, dpoint_t a, dpoint_t c[3], dpoint_t dir, interval_t *i) {
112 switch (tag) {
113 case POTRACE_CORNER:
114 extend(i, iprod(c[1], dir));
115 extend(i, iprod(c[2], dir));
116 break;
117 case POTRACE_CURVETO:
118 bezier_limits(iprod(a, dir), iprod(c[0], dir), iprod(c[1], dir), iprod(c[2], dir), i);
119 break;
120 }
121 }
122
123 /* extend the interval i to include <v | dir> for all points v on the
124 curve. */
curve_limits(potrace_curve_t * curve,dpoint_t dir,interval_t * i)125 static void curve_limits(potrace_curve_t *curve, dpoint_t dir, interval_t *i) {
126 int k;
127 int n = curve->n;
128
129 segment_limits(curve->tag[0], curve->c[n-1][2], curve->c[0], dir, i);
130 for (k=1; k<n; k++) {
131 segment_limits(curve->tag[k], curve->c[k-1][2], curve->c[k], dir, i);
132 }
133 }
134
135 /* compute the interval i to be the smallest interval including all <v
136 | dir> for points in the pathlist. If the pathlist is empty, return
137 the singleton interval [0,0]. */
path_limits(potrace_path_t * path,dpoint_t dir,interval_t * i)138 void path_limits(potrace_path_t *path, dpoint_t dir, interval_t *i) {
139 potrace_path_t *p;
140
141 /* empty image? */
142 if (path == NULL) {
143 interval(i, 0, 0);
144 return;
145 }
146
147 /* initialize interval to a point on the first curve */
148 singleton(i, iprod(path->curve.c[0][2], dir));
149
150 /* iterate */
151 list_forall(p, path) {
152 curve_limits(&p->curve, dir, i);
153 }
154 }
155