summaryrefslogtreecommitdiff
path: root/Build/source/libs/potrace/potrace-src/src/bbox.c
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/libs/potrace/potrace-src/src/bbox.c')
-rw-r--r--Build/source/libs/potrace/potrace-src/src/bbox.c154
1 files changed, 154 insertions, 0 deletions
diff --git a/Build/source/libs/potrace/potrace-src/src/bbox.c b/Build/source/libs/potrace/potrace-src/src/bbox.c
new file mode 100644
index 00000000000..5cc889192e4
--- /dev/null
+++ b/Build/source/libs/potrace/potrace-src/src/bbox.c
@@ -0,0 +1,154 @@
+/* Copyright (C) 2001-2019 Peter Selinger.
+ This file is part of Potrace. It is free software and it is covered
+ by the GNU General Public License. See the file COPYING for details. */
+
+/* figure out the true bounding box of a vector image */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <math.h>
+#include <stdlib.h>
+
+#include "bbox.h"
+#include "potracelib.h"
+#include "lists.h"
+
+/* ---------------------------------------------------------------------- */
+/* intervals */
+
+/* initialize the interval to [min, max] */
+static void interval(interval_t *i, double min, double max) {
+ i->min = min;
+ i->max = max;
+}
+
+/* initialize the interval to [x, x] */
+static inline void singleton(interval_t *i, double x) {
+ interval(i, x, x);
+}
+
+/* extend the interval to include the number x */
+static inline void extend(interval_t *i, double x) {
+ if (x < i->min) {
+ i->min = x;
+ } else if (x > i->max) {
+ i->max = x;
+ }
+}
+
+static inline int in_interval(interval_t *i, double x) {
+ return i->min <= x && x <= i->max;
+}
+
+/* ---------------------------------------------------------------------- */
+/* inner product */
+
+typedef potrace_dpoint_t dpoint_t;
+
+static double iprod(dpoint_t a, dpoint_t b) {
+ return a.x * b.x + a.y * b.y;
+}
+
+/* ---------------------------------------------------------------------- */
+/* linear Bezier segments */
+
+/* return a point on a 1-dimensional Bezier segment */
+static inline double bezier(double t, double x0, double x1, double x2, double x3) {
+ double s = 1-t;
+ return s*s*s*x0 + 3*(s*s*t)*x1 + 3*(t*t*s)*x2 + t*t*t*x3;
+}
+
+/* Extend the interval i to include the minimum and maximum of a
+ 1-dimensional Bezier segment given by control points x0..x3. For
+ efficiency, x0 in i is assumed as a precondition. */
+static void bezier_limits(double x0, double x1, double x2, double x3, interval_t *i) {
+ double a, b, c, d, r;
+ double t, x;
+
+ /* the min and max of a cubic curve segment are attained at one of
+ at most 4 critical points: the 2 endpoints and at most 2 local
+ extrema. We don't check the first endpoint, because all our
+ curves are cyclic so it's more efficient not to check endpoints
+ twice. */
+
+ /* endpoint */
+ extend(i, x3);
+
+ /* optimization: don't bother calculating extrema if all control
+ points are already in i */
+ if (in_interval(i, x1) && in_interval(i, x2)) {
+ return;
+ }
+
+ /* solve for extrema. at^2 + bt + c = 0 */
+ a = -3*x0 + 9*x1 - 9*x2 + 3*x3;
+ b = 6*x0 - 12*x1 + 6*x2;
+ c = -3*x0 + 3*x1;
+ d = b*b - 4*a*c;
+ if (d > 0) {
+ r = sqrt(d);
+ t = (-b-r)/(2*a);
+ if (t > 0 && t < 1) {
+ x = bezier(t, x0, x1, x2, x3);
+ extend(i, x);
+ }
+ t = (-b+r)/(2*a);
+ if (t > 0 && t < 1) {
+ x = bezier(t, x0, x1, x2, x3);
+ extend(i, x);
+ }
+ }
+ return;
+}
+
+/* ---------------------------------------------------------------------- */
+/* Potrace segments, curves, and pathlists */
+
+/* extend the interval i to include the inner product <v | dir> for
+ all points v on the segment. Assume precondition a in i. */
+static inline void segment_limits(int tag, dpoint_t a, dpoint_t c[3], dpoint_t dir, interval_t *i) {
+ switch (tag) {
+ case POTRACE_CORNER:
+ extend(i, iprod(c[1], dir));
+ extend(i, iprod(c[2], dir));
+ break;
+ case POTRACE_CURVETO:
+ bezier_limits(iprod(a, dir), iprod(c[0], dir), iprod(c[1], dir), iprod(c[2], dir), i);
+ break;
+ }
+}
+
+/* extend the interval i to include <v | dir> for all points v on the
+ curve. */
+static void curve_limits(potrace_curve_t *curve, dpoint_t dir, interval_t *i) {
+ int k;
+ int n = curve->n;
+
+ segment_limits(curve->tag[0], curve->c[n-1][2], curve->c[0], dir, i);
+ for (k=1; k<n; k++) {
+ segment_limits(curve->tag[k], curve->c[k-1][2], curve->c[k], dir, i);
+ }
+}
+
+/* compute the interval i to be the smallest interval including all <v
+ | dir> for points in the pathlist. If the pathlist is empty, return
+ the singleton interval [0,0]. */
+void path_limits(potrace_path_t *path, dpoint_t dir, interval_t *i) {
+ potrace_path_t *p;
+
+ /* empty image? */
+ if (path == NULL) {
+ interval(i, 0, 0);
+ return;
+ }
+
+ /* initialize interval to a point on the first curve */
+ singleton(i, iprod(path->curve.c[0][2], dir));
+
+ /* iterate */
+ list_forall(p, path) {
+ curve_limits(&p->curve, dir, i);
+ }
+}