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 #include "chop.h"
30 #include "outlines.h"
31 #include "olutil.h"
32 #include "tordvars.h"
33 #include "callcpp.h"
34 #include "plotedges.h"
35 #include "const.h"
36
37 #include <math.h>
38
39 /*----------------------------------------------------------------------
40 V a r i a b l e s
41 ----------------------------------------------------------------------*/
42 INT_VAR(chop_debug, 0, "Chop debug");
43
44 BOOL_VAR(chop_enable, 1, "Chop enable");
45
46 BOOL_VAR(chop_vertical_creep, 0, "Vertical creep");
47
48 INT_VAR(chop_split_length, 10000, "Split Length");
49
50 INT_VAR(chop_same_distance, 2, "Same distance");
51
52 INT_VAR(chop_min_outline_points, 6, "Min Number of Points on Outline");
53
54 INT_VAR(chop_inside_angle, -50, "Min Inside Angle Bend");
55
56 INT_VAR(chop_min_outline_area, 2000, "Min Outline Area");
57
58 double_VAR(chop_split_dist_knob, 0.5, "Split length adjustment");
59
60 double_VAR(chop_overlap_knob, 0.9, "Split overlap adjustment");
61
62 double_VAR(chop_center_knob, 0.15, "Split center adjustment");
63
64 double_VAR(chop_sharpness_knob, 0.06, "Split sharpness adjustment");
65
66 double_VAR(chop_width_change_knob, 5.0, "Width change adjustment");
67
68 double_VAR(chop_ok_split, 100.0, "OK split limit");
69
70 double_VAR(chop_good_split, 50.0, "Good split limit");
71
72 INT_VAR(chop_x_y_weight, 3, "X / Y length weight");
73
74 /*----------------------------------------------------------------------
75 M a c r o s
76 ----------------------------------------------------------------------*/
77 /**********************************************************************
78 * length_product
79 *
80 * Compute the product of the length of two vectors. The
81 * vectors must be of type POINT. This product is used in computing
82 * angles.
83 **********************************************************************/
84 #define length_product(p1,p2) \
85 (sqrt ((((float) (p1).x * (p1).x + (float) (p1).y * (p1).y) * \
86 ((float) (p2).x * (p2).x + (float) (p2).y * (p2).y))))
87
88 /*----------------------------------------------------------------------
89 F u n c t i o n s
90 ----------------------------------------------------------------------*/
91 /**********************************************************************
92 * point_priority
93 *
94 * Assign a priority to and edge point that might be used as part of a
95 * split. The argument should be of type EDGEPT.
96 **********************************************************************/
point_priority(EDGEPT * point)97 PRIORITY point_priority(EDGEPT *point) {
98 return ((PRIORITY) point_bend_angle (point));
99 }
100
101
102 /**********************************************************************
103 * add_point_to_list
104 *
105 * Add an edge point to a POINT_GROUP containg a list of other points.
106 **********************************************************************/
add_point_to_list(POINT_GROUP point_list,EDGEPT * point)107 void add_point_to_list(POINT_GROUP point_list, EDGEPT *point) {
108 HEAPENTRY data;
109
110 if (SizeOfHeap (point_list) < MAX_NUM_POINTS - 2) {
111 data.Data = (char *) point;
112 data.Key = point_priority (point);
113 HeapStore(point_list, &data);
114 }
115
116 #ifndef GRAPHICS_DISABLED
117 if (chop_debug > 2)
118 mark_outline(point);
119 #endif
120 }
121
122
123 /**********************************************************************
124 * angle_change
125 *
126 * Return the change in angle (degrees) of the line segments between
127 * points one and two, and two and three.
128 **********************************************************************/
angle_change(EDGEPT * point1,EDGEPT * point2,EDGEPT * point3)129 int angle_change(EDGEPT *point1, EDGEPT *point2, EDGEPT *point3) {
130 VECTOR vector1;
131 VECTOR vector2;
132
133 int angle;
134 float length;
135
136 /* Compute angle */
137 vector1.x = point2->pos.x - point1->pos.x;
138 vector1.y = point2->pos.y - point1->pos.y;
139 vector2.x = point3->pos.x - point2->pos.x;
140 vector2.y = point3->pos.y - point2->pos.y;
141 /* Use cross product */
142 length = length_product (vector1, vector2);
143 if ((int) length == 0)
144 return (0);
145 angle = static_cast<int>(floor(asin(CROSS (vector1, vector2) /
146 length) / PI * 180.0 + 0.5));
147
148 /* Use dot product */
149 if (SCALAR (vector1, vector2) < 0)
150 angle = 180 - angle;
151 /* Adjust angle */
152 if (angle > 180)
153 angle -= 360;
154 if (angle <= -180)
155 angle += 360;
156 return (angle);
157 }
158
159 /**********************************************************************
160 * is_little_chunk
161 *
162 * Return TRUE if one of the pieces resulting from this split would
163 * less than some number of edge points.
164 **********************************************************************/
is_little_chunk(EDGEPT * point1,EDGEPT * point2)165 int is_little_chunk(EDGEPT *point1, EDGEPT *point2) {
166 EDGEPT *p = point1; /* Iterator */
167 int counter = 0;
168
169 do {
170 /* Go from P1 to P2 */
171 if (is_same_edgept (point2, p)) {
172 if (is_small_area (point1, point2))
173 return (TRUE);
174 else
175 break;
176 }
177 p = p->next;
178 }
179 while ((p != point1) && (counter++ < chop_min_outline_points));
180 /* Go from P2 to P1 */
181 p = point2;
182 counter = 0;
183 do {
184 if (is_same_edgept (point1, p)) {
185 return (is_small_area (point2, point1));
186 }
187 p = p->next;
188 }
189 while ((p != point2) && (counter++ < chop_min_outline_points));
190
191 return (FALSE);
192 }
193
194
195 /**********************************************************************
196 * is_small_area
197 *
198 * Test the area defined by a split accross this outline.
199 **********************************************************************/
is_small_area(EDGEPT * point1,EDGEPT * point2)200 int is_small_area(EDGEPT *point1, EDGEPT *point2) {
201 EDGEPT *p = point1->next; /* Iterator */
202 int area = 0;
203 TPOINT origin;
204
205 do {
206 /* Go from P1 to P2 */
207 origin.x = p->pos.x - point1->pos.x;
208 origin.y = p->pos.y - point1->pos.y;
209 area += CROSS (origin, p->vec);
210 p = p->next;
211 }
212 while (!is_same_edgept (point2, p));
213
214 return (area < chop_min_outline_area);
215 }
216
217
218 /**********************************************************************
219 * pick_close_point
220 *
221 * Choose the edge point that is closest to the critical point. This
222 * point may not be exactly vertical from the critical point.
223 **********************************************************************/
pick_close_point(EDGEPT * critical_point,EDGEPT * vertical_point,int * best_dist)224 EDGEPT *pick_close_point(EDGEPT *critical_point,
225 EDGEPT *vertical_point,
226 int *best_dist) {
227 EDGEPT *best_point = NULL;
228 int this_distance;
229 int found_better;
230
231 do {
232 found_better = FALSE;
233
234 this_distance = edgept_dist (critical_point, vertical_point);
235 if (this_distance <= *best_dist) {
236
237 if (!(same_point (critical_point->pos, vertical_point->pos) ||
238 same_point (critical_point->pos, vertical_point->next->pos) ||
239 (best_point && same_point (best_point->pos, vertical_point->pos)) ||
240 is_exterior_point (critical_point, vertical_point))) {
241 *best_dist = this_distance;
242 best_point = vertical_point;
243 if (chop_vertical_creep)
244 found_better = TRUE;
245 }
246 }
247 vertical_point = vertical_point->next;
248 }
249 while (found_better == TRUE);
250
251 return (best_point);
252 }
253
254
255 /**********************************************************************
256 * prioritize_points
257 *
258 * Find a list of edge points from the outer outline of this blob. For
259 * each of these points assign a priority. Sort these points using a
260 * heap structure so that they can be visited in order.
261 **********************************************************************/
prioritize_points(TESSLINE * outline,POINT_GROUP points)262 void prioritize_points(TESSLINE *outline, POINT_GROUP points) {
263 EDGEPT *this_point;
264 EDGEPT *local_min = NULL;
265 EDGEPT *local_max = NULL;
266
267 this_point = outline->loop;
268 local_min = this_point;
269 local_max = this_point;
270 do {
271 if (tord_debug_5)
272 cprintf ("(%3d,%3d) min=%3d, max=%3d, dir=%2d, ang=%2.0f\n",
273 this_point->pos.x, this_point->pos.y,
274 (local_min ? local_min->pos.y : 999),
275 (local_max ? local_max->pos.y : 999),
276 direction (this_point), point_priority (this_point));
277
278 if (this_point->vec.y < 0) {
279 /* Look for minima */
280 if (local_max != NULL)
281 new_max_point(local_max, points);
282 else if (is_inside_angle (this_point))
283 add_point_to_list(points, this_point);
284 local_max = NULL;
285 local_min = this_point->next;
286 }
287 else if (this_point->vec.y > 0) {
288 /* Look for maxima */
289 if (local_min != NULL)
290 new_min_point(local_min, points);
291 else if (is_inside_angle (this_point))
292 add_point_to_list(points, this_point);
293 local_min = NULL;
294 local_max = this_point->next;
295 }
296 else {
297 /* Flat area */
298 if (local_max != NULL) {
299 if (local_max->prev->vec.y != 0) {
300 new_max_point(local_max, points);
301 }
302 local_max = this_point->next;
303 local_min = NULL;
304 }
305 else {
306 if (local_min->prev->vec.y != 0) {
307 new_min_point(local_min, points);
308 }
309 local_min = this_point->next;
310 local_max = NULL;
311 }
312 }
313
314 /* Next point */
315 this_point = this_point->next;
316 }
317 while (this_point != outline->loop);
318 }
319
320
321 /**********************************************************************
322 * new_min_point
323 *
324 * Found a new minimum point try to decide whether to save it or not.
325 * Return the new value for the local minimum. If a point is saved then
326 * the local minimum is reset to NULL.
327 **********************************************************************/
new_min_point(EDGEPT * local_min,POINT_GROUP points)328 void new_min_point(EDGEPT *local_min, POINT_GROUP points) {
329 inT16 dir;
330
331 dir = direction (local_min);
332
333 if (dir < 0) {
334 add_point_to_list(points, local_min);
335 return;
336 }
337
338 if (dir == 0 && point_priority (local_min) < 0) {
339 add_point_to_list(points, local_min);
340 return;
341 }
342 }
343
344
345 /**********************************************************************
346 * new_max_point
347 *
348 * Found a new minimum point try to decide whether to save it or not.
349 * Return the new value for the local minimum. If a point is saved then
350 * the local minimum is reset to NULL.
351 **********************************************************************/
new_max_point(EDGEPT * local_max,POINT_GROUP points)352 void new_max_point(EDGEPT *local_max, POINT_GROUP points) {
353 inT16 dir;
354
355 dir = direction (local_max);
356
357 if (dir > 0) {
358 add_point_to_list(points, local_max);
359 return;
360 }
361
362 if (dir == 0 && point_priority (local_max) < 0) {
363 add_point_to_list(points, local_max);
364 return;
365 }
366 }
367
368
369 /**********************************************************************
370 * vertical_projection_point
371 *
372 * For one point on the outline, find the corresponding point on the
373 * other side of the outline that is a likely projection for a split
374 * point. This is done by iterating through the edge points until the
375 * X value of the point being looked at is greater than the X value of
376 * the split point. Ensure that the point being returned is not right
377 * next to the split point. Return the edge point as a result.
378 **********************************************************************/
vertical_projection_point(EDGEPT * split_point,EDGEPT * target_point,EDGEPT ** best_point)379 void vertical_projection_point(EDGEPT *split_point, EDGEPT *target_point,
380 EDGEPT** best_point) {
381 EDGEPT *p; /* Iterator */
382 EDGEPT *this_edgept; /* Iterator */
383 int x = split_point->pos.x; /* X value of vertical */
384 int best_dist = LARGE_DISTANCE;/* Best point found */
385
386 if (*best_point != NULL)
387 best_dist = edgept_dist(split_point, *best_point);
388
389 p = target_point;
390 /* Look at each edge point */
391 do {
392 if ((((p->pos.x <= x) && (x <= p->next->pos.x)) ||
393 ((p->next->pos.x <= x) && (x <= p->pos.x))) &&
394 !same_point (split_point->pos, p->pos) &&
395 !same_point (split_point->pos, p->next->pos)
396 && (*best_point == NULL || !same_point ((*best_point)->pos, p->pos))) {
397
398 this_edgept = near_point (split_point, p, p->next);
399
400 if (*best_point == NULL)
401 best_dist = edgept_dist (split_point, this_edgept);
402
403 this_edgept =
404 pick_close_point(split_point, this_edgept, &best_dist);
405 if (this_edgept)
406 *best_point = this_edgept;
407 }
408
409 p = p->next;
410 }
411 while (p != target_point);
412 }
413