tesseract 4.1.1
Loading...
Searching...
No Matches
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
37namespace tesseract {
38
39// Show if the line is going in the positive or negative X direction.
40static 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
76void 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
100int 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
232void 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
256void 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
285void 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
float PRIORITY
Definition: seam.h:36
#define MAX_NUM_POINTS
Definition: chop.h:33
#define edgept_dist(p1, p2)
Definition: outlines.h:83
#define is_exterior_point(edge, point)
Definition: outlines.h:93
#define same_point(p1, p2)
Definition: outlines.h:45
#define LARGE_DISTANCE
Definition: outlines.h:32
void mark_outline(EDGEPT *edgept)
Definition: plotedges.cpp:86
Definition: blobs.h:51
int16_t x
Definition: blobs.h:93
int16_t y
Definition: blobs.h:94
int dot(const TPOINT &other) const
Definition: blobs.h:84
int length() const
Definition: blobs.h:89
int cross(const TPOINT &other) const
Definition: blobs.h:79
Definition: blobs.h:99
EDGEPT * next
Definition: blobs.h:192
VECTOR vec
Definition: blobs.h:187
EDGEPT * prev
Definition: blobs.h:193
bool IsChopPt() const
Definition: blobs.h:182
TPOINT pos
Definition: blobs.h:186
EDGEPT * loop
Definition: blobs.h:280
void Push(Pair *entry)
Definition: genericheap.h:95
bool is_inside_angle(EDGEPT *pt)
Definition: chop.cpp:90
void new_min_point(EDGEPT *local_min, PointHeap *points)
Definition: chop.cpp:232
void add_point_to_list(PointHeap *point_heap, EDGEPT *point)
Definition: chop.cpp:76
void prioritize_points(TESSLINE *outline, PointHeap *points)
Definition: chop.cpp:173
int angle_change(EDGEPT *point1, EDGEPT *point2, EDGEPT *point3)
Definition: chop.cpp:100
bool near_point(EDGEPT *point, EDGEPT *line_pt_0, EDGEPT *line_pt_1, EDGEPT **near_pt)
Definition: outlines.cpp:40
EDGEPT * pick_close_point(EDGEPT *critical_point, EDGEPT *vertical_point, int *best_dist)
Definition: chop.cpp:135
bool chop_vertical_creep
Definition: wordrec.h:206
void vertical_projection_point(EDGEPT *split_point, EDGEPT *target_point, EDGEPT **best_point, EDGEPT_CLIST *new_points)
Definition: chop.cpp:285
PRIORITY point_priority(EDGEPT *point)
Definition: chop.cpp:66
void new_max_point(EDGEPT *local_max, PointHeap *points)
Definition: chop.cpp:256