tesseract 4.1.1
Loading...
Searching...
No Matches
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
39QSPLINE::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
68QSPLINE::QSPLINE ( //constructor
69int xstarts[], //spline boundaries
70int segcount, //no of segments
71int xpts[], //points to fit
72int ypts[], int pointcount, //no of pts
73int 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
137QSPLINE::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
165const 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
184double 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
209double 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
225int32_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
251void 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
272bool 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
291void 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
347void 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
373void 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}
#define QSPLINE_PRECISION
Definition: quspline.cpp:31
int count(LIST var_list)
Definition: oldlist.cpp:95
integer coordinate
Definition: points.h:32
int16_t x() const
access function
Definition: points.h:52
Definition: quadlsq.h:26
double get_a()
Definition: quadlsq.h:45
void fit(int degree)
Definition: quadlsq.cpp:99
void clear()
Definition: quadlsq.cpp:33
double get_b()
Definition: quadlsq.h:48
void add(double x, double y)
Definition: quadlsq.cpp:55
double get_c()
Definition: quadlsq.h:51
float y(float x) const
Definition: quadratc.h:38
float b
Definition: quadratc.h:58
void move(ICOORD vec)
Definition: quadratc.h:43
float c
Definition: quadratc.h:59
double a
Definition: quadratc.h:57
void extrapolate(double gradient, int left, int right)
Definition: quspline.cpp:291
void move(ICOORD vec)
Definition: quspline.cpp:251
QSPLINE()
Definition: quspline.h:44
bool overlap(QSPLINE *spline2, double fraction)
Definition: quspline.cpp:272
double y(double x) const
Definition: quspline.cpp:209
~QSPLINE()
Definition: quspline.cpp:152
void plot(ScrollView *window, ScrollView::Color colour) const
Definition: quspline.cpp:347
QSPLINE & operator=(const QSPLINE &source)
Definition: quspline.cpp:164
double step(double x1, double x2)
Definition: quspline.cpp:184
void DrawTo(int x, int y)
Definition: scrollview.cpp:525
void SetCursor(int x, int y)
Definition: scrollview.cpp:519
void Pen(Color color)
Definition: scrollview.cpp:719