tesseract 4.1.1
Loading...
Searching...
No Matches
polyblk.cpp
Go to the documentation of this file.
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 "polyblk.h"
19#include "elst.h"
20#include <cctype>
21#include <cinttypes> // PRId32
22#include <cmath>
23#include <cstdio>
24#include <memory> // std::unique_ptr
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 INTERSECTING INT16_MAX
32
33int lessthan(const void *first, const void *second);
34
35POLY_BLOCK::POLY_BLOCK(ICOORDELT_LIST *points, PolyBlockType t) {
36 ICOORDELT_IT v = &vertices;
37
38 vertices.clear();
39 v.move_to_first();
40 v.add_list_before(points);
41 compute_bb();
42 type = t;
43}
44
45// Initialize from box coordinates.
47 vertices.clear();
48 ICOORDELT_IT v = &vertices;
49 v.move_to_first();
50 v.add_to_end(new ICOORDELT(tbox.left(), tbox.top()));
51 v.add_to_end(new ICOORDELT(tbox.left(), tbox.bottom()));
52 v.add_to_end(new ICOORDELT(tbox.right(), tbox.bottom()));
53 v.add_to_end(new ICOORDELT(tbox.right(), tbox.top()));
54 compute_bb();
55 type = t;
56}
57
64void POLY_BLOCK::compute_bb() { //constructor
65 ICOORD ibl, itr; //integer bb
66 ICOORD botleft; //bounding box
67 ICOORD topright;
68 ICOORD pos; //current pos;
69 ICOORDELT_IT pts = &vertices; //iterator
70
71 botleft = *pts.data ();
72 topright = botleft;
73 do {
74 pos = *pts.data ();
75 if (pos.x () < botleft.x ())
76 //get bounding box
77 botleft = ICOORD (pos.x (), botleft.y ());
78 if (pos.y () < botleft.y ())
79 botleft = ICOORD (botleft.x (), pos.y ());
80 if (pos.x () > topright.x ())
81 topright = ICOORD (pos.x (), topright.y ());
82 if (pos.y () > topright.y ())
83 topright = ICOORD (topright.x (), pos.y ());
84 pts.forward ();
85 }
86 while (!pts.at_first ());
87 ibl = ICOORD (botleft.x (), botleft.y ());
88 itr = ICOORD (topright.x (), topright.y ());
89 box = TBOX (ibl, itr);
90}
91
92
100int16_t POLY_BLOCK::winding_number(const ICOORD &point) {
101 int16_t count; //winding count
102 ICOORD pt; //current point
103 ICOORD vec; //point to current point
104 ICOORD vvec; //current point to next point
105 int32_t cross; //cross product
106 ICOORDELT_IT it = &vertices; //iterator
107
108 count = 0;
109 do {
110 pt = *it.data ();
111 vec = pt - point;
112 vvec = *it.data_relative (1) - pt;
113 //crossing the line
114 if (vec.y () <= 0 && vec.y () + vvec.y () > 0) {
115 cross = vec * vvec; //cross product
116 if (cross > 0)
117 count++; //crossing right half
118 else if (cross == 0)
119 return INTERSECTING; //going through point
120 }
121 else if (vec.y () > 0 && vec.y () + vvec.y () <= 0) {
122 cross = vec * vvec;
123 if (cross < 0)
124 count--; //crossing back
125 else if (cross == 0)
126 return INTERSECTING; //illegal
127 }
128 else if (vec.y () == 0 && vec.x () == 0)
129 return INTERSECTING;
130 it.forward ();
131 }
132 while (!it.at_first ());
133 return count; //winding number
134}
135
136
139 int16_t count; // winding count
140 ICOORDELT_IT it = &vertices; // iterator
141 ICOORD vertex;
142
143 if (!box.overlap (*(other->bounding_box ())))
144 return false; // can't be contained
145
146 /* check that no vertex of this is inside other */
147
148 do {
149 vertex = *it.data ();
150 // get winding number
151 count = other->winding_number (vertex);
152 if (count != INTERSECTING)
153 if (count != 0)
154 return false;
155 it.forward ();
156 }
157 while (!it.at_first ());
158
159 /* check that all vertices of other are inside this */
160
161 //switch lists
162 it.set_to_list (other->points ());
163 do {
164 vertex = *it.data ();
165 //try other way round
166 count = winding_number (vertex);
167 if (count != INTERSECTING)
168 if (count == 0)
169 return false;
170 it.forward ();
171 }
172 while (!it.at_first ());
173 return true;
174}
175
176
185 FCOORD pos; //current pos;
186 ICOORDELT *pt; //current point
187 ICOORDELT_IT pts = &vertices; //iterator
188
189 do {
190 pt = pts.data ();
191 pos.set_x (pt->x ());
192 pos.set_y (pt->y ());
193 pos.rotate (rotation);
194 pt->set_x(static_cast<int16_t>(floor(pos.x() + 0.5)));
195 pt->set_y(static_cast<int16_t>(floor(pos.y() + 0.5)));
196 pts.forward ();
197 }
198 while (!pts.at_first ());
199 compute_bb();
200}
201
209 ICOORDELT *pt; // current point
210 ICOORDELT_IT pts = &vertices; // Iterator.
211
212 do {
213 pt = pts.data();
214 pt->set_x(-pt->x());
215 pts.forward();
216 }
217 while (!pts.at_first());
218 compute_bb();
219}
220
221
230 ICOORDELT *pt; //current point
231 ICOORDELT_IT pts = &vertices; //iterator
232
233 do {
234 pt = pts.data ();
235 *pt += shift;
236 pts.forward ();
237 }
238 while (!pts.at_first ());
239 compute_bb();
240}
241
242
243#ifndef GRAPHICS_DISABLED
244void POLY_BLOCK::plot(ScrollView* window, int32_t num) {
245 ICOORDELT_IT v = &vertices;
246
247 window->Pen(ColorForPolyBlockType(type));
248
249 v.move_to_first ();
250
251 if (num > 0) {
252 window->TextAttributes("Times", 80, false, false, false);
253 char temp_buff[34];
254#if !defined(_WIN32) || defined(__MINGW32__)
255 snprintf(temp_buff, sizeof(temp_buff), "%" PRId32, num);
256#else
257 _ltoa(num, temp_buff, 10);
258#endif
259 window->Text(v.data ()->x (), v.data ()->y (), temp_buff);
260 }
261
262 window->SetCursor(v.data ()->x (), v.data ()->y ());
263 for (v.mark_cycle_pt (); !v.cycled_list (); v.forward ()) {
264 window->DrawTo(v.data ()->x (), v.data ()->y ());
265 }
266 v.move_to_first ();
267 window->DrawTo(v.data ()->x (), v.data ()->y ());
268}
269
270
272 int16_t y;
273 int16_t width;
274 PB_LINE_IT *lines;
275 ICOORDELT_IT s_it;
276
277 lines = new PB_LINE_IT (this);
278 window->Pen(colour);
279
280 for (y = this->bounding_box ()->bottom ();
281 y <= this->bounding_box ()->top (); y++) {
282 const std::unique_ptr</*non-const*/ ICOORDELT_LIST> segments(
283 lines->get_line(y));
284 if (!segments->empty ()) {
285 s_it.set_to_list(segments.get());
286 for (s_it.mark_cycle_pt (); !s_it.cycled_list (); s_it.forward ()) {
287 // Note different use of ICOORDELT, x coord is x coord of pixel
288 // at the start of line segment, y coord is length of line segment
289 // Last pixel is start pixel + length.
290 width = s_it.data ()->y ();
291 window->SetCursor(s_it.data ()->x (), y);
292 window->DrawTo(s_it.data()->x() + static_cast<float>(width), y);
293 }
294 }
295 }
296
297 delete lines;
298}
299#endif
300
301
304 int16_t count; // winding count
305 ICOORDELT_IT it = &vertices; // iterator
306 ICOORD vertex;
307
308 if (!box.overlap(*(other->bounding_box())))
309 return false; // can't be any overlap.
310
311 /* see if a vertex of this is inside other */
312
313 do {
314 vertex = *it.data ();
315 // get winding number
316 count = other->winding_number (vertex);
317 if (count != INTERSECTING)
318 if (count != 0)
319 return true;
320 it.forward ();
321 }
322 while (!it.at_first ());
323
324 /* see if a vertex of other is inside this */
325
326 // switch lists
327 it.set_to_list (other->points ());
328 do {
329 vertex = *it.data();
330 // try other way round
331 count = winding_number (vertex);
332 if (count != INTERSECTING)
333 if (count != 0)
334 return true;
335 it.forward ();
336 }
337 while (!it.at_first ());
338 return false;
339}
340
341
342ICOORDELT_LIST *PB_LINE_IT::get_line(int16_t y) {
343 ICOORDELT_IT v, r;
344 ICOORDELT_LIST *result;
345 ICOORDELT *x, *current, *previous;
346 float fy = y + 0.5f;
347 result = new ICOORDELT_LIST ();
348 r.set_to_list (result);
349 v.set_to_list (block->points ());
350
351 for (v.mark_cycle_pt (); !v.cycled_list (); v.forward ()) {
352 if (((v.data_relative (-1)->y () > y) && (v.data ()->y () <= y))
353 || ((v.data_relative (-1)->y () <= y) && (v.data ()->y () > y))) {
354 previous = v.data_relative (-1);
355 current = v.data ();
356 float fx = 0.5f + previous->x() +
357 (current->x() - previous->x()) * (fy - previous->y()) /
358 (current->y() - previous->y());
359 x = new ICOORDELT(static_cast<int16_t>(fx), 0);
360 r.add_to_end (x);
361 }
362 }
363
364 if (!r.empty ()) {
365 r.sort (lessthan);
366 for (r.mark_cycle_pt (); !r.cycled_list (); r.forward ())
367 x = r.data ();
368 for (r.mark_cycle_pt (); !r.cycled_list (); r.forward ()) {
369 r.data ()->set_y (r.data_relative (1)->x () - r.data ()->x ());
370 r.forward ();
371 delete (r.extract ());
372 }
373 }
374
375 return result;
376}
377
378
379int lessthan(const void *first, const void *second) {
380 const ICOORDELT *p1 = *reinterpret_cast<const ICOORDELT* const*>(first);
381 const ICOORDELT *p2 = *reinterpret_cast<const ICOORDELT* const*>(second);
382
383 if (p1->x () < p2->x ())
384 return (-1);
385 else if (p1->x () > p2->x ())
386 return (1);
387 else
388 return (0);
389}
390
391#ifndef GRAPHICS_DISABLED
394 // Keep kPBColors in sync with PolyBlockType.
395 const ScrollView::Color kPBColors[PT_COUNT] = {
396 ScrollView::WHITE, // Type is not yet known. Keep as the 1st element.
397 ScrollView::BLUE, // Text that lives inside a column.
398 ScrollView::CYAN, // Text that spans more than one column.
399 ScrollView::MEDIUM_BLUE, // Text that is in a cross-column pull-out region.
400 ScrollView::AQUAMARINE, // Partition belonging to an equation region.
401 ScrollView::SKY_BLUE, // Partition belonging to an inline equation region.
402 ScrollView::MAGENTA, // Partition belonging to a table region.
403 ScrollView::GREEN, // Text-line runs vertically.
404 ScrollView::LIGHT_BLUE, // Text that belongs to an image.
405 ScrollView::RED, // Image that lives inside a column.
406 ScrollView::YELLOW, // Image that spans more than one column.
407 ScrollView::ORANGE, // Image in a cross-column pull-out region.
408 ScrollView::BROWN, // Horizontal Line.
409 ScrollView::DARK_GREEN, // Vertical Line.
410 ScrollView::GREY // Lies outside of any column.
411 };
412 if (type < PT_COUNT) {
413 return kPBColors[type];
414 }
415 return ScrollView::WHITE;
416}
417#endif // GRAPHICS_DISABLED
@ PT_COUNT
Definition: capi.h:144
#define INTERSECTING
Definition: coutln.h:35
int lessthan(const void *first, const void *second)
Definition: polyblk.cpp:379
PolyBlockType
Definition: publictypes.h:53
int count(LIST var_list)
Definition: oldlist.cpp:95
integer coordinate
Definition: points.h:32
void set_x(int16_t xin)
rewrite function
Definition: points.h:61
int16_t y() const
access_function
Definition: points.h:56
void set_y(int16_t yin)
rewrite function
Definition: points.h:65
int16_t x() const
access function
Definition: points.h:52
Definition: points.h:189
void rotate(const FCOORD vec)
Definition: points.h:763
float y() const
Definition: points.h:210
void set_y(float yin)
rewrite function
Definition: points.h:218
void set_x(float xin)
rewrite function
Definition: points.h:214
float x() const
Definition: points.h:207
POLY_BLOCK()=default
void reflect_in_y_axis()
Definition: polyblk.cpp:208
ICOORDELT_LIST * points()
Definition: polyblk.h:39
void compute_bb()
Definition: polyblk.cpp:64
bool overlap(POLY_BLOCK *other)
Definition: polyblk.cpp:303
void move(ICOORD shift)
Definition: polyblk.cpp:229
int16_t winding_number(const ICOORD &test_pt)
Definition: polyblk.cpp:100
void fill(ScrollView *window, ScrollView::Color colour)
Definition: polyblk.cpp:271
static ScrollView::Color ColorForPolyBlockType(PolyBlockType type)
Returns a color to draw the given type.
Definition: polyblk.cpp:393
TBOX * bounding_box()
Definition: polyblk.h:35
bool contains(POLY_BLOCK *other)
Definition: polyblk.cpp:138
void rotate(FCOORD rotation)
Definition: polyblk.cpp:184
void plot(ScrollView *window, int32_t num)
Definition: polyblk.cpp:244
ICOORDELT_LIST * get_line(int16_t y)
Definition: polyblk.cpp:342
Definition: rect.h:34
int16_t top() const
Definition: rect.h:58
bool overlap(const TBOX &box) const
Definition: rect.h:355
int16_t left() const
Definition: rect.h:72
int16_t bottom() const
Definition: rect.h:65
int16_t right() const
Definition: rect.h:79
void DrawTo(int x, int y)
Definition: scrollview.cpp:525
void TextAttributes(const char *font, int pixel_size, bool bold, bool italic, bool underlined)
Definition: scrollview.cpp:635
void Text(int x, int y, const char *mystring)
Definition: scrollview.cpp:652
void SetCursor(int x, int y)
Definition: scrollview.cpp:519
void Pen(Color color)
Definition: scrollview.cpp:719