third-party/glyphy/glyphy-arcs-bezier.hh

   1 /*
   2  * Copyright 2012 Google, Inc. All Rights Reserved.
   3  *
   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
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  *
  16  * Google Author(s): Behdad Esfahbod, Maysum Panju
  17  */
  18
  19 #ifndef GLYPHY_ARCS_BEZIER_HH
  20 #define GLYPHY_ARCS_BEZIER_HH
  21
  22 #include "glyphy-common.hh"
  23 #include "glyphy-geometry.hh"
  24 #include "glyphy-arc-bezier.hh"
  25
  26 namespace GLyphy {
  27 namespace ArcsBezier {
  28
  29 using namespace Geometry;
  30 using namespace ArcBezier;
  31
  32 template <class ArcBezierApproximator>
  33 class ArcsBezierApproximatorSpringSystem
  34 {
  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)
  41   {
  42     unsigned int n = t.size () - 1;
  43     e.resize (n);
  44     arcs.clear ();
  45     max_e = 0;
  46     min_e = GLYPHY_INFINITY;
  47     for (unsigned int i = 0; i < n; i++)
  48     {
  49       Bezier segment = b.segment (t[i], t[i + 1]);
  50       arcs.push_back (appx.approximate_bezier_with_arc (segment, &e[i]));
  51
  52       max_e = std::max (max_e, e[i]);
  53       min_e = std::min (min_e, e[i]);
  54     }
  55   }
  56
  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,
  63                              double tolerance,
  64                              unsigned int &n_jiggle)
  65   {
  66     unsigned int n = t.size () - 1;
  67     unsigned int max_jiggle = log2 (n) + 1;
  68     unsigned int s;
  69     for (s = 0; s < max_jiggle; s++)
  70     {
  71       double total = 0;
  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);
  75         total += k_inv;
  76         e[i] = k_inv;
  77       }
  78       for (unsigned int i = 0; i < n; i++) {
  79         double k_inv = e[i];
  80         double l = k_inv / total;
  81         t[i + 1] = t[i] + l;
  82       }
  83       t[n] = 1.0; // Do this to get real 1.0, not .9999999999999998!
  84
  85       calc_arcs (b, t, appx, e, arcs, max_e, min_e);
  86
  87       n_jiggle++;
  88       if (max_e < tolerance || (2 * min_e - max_e > tolerance))
  89         break;
  90     }
  91   }
  92
  93   public:
  94   static void approximate_bezier_with_arcs (const Bezier &b,
  95                                             double tolerance,
  96                                             const ArcBezierApproximator &appx,
  97                                             std::vector<Arc> &arcs,
  98                                             double *perror,
  99                                             unsigned int max_segments = 100)
 100   {
 101     std::vector<double> t;
 102     std::vector<double> e;
 103     double max_e, min_e;
 104     unsigned int n_jiggle = 0;
 105
 106     /* Technically speaking we can bsearch for n. */
 107     for (unsigned int n = 1; n <= max_segments; n++)
 108     {
 109       t.resize (n + 1);
 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!
 113
 114       calc_arcs (b, t, appx, e, arcs, max_e, min_e);
 115
 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);
 119           break;
 120         }
 121
 122       if (max_e <= tolerance)
 123         break;
 124     }
 125     if (perror)
 126       *perror = max_e;
 127   }
 128 };
 129
 130 } /* namespace ArcsBezier */
 131 } /* namespace GLyphy */
 132
 133 #endif /* GLYPHY_ARCS_BEZIER_HH */