tesseract v5.3.3.20231005
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
35namespace tesseract {
36
37// Show if the line is going in the positive or negative X direction.
38static 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
73void 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
98int 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
136EDGEPT *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
226void 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
249void 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
277void 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
const char * p
void mark_outline(EDGEPT *edgept)
Definition: plotedges.cpp:83
float PRIORITY
Definition: seam.h:31
def next(obj)
Definition: ast.py:56
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
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