tesseract  4.1.1
chop.cpp
Go to the documentation of this file.
1 /* -*-C-*-
2  ******************************************************************************
3  *
4  * File: chop.cpp (Formerly chop.c)
5  * Author: Mark Seaman, OCR Technology
6  *
7  * (c) Copyright 1987, Hewlett-Packard Company.
8  ** Licensed under the Apache License, Version 2.0 (the "License");
9  ** you may not use this file except in compliance with the License.
10  ** You may obtain a copy of the License at
11  ** http://www.apache.org/licenses/LICENSE-2.0
12  ** Unless required by applicable law or agreed to in writing, software
13  ** distributed under the License is distributed on an "AS IS" BASIS,
14  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  ** See the License for the specific language governing permissions and
16  ** limitations under the License.
17  *
18  *****************************************************************************/
19 
20 /*----------------------------------------------------------------------
21  I n c l u d e s
22 ----------------------------------------------------------------------*/
23 
24 #define _USE_MATH_DEFINES // for M_PI
25 #include <cmath> // for M_PI
26 #include "chop.h"
27 #include "outlines.h"
28 #include "callcpp.h"
29 #include "plotedges.h"
30 #include "wordrec.h"
31 
32 // Include automatically generated configuration file if running autoconf.
33 #ifdef HAVE_CONFIG_H
34 #include "config_auto.h"
35 #endif
36 
37 namespace tesseract {
38 
39 // Show if the line is going in the positive or negative X direction.
40 static int direction(const EDGEPT* point) {
41  //* direction to return
42  int dir = 0;
43  //* prev point
44  const EDGEPT* prev = point->prev;
45  //* next point
46  const EDGEPT* next = point->next;
47 
48  if (((prev->pos.x <= point->pos.x) && (point->pos.x < next->pos.x)) ||
49  ((prev->pos.x < point->pos.x) && (point->pos.x <= next->pos.x))) {
50  dir = 1;
51  }
52  if (((prev->pos.x >= point->pos.x) && (point->pos.x > next->pos.x)) ||
53  ((prev->pos.x > point->pos.x) && (point->pos.x >= next->pos.x))) {
54  dir = -1;
55  }
56 
57  return dir;
58 }
59 
67  return static_cast<PRIORITY>(angle_change(point->prev, point, point->next));
68 }
69 
70 
76 void Wordrec::add_point_to_list(PointHeap* point_heap, EDGEPT *point) {
77  if (point_heap->size() < MAX_NUM_POINTS - 2) {
78  PointPair pair(point_priority(point), point);
79  point_heap->Push(&pair);
80  }
81 
82 #ifndef GRAPHICS_DISABLED
83  if (chop_debug > 2)
84  mark_outline(point);
85 #endif
86 }
87 
88 // Returns true if the edgept supplied as input is an inside angle. This
89 // is determined by the angular change of the vectors from point to point.
91  return angle_change(pt->prev, pt, pt->next) < chop_inside_angle;
92 }
93 
100 int Wordrec::angle_change(EDGEPT *point1, EDGEPT *point2, EDGEPT *point3) {
101  VECTOR vector1;
102  VECTOR vector2;
103 
104  int angle;
105 
106  /* Compute angle */
107  vector1.x = point2->pos.x - point1->pos.x;
108  vector1.y = point2->pos.y - point1->pos.y;
109  vector2.x = point3->pos.x - point2->pos.x;
110  vector2.y = point3->pos.y - point2->pos.y;
111  /* Use cross product */
112  float length = std::sqrt(static_cast<float>(vector1.length()) * vector2.length());
113  if (static_cast<int>(length) == 0)
114  return (0);
115  angle = static_cast<int>(floor(asin(vector1.cross(vector2) /
116  length) / M_PI * 180.0 + 0.5));
117 
118  /* Use dot product */
119  if (vector1.dot(vector2) < 0)
120  angle = 180 - angle;
121  /* Adjust angle */
122  if (angle > 180)
123  angle -= 360;
124  if (angle <= -180)
125  angle += 360;
126  return (angle);
127 }
128 
136  EDGEPT *vertical_point,
137  int *best_dist) {
138  EDGEPT *best_point = nullptr;
139  int this_distance;
140  int found_better;
141 
142  do {
143  found_better = false;
144 
145  this_distance = edgept_dist (critical_point, vertical_point);
146  if (this_distance <= *best_dist) {
147 
148  if (!(same_point (critical_point->pos, vertical_point->pos) ||
149  same_point (critical_point->pos, vertical_point->next->pos) ||
150  (best_point && same_point (best_point->pos, vertical_point->pos)) ||
151  is_exterior_point (critical_point, vertical_point))) {
152  *best_dist = this_distance;
153  best_point = vertical_point;
155  found_better = true;
156  }
157  }
158  vertical_point = vertical_point->next;
159  }
160  while (found_better == true);
161 
162  return (best_point);
163 }
164 
165 
174  EDGEPT *this_point;
175  EDGEPT *local_min = nullptr;
176  EDGEPT *local_max = nullptr;
177 
178  this_point = outline->loop;
179  local_min = this_point;
180  local_max = this_point;
181  do {
182  if (this_point->vec.y < 0) {
183  /* Look for minima */
184  if (local_max != nullptr)
185  new_max_point(local_max, points);
186  else if (is_inside_angle (this_point))
187  add_point_to_list(points, this_point);
188  local_max = nullptr;
189  local_min = this_point->next;
190  }
191  else if (this_point->vec.y > 0) {
192  /* Look for maxima */
193  if (local_min != nullptr)
194  new_min_point(local_min, points);
195  else if (is_inside_angle (this_point))
196  add_point_to_list(points, this_point);
197  local_min = nullptr;
198  local_max = this_point->next;
199  }
200  else {
201  /* Flat area */
202  if (local_max != nullptr) {
203  if (local_max->prev->vec.y != 0) {
204  new_max_point(local_max, points);
205  }
206  local_max = this_point->next;
207  local_min = nullptr;
208  }
209  else {
210  if (local_min->prev->vec.y != 0) {
211  new_min_point(local_min, points);
212  }
213  local_min = this_point->next;
214  local_max = nullptr;
215  }
216  }
217 
218  /* Next point */
219  this_point = this_point->next;
220  }
221  while (this_point != outline->loop);
222 }
223 
224 
232 void Wordrec::new_min_point(EDGEPT *local_min, PointHeap* points) {
233  int16_t dir;
234 
235  dir = direction (local_min);
236 
237  if (dir < 0) {
238  add_point_to_list(points, local_min);
239  return;
240  }
241 
242  if (dir == 0 && point_priority (local_min) < 0) {
243  add_point_to_list(points, local_min);
244  return;
245  }
246 }
247 
248 
256 void Wordrec::new_max_point(EDGEPT *local_max, PointHeap* points) {
257  int16_t dir;
258 
259  dir = direction (local_max);
260 
261  if (dir > 0) {
262  add_point_to_list(points, local_max);
263  return;
264  }
265 
266  if (dir == 0 && point_priority (local_max) < 0) {
267  add_point_to_list(points, local_max);
268  return;
269  }
270 }
271 
272 
285 void Wordrec::vertical_projection_point(EDGEPT *split_point, EDGEPT *target_point,
286  EDGEPT** best_point,
287  EDGEPT_CLIST *new_points) {
288  EDGEPT *p; /* Iterator */
289  EDGEPT *this_edgept; /* Iterator */
290  EDGEPT_C_IT new_point_it(new_points);
291  int x = split_point->pos.x; /* X value of vertical */
292  int best_dist = LARGE_DISTANCE;/* Best point found */
293 
294  if (*best_point != nullptr)
295  best_dist = edgept_dist(split_point, *best_point);
296 
297  p = target_point;
298  /* Look at each edge point */
299  do {
300  if (((p->pos.x <= x && x <= p->next->pos.x) ||
301  (p->next->pos.x <= x && x <= p->pos.x)) &&
302  !same_point(split_point->pos, p->pos) &&
303  !same_point(split_point->pos, p->next->pos) &&
304  !p->IsChopPt() &&
305  (*best_point == nullptr || !same_point((*best_point)->pos, p->pos))) {
306 
307  if (near_point(split_point, p, p->next, &this_edgept)) {
308  new_point_it.add_before_then_move(this_edgept);
309  }
310 
311  if (*best_point == nullptr)
312  best_dist = edgept_dist (split_point, this_edgept);
313 
314  this_edgept =
315  pick_close_point(split_point, this_edgept, &best_dist);
316  if (this_edgept)
317  *best_point = this_edgept;
318  }
319 
320  p = p->next;
321  }
322  while (p != target_point);
323 }
324 
325 } // namespace tesseract
tesseract::Wordrec::chop_inside_angle
int chop_inside_angle
Definition: wordrec.h:212
tesseract::GenericHeap::Push
void Push(Pair *entry)
Definition: genericheap.h:95
tesseract::Wordrec::add_point_to_list
void add_point_to_list(PointHeap *point_heap, EDGEPT *point)
Definition: chop.cpp:76
TPOINT::dot
int dot(const TPOINT &other) const
Definition: blobs.h:84
tesseract::GenericHeap::size
int size() const
Definition: genericheap.h:71
EDGEPT::prev
EDGEPT * prev
Definition: blobs.h:193
outlines.h
tesseract::Wordrec::chop_debug
int chop_debug
Definition: wordrec.h:204
callcpp.h
same_point
#define same_point(p1, p2)
Definition: outlines.h:45
tesseract::KDPairInc
Definition: kdpair.h:51
EDGEPT
Definition: blobs.h:99
EDGEPT::vec
VECTOR vec
Definition: blobs.h:187
tesseract::Wordrec::point_priority
PRIORITY point_priority(EDGEPT *point)
Definition: chop.cpp:66
TPOINT::y
int16_t y
Definition: blobs.h:94
wordrec.h
PRIORITY
float PRIORITY
Definition: seam.h:36
tesseract::Wordrec::angle_change
int angle_change(EDGEPT *point1, EDGEPT *point2, EDGEPT *point3)
Definition: chop.cpp:100
TESSLINE::loop
EDGEPT * loop
Definition: blobs.h:280
tesseract::Wordrec::pick_close_point
EDGEPT * pick_close_point(EDGEPT *critical_point, EDGEPT *vertical_point, int *best_dist)
Definition: chop.cpp:135
tesseract
Definition: altorenderer.cpp:25
TPOINT::cross
int cross(const TPOINT &other) const
Definition: blobs.h:79
TPOINT
Definition: blobs.h:51
MAX_NUM_POINTS
#define MAX_NUM_POINTS
Definition: chop.h:33
tesseract::Wordrec::near_point
bool near_point(EDGEPT *point, EDGEPT *line_pt_0, EDGEPT *line_pt_1, EDGEPT **near_pt)
Definition: outlines.cpp:40
EDGEPT::IsChopPt
bool IsChopPt() const
Definition: blobs.h:182
plotedges.h
edgept_dist
#define edgept_dist(p1, p2)
Definition: outlines.h:83
tesseract::Wordrec::new_min_point
void new_min_point(EDGEPT *local_min, PointHeap *points)
Definition: chop.cpp:232
tesseract::Wordrec::is_inside_angle
bool is_inside_angle(EDGEPT *pt)
Definition: chop.cpp:90
LARGE_DISTANCE
#define LARGE_DISTANCE
Definition: outlines.h:32
TPOINT::length
int length() const
Definition: blobs.h:89
tesseract::Wordrec::new_max_point
void new_max_point(EDGEPT *local_max, PointHeap *points)
Definition: chop.cpp:256
TPOINT::x
int16_t x
Definition: blobs.h:93
tesseract::Wordrec::prioritize_points
void prioritize_points(TESSLINE *outline, PointHeap *points)
Definition: chop.cpp:173
EDGEPT::pos
TPOINT pos
Definition: blobs.h:186
EDGEPT::next
EDGEPT * next
Definition: blobs.h:192
mark_outline
void mark_outline(EDGEPT *edgept)
Definition: plotedges.cpp:86
chop.h
is_exterior_point
#define is_exterior_point(edge, point)
Definition: outlines.h:93
tesseract::Wordrec::chop_vertical_creep
bool chop_vertical_creep
Definition: wordrec.h:206
tesseract::GenericHeap
Definition: genericheap.h:58
tesseract::Wordrec::vertical_projection_point
void vertical_projection_point(EDGEPT *split_point, EDGEPT *target_point, EDGEPT **best_point, EDGEPT_CLIST *new_points)
Definition: chop.cpp:285
TESSLINE
Definition: blobs.h:203