Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/ccstruct/quspline.cpp @ 3:2c135c81b16c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
MERGE: upstream PyMuPDF 1.26.4 with MuPDF 1.26.7
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:44:09 +0200
parents b50eed0cc0ef
children
comparison
equal deleted inserted replaced
0:6015a75abc2d 3:2c135c81b16c
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
150 QSPLINE::~QSPLINE() {
151 delete[] xcoords;
152 delete[] quadratics;
153 }
154
155 /**********************************************************************
156 * QSPLINE::operator=
157 *
158 * Copy a QSPLINE
159 **********************************************************************/
160
161 QSPLINE &QSPLINE::operator=( // assignment
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