tesseract  5.0.0-alpha-619-ge9db
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 
33 int lessthan(const void *first, const void *second);
34 
35 POLY_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 
64 void 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 
100 int16_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 
138 bool POLY_BLOCK::contains(POLY_BLOCK *other) {
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 
184 void POLY_BLOCK::rotate(FCOORD rotation) {
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 
229 void POLY_BLOCK::move(ICOORD shift) {
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
244 void 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 
271 void POLY_BLOCK::fill(ScrollView* window, ScrollView::Color colour) {
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 
303 bool POLY_BLOCK::overlap(POLY_BLOCK *other) {
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 
342 ICOORDELT_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 
379 int 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
ScrollView::GREY
Definition: scrollview.h:133
TBOX
Definition: cleanapi_test.cc:19
ScrollView
Definition: scrollview.h:97
elst.h
ICOORD::set_x
void set_x(int16_t xin)
rewrite function
Definition: points.h:60
ScrollView::DARK_GREEN
Definition: scrollview.h:124
lessthan
int lessthan(const void *first, const void *second)
Definition: polyblk.cpp:378
POLY_BLOCK::move
void move(ICOORD shift)
Definition: polyblk.cpp:228
POLY_BLOCK::compute_bb
void compute_bb()
Definition: polyblk.cpp:63
FCOORD::set_x
void set_x(float xin)
rewrite function
Definition: points.h:213
TBOX::overlap
bool overlap(const TBOX &box) const
Definition: rect.h:350
POLY_BLOCK::overlap
bool overlap(POLY_BLOCK *other)
Definition: polyblk.cpp:302
FCOORD::y
float y() const
Definition: points.h:209
ICOORD
integer coordinate
Definition: points.h:30
FCOORD::x
float x() const
Definition: points.h:206
TBOX::top
int16_t top() const
Definition: rect.h:57
PB_LINE_IT
Definition: polyblk.h:90
polyblk.h
ScrollView::BROWN
Definition: scrollview.h:120
ScrollView::CYAN
Definition: scrollview.h:107
ScrollView::Pen
void Pen(Color color)
Definition: scrollview.cpp:717
ScrollView::DrawTo
void DrawTo(int x, int y)
Definition: scrollview.cpp:524
INTERSECTING
#define INTERSECTING
Definition: polyblk.cpp:30
ScrollView::MEDIUM_BLUE
Definition: scrollview.h:113
ICOORD::x
int16_t x() const
access function
Definition: points.h:51
FCOORD
Definition: points.h:187
FCOORD::set_y
void set_y(float yin)
rewrite function
Definition: points.h:217
ScrollView::BLUE
Definition: scrollview.h:108
ICOORD::set_y
void set_y(int16_t yin)
rewrite function
Definition: points.h:64
PT_COUNT
Definition: capi.h:123
POLY_BLOCK::rotate
void rotate(FCOORD rotation)
Definition: polyblk.cpp:183
POLY_BLOCK::plot
void plot(ScrollView *window, int32_t num)
Definition: polyblk.cpp:243
ScrollView::ORANGE
Definition: scrollview.h:136
ScrollView::LIGHT_BLUE
Definition: scrollview.h:112
ScrollView::MAGENTA
Definition: scrollview.h:109
POLY_BLOCK::winding_number
int16_t winding_number(const ICOORD &test_pt)
Definition: polyblk.cpp:99
ScrollView::SKY_BLUE
Definition: scrollview.h:116
ScrollView::YELLOW
Definition: scrollview.h:105
TBOX::bottom
int16_t bottom() const
Definition: rect.h:64
ScrollView::WHITE
Definition: scrollview.h:103
ScrollView::AQUAMARINE
Definition: scrollview.h:110
FCOORD::rotate
void rotate(const FCOORD vec)
Definition: points.h:736
ScrollView::RED
Definition: scrollview.h:104
POLY_BLOCK::points
ICOORDELT_LIST * points()
Definition: polyblk.h:52
POLY_BLOCK::bounding_box
TBOX * bounding_box()
Definition: polyblk.h:48
POLY_BLOCK::contains
bool contains(POLY_BLOCK *other)
Definition: polyblk.cpp:137
count
int count(LIST var_list)
Definition: oldlist.cpp:79
ScrollView::TextAttributes
void TextAttributes(const char *font, int pixel_size, bool bold, bool italic, bool underlined)
Definition: scrollview.cpp:634
TBOX::left
int16_t left() const
Definition: rect.h:71
ScrollView::GREEN
Definition: scrollview.h:106
TBOX::right
int16_t right() const
Definition: rect.h:78
POLY_BLOCK::ColorForPolyBlockType
static ScrollView::Color ColorForPolyBlockType(PolyBlockType type)
Returns a color to draw the given type.
Definition: polyblk.cpp:392
tesstrain_utils.type
type
Definition: tesstrain_utils.py:141
POLY_BLOCK
Definition: polyblk.h:26
ScrollView::SetCursor
void SetCursor(int x, int y)
Definition: scrollview.cpp:518
PB_LINE_IT::get_line
ICOORDELT_LIST * get_line(int16_t y)
Definition: polyblk.cpp:341
ScrollView::Text
void Text(int x, int y, const char *mystring)
Definition: scrollview.cpp:651
ScrollView::Color
Color
Definition: scrollview.h:100
PolyBlockType
PolyBlockType
Definition: publictypes.h:52
ICOORDELT
Definition: points.h:160
POLY_BLOCK::fill
void fill(ScrollView *window, ScrollView::Color colour)
Definition: polyblk.cpp:270
POLY_BLOCK::reflect_in_y_axis
void reflect_in_y_axis()
Definition: polyblk.cpp:207
POLY_BLOCK::POLY_BLOCK
POLY_BLOCK()=default
ICOORD::y
int16_t y() const
access_function
Definition: points.h:55
TBOX
Definition: rect.h:33