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.
direction(const EDGEPT * point)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
58 /**
59 * @name point_priority
60 *
61 * Assign a priority to and edge point that might be used as part of a
62 * split. The argument should be of type EDGEPT.
63 */
point_priority(EDGEPT * point)64 PRIORITY Wordrec::point_priority(EDGEPT *point) {
65 return static_cast<PRIORITY>(angle_change(point->prev, point, point->next));
66 }
67
68 /**
69 * @name add_point_to_list
70 *
71 * Add an edge point to a POINT_GROUP containing a list of other points.
72 */
add_point_to_list(PointHeap * point_heap,EDGEPT * point)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.
is_inside_angle(EDGEPT * pt)88 bool Wordrec::is_inside_angle(EDGEPT *pt) {
89 return angle_change(pt->prev, pt, pt->next) < chop_inside_angle;
90 }
91
92 /**
93 * @name angle_change
94 *
95 * Return the change in angle (degrees) of the line segments between
96 * points one and two, and two and three.
97 */
angle_change(EDGEPT * point1,EDGEPT * point2,EDGEPT * point3)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
130 /**
131 * @name pick_close_point
132 *
133 * Choose the edge point that is closest to the critical point. This
134 * point may not be exactly vertical from the critical point.
135 */
pick_close_point(EDGEPT * critical_point,EDGEPT * vertical_point,int * best_dist)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
163 /**
164 * @name prioritize_points
165 *
166 * Find a list of edge points from the outer outline of this blob. For
167 * each of these points assign a priority. Sort these points using a
168 * heap structure so that they can be visited in order.
169 */
prioritize_points(TESSLINE * outline,PointHeap * points)170 void Wordrec::prioritize_points(TESSLINE *outline, PointHeap *points) {
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
219 /**
220 * @name new_min_point
221 *
222 * Found a new minimum point try to decide whether to save it or not.
223 * Return the new value for the local minimum. If a point is saved then
224 * the local minimum is reset to nullptr.
225 */
new_min_point(EDGEPT * local_min,PointHeap * points)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
242 /**
243 * @name new_max_point
244 *
245 * Found a new minimum point try to decide whether to save it or not.
246 * Return the new value for the local minimum. If a point is saved then
247 * the local minimum is reset to nullptr.
248 */
new_max_point(EDGEPT * local_max,PointHeap * points)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
265 /**
266 * @name vertical_projection_point
267 *
268 * For one point on the outline, find the corresponding point on the
269 * other side of the outline that is a likely projection for a split
270 * point. This is done by iterating through the edge points until the
271 * X value of the point being looked at is greater than the X value of
272 * the split point. Ensure that the point being returned is not right
273 * next to the split point. Return the edge point in *best_point as
274 * a result, and any points that were newly created are also saved on
275 * the new_points list.
276 */
vertical_projection_point(EDGEPT * split_point,EDGEPT * target_point,EDGEPT ** best_point,EDGEPT_CLIST * new_points)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
314