Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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