tesseract  5.0.0
quspline.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * File: quspline.cpp (Formerly qspline.c)
3  * Description: Code for the QSPLINE class.
4  * Author: Ray Smith
5  *
6  * (C) Copyright 1991, Hewlett-Packard Ltd.
7  ** Licensed under the Apache License, Version 2.0 (the "License");
8  ** you may not use this file except in compliance with the License.
9  ** You may obtain a copy of the License at
10  ** http://www.apache.org/licenses/LICENSE-2.0
11  ** Unless required by applicable law or agreed to in writing, software
12  ** distributed under the License is distributed on an "AS IS" BASIS,
13  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  ** See the License for the specific language governing permissions and
15  ** limitations under the License.
16  *
17  **********************************************************************/
18 
19 // Include automatically generated configuration file if running autoconf.
20 #ifdef HAVE_CONFIG_H
21 # include "config_auto.h"
22 #endif
23 
24 #include "quspline.h"
25 
26 #include "points.h" // for ICOORD
27 #include "quadlsq.h" // for QLSQ
28 #include "quadratc.h" // for QUAD_COEFFS
29 
30 #include <allheaders.h> // for pixRenderPolyline, pixGetDepth, pixGetHeight
31 #include "pix.h" // for L_CLEAR_PIXELS, L_SET_PIXELS, Pix (ptr only)
32 
33 namespace tesseract {
34 
35 #define QSPLINE_PRECISION 16 // no of steps to draw
36 
37 /**********************************************************************
38  * QSPLINE::QSPLINE
39  *
40  * Constructor to build a QSPLINE given the components used in the old code.
41  **********************************************************************/
42 
43 QSPLINE::QSPLINE( // constructor
44  int32_t count, // no of segments
45  int32_t *xstarts, // start coords
46  double *coeffs // coefficients
47 ) {
48  int32_t index; // segment index
49 
50  // get memory
51  xcoords = new int32_t[count + 1];
52  quadratics = new QUAD_COEFFS[count];
53  segments = count;
54  for (index = 0; index < segments; index++) {
55  // copy them
56  xcoords[index] = xstarts[index];
57  quadratics[index] =
58  QUAD_COEFFS(coeffs[index * 3], coeffs[index * 3 + 1], coeffs[index * 3 + 2]);
59  }
60  // right edge
61  xcoords[index] = xstarts[index];
62 }
63 
64 /**********************************************************************
65  * QSPLINE::QSPLINE
66  *
67  * Constructor to build a QSPLINE by appproximation of points.
68  **********************************************************************/
69 
70 QSPLINE::QSPLINE( // constructor
71  int xstarts[], // spline boundaries
72  int segcount, // no of segments
73  int xpts[], // points to fit
74  int ypts[], int pointcount, // no of pts
75  int degree // fit required
76 ) {
77  int pointindex; /*no along text line */
78  int segment; /*segment no */
79  int32_t *ptcounts; // no in each segment
80  QLSQ qlsq; /*accumulator */
81 
82  segments = segcount;
83  xcoords = new int32_t[segcount + 1];
84  ptcounts = new int32_t[segcount + 1];
85  quadratics = new QUAD_COEFFS[segcount];
86  memmove(xcoords, xstarts, (segcount + 1) * sizeof(int32_t));
87  ptcounts[0] = 0; /*none in any yet */
88  for (segment = 0, pointindex = 0; pointindex < pointcount; pointindex++) {
89  while (segment < segcount && xpts[pointindex] >= xstarts[segment]) {
90  segment++; /*try next segment */
91  /*cumulative counts */
92  ptcounts[segment] = ptcounts[segment - 1];
93  }
94  ptcounts[segment]++; /*no in previous partition */
95  }
96  while (segment < segcount) {
97  segment++;
98  /*zero the rest */
99  ptcounts[segment] = ptcounts[segment - 1];
100  }
101 
102  for (segment = 0; segment < segcount; segment++) {
103  qlsq.clear();
104  /*first blob */
105  pointindex = ptcounts[segment];
106  if (pointindex > 0 && xpts[pointindex] != xpts[pointindex - 1] &&
107  xpts[pointindex] != xstarts[segment]) {
108  qlsq.add(xstarts[segment],
109  ypts[pointindex - 1] + (ypts[pointindex] - ypts[pointindex - 1]) *
110  (xstarts[segment] - xpts[pointindex - 1]) /
111  (xpts[pointindex] - xpts[pointindex - 1]));
112  }
113  for (; pointindex < ptcounts[segment + 1]; pointindex++) {
114  qlsq.add(xpts[pointindex], ypts[pointindex]);
115  }
116  if (pointindex > 0 && pointindex < pointcount && xpts[pointindex] != xstarts[segment + 1]) {
117  qlsq.add(xstarts[segment + 1],
118  ypts[pointindex - 1] + (ypts[pointindex] - ypts[pointindex - 1]) *
119  (xstarts[segment + 1] - xpts[pointindex - 1]) /
120  (xpts[pointindex] - xpts[pointindex - 1]));
121  }
122  qlsq.fit(degree);
123  quadratics[segment].a = qlsq.get_a();
124  quadratics[segment].b = qlsq.get_b();
125  quadratics[segment].c = qlsq.get_c();
126  }
127  delete[] ptcounts;
128 }
129 
130 /**********************************************************************
131  * QSPLINE::QSPLINE
132  *
133  * Constructor to build a QSPLINE from another.
134  **********************************************************************/
135 
136 QSPLINE::QSPLINE( // constructor
137  const QSPLINE &src) {
138  segments = 0;
139  xcoords = nullptr;
140  quadratics = nullptr;
141  *this = src;
142 }
143 
144 /**********************************************************************
145  * QSPLINE::~QSPLINE
146  *
147  * Destroy a QSPLINE.
148  **********************************************************************/
149 
151  delete[] xcoords;
152  delete[] quadratics;
153 }
154 
155 /**********************************************************************
156  * QSPLINE::operator=
157  *
158  * Copy a QSPLINE
159  **********************************************************************/
160 
162  const QSPLINE &source) {
163  delete[] xcoords;
164  delete[] quadratics;
165 
166  segments = source.segments;
167  xcoords = new int32_t[segments + 1];
168  quadratics = new QUAD_COEFFS[segments];
169  memmove(xcoords, source.xcoords, (segments + 1) * sizeof(int32_t));
170  memmove(quadratics, source.quadratics, segments * sizeof(QUAD_COEFFS));
171  return *this;
172 }
173 
174 /**********************************************************************
175  * QSPLINE::step
176  *
177  * Return the total of the step functions between the given coords.
178  **********************************************************************/
179 
180 double QSPLINE::step( // find step functions
181  double x1, // between coords
182  double x2) {
183  int index1, index2; // indices of coords
184  double total; /*total steps */
185 
186  index1 = spline_index(x1);
187  index2 = spline_index(x2);
188  total = 0;
189  while (index1 < index2) {
190  total += static_cast<double>(quadratics[index1 + 1].y(static_cast<float>(xcoords[index1 + 1])));
191  total -= static_cast<double>(quadratics[index1].y(static_cast<float>(xcoords[index1 + 1])));
192  index1++; /*next segment */
193  }
194  return total; /*total steps */
195 }
196 
197 /**********************************************************************
198  * QSPLINE::y
199  *
200  * Return the y value at the given x value.
201  **********************************************************************/
202 
203 double QSPLINE::y( // evaluate
204  double x // coord to evaluate at
205  ) const {
206  int32_t index; // segment index
207 
208  index = spline_index(x);
209  return quadratics[index].y(x); // in correct segment
210 }
211 
212 /**********************************************************************
213  * QSPLINE::spline_index
214  *
215  * Return the index to the largest xcoord not greater than x.
216  **********************************************************************/
217 
218 int32_t QSPLINE::spline_index( // evaluate
219  double x // coord to evaluate at
220  ) const {
221  int32_t index; // segment index
222  int32_t bottom; // bottom of range
223  int32_t top; // top of range
224 
225  bottom = 0;
226  top = segments;
227  while (top - bottom > 1) {
228  index = (top + bottom) / 2; // centre of range
229  if (x >= xcoords[index]) {
230  bottom = index; // new min
231  } else {
232  top = index; // new max
233  }
234  }
235  return bottom;
236 }
237 
238 /**********************************************************************
239  * QSPLINE::move
240  *
241  * Reposition spline by vector
242  **********************************************************************/
243 
244 void QSPLINE::move( // reposition spline
245  ICOORD vec // by vector
246 ) {
247  int32_t segment; // index of segment
248  int16_t x_shift = vec.x();
249 
250  for (segment = 0; segment < segments; segment++) {
251  xcoords[segment] += x_shift;
252  quadratics[segment].move(vec);
253  }
254  xcoords[segment] += x_shift;
255 }
256 
257 /**********************************************************************
258  * QSPLINE::overlap
259  *
260  * Return true if spline2 overlaps this by no more than fraction less
261  * than the bounds of this.
262  **********************************************************************/
263 
264 bool QSPLINE::overlap( // test overlap
265  QSPLINE *spline2, // 2 cannot be smaller
266  double fraction // by more than this
267 ) {
268  int leftlimit = xcoords[1]; /*common left limit */
269  int rightlimit = xcoords[segments - 1]; /*common right limit */
270  /*or too non-overlap */
271  return !(spline2->segments < 3 ||
272  spline2->xcoords[1] > leftlimit + fraction * (rightlimit - leftlimit) ||
273  spline2->xcoords[spline2->segments - 1] <
274  rightlimit - fraction * (rightlimit - leftlimit));
275 }
276 
277 /**********************************************************************
278  * extrapolate_spline
279  *
280  * Extrapolates the spline linearly using the same gradient as the
281  * quadratic has at either end.
282  **********************************************************************/
283 
284 void QSPLINE::extrapolate( // linear extrapolation
285  double gradient, // gradient to use
286  int xmin, // new left edge
287  int xmax // new right edge
288 ) {
289  int segment; /*current segment of spline */
290  int dest_segment; // dest index
291  int32_t *xstarts; // new boundaries
292  QUAD_COEFFS *quads; // new ones
293  int increment; // in size
294 
295  increment = xmin < xcoords[0] ? 1 : 0;
296  if (xmax > xcoords[segments]) {
297  increment++;
298  }
299  if (increment == 0) {
300  return;
301  }
302  xstarts = new int32_t[segments + 1 + increment];
303  quads = new QUAD_COEFFS[segments + increment];
304  if (xmin < xcoords[0]) {
305  xstarts[0] = xmin;
306  quads[0].a = 0;
307  quads[0].b = gradient;
308  quads[0].c = y(xcoords[0]) - quads[0].b * xcoords[0];
309  dest_segment = 1;
310  } else {
311  dest_segment = 0;
312  }
313  for (segment = 0; segment < segments; segment++) {
314  xstarts[dest_segment] = xcoords[segment];
315  quads[dest_segment] = quadratics[segment];
316  dest_segment++;
317  }
318  xstarts[dest_segment] = xcoords[segment];
319  if (xmax > xcoords[segments]) {
320  quads[dest_segment].a = 0;
321  quads[dest_segment].b = gradient;
322  quads[dest_segment].c = y(xcoords[segments]) - quads[dest_segment].b * xcoords[segments];
323  dest_segment++;
324  xstarts[dest_segment] = xmax + 1;
325  }
326  segments = dest_segment;
327  delete[] xcoords;
328  delete[] quadratics;
329  xcoords = xstarts;
330  quadratics = quads;
331 }
332 
333 /**********************************************************************
334  * QSPLINE::plot
335  *
336  * Draw the QSPLINE in the given colour.
337  **********************************************************************/
338 
339 #ifndef GRAPHICS_DISABLED
340 void QSPLINE::plot( // draw it
341  ScrollView *window, // window to draw in
342  ScrollView::Color colour // colour to draw in
343  ) const {
344  int32_t segment; // index of segment
345  int16_t step; // index of poly piece
346  double increment; // x increment
347  double x; // x coord
348 
349  window->Pen(colour);
350  for (segment = 0; segment < segments; segment++) {
351  increment = static_cast<double>(xcoords[segment + 1] - xcoords[segment]) / QSPLINE_PRECISION;
352  x = xcoords[segment];
353  for (step = 0; step <= QSPLINE_PRECISION; step++) {
354  if (segment == 0 && step == 0) {
355  window->SetCursor(x, quadratics[segment].y(x));
356  } else {
357  window->DrawTo(x, quadratics[segment].y(x));
358  }
359  x += increment;
360  }
361  }
362 }
363 #endif
364 
365 void QSPLINE::plot(Image pix) const {
366  if (pix == nullptr) {
367  return;
368  }
369 
370  int32_t segment; // Index of segment
371  int16_t step; // Index of poly piece
372  double increment; // x increment
373  double x; // x coord
374  auto height = static_cast<double>(pixGetHeight(pix));
375  Pta *points = ptaCreate(QSPLINE_PRECISION * segments);
376  const int kLineWidth = 5;
377 
378  for (segment = 0; segment < segments; segment++) {
379  increment = static_cast<double>((xcoords[segment + 1] - xcoords[segment])) / QSPLINE_PRECISION;
380  x = xcoords[segment];
381  for (step = 0; step <= QSPLINE_PRECISION; step++) {
382  double y = height - quadratics[segment].y(x);
383  ptaAddPt(points, x, y);
384  x += increment;
385  }
386  }
387 
388  switch (pixGetDepth(pix)) {
389  case 1:
390  pixRenderPolyline(pix, points, kLineWidth, L_SET_PIXELS, 1);
391  break;
392  case 32:
393  pixRenderPolylineArb(pix, points, kLineWidth, 255, 0, 0, 1);
394  break;
395  default:
396  pixRenderPolyline(pix, points, kLineWidth, L_CLEAR_PIXELS, 1);
397  break;
398  }
399  ptaDestroy(&points);
400 }
401 
402 } // namespace tesseract
#define QSPLINE_PRECISION
Definition: quspline.cpp:35
integer coordinate
Definition: points.h:36
TDimension x() const
access function
Definition: points.h:58
void fit(int degree)
Definition: quadlsq.cpp:100
void clear()
Definition: quadlsq.cpp:37
double get_a() const
Definition: quadlsq.h:45
double get_b() const
Definition: quadlsq.h:48
double get_c() const
Definition: quadlsq.h:51
void add(double x, double y)
Definition: quadlsq.cpp:58
float y(float x) const
Definition: quadratc.h:38
void move(ICOORD vec)
Definition: quadratc.h:43
void move(ICOORD vec)
Definition: quspline.cpp:244
double y(double x) const
Definition: quspline.cpp:203
void plot(ScrollView *window, ScrollView::Color colour) const
Definition: quspline.cpp:340
bool overlap(QSPLINE *spline2, double fraction)
Definition: quspline.cpp:264
double step(double x1, double x2)
Definition: quspline.cpp:180
void extrapolate(double gradient, int left, int right)
Definition: quspline.cpp:284
QSPLINE & operator=(const QSPLINE &source)
Definition: quspline.cpp:161
void Pen(Color color)
Definition: scrollview.cpp:723
void SetCursor(int x, int y)
Definition: scrollview.cpp:498
void DrawTo(int x, int y)
Definition: scrollview.cpp:504