tesseract  5.0.0
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 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.
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 
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 
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 
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 
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 
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 
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 
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 
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
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
#define INTERSECTING
Definition: polyblk.cpp:35
@ TBOX
int16_t TDimension
Definition: tesstypes.h:32
int lessthan(const void *first, const void *second)
Definition: polyblk.cpp:374
integer coordinate
Definition: points.h:36
void set_x(TDimension xin)
rewrite function
Definition: points.h:67
TDimension y() const
access_function
Definition: points.h:62
void set_y(TDimension yin)
rewrite function
Definition: points.h:71
TDimension x() const
access function
Definition: points.h:58
void set_y(float yin)
rewrite function
Definition: points.h:217
void set_x(float xin)
rewrite function
Definition: points.h:213
void rotate(const FCOORD vec)
Definition: points.h:712
float y() const
Definition: points.h:209
float x() const
Definition: points.h:206
TBOX * bounding_box()
Definition: polyblk.h:38
bool overlap(POLY_BLOCK *other)
Definition: polyblk.cpp:296
void rotate(FCOORD rotation)
Definition: polyblk.cpp:191
static ScrollView::Color ColorForPolyBlockType(PolyBlockType type)
Returns a color to draw the given type.
Definition: polyblk.cpp:389
ICOORDELT_LIST * points()
Definition: polyblk.h:42
void move(ICOORD shift)
Definition: polyblk.cpp:233
void fill(ScrollView *window, ScrollView::Color colour)
Definition: polyblk.cpp:272
void plot(ScrollView *window, int32_t num)
Definition: polyblk.cpp:246
bool contains(POLY_BLOCK *other)
Definition: polyblk.cpp:143
int16_t winding_number(const ICOORD &test_pt)
Definition: polyblk.cpp:106
ICOORDELT_LIST * get_line(TDimension y)
Definition: polyblk.cpp:337
TDimension left() const
Definition: rect.h:82
TDimension top() const
Definition: rect.h:68
TDimension right() const
Definition: rect.h:89
bool overlap(const TBOX &box) const
Definition: rect.h:363
TDimension bottom() const
Definition: rect.h:75
void TextAttributes(const char *font, int pixel_size, bool bold, bool italic, bool underlined)
Definition: scrollview.cpp:623
void Text(int x, int y, const char *mystring)
Definition: scrollview.cpp:648
void Pen(Color color)
Definition: scrollview.cpp:723
void SetCursor(int x, int y)
Definition: scrollview.cpp:498
void DrawTo(int x, int y)
Definition: scrollview.cpp:504