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