Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/ccstruct/polyblk.cpp @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /**********************************************************************
2 * File: polyblk.cpp (Formerly poly_block.c)
3 * Description: Polygonal blocks
4 *
5 * (C) Copyright 1993, Hewlett-Packard Ltd.
6 ** Licensed under the Apache License, Version 2.0 (the "License");
7 ** you may not use this file except in compliance with the License.
8 ** You may obtain a copy of the License at
9 ** http://www.apache.org/licenses/LICENSE-2.0
10 ** Unless required by applicable law or agreed to in writing, software
11 ** distributed under the License is distributed on an "AS IS" BASIS,
12 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 ** See the License for the specific language governing permissions and
14 ** limitations under the License.
15 *
16 **********************************************************************/
17
18 // Include automatically generated configuration file if running autoconf.
19 #ifdef HAVE_CONFIG_H
20 # include "config_auto.h"
21 #endif
22
23 #include "polyblk.h"
24
25 #include "elst.h"
26
27 #include <cctype>
28 #include <cinttypes> // PRId32
29 #include <cmath>
30 #include <cstdio>
31 #include <memory> // std::unique_ptr
32
33 namespace tesseract {
34
35 #define INTERSECTING INT16_MAX
36
37 int lessthan(const void *first, const void *second);
38
39 POLY_BLOCK::POLY_BLOCK(ICOORDELT_LIST *points, PolyBlockType t) {
40 ICOORDELT_IT v = &vertices;
41
42 vertices.clear();
43 v.move_to_first();
44 v.add_list_before(points);
45 compute_bb();
46 type = t;
47 }
48
49 // Initialize from box coordinates.
50 POLY_BLOCK::POLY_BLOCK(const TBOX &tbox, PolyBlockType t) {
51 vertices.clear();
52 ICOORDELT_IT v = &vertices;
53 v.move_to_first();
54 v.add_to_end(new ICOORDELT(tbox.left(), tbox.top()));
55 v.add_to_end(new ICOORDELT(tbox.left(), tbox.bottom()));
56 v.add_to_end(new ICOORDELT(tbox.right(), tbox.bottom()));
57 v.add_to_end(new ICOORDELT(tbox.right(), tbox.top()));
58 compute_bb();
59 type = t;
60 }
61
62 /**
63 * @name POLY_BLOCK::compute_bb
64 *
65 * Compute the bounding box from the outline points.
66 */
67
68 void POLY_BLOCK::compute_bb() { // constructor
69 ICOORD ibl, itr; // integer bb
70 ICOORD botleft; // bounding box
71 ICOORD topright;
72 ICOORD pos; // current pos;
73 ICOORDELT_IT pts = &vertices; // iterator
74
75 botleft = *pts.data();
76 topright = botleft;
77 do {
78 pos = *pts.data();
79 if (pos.x() < botleft.x()) {
80 // get bounding box
81 botleft = ICOORD(pos.x(), botleft.y());
82 }
83 if (pos.y() < botleft.y()) {
84 botleft = ICOORD(botleft.x(), pos.y());
85 }
86 if (pos.x() > topright.x()) {
87 topright = ICOORD(pos.x(), topright.y());
88 }
89 if (pos.y() > topright.y()) {
90 topright = ICOORD(topright.x(), pos.y());
91 }
92 pts.forward();
93 } while (!pts.at_first());
94 ibl = ICOORD(botleft.x(), botleft.y());
95 itr = ICOORD(topright.x(), topright.y());
96 box = TBOX(ibl, itr);
97 }
98
99 /**
100 * @name POLY_BLOCK::winding_number
101 *
102 * Return the winding number of the outline around the given point.
103 * @param point point to wind around
104 */
105
106 int16_t POLY_BLOCK::winding_number(const ICOORD &point) {
107 int16_t count; // winding count
108 ICOORD pt; // current point
109 ICOORD vec; // point to current point
110 ICOORD vvec; // current point to next point
111 int32_t cross; // cross product
112 ICOORDELT_IT it = &vertices; // iterator
113
114 count = 0;
115 do {
116 pt = *it.data();
117 vec = pt - point;
118 vvec = *it.data_relative(1) - pt;
119 // crossing the line
120 if (vec.y() <= 0 && vec.y() + vvec.y() > 0) {
121 cross = vec * vvec; // cross product
122 if (cross > 0) {
123 count++; // crossing right half
124 } else if (cross == 0) {
125 return INTERSECTING; // going through point
126 }
127 } else if (vec.y() > 0 && vec.y() + vvec.y() <= 0) {
128 cross = vec * vvec;
129 if (cross < 0) {
130 count--; // crossing back
131 } else if (cross == 0) {
132 return INTERSECTING; // illegal
133 }
134 } else if (vec.y() == 0 && vec.x() == 0) {
135 return INTERSECTING;
136 }
137 it.forward();
138 } while (!it.at_first());
139 return count; // winding number
140 }
141
142 /// @return true if other is inside this.
143 bool POLY_BLOCK::contains(POLY_BLOCK *other) {
144 int16_t count; // winding count
145 ICOORDELT_IT it = &vertices; // iterator
146 ICOORD vertex;
147
148 if (!box.overlap(*(other->bounding_box()))) {
149 return false; // can't be contained
150 }
151
152 /* check that no vertex of this is inside other */
153
154 do {
155 vertex = *it.data();
156 // get winding number
157 count = other->winding_number(vertex);
158 if (count != INTERSECTING) {
159 if (count != 0) {
160 return false;
161 }
162 }
163 it.forward();
164 } while (!it.at_first());
165
166 /* check that all vertices of other are inside this */
167
168 // switch lists
169 it.set_to_list(other->points());
170 do {
171 vertex = *it.data();
172 // try other way round
173 count = winding_number(vertex);
174 if (count != INTERSECTING) {
175 if (count == 0) {
176 return false;
177 }
178 }
179 it.forward();
180 } while (!it.at_first());
181 return true;
182 }
183
184 /**
185 * @name POLY_BLOCK::rotate
186 *
187 * Rotate the POLY_BLOCK.
188 * @param rotation cos, sin of angle
189 */
190
191 void POLY_BLOCK::rotate(FCOORD rotation) {
192 FCOORD pos; // current pos;
193 ICOORDELT *pt; // current point
194 ICOORDELT_IT pts = &vertices; // iterator
195
196 do {
197 pt = pts.data();
198 pos.set_x(pt->x());
199 pos.set_y(pt->y());
200 pos.rotate(rotation);
201 pt->set_x(static_cast<TDimension>(floor(pos.x() + 0.5)));
202 pt->set_y(static_cast<TDimension>(floor(pos.y() + 0.5)));
203 pts.forward();
204 } while (!pts.at_first());
205 compute_bb();
206 }
207
208 /**
209 * @name POLY_BLOCK::reflect_in_y_axis
210 *
211 * Reflect the coords of the polygon in the y-axis. (Flip the sign of x.)
212 */
213
214 void POLY_BLOCK::reflect_in_y_axis() {
215 ICOORDELT *pt; // current point
216 ICOORDELT_IT pts = &vertices; // Iterator.
217
218 do {
219 pt = pts.data();
220 pt->set_x(-pt->x());
221 pts.forward();
222 } while (!pts.at_first());
223 compute_bb();
224 }
225
226 /**
227 * POLY_BLOCK::move
228 *
229 * Move the POLY_BLOCK.
230 * @param shift x,y translation vector
231 */
232
233 void POLY_BLOCK::move(ICOORD shift) {
234 ICOORDELT *pt; // current point
235 ICOORDELT_IT pts = &vertices; // iterator
236
237 do {
238 pt = pts.data();
239 *pt += shift;
240 pts.forward();
241 } while (!pts.at_first());
242 compute_bb();
243 }
244
245 #ifndef GRAPHICS_DISABLED
246 void POLY_BLOCK::plot(ScrollView *window, int32_t num) {
247 ICOORDELT_IT v = &vertices;
248
249 window->Pen(ColorForPolyBlockType(type));
250
251 v.move_to_first();
252
253 if (num > 0) {
254 window->TextAttributes("Times", 80, false, false, false);
255 char temp_buff[34];
256 # if !defined(_WIN32) || defined(__MINGW32__)
257 snprintf(temp_buff, sizeof(temp_buff), "%" PRId32, num);
258 # else
259 _ltoa(num, temp_buff, 10);
260 # endif
261 window->Text(v.data()->x(), v.data()->y(), temp_buff);
262 }
263
264 window->SetCursor(v.data()->x(), v.data()->y());
265 for (v.mark_cycle_pt(); !v.cycled_list(); v.forward()) {
266 window->DrawTo(v.data()->x(), v.data()->y());
267 }
268 v.move_to_first();
269 window->DrawTo(v.data()->x(), v.data()->y());
270 }
271
272 void POLY_BLOCK::fill(ScrollView *window, ScrollView::Color colour) {
273 ICOORDELT_IT s_it;
274
275 std::unique_ptr<PB_LINE_IT> lines(new PB_LINE_IT(this));
276 window->Pen(colour);
277
278 for (auto y = this->bounding_box()->bottom(); y <= this->bounding_box()->top(); y++) {
279 const std::unique_ptr</*non-const*/ ICOORDELT_LIST> segments(lines->get_line(y));
280 if (!segments->empty()) {
281 s_it.set_to_list(segments.get());
282 for (s_it.mark_cycle_pt(); !s_it.cycled_list(); s_it.forward()) {
283 // Note different use of ICOORDELT, x coord is x coord of pixel
284 // at the start of line segment, y coord is length of line segment
285 // Last pixel is start pixel + length.
286 auto width = s_it.data()->y();
287 window->SetCursor(s_it.data()->x(), y);
288 window->DrawTo(s_it.data()->x() + static_cast<float>(width), y);
289 }
290 }
291 }
292 }
293 #endif
294
295 /// @return true if the polygons of other and this overlap.
296 bool POLY_BLOCK::overlap(POLY_BLOCK *other) {
297 int16_t count; // winding count
298 ICOORDELT_IT it = &vertices; // iterator
299 ICOORD vertex;
300
301 if (!box.overlap(*(other->bounding_box()))) {
302 return false; // can't be any overlap.
303 }
304
305 /* see if a vertex of this is inside other */
306
307 do {
308 vertex = *it.data();
309 // get winding number
310 count = other->winding_number(vertex);
311 if (count != INTERSECTING) {
312 if (count != 0) {
313 return true;
314 }
315 }
316 it.forward();
317 } while (!it.at_first());
318
319 /* see if a vertex of other is inside this */
320
321 // switch lists
322 it.set_to_list(other->points());
323 do {
324 vertex = *it.data();
325 // try other way round
326 count = winding_number(vertex);
327 if (count != INTERSECTING) {
328 if (count != 0) {
329 return true;
330 }
331 }
332 it.forward();
333 } while (!it.at_first());
334 return false;
335 }
336
337 ICOORDELT_LIST *PB_LINE_IT::get_line(TDimension y) {
338 ICOORDELT_IT v, r;
339 ICOORDELT_LIST *result;
340 ICOORDELT *x, *current, *previous;
341 float fy = y + 0.5f;
342 result = new ICOORDELT_LIST();
343 r.set_to_list(result);
344 v.set_to_list(block->points());
345
346 for (v.mark_cycle_pt(); !v.cycled_list(); v.forward()) {
347 if (((v.data_relative(-1)->y() > y) && (v.data()->y() <= y)) ||
348 ((v.data_relative(-1)->y() <= y) && (v.data()->y() > y))) {
349 previous = v.data_relative(-1);
350 current = v.data();
351 float fx =
352 0.5f + previous->x() +
353 (current->x() - previous->x()) * (fy - previous->y()) / (current->y() - previous->y());
354 x = new ICOORDELT(static_cast<TDimension>(fx), 0);
355 r.add_to_end(x);
356 }
357 }
358
359 if (!r.empty()) {
360 r.sort(lessthan);
361 for (r.mark_cycle_pt(); !r.cycled_list(); r.forward()) {
362 x = r.data();
363 }
364 for (r.mark_cycle_pt(); !r.cycled_list(); r.forward()) {
365 r.data()->set_y(r.data_relative(1)->x() - r.data()->x());
366 r.forward();
367 delete (r.extract());
368 }
369 }
370
371 return result;
372 }
373
374 int lessthan(const void *first, const void *second) {
375 const ICOORDELT *p1 = *reinterpret_cast<const ICOORDELT *const *>(first);
376 const ICOORDELT *p2 = *reinterpret_cast<const ICOORDELT *const *>(second);
377
378 if (p1->x() < p2->x()) {
379 return (-1);
380 } else if (p1->x() > p2->x()) {
381 return (1);
382 } else {
383 return (0);
384 }
385 }
386
387 #ifndef GRAPHICS_DISABLED
388 /// Returns a color to draw the given type.
389 ScrollView::Color POLY_BLOCK::ColorForPolyBlockType(PolyBlockType type) {
390 // Keep kPBColors in sync with PolyBlockType.
391 const ScrollView::Color kPBColors[PT_COUNT] = {
392 ScrollView::WHITE, // Type is not yet known. Keep as the 1st element.
393 ScrollView::BLUE, // Text that lives inside a column.
394 ScrollView::CYAN, // Text that spans more than one column.
395 ScrollView::MEDIUM_BLUE, // Text that is in a cross-column pull-out
396 // region.
397 ScrollView::AQUAMARINE, // Partition belonging to an equation region.
398 ScrollView::SKY_BLUE, // Partition belonging to an inline equation
399 // region.
400 ScrollView::MAGENTA, // Partition belonging to a table region.
401 ScrollView::GREEN, // Text-line runs vertically.
402 ScrollView::LIGHT_BLUE, // Text that belongs to an image.
403 ScrollView::RED, // Image that lives inside a column.
404 ScrollView::YELLOW, // Image that spans more than one column.
405 ScrollView::ORANGE, // Image in a cross-column pull-out region.
406 ScrollView::BROWN, // Horizontal Line.
407 ScrollView::DARK_GREEN, // Vertical Line.
408 ScrollView::GREY // Lies outside of any column.
409 };
410 if (type < PT_COUNT) {
411 return kPBColors[type];
412 }
413 return ScrollView::WHITE;
414 }
415 #endif // !GRAPHICS_DISABLED
416
417 } // namespace tesseract