2 * Copyright 2012 Google, Inc. All Rights Reserved.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
16 * Google Author(s): Behdad Esfahbod, Maysum Panju
19 #ifndef GLYPHY_ARCS_BEZIER_HH
20 #define GLYPHY_ARCS_BEZIER_HH
22 #include "glyphy-common.hh"
23 #include "glyphy-geometry.hh"
24 #include "glyphy-arc-bezier.hh"
27 namespace ArcsBezier {
29 using namespace Geometry;
30 using namespace ArcBezier;
32 template <class ArcBezierApproximator>
33 class ArcsBezierApproximatorSpringSystem
35 static inline void calc_arcs (const Bezier &b,
36 const std::vector<double> &t,
37 const ArcBezierApproximator &appx,
38 std::vector<double> &e,
39 std::vector<Arc > &arcs,
40 double &max_e, double &min_e)
42 unsigned int n = t.size () - 1;
46 min_e = GLYPHY_INFINITY;
47 for (unsigned int i = 0; i < n; i++)
49 Bezier segment = b.segment (t[i], t[i + 1]);
50 arcs.push_back (appx.approximate_bezier_with_arc (segment, &e[i]));
52 max_e = std::max (max_e, e[i]);
53 min_e = std::min (min_e, e[i]);
57 static inline void jiggle (const Bezier &b,
58 const ArcBezierApproximator &appx,
59 std::vector<double> &t,
60 std::vector<double> &e,
61 std::vector<Arc > &arcs,
62 double &max_e, double &min_e,
64 unsigned int &n_jiggle)
66 unsigned int n = t.size () - 1;
67 unsigned int max_jiggle = log2 (n) + 1;
69 for (s = 0; s < max_jiggle; s++)
72 for (unsigned int i = 0; i < n; i++) {
73 double l = t[i + 1] - t[i];
74 double k_inv = l * pow (e[i], -.3);
78 for (unsigned int i = 0; i < n; i++) {
80 double l = k_inv / total;
83 t[n] = 1.0; // Do this to get real 1.0, not .9999999999999998!
85 calc_arcs (b, t, appx, e, arcs, max_e, min_e);
88 if (max_e < tolerance || (2 * min_e - max_e > tolerance))
94 static void approximate_bezier_with_arcs (const Bezier &b,
96 const ArcBezierApproximator &appx,
97 std::vector<Arc> &arcs,
99 unsigned int max_segments = 100)
101 std::vector<double> t;
102 std::vector<double> e;
104 unsigned int n_jiggle = 0;
106 /* Technically speaking we can bsearch for n. */
107 for (unsigned int n = 1; n <= max_segments; n++)
110 for (unsigned int i = 0; i < n; i++)
111 t[i] = double (i) / n;
112 t[n] = 1.0; // Do this out of the loop to get real 1.0, not .9999999999999998!
114 calc_arcs (b, t, appx, e, arcs, max_e, min_e);
116 for (unsigned int i = 0; i < n; i++)
117 if (e[i] <= tolerance) {
118 jiggle (b, appx, t, e, arcs, max_e, min_e, tolerance, n_jiggle);
122 if (max_e <= tolerance)
130 } /* namespace ArcsBezier */
131 } /* namespace GLyphy */
133 #endif /* GLYPHY_ARCS_BEZIER_HH */