Tesseract  3.02
tesseract-ocr/ccstruct/quspline.cpp
Go to the documentation of this file.
00001 /**********************************************************************
00002  * File:        quspline.cpp  (Formerly qspline.c)
00003  * Description: Code for the QSPLINE class.
00004  * Author:      Ray Smith
00005  * Created:     Tue Oct 08 17:16:12 BST 1991
00006  *
00007  * (C) Copyright 1991, Hewlett-Packard Ltd.
00008  ** Licensed under the Apache License, Version 2.0 (the "License");
00009  ** you may not use this file except in compliance with the License.
00010  ** You may obtain a copy of the License at
00011  ** http://www.apache.org/licenses/LICENSE-2.0
00012  ** Unless required by applicable law or agreed to in writing, software
00013  ** distributed under the License is distributed on an "AS IS" BASIS,
00014  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00015  ** See the License for the specific language governing permissions and
00016  ** limitations under the License.
00017  *
00018  **********************************************************************/
00019 
00020 #include "mfcpch.h"
00021 #include          "memry.h"
00022 #include          "quadlsq.h"
00023 #include          "quspline.h"
00024 
00025 // Include automatically generated configuration file if running autoconf.
00026 #ifdef HAVE_CONFIG_H
00027 #include "config_auto.h"
00028 #endif
00029 
00030 #define QSPLINE_PRECISION 16     //no of steps to draw
00031 
00032 /**********************************************************************
00033  * QSPLINE::QSPLINE
00034  *
00035  * Constructor to build a QSPLINE given the components used in the old code.
00036  **********************************************************************/
00037 
00038 QSPLINE::QSPLINE(                 //constructor
00039                  inT32 count,     //no of segments
00040                  inT32 *xstarts,  //start coords
00041                  double *coeffs   //coefficients
00042                 ) {
00043   inT32 index;                   //segment index
00044 
00045                                  //get memory
00046   xcoords = (inT32 *) alloc_mem ((count + 1) * sizeof (inT32));
00047   quadratics = (QUAD_COEFFS *) alloc_mem (count * sizeof (QUAD_COEFFS));
00048   segments = count;
00049   for (index = 0; index < segments; index++) {
00050                                  //copy them
00051     xcoords[index] = xstarts[index];
00052     quadratics[index] = QUAD_COEFFS (coeffs[index * 3],
00053       coeffs[index * 3 + 1],
00054       coeffs[index * 3 + 2]);
00055   }
00056                                  //right edge
00057   xcoords[index] = xstarts[index];
00058 }
00059 
00060 
00061 /**********************************************************************
00062  * QSPLINE::QSPLINE
00063  *
00064  * Constructor to build a QSPLINE by appproximation of points.
00065  **********************************************************************/
00066 
00067 QSPLINE::QSPLINE (               //constructor
00068 int xstarts[],                   //spline boundaries
00069 int segcount,                    //no of segments
00070 int xpts[],                      //points to fit
00071 int ypts[], int pointcount,      //no of pts
00072 int degree                       //fit required
00073 ) {
00074   register int pointindex;       /*no along text line */
00075   register int segment;          /*segment no */
00076   inT32 *ptcounts;               //no in each segment
00077   QLSQ qlsq;                     /*accumulator */
00078 
00079   segments = segcount;
00080   xcoords = (inT32 *) alloc_mem ((segcount + 1) * sizeof (inT32));
00081   ptcounts = (inT32 *) alloc_mem ((segcount + 1) * sizeof (inT32));
00082   quadratics = (QUAD_COEFFS *) alloc_mem (segcount * sizeof (QUAD_COEFFS));
00083   memmove (xcoords, xstarts, (segcount + 1) * sizeof (inT32));
00084   ptcounts[0] = 0;               /*none in any yet */
00085   for (segment = 0, pointindex = 0; pointindex < pointcount; pointindex++) {
00086     while (segment < segcount && xpts[pointindex] >= xstarts[segment]) {
00087       segment++;                 /*try next segment */
00088                                  /*cumulative counts */
00089       ptcounts[segment] = ptcounts[segment - 1];
00090     }
00091     ptcounts[segment]++;         /*no in previous partition */
00092   }
00093   while (segment < segcount) {
00094     segment++;
00095                                  /*zero the rest */
00096     ptcounts[segment] = ptcounts[segment - 1];
00097   }
00098 
00099   for (segment = 0; segment < segcount; segment++) {
00100     qlsq.clear ();
00101                                  /*first blob */
00102     pointindex = ptcounts[segment];
00103     if (pointindex > 0
00104       && xpts[pointindex] != xpts[pointindex - 1]
00105       && xpts[pointindex] != xstarts[segment])
00106       qlsq.add (xstarts[segment],
00107         ypts[pointindex - 1]
00108         + (ypts[pointindex] - ypts[pointindex - 1])
00109         * (xstarts[segment] - xpts[pointindex - 1])
00110         / (xpts[pointindex] - xpts[pointindex - 1]));
00111     for (; pointindex < ptcounts[segment + 1]; pointindex++) {
00112       qlsq.add (xpts[pointindex], ypts[pointindex]);
00113     }
00114     if (pointindex > 0 && pointindex < pointcount
00115       && xpts[pointindex] != xstarts[segment + 1])
00116       qlsq.add (xstarts[segment + 1],
00117         ypts[pointindex - 1]
00118         + (ypts[pointindex] - ypts[pointindex - 1])
00119         * (xstarts[segment + 1] - xpts[pointindex - 1])
00120         / (xpts[pointindex] - xpts[pointindex - 1]));
00121     qlsq.fit (degree);
00122     quadratics[segment].a = qlsq.get_a ();
00123     quadratics[segment].b = qlsq.get_b ();
00124     quadratics[segment].c = qlsq.get_c ();
00125   }
00126   free_mem(ptcounts);
00127 }
00128 
00129 
00130 /**********************************************************************
00131  * QSPLINE::QSPLINE
00132  *
00133  * Constructor to build a QSPLINE from another.
00134  **********************************************************************/
00135 
00136 QSPLINE::QSPLINE(  //constructor
00137                  const QSPLINE &src) {
00138   segments = 0;
00139   xcoords = NULL;
00140   quadratics = NULL;
00141   *this = src;
00142 }
00143 
00144 
00145 /**********************************************************************
00146  * QSPLINE::~QSPLINE
00147  *
00148  * Destroy a QSPLINE.
00149  **********************************************************************/
00150 
00151 QSPLINE::~QSPLINE (              //constructor
00152 ) {
00153   if (xcoords != NULL) {
00154     free_mem(xcoords);
00155     xcoords = NULL;
00156   }
00157   if (quadratics != NULL) {
00158     free_mem(quadratics);
00159     quadratics = NULL;
00160   }
00161 }
00162 
00163 
00164 /**********************************************************************
00165  * QSPLINE::operator=
00166  *
00167  * Copy a QSPLINE
00168  **********************************************************************/
00169 
00170 QSPLINE & QSPLINE::operator= (   //assignment
00171 const QSPLINE & source) {
00172   if (xcoords != NULL)
00173     free_mem(xcoords);
00174   if (quadratics != NULL)
00175     free_mem(quadratics);
00176 
00177   segments = source.segments;
00178   xcoords = (inT32 *) alloc_mem ((segments + 1) * sizeof (inT32));
00179   quadratics = (QUAD_COEFFS *) alloc_mem (segments * sizeof (QUAD_COEFFS));
00180   memmove (xcoords, source.xcoords, (segments + 1) * sizeof (inT32));
00181   memmove (quadratics, source.quadratics, segments * sizeof (QUAD_COEFFS));
00182   return *this;
00183 }
00184 
00185 
00186 /**********************************************************************
00187  * QSPLINE::step
00188  *
00189  * Return the total of the step functions between the given coords.
00190  **********************************************************************/
00191 
00192 double QSPLINE::step(            //find step functions
00193                      double x1,  //between coords
00194                      double x2) {
00195   int index1, index2;            //indices of coords
00196   double total;                  /*total steps */
00197 
00198   index1 = spline_index (x1);
00199   index2 = spline_index (x2);
00200   total = 0;
00201   while (index1 < index2) {
00202     total +=
00203       (double) quadratics[index1 + 1].y ((float) xcoords[index1 + 1]);
00204     total -= (double) quadratics[index1].y ((float) xcoords[index1 + 1]);
00205     index1++;                    /*next segment */
00206   }
00207   return total;                  /*total steps */
00208 }
00209 
00210 
00211 /**********************************************************************
00212  * QSPLINE::y
00213  *
00214  * Return the y value at the given x value.
00215  **********************************************************************/
00216 
00217 double QSPLINE::y(          //evaluate
00218                   double x  //coord to evaluate at
00219                  ) const {
00220   inT32 index;                   //segment index
00221 
00222   index = spline_index (x);
00223   return quadratics[index].y (x);//in correct segment
00224 }
00225 
00226 
00227 /**********************************************************************
00228  * QSPLINE::spline_index
00229  *
00230  * Return the index to the largest xcoord not greater than x.
00231  **********************************************************************/
00232 
00233 inT32 QSPLINE::spline_index(          //evaluate
00234                             double x  //coord to evaluate at
00235                            ) const {
00236   inT32 index;                   //segment index
00237   inT32 bottom;                  //bottom of range
00238   inT32 top;                     //top of range
00239 
00240   bottom = 0;
00241   top = segments;
00242   while (top - bottom > 1) {
00243     index = (top + bottom) / 2;  //centre of range
00244     if (x >= xcoords[index])
00245       bottom = index;            //new min
00246     else
00247       top = index;               //new max
00248   }
00249   return bottom;
00250 }
00251 
00252 
00253 /**********************************************************************
00254  * QSPLINE::move
00255  *
00256  * Reposition spline by vector
00257  **********************************************************************/
00258 
00259 void QSPLINE::move(            // reposition spline
00260                    ICOORD vec  // by vector
00261                   ) {
00262   inT32 segment;                 //index of segment
00263   inT16 x_shift = vec.x ();
00264 
00265   for (segment = 0; segment < segments; segment++) {
00266     xcoords[segment] += x_shift;
00267     quadratics[segment].move (vec);
00268   }
00269   xcoords[segment] += x_shift;
00270 }
00271 
00272 
00273 /**********************************************************************
00274  * QSPLINE::overlap
00275  *
00276  * Return TRUE if spline2 overlaps this by no more than fraction less
00277  * than the bounds of this.
00278  **********************************************************************/
00279 
00280 BOOL8 QSPLINE::overlap(                   //test overlap
00281                        QSPLINE *spline2,  //2 cannot be smaller
00282                        double fraction    //by more than this
00283                       ) {
00284   int leftlimit;                 /*common left limit */
00285   int rightlimit;                /*common right limit */
00286 
00287   leftlimit = xcoords[1];
00288   rightlimit = xcoords[segments - 1];
00289                                  /*or too non-overlap */
00290   if (spline2->segments < 3 || spline2->xcoords[1] > leftlimit + fraction * (rightlimit - leftlimit)
00291     || spline2->xcoords[spline2->segments - 1] < rightlimit
00292     - fraction * (rightlimit - leftlimit))
00293     return FALSE;
00294   else
00295     return TRUE;
00296 }
00297 
00298 
00299 /**********************************************************************
00300  * extrapolate_spline
00301  *
00302  * Extrapolates the spline linearly using the same gradient as the
00303  * quadratic has at either end.
00304  **********************************************************************/
00305 
00306 void QSPLINE::extrapolate(                  //linear extrapolation
00307                           double gradient,  //gradient to use
00308                           int xmin,         //new left edge
00309                           int xmax          //new right edge
00310                          ) {
00311   register int segment;          /*current segment of spline */
00312   int dest_segment;              //dest index
00313   int *xstarts;                  //new boundaries
00314   QUAD_COEFFS *quads;            //new ones
00315   int increment;                 //in size
00316 
00317   increment = xmin < xcoords[0] ? 1 : 0;
00318   if (xmax > xcoords[segments])
00319     increment++;
00320   if (increment == 0)
00321     return;
00322   xstarts = (int *) alloc_mem ((segments + 1 + increment) * sizeof (int));
00323   quads =
00324     (QUAD_COEFFS *) alloc_mem ((segments + increment) * sizeof (QUAD_COEFFS));
00325   if (xmin < xcoords[0]) {
00326     xstarts[0] = xmin;
00327     quads[0].a = 0;
00328     quads[0].b = gradient;
00329     quads[0].c = y (xcoords[0]) - quads[0].b * xcoords[0];
00330     dest_segment = 1;
00331   }
00332   else
00333     dest_segment = 0;
00334   for (segment = 0; segment < segments; segment++) {
00335     xstarts[dest_segment] = xcoords[segment];
00336     quads[dest_segment] = quadratics[segment];
00337     dest_segment++;
00338   }
00339   xstarts[dest_segment] = xcoords[segment];
00340   if (xmax > xcoords[segments]) {
00341     quads[dest_segment].a = 0;
00342     quads[dest_segment].b = gradient;
00343     quads[dest_segment].c = y (xcoords[segments])
00344       - quads[dest_segment].b * xcoords[segments];
00345     dest_segment++;
00346     xstarts[dest_segment] = xmax + 1;
00347   }
00348   segments = dest_segment;
00349   free_mem(xcoords);
00350   free_mem(quadratics);
00351   xcoords = (inT32 *) xstarts;
00352   quadratics = quads;
00353 }
00354 
00355 
00356 /**********************************************************************
00357  * QSPLINE::plot
00358  *
00359  * Draw the QSPLINE in the given colour.
00360  **********************************************************************/
00361 
00362 #ifndef GRAPHICS_DISABLED
00363 void QSPLINE::plot(                //draw it
00364                    ScrollView* window,  //window to draw in
00365                    ScrollView::Color colour   //colour to draw in
00366                   ) const {
00367   inT32 segment;                 //index of segment
00368   inT16 step;                    //index of poly piece
00369   double increment;              //x increment
00370   double x;                      //x coord
00371 
00372   window->Pen(colour);
00373   for (segment = 0; segment < segments; segment++) {
00374     increment =
00375       (double) (xcoords[segment + 1] -
00376       xcoords[segment]) / QSPLINE_PRECISION;
00377     x = xcoords[segment];
00378     for (step = 0; step <= QSPLINE_PRECISION; step++) {
00379       if (segment == 0 && step == 0)
00380         window->SetCursor(x, quadratics[segment].y (x));
00381       else
00382         window->DrawTo(x, quadratics[segment].y (x));
00383       x += increment;
00384     }
00385   }
00386 }
00387 #endif