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