quspline.cpp

Go to the documentation of this file.

/**********************************************************************
 * File:        quspline.cpp  (Formerly qspline.c)
 * Description: Code for the QSPLINE class.
 * Author:      Ray Smith
 *
 * (C) Copyright 1991, Hewlett-Packard Ltd.
 ** Licensed under the Apache License, Version 2.0 (the "License");
 ** you may not use this file except in compliance with the License.
 ** You may obtain a copy of the License at
 ** http://www.apache.org/licenses/LICENSE-2.0
 ** Unless required by applicable law or agreed to in writing, software
 ** distributed under the License is distributed on an "AS IS" BASIS,
 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 ** See the License for the specific language governing permissions and
 ** limitations under the License.
 *
 **********************************************************************/
 
// Include automatically generated configuration file if running autoconf.
#ifdef HAVE_CONFIG_H
#  include "config_auto.h"
#endif
 
#include "quspline.h"
 
#include "points.h"   // for ICOORD
#include "quadlsq.h"  // for QLSQ
#include "quadratc.h" // for QUAD_COEFFS
 
#include <allheaders.h> // for pixRenderPolyline, pixGetDepth, pixGetHeight
#include "pix.h"        // for L_CLEAR_PIXELS, L_SET_PIXELS, Pix (ptr only)
 
