tesseract  5.0.0-alpha-619-ge9db
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 <cmath> // for M_PI
25 #include "chop.h"
26 #include "outlines.h"
27 #include "callcpp.h"
28 #include "plotedges.h"
29 #include "wordrec.h"
30 
31 // Include automatically generated configuration file if running autoconf.
32 #ifdef HAVE_CONFIG_H
33 #include "config_auto.h"
34 #endif
35 
36 namespace tesseract {
37 
38 // Show if the line is going in the positive or negative X direction.
39 static int direction(const EDGEPT* point) {
40  //* direction to return
41  int dir = 0;
42  //* prev point
43  const EDGEPT* prev = point->prev;
44  //* next point
45  const EDGEPT* next = point->next;
46 
47  if (((prev->pos.x <= point->pos.x) && (point->pos.x < next->pos.x)) ||
48  ((prev->pos.x < point->pos.x) && (point->pos.x <= next->pos.x))) {
49  dir = 1;
50  }
51  if (((prev->pos.x >= point->pos.x) && (point->pos.x > next->pos.x)) ||
52  ((prev->pos.x > point->pos.x) && (point->pos.x >= next->pos.x))) {
53  dir = -1;
54  }
55 
56  return dir;
57 }
58 
66  return static_cast<PRIORITY>(angle_change(point->prev, point, point->next));
67 }
68 
69 
75 void Wordrec::add_point_to_list(PointHeap* point_heap, EDGEPT *point) {
76  if (point_heap->size() < MAX_NUM_POINTS - 2) {
77  PointPair pair(point_priority(point), point);
78  point_heap->Push(&pair);
79  }
80 
81 #ifndef GRAPHICS_DISABLED
82  if (chop_debug > 2)
83  mark_outline(point);
84 #endif
85 }
86 
87 // Returns true if the edgept supplied as input is an inside angle. This
88 // is determined by the angular change of the vectors from point to point.
90  return angle_change(pt->prev, pt, pt->next) < chop_inside_angle;
91 }
92 
99 int Wordrec::angle_change(EDGEPT *point1, EDGEPT *point2, EDGEPT *point3) {
100  VECTOR vector1;
101  VECTOR vector2;
102 
103  int angle;
104 
105  /* Compute angle */
106  vector1.x = point2->pos.x - point1->pos.x;
107  vector1.y = point2->pos.y - point1->pos.y;
108  vector2.x = point3->pos.x - point2->pos.x;
109  vector2.y = point3->pos.y - point2->pos.y;
110  /* Use cross product */
111  float length = std::sqrt(static_cast<float>(vector1.length()) * vector2.length());
112  if (static_cast<int>(length) == 0)
113  return (0);
114  angle = static_cast<int>(floor(asin(vector1.cross(vector2) /
115  length) / M_PI * 180.0 + 0.5));
116 
117  /* Use dot product */
118  if (vector1.dot(vector2) < 0)
119  angle = 180 - angle;
120  /* Adjust angle */
121  if (angle > 180)
122  angle -= 360;
123  if (angle <= -180)
124  angle += 360;
125  return (angle);
126 }
127 
135  EDGEPT *vertical_point,
136  int *best_dist) {
137  EDGEPT *best_point = nullptr;
138  int this_distance;
139  int 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 
147  if (!(same_point (critical_point->pos, vertical_point->pos) ||
148  same_point (critical_point->pos, vertical_point->next->pos) ||
149  (best_point && same_point (best_point->pos, vertical_point->pos)) ||
150  is_exterior_point (critical_point, vertical_point))) {
151  *best_dist = this_distance;
152  best_point = vertical_point;
154  found_better = true;
155  }
156  }
157  vertical_point = vertical_point->next;
158  }
159  while (found_better == true);
160 
161  return (best_point);
162 }
163 
164 
173  EDGEPT *this_point;
174  EDGEPT *local_min = nullptr;
175  EDGEPT *local_max = nullptr;
176 
177  this_point = outline->loop;
178  local_min = this_point;
179  local_max = this_point;
180  do {
181  if (this_point->vec.y < 0) {
182  /* Look for minima */
183  if (local_max != nullptr)
184  new_max_point(local_max, points);
185  else if (is_inside_angle (this_point))
186  add_point_to_list(points, this_point);
187  local_max = nullptr;
188  local_min = this_point->next;
189  }
190  else if (this_point->vec.y > 0) {
191  /* Look for maxima */
192  if (local_min != nullptr)
193  new_min_point(local_min, points);
194  else if (is_inside_angle (this_point))
195  add_point_to_list(points, this_point);
196  local_min = nullptr;
197  local_max = this_point->next;
198  }
199  else {
200  /* Flat area */
201  if (local_max != nullptr) {
202  if (local_max->prev->vec.y != 0) {
203  new_max_point(local_max, points);
204  }
205  local_max = this_point->next;
206  local_min = nullptr;
207  }
208  else {
209  if (local_min->prev->vec.y != 0) {
210  new_min_point(local_min, points);
211  }
212  local_min = this_point->next;
213  local_max = nullptr;
214  }
215  }
216 
217  /* Next point */
218  this_point = this_point->next;
219  }
220  while (this_point != outline->loop);
221 }
222 
223 
231 void Wordrec::new_min_point(EDGEPT *local_min, PointHeap* points) {
232  int16_t dir;
233 
234  dir = direction (local_min);
235 
236  if (dir < 0) {
237  add_point_to_list(points, local_min);
238  return;
239  }
240 
241  if (dir == 0 && point_priority (local_min) < 0) {
242  add_point_to_list(points, local_min);
243  return;
244  }
245 }
246 
247 
255 void Wordrec::new_max_point(EDGEPT *local_max, PointHeap* points) {
256  int16_t dir;
257 
258  dir = direction (local_max);
259 
260  if (dir > 0) {
261  add_point_to_list(points, local_max);
262  return;
263  }
264 
265  if (dir == 0 && point_priority (local_max) < 0) {
266  add_point_to_list(points, local_max);
267  return;
268  }
269 }
270 
271 
284 void Wordrec::vertical_projection_point(EDGEPT *split_point, EDGEPT *target_point,
285  EDGEPT** best_point,
286  EDGEPT_CLIST *new_points) {
287  EDGEPT *p; /* Iterator */
288  EDGEPT *this_edgept; /* Iterator */
289  EDGEPT_C_IT new_point_it(new_points);
290  int x = split_point->pos.x; /* X value of vertical */
291  int best_dist = LARGE_DISTANCE;/* Best point found */
292 
293  if (*best_point != nullptr)
294  best_dist = edgept_dist(split_point, *best_point);
295 
296  p = target_point;
297  /* Look at each edge point */
298  do {
299  if (((p->pos.x <= x && x <= p->next->pos.x) ||
300  (p->next->pos.x <= x && x <= p->pos.x)) &&
301  !same_point(split_point->pos, p->pos) &&
302  !same_point(split_point->pos, p->next->pos) &&
303  !p->IsChopPt() &&
304  (*best_point == nullptr || !same_point((*best_point)->pos, p->pos))) {
305 
306  if (near_point(split_point, p, p->next, &this_edgept)) {
307  new_point_it.add_before_then_move(this_edgept);
308  }
309 
310  if (*best_point == nullptr)
311  best_dist = edgept_dist (split_point, this_edgept);
312 
313  this_edgept =
314  pick_close_point(split_point, this_edgept, &best_dist);
315  if (this_edgept)
316  *best_point = this_edgept;
317  }
318 
319  p = p->next;
320  }
321  while (p != target_point);
322 }
323 
324 } // namespace tesseract
tesseract::GenericHeap
Definition: genericheap.h:58
tesseract::Wordrec::point_priority
PRIORITY point_priority(EDGEPT *point)
Definition: chop.cpp:65
plotedges.h
MAX_NUM_POINTS
#define MAX_NUM_POINTS
Definition: chop.h:31
TPOINT
Definition: blobs.h:49
TESSLINE::loop
EDGEPT * loop
Definition: blobs.h:278
same_point
#define same_point(p1, p2)
Definition: outlines.h:42
tesseract::Wordrec::pick_close_point
EDGEPT * pick_close_point(EDGEPT *critical_point, EDGEPT *vertical_point, int *best_dist)
Definition: chop.cpp:134
chop.h
wordrec.h
TPOINT::length
int length() const
Definition: blobs.h:87
tesseract::Wordrec::chop_debug
int chop_debug
Definition: wordrec.h:204
tesseract::Wordrec::chop_vertical_creep
bool chop_vertical_creep
Definition: wordrec.h:206
TESSLINE
Definition: blobs.h:201
tesseract::Wordrec::angle_change
int angle_change(EDGEPT *point1, EDGEPT *point2, EDGEPT *point3)
Definition: chop.cpp:99
tesseract::Wordrec::is_inside_angle
bool is_inside_angle(EDGEPT *pt)
Definition: chop.cpp:89
tesseract::GenericHeap::size
int size() const
Definition: genericheap.h:71
EDGEPT::prev
EDGEPT * prev
Definition: blobs.h:191
TPOINT::dot
int dot(const TPOINT &other) const
Definition: blobs.h:82
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:284
tesseract::Wordrec::near_point
bool near_point(EDGEPT *point, EDGEPT *line_pt_0, EDGEPT *line_pt_1, EDGEPT **near_pt)
Definition: outlines.cpp:50
tesseract::Wordrec::new_max_point
void new_max_point(EDGEPT *local_max, PointHeap *points)
Definition: chop.cpp:255
TPOINT::x
int16_t x
Definition: blobs.h:91
LARGE_DISTANCE
#define LARGE_DISTANCE
Definition: outlines.h:30
is_exterior_point
#define is_exterior_point(edge, point)
Definition: outlines.h:86
TPOINT::y
int16_t y
Definition: blobs.h:92
edgept_dist
#define edgept_dist(p1, p2)
Definition: outlines.h:77
tesseract::Wordrec::prioritize_points
void prioritize_points(TESSLINE *outline, PointHeap *points)
Definition: chop.cpp:172
tesseract
Definition: baseapi.h:65
tesseract::Wordrec::add_point_to_list
void add_point_to_list(PointHeap *point_heap, EDGEPT *point)
Definition: chop.cpp:75
tesseract::Wordrec::new_min_point
void new_min_point(EDGEPT *local_min, PointHeap *points)
Definition: chop.cpp:231
EDGEPT::vec
VECTOR vec
Definition: blobs.h:185
callcpp.h
tesseract::KDPairInc
Definition: kdpair.h:51
tesseract::Wordrec::chop_inside_angle
int chop_inside_angle
Definition: wordrec.h:212
TPOINT::cross
int cross(const TPOINT &other) const
Definition: blobs.h:77
tesseract::GenericHeap::Push
void Push(Pair *entry)
Definition: genericheap.h:95
EDGEPT
Definition: blobs.h:97
EDGEPT::IsChopPt
bool IsChopPt() const
Definition: blobs.h:180
mark_outline
void mark_outline(EDGEPT *edgept)
Definition: plotedges.cpp:81
outlines.h
PRIORITY
float PRIORITY
Definition: seam.h:34
EDGEPT::pos
TPOINT pos
Definition: blobs.h:184
EDGEPT::next
EDGEPT * next
Definition: blobs.h:190