All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
chop.cpp
Go to the documentation of this file.
1 /* -*-C-*-
2  ********************************************************************************
3  *
4  * File: chop.c (Formerly chop.c)
5  * Description:
6  * Author: Mark Seaman, OCR Technology
7  * Created: Fri Oct 16 14:37:00 1987
8  * Modified: Tue Jul 30 16:41:11 1991 (Mark Seaman) marks@hpgrlt
9  * Language: C
10  * Package: N/A
11  * Status: Reusable Software Component
12  *
13  * (c) Copyright 1987, Hewlett-Packard Company.
14  ** Licensed under the Apache License, Version 2.0 (the "License");
15  ** you may not use this file except in compliance with the License.
16  ** You may obtain a copy of the License at
17  ** http://www.apache.org/licenses/LICENSE-2.0
18  ** Unless required by applicable law or agreed to in writing, software
19  ** distributed under the License is distributed on an "AS IS" BASIS,
20  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
21  ** See the License for the specific language governing permissions and
22  ** limitations under the License.
23  *
24  *********************************************************************************/
25 
26 /*----------------------------------------------------------------------
27  I n c l u d e s
28 ----------------------------------------------------------------------*/
29 
30 #include "chop.h"
31 #include "outlines.h"
32 #include "callcpp.h"
33 #include "plotedges.h"
34 #include "const.h"
35 #include "wordrec.h"
36 
37 #include <math.h>
38 
39 // Include automatically generated configuration file if running autoconf.
40 #ifdef HAVE_CONFIG_H
41 #include "config_auto.h"
42 #endif
43 
44 namespace tesseract {
45 /*----------------------------------------------------------------------
46  F u n c t i o n s
47 ----------------------------------------------------------------------*/
55  return (PRIORITY)angle_change(point->prev, point, point->next);
56 }
57 
58 
64 void Wordrec::add_point_to_list(PointHeap* point_heap, EDGEPT *point) {
65  if (point_heap->size() < MAX_NUM_POINTS - 2) {
66  PointPair pair(point_priority(point), point);
67  point_heap->Push(&pair);
68  }
69 
70 #ifndef GRAPHICS_DISABLED
71  if (chop_debug > 2)
72  mark_outline(point);
73 #endif
74 }
75 
76 // Returns true if the edgept supplied as input is an inside angle. This
77 // is determined by the angular change of the vectors from point to point.
79  return angle_change(pt->prev, pt, pt->next) < chop_inside_angle;
80 }
81 
88 int Wordrec::angle_change(EDGEPT *point1, EDGEPT *point2, EDGEPT *point3) {
89  VECTOR vector1;
90  VECTOR vector2;
91 
92  int angle;
93  float length;
94 
95  /* Compute angle */
96  vector1.x = point2->pos.x - point1->pos.x;
97  vector1.y = point2->pos.y - point1->pos.y;
98  vector2.x = point3->pos.x - point2->pos.x;
99  vector2.y = point3->pos.y - point2->pos.y;
100  /* Use cross product */
101  length = (float)sqrt((float)LENGTH(vector1) * LENGTH(vector2));
102  if ((int) length == 0)
103  return (0);
104  angle = static_cast<int>(floor(asin(CROSS (vector1, vector2) /
105  length) / PI * 180.0 + 0.5));
106 
107  /* Use dot product */
108  if (SCALAR (vector1, vector2) < 0)
109  angle = 180 - angle;
110  /* Adjust angle */
111  if (angle > 180)
112  angle -= 360;
113  if (angle <= -180)
114  angle += 360;
115  return (angle);
116 }
117 
125  EDGEPT *vertical_point,
126  int *best_dist) {
127  EDGEPT *best_point = NULL;
128  int this_distance;
129  int found_better;
130 
131  do {
132  found_better = FALSE;
133 
134  this_distance = edgept_dist (critical_point, vertical_point);
135  if (this_distance <= *best_dist) {
136 
137  if (!(same_point (critical_point->pos, vertical_point->pos) ||
138  same_point (critical_point->pos, vertical_point->next->pos) ||
139  (best_point && same_point (best_point->pos, vertical_point->pos)) ||
140  is_exterior_point (critical_point, vertical_point))) {
141  *best_dist = this_distance;
142  best_point = vertical_point;
144  found_better = TRUE;
145  }
146  }
147  vertical_point = vertical_point->next;
148  }
149  while (found_better == TRUE);
150 
151  return (best_point);
152 }
153 
154 
163  EDGEPT *this_point;
164  EDGEPT *local_min = NULL;
165  EDGEPT *local_max = NULL;
166 
167  this_point = outline->loop;
168  local_min = this_point;
169  local_max = this_point;
170  do {
171  if (this_point->vec.y < 0) {
172  /* Look for minima */
173  if (local_max != NULL)
174  new_max_point(local_max, points);
175  else if (is_inside_angle (this_point))
176  add_point_to_list(points, this_point);
177  local_max = NULL;
178  local_min = this_point->next;
179  }
180  else if (this_point->vec.y > 0) {
181  /* Look for maxima */
182  if (local_min != NULL)
183  new_min_point(local_min, points);
184  else if (is_inside_angle (this_point))
185  add_point_to_list(points, this_point);
186  local_min = NULL;
187  local_max = this_point->next;
188  }
189  else {
190  /* Flat area */
191  if (local_max != NULL) {
192  if (local_max->prev->vec.y != 0) {
193  new_max_point(local_max, points);
194  }
195  local_max = this_point->next;
196  local_min = NULL;
197  }
198  else {
199  if (local_min->prev->vec.y != 0) {
200  new_min_point(local_min, points);
201  }
202  local_min = this_point->next;
203  local_max = NULL;
204  }
205  }
206 
207  /* Next point */
208  this_point = this_point->next;
209  }
210  while (this_point != outline->loop);
211 }
212 
213 
221 void Wordrec::new_min_point(EDGEPT *local_min, PointHeap* points) {
222  inT16 dir;
223 
224  dir = direction (local_min);
225 
226  if (dir < 0) {
227  add_point_to_list(points, local_min);
228  return;
229  }
230 
231  if (dir == 0 && point_priority (local_min) < 0) {
232  add_point_to_list(points, local_min);
233  return;
234  }
235 }
236 
237 
245 void Wordrec::new_max_point(EDGEPT *local_max, PointHeap* points) {
246  inT16 dir;
247 
248  dir = direction (local_max);
249 
250  if (dir > 0) {
251  add_point_to_list(points, local_max);
252  return;
253  }
254 
255  if (dir == 0 && point_priority (local_max) < 0) {
256  add_point_to_list(points, local_max);
257  return;
258  }
259 }
260 
261 
274 void Wordrec::vertical_projection_point(EDGEPT *split_point, EDGEPT *target_point,
275  EDGEPT** best_point,
276  EDGEPT_CLIST *new_points) {
277  EDGEPT *p; /* Iterator */
278  EDGEPT *this_edgept; /* Iterator */
279  EDGEPT_C_IT new_point_it(new_points);
280  int x = split_point->pos.x; /* X value of vertical */
281  int best_dist = LARGE_DISTANCE;/* Best point found */
282 
283  if (*best_point != NULL)
284  best_dist = edgept_dist(split_point, *best_point);
285 
286  p = target_point;
287  /* Look at each edge point */
288  do {
289  if (((p->pos.x <= x && x <= p->next->pos.x) ||
290  (p->next->pos.x <= x && x <= p->pos.x)) &&
291  !same_point(split_point->pos, p->pos) &&
292  !same_point(split_point->pos, p->next->pos) &&
293  !p->IsChopPt() &&
294  (*best_point == NULL || !same_point((*best_point)->pos, p->pos))) {
295 
296  if (near_point(split_point, p, p->next, &this_edgept)) {
297  new_point_it.add_before_then_move(this_edgept);
298  }
299 
300  if (*best_point == NULL)
301  best_dist = edgept_dist (split_point, this_edgept);
302 
303  this_edgept =
304  pick_close_point(split_point, this_edgept, &best_dist);
305  if (this_edgept)
306  *best_point = this_edgept;
307  }
308 
309  p = p->next;
310  }
311  while (p != target_point);
312 }
313 
314 } // namespace tesseract
#define MAX_NUM_POINTS
Definition: chop.h:39
bool near_point(EDGEPT *point, EDGEPT *line_pt_0, EDGEPT *line_pt_1, EDGEPT **near_pt)
Definition: outlines.cpp:49
bool IsChopPt() const
Definition: blobs.h:159
EDGEPT * prev
Definition: blobs.h:170
void add_point_to_list(PointHeap *point_heap, EDGEPT *point)
Definition: chop.cpp:64
void new_max_point(EDGEPT *local_max, PointHeap *points)
Definition: chop.cpp:245
int direction(EDGEPT *point)
Definition: vecfuncs.cpp:43
#define is_exterior_point(edge, point)
Definition: outlines.h:97
inT16 y
Definition: blobs.h:72
bool is_inside_angle(EDGEPT *pt)
Definition: chop.cpp:78
float PRIORITY
Definition: seam.h:42
EDGEPT * pick_close_point(EDGEPT *critical_point, EDGEPT *vertical_point, int *best_dist)
Definition: chop.cpp:124
PRIORITY point_priority(EDGEPT *point)
Definition: chop.cpp:54
void vertical_projection_point(EDGEPT *split_point, EDGEPT *target_point, EDGEPT **best_point, EDGEPT_CLIST *new_points)
Definition: chop.cpp:274
int angle_change(EDGEPT *point1, EDGEPT *point2, EDGEPT *point3)
Definition: chop.cpp:88
#define edgept_dist(p1, p2)
Definition: outlines.h:87
VECTOR vec
Definition: blobs.h:164
#define CROSS(a, b)
Definition: vecfuncs.h:52
#define same_point(p1, p2)
Definition: outlines.h:49
Definition: blobs.h:50
EDGEPT * next
Definition: blobs.h:169
void Push(Pair *entry)
Definition: genericheap.h:95
inT16 x
Definition: blobs.h:71
void new_min_point(EDGEPT *local_min, PointHeap *points)
Definition: chop.cpp:221
void prioritize_points(TESSLINE *outline, PointHeap *points)
Definition: chop.cpp:162
bool chop_vertical_creep
Definition: wordrec.h:141
#define FALSE
Definition: capi.h:29
TPOINT pos
Definition: blobs.h:163
Definition: blobs.h:76
#define PI
Definition: const.h:19
#define TRUE
Definition: capi.h:28
#define SCALAR(a, b)
Definition: vecfuncs.h:61
#define LENGTH(a)
Definition: vecfuncs.h:70
#define NULL
Definition: host.h:144
void mark_outline(EDGEPT *edgept)
Definition: plotedges.cpp:95
EDGEPT * loop
Definition: blobs.h:257
#define LARGE_DISTANCE
Definition: outlines.h:36
short inT16
Definition: host.h:100