namespace tesseract {
 
#define QSPLINE_PRECISION 16 // no of steps to draw
 
/**********************************************************************
 * QSPLINE::QSPLINE
 *
 * Constructor to build a QSPLINE given the components used in the old code.
 **********************************************************************/
 
QSPLINE::QSPLINE(     // constructor
    int32_t count,    // no of segments
    int32_t *xstarts, // start coords
    double *coeffs    // coefficients
) {
  int32_t index; // segment index
 
  // get memory
  xcoords = new int32_t[count + 1];
  quadratics = new QUAD_COEFFS[count];
  segments = count;
  for (index = 0; index < segments; index++) {
    // copy them
    xcoords[index] = xstarts[index];
    quadratics[index] =
        QUAD_COEFFS(coeffs[index * 3], coeffs[index * 3 + 1], coeffs[index * 3 + 2]);
  }
  // right edge
  xcoords[index] = xstarts[index];
}
 
/**********************************************************************
 * QSPLINE::QSPLINE
 *
 * Constructor to build a QSPLINE by appproximation of points.
 **********************************************************************/
 
QSPLINE::QSPLINE(               // constructor
    int xstarts[],              // spline boundaries
    int segcount,               // no of segments
    int xpts[],                 // points to fit
    int ypts[], int pointcount, // no of pts
    int degree                  // fit required
) {
  int pointindex;    /*no along text line */
  int segment;       /*segment no */
  int32_t *ptcounts; // no in each segment
  QLSQ qlsq;         /*accumulator */
 
  segments = segcount;
  xcoords = new int32_t[segcount + 1];
  ptcounts = new int32_t[segcount + 1];
  quadratics = new QUAD_COEFFS[segcount];
  memmove(xcoords, xstarts, (segcount + 1) * sizeof(int32_t));
  ptcounts[0] = 0; /*none in any yet */
  for (segment = 0, pointindex = 0; pointindex < pointcount; pointindex++) {
    while (segment < segcount && xpts[pointindex] >= xstarts[segment]) {
      segment++; /*try next segment */
                 /*cumulative counts */
      ptcounts[segment] = ptcounts[segment - 1];
    }
    ptcounts[segment]++; /*no in previous partition */
  }
  while (segment < segcount) {
    segment++;
    /*zero the rest */
    ptcounts[segment] = ptcounts[segment - 1];
  }
 
  for (segment = 0; segment < segcount; segment++) {
    qlsq.clear();
    /*first blob */
    pointindex = ptcounts[segment];
    if (pointindex > 0 && xpts[pointindex] != xpts[pointindex - 1] &&
        xpts[pointindex] != xstarts[segment]) {
      qlsq.add(xstarts[segment],
               ypts[pointindex - 1] + (ypts[pointindex] - ypts[pointindex - 1]) *
                                          (xstarts[segment] - xpts[pointindex - 1]) /
                                          (xpts[pointindex] - xpts[pointindex - 1]));
    }
    for (; pointindex < ptcounts[segment + 1]; pointindex++) {
      qlsq.add(xpts[pointindex], ypts[pointindex]);
    }
    if (pointindex > 0 && pointindex < pointcount && xpts[pointindex] != xstarts[segment + 1]) {
      qlsq.add(xstarts[segment + 1],
               ypts[pointindex - 1] + (ypts[pointindex] - ypts[pointindex - 1]) *
                                          (xstarts[segment + 1] - xpts[pointindex - 1]) /
                                          (xpts[pointindex] - xpts[pointindex - 1]));
    }
    qlsq.fit(degree);
    quadratics[segment].a = qlsq.get_a();
    quadratics[segment].b = qlsq.get_b();
    quadratics[segment].c = qlsq.get_c();
  }
  delete[] ptcounts;
}
 
/**********************************************************************
 * QSPLINE::QSPLINE
 *
 * Constructor to build a QSPLINE from another.
 **********************************************************************/
 
QSPLINE::QSPLINE( // constructor
    const QSPLINE &src) {
  segments = 0;
  xcoords = nullptr;
  quadratics = nullptr;
  *this = src;
}
 
/**********************************************************************
 * QSPLINE::~QSPLINE
 *
 * Destroy a QSPLINE.
 **********************************************************************/
 
QSPLINE::~QSPLINE() {
  delete[] xcoords;
  delete[] quadratics;
}
 
/**********************************************************************
 * QSPLINE::operator=
 *
 * Copy a QSPLINE
 **********************************************************************/
 
QSPLINE &QSPLINE::operator=( // assignment
    const QSPLINE &source) {
  delete[] xcoords;
  delete[] quadratics;
 
  segments = source.segments;
  xcoords = new int32_t[segments + 1];
  quadratics = new QUAD_COEFFS[segments];
  memmove(xcoords, source.xcoords, (segments + 1) * sizeof(int32_t));
  memmove(quadratics, source.quadratics, segments * sizeof(QUAD_COEFFS));
  return *this;
}
 
/**********************************************************************
 * QSPLINE::step
 *
 * Return the total of the step functions between the given coords.
 **********************************************************************/
 
double QSPLINE::step( // find step functions
    double x1,        // between coords
    double x2) {
  int index1, index2; // indices of coords
  double total;       /*total steps */
 
  index1 = spline_index(x1);
  index2 = spline_index(x2);
  total = 0;
  while (index1 < index2) {
    total += static_cast<double>(quadratics[index1 + 1].y(static_cast<float>(xcoords[index1 + 1])));
    total -= static_cast<double>(quadratics[index1].y(static_cast<float>(xcoords[index1 + 1])));
    index1++; /*next segment */
  }
  return total; /*total steps */
}
 
/**********************************************************************
 * QSPLINE::y
 *
 * Return the y value at the given x value.
 **********************************************************************/
 
double QSPLINE::y( // evaluate
    double x       // coord to evaluate at
    ) const {
  int32_t index; // segment index
 
  index = spline_index(x);
  return quadratics[index].y(x); // in correct segment
}
 
/**********************************************************************
 * QSPLINE::spline_index
 *
 * Return the index to the largest xcoord not greater than x.
 **********************************************************************/
 
int32_t QSPLINE::spline_index( // evaluate
    double x                   // coord to evaluate at
    ) const {
  int32_t index;  // segment index
  int32_t bottom; // bottom of range
  int32_t top;    // top of range
 
  bottom = 0;
  top = segments;
  while (top - bottom > 1) {
    index = (top + bottom) / 2; // centre of range
    if (x >= xcoords[index]) {
      bottom = index; // new min
    } else {
      top = index; // new max
    }
  }
  return bottom;
}
 
/**********************************************************************
 * QSPLINE::move
 *
 * Reposition spline by vector
 **********************************************************************/
 
void QSPLINE::move( // reposition spline
    ICOORD vec      // by vector
) {
  int32_t segment; // index of segment
  int16_t x_shift = vec.x();
 
  for (segment = 0; segment < segments; segment++) {
    xcoords[segment] += x_shift;
    quadratics[segment].move(vec);
  }
  xcoords[segment] += x_shift;
}
 
/**********************************************************************
 * QSPLINE::overlap
 *
 * Return true if spline2 overlaps this by no more than fraction less
 * than the bounds of this.
 **********************************************************************/
 
bool QSPLINE::overlap( // test overlap
    QSPLINE *spline2,  // 2 cannot be smaller
    double fraction    // by more than this
) {
  int leftlimit = xcoords[1];             /*common left limit */
  int rightlimit = xcoords[segments - 1]; /*common right limit */
                                          /*or too non-overlap */
  return !(spline2->segments < 3 ||
           spline2->xcoords[1] > leftlimit + fraction * (rightlimit - leftlimit) ||
           spline2->xcoords[spline2->segments - 1] <
               rightlimit - fraction * (rightlimit - leftlimit));
}
 
/**********************************************************************
 * extrapolate_spline
 *
 * Extrapolates the spline linearly using the same gradient as the
 * quadratic has at either end.
 **********************************************************************/
 
void QSPLINE::extrapolate( // linear extrapolation
    double gradient,       // gradient to use
    int xmin,              // new left edge
    int xmax               // new right edge
) {
  int segment;        /*current segment of spline */
  int dest_segment;   // dest index
  int32_t *xstarts;   // new boundaries
  QUAD_COEFFS *quads; // new ones
  int increment;      // in size
 
  increment = xmin < xcoords[0] ? 1 : 0;
  if (xmax > xcoords[segments]) {
    increment++;
  }
  if (increment == 0) {
    return;
  }
  xstarts = new int32_t[segments + 1 + increment];
  quads = new QUAD_COEFFS[segments + increment];
  if (xmin < xcoords[0]) {
    xstarts[0] = xmin;
    quads[0].a = 0;
    quads[0].b = gradient;
    quads[0].c = y(xcoords[0]) - quads[0].b * xcoords[0];
    dest_segment = 1;
  } else {
    dest_segment = 0;
  }
  for (segment = 0; segment < segments; segment++) {
    xstarts[dest_segment] = xcoords[segment];
    quads[dest_segment] = quadratics[segment];
    dest_segment++;
  }
  xstarts[dest_segment] = xcoords[segment];
  if (xmax > xcoords[segments]) {
    quads[dest_segment].a = 0;
    quads[dest_segment].b = gradient;
    quads[dest_segment].c = y(xcoords[segments]) - quads[dest_segment].b * xcoords[segments];
    dest_segment++;
    xstarts[dest_segment] = xmax + 1;
  }
  segments = dest_segment;
  delete[] xcoords;
  delete[] quadratics;
  xcoords = xstarts;
  quadratics = quads;
}
 
/**********************************************************************
 * QSPLINE::plot
 *
 * Draw the QSPLINE in the given colour.
 **********************************************************************/
 
#ifndef GRAPHICS_DISABLED
void QSPLINE::plot(          // draw it
    ScrollView *window,      // window to draw in
    ScrollView::Color colour // colour to draw in
    ) const {
  int32_t segment;  // index of segment
  int16_t step;     // index of poly piece
  double increment; // x increment
  double x;         // x coord
 
  window->Pen(colour);
  for (segment = 0; segment < segments; segment++) {
    increment = static_cast<double>(xcoords[segment + 1] - xcoords[segment]) / QSPLINE_PRECISION;
    x = xcoords[segment];
    for (step = 0; step <= QSPLINE_PRECISION; step++) {
      if (segment == 0 && step == 0) {
        window->SetCursor(x, quadratics[segment].y(x));
      } else {
        window->DrawTo(x, quadratics[segment].y(x));
      }
      x += increment;
    }
  }
}
#endif
 
void QSPLINE::plot(Image pix) const {
  if (pix == nullptr) {
    return;
  }
 
  int32_t segment;  // Index of segment
  int16_t step;     // Index of poly piece
  double increment; // x increment
  double x;         // x coord
  auto height = static_cast<double>(pixGetHeight(pix));
  Pta *points = ptaCreate(QSPLINE_PRECISION * segments);
  const int kLineWidth = 5;
 
  for (segment = 0; segment < segments; segment++) {
    increment = static_cast<double>((xcoords[segment + 1] - xcoords[segment])) / QSPLINE_PRECISION;
    x = xcoords[segment];
    for (step = 0; step <= QSPLINE_PRECISION; step++) {
      double y = height - quadratics[segment].y(x);
      ptaAddPt(points, x, y);
      x += increment;
    }
  }
 
  switch (pixGetDepth(pix)) {
    case 1:
      pixRenderPolyline(pix, points, kLineWidth, L_SET_PIXELS, 1);
      break;
    case 32:
      pixRenderPolylineArb(pix, points, kLineWidth, 255, 0, 0, 1);
      break;
    default:
      pixRenderPolyline(pix, points, kLineWidth, L_CLEAR_PIXELS, 1);
      break;
  }
  ptaDestroy(&points);
}
 
} // namespace tesseract