Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
fpchop.cpp
Go to the documentation of this file.
1 /**********************************************************************
2 * File: fpchop.cpp (Formerly fp_chop.c)
3 * Description: Code to chop fixed pitch text into character cells.
4 * Author: Ray Smith
5 * Created: Thu Sep 16 11:14:15 BST 1993
6 *
7 * (C) Copyright 1993, Hewlett-Packard Ltd.
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 #include "mfcpch.h"
21 #ifdef __UNIX__
22 #include <assert.h>
23 #endif
24 #include "stderr.h"
25 #include "blobbox.h"
26 #include "statistc.h"
27 #include "drawtord.h"
28 #include "tovars.h"
29 #include "topitch.h"
30 #include "fpchop.h"
31 #include "notdll.h"
32
33 // Include automatically generated configuration file if running autoconf.
34 #ifdef HAVE_CONFIG_H
35 #include "config_auto.h"
36 #endif
37
38 #define EXTERN
39
40 EXTERN INT_VAR (textord_fp_chop_error, 2,
41 "Max allowed bending of chop cells");
42 EXTERN double_VAR (textord_fp_chop_snap, 0.5,
43 "Max distance of chop pt from vertex");
44
45 ELISTIZE(C_OUTLINE_FRAG)
46 //#undef ASSERT_HOST
47 //#define ASSERT_HOST(x) if (!(x)) AfxMessageBox(#x);
48 /**********************************************************************
49 * fixed_pitch_words
50 *
51 * Make a ROW from a fixed pitch TO_ROW.
52 **********************************************************************/
53 ROW *fixed_pitch_words( //find lines
54 TO_ROW *row, //row to do
55 FCOORD rotation //for drawing
56 ) {
57 BOOL8 bol; //start of line
58 uinT8 blanks; //in front of word
59 uinT8 new_blanks; //blanks in empty cell
60 inT16 chop_coord; //chop boundary
61 inT16 prev_chop_coord; //start of cell
62 inT16 rep_left; //left edge of rep word
63 ROW *real_row; //output row
64 C_OUTLINE_LIST left_coutlines;
65 C_OUTLINE_LIST right_coutlines;
66 C_BLOB_LIST cblobs;
67 C_BLOB_IT cblob_it = &cblobs;
68 WERD_LIST words;
69 WERD_IT word_it = &words; //new words
70 //repeated blobs
71 WERD_IT rep_it = &row->rep_words;
72 WERD *word; //new word
73 inT32 xstarts[2]; //row ends
74 double coeffs[3]; //quadratic
75 inT32 prev_x; //end of prev blob
76 //iterator
77 BLOBNBOX_IT box_it = row->blob_list ();
78 //boundaries
79 ICOORDELT_IT cell_it = &row->char_cells;
80
81 #ifndef GRAPHICS_DISABLED
82 if (textord_show_page_cuts && to_win != NULL) {
83 plot_row_cells (to_win, ScrollView::RED, row, 0, &row->char_cells);
84 }
85 #endif
86
87 prev_x = -MAX_INT16;
88 bol = TRUE;
89 blanks = 0;
90 if (rep_it.empty ())
91 rep_left = MAX_INT16;
92 else
93 rep_left = rep_it.data ()->bounding_box ().left ();
94 if (box_it.empty ())
95 return NULL; //empty row
96 xstarts[0] = box_it.data ()->bounding_box ().left ();
97 if (rep_left < xstarts[0]) {
98 xstarts[0] = rep_left;
99 }
100 if (cell_it.empty () || row->char_cells.singleton ()) {
101 tprintf ("Row without enough char cells!\n");
102 tprintf ("Leftmost blob is at (%d,%d)\n",
103 box_it.data ()->bounding_box ().left (),
104 box_it.data ()->bounding_box ().bottom ());
105 return NULL;
106 }
107 ASSERT_HOST (!cell_it.empty () && !row->char_cells.singleton ());
108 prev_chop_coord = cell_it.data ()->x ();
109 word = NULL;
110 while (rep_left < cell_it.data ()->x ()) {
111 word = add_repeated_word (&rep_it, rep_left, prev_chop_coord,
112 blanks, row->fixed_pitch, &word_it);
113 }
114 cell_it.mark_cycle_pt ();
115 if (prev_chop_coord >= cell_it.data ()->x ())
116 cell_it.forward ();
117 for (; !cell_it.cycled_list (); cell_it.forward ()) {
118 chop_coord = cell_it.data ()->x ();
119 while (!box_it.empty ()
120 && box_it.data ()->bounding_box ().left () <= chop_coord) {
121 if (box_it.data ()->bounding_box ().right () > prev_x)
122 prev_x = box_it.data ()->bounding_box ().right ();
123 split_to_blob (box_it.extract (), chop_coord,
124 textord_fp_chop_error + 0.5f,
125 &left_coutlines,
126 &right_coutlines);
127 box_it.forward ();
128 while (!box_it.empty() && box_it.data()->cblob() == NULL) {
129 delete box_it.extract();
130 box_it.forward();
131 }
132 }
133 if (!right_coutlines.empty() && left_coutlines.empty())
134 split_to_blob (NULL, chop_coord,
135 textord_fp_chop_error + 0.5f,
136 &left_coutlines,
137 &right_coutlines);
138 if (!left_coutlines.empty ())
139 cblob_it.add_after_then_move (new C_BLOB (&left_coutlines));
140 else {
141 if (rep_left < chop_coord) {
142 if (rep_left > prev_chop_coord)
143 new_blanks = (uinT8) floor ((rep_left - prev_chop_coord)
144 / row->fixed_pitch + 0.5);
145 else
146 new_blanks = 0;
147 }
148 else {
149 if (chop_coord > prev_chop_coord)
150 new_blanks = (uinT8) floor ((chop_coord - prev_chop_coord)
151 / row->fixed_pitch + 0.5);
152 else
153 new_blanks = 0;
154 }
155 if (!cblob_it.empty()) {
156 if (blanks < 1 && word != NULL && !word->flag (W_REP_CHAR))
157 blanks = 1;
158 word = new WERD (&cblobs, blanks, NULL);
159 cblob_it.set_to_list (&cblobs);
160 word->set_flag (W_DONT_CHOP, TRUE);
161 word_it.add_after_then_move (word);
162 if (bol) {
163 word->set_flag (W_BOL, TRUE);
164 bol = FALSE;
165 }
166 blanks = new_blanks;
167 }
168 else
169 blanks += new_blanks;
170 while (rep_left < chop_coord) {
171 word = add_repeated_word (&rep_it, rep_left, prev_chop_coord,
172 blanks, row->fixed_pitch, &word_it);
173 }
174 }
175 if (prev_chop_coord < chop_coord)
176 prev_chop_coord = chop_coord;
177 }
178 if (!cblob_it.empty()) {
179 word = new WERD(&cblobs, blanks, NULL);
180 word->set_flag (W_DONT_CHOP, TRUE);
181 word_it.add_after_then_move (word);
182 if (bol)
183 word->set_flag (W_BOL, TRUE);
184 }
185 ASSERT_HOST (word != NULL);
186 while (!rep_it.empty ()) {
187 add_repeated_word (&rep_it, rep_left, prev_chop_coord,
188 blanks, row->fixed_pitch, &word_it);
189 }
190 //at end of line
191 word_it.data ()->set_flag (W_EOL, TRUE);
192 if (prev_chop_coord > prev_x)
193 prev_x = prev_chop_coord;
194 xstarts[1] = prev_x + 1;
195 coeffs[0] = 0;
196 coeffs[1] = row->line_m ();
197 coeffs[2] = row->line_c ();
198 real_row = new ROW (row, (inT16) row->kern_size, (inT16) row->space_size);
199 word_it.set_to_list (real_row->word_list ());
200 //put words in row
201 word_it.add_list_after (&words);
202 real_row->recalc_bounding_box ();
203 return real_row;
204 }
205
206
207 /**********************************************************************
208 * add_repeated_word
209 *
210 * Add repeated word into the row at the given point.
211 **********************************************************************/
212
213 WERD *add_repeated_word( //move repeated word
214 WERD_IT *rep_it, //repeated words
215 inT16 &rep_left, //left edge of word
216 inT16 &prev_chop_coord, //previous word end
217 uinT8 &blanks, //no of blanks
218 float pitch, //char cell size
219 WERD_IT *word_it //list of words
220 ) {
221 WERD *word; //word to move
222 inT16 new_blanks; //extra blanks
223
224 if (rep_left > prev_chop_coord) {
225 new_blanks = (uinT8) floor ((rep_left - prev_chop_coord) / pitch + 0.5);
226 blanks += new_blanks;
227 }
228 word = rep_it->extract ();
229 prev_chop_coord = word->bounding_box ().right ();
230 word_it->add_after_then_move (word);
231 word->set_blanks (blanks);
232 rep_it->forward ();
233 if (rep_it->empty ())
234 rep_left = MAX_INT16;
235 else
236 rep_left = rep_it->data ()->bounding_box ().left ();
237 blanks = 0;
238 return word;
239 }
240
241
242 /**********************************************************************
243 * split_to_blob
244 *
245 * Split a BLOBNBOX across a vertical chop line and put the pieces
246 * into a left outline list and a right outline list.
247 **********************************************************************/
248
249 void split_to_blob( //split the blob
250 BLOBNBOX *blob, //blob to split
251 inT16 chop_coord, //place to chop
252 float pitch_error, //allowed deviation
253 C_OUTLINE_LIST *left_coutlines, //for cblobs
254 C_OUTLINE_LIST *right_coutlines) {
255 C_BLOB *real_cblob; //cblob to chop
256
257 if (blob != NULL) {
258 real_cblob = blob->cblob();
259 } else {
260 real_cblob = NULL;
261 }
262 if (!right_coutlines->empty() || real_cblob != NULL)
263 fixed_chop_cblob(real_cblob,
264 chop_coord,
265 pitch_error,
266 left_coutlines,
267 right_coutlines);
268 if (blob != NULL)
269 delete blob; //free it
270 }
271
272 /**********************************************************************
273 * fixed_chop_cblob
274 *
275 * Chop the given cblob (if any) and the existing right outlines to
276 * produce a list of outlines left of the chop point and more to the right.
277 **********************************************************************/
278
279 void fixed_chop_cblob( //split the blob
280 C_BLOB *blob, //blob to split
281 inT16 chop_coord, //place to chop
282 float pitch_error, //allowed deviation
283 C_OUTLINE_LIST *left_outlines, //left half of chop
284 C_OUTLINE_LIST *right_outlines //right half of chop
285 ) {
286 C_OUTLINE *old_right; //already there
287 C_OUTLINE_LIST new_outlines; //new right ones
288 //ouput iterator
289 C_OUTLINE_IT left_it = left_outlines;
290 //in/out iterator
291 C_OUTLINE_IT right_it = right_outlines;
292 C_OUTLINE_IT new_it = &new_outlines;
293 C_OUTLINE_IT blob_it; //outlines in blob
294
295 if (!right_it.empty ()) {
296 while (!right_it.empty ()) {
297 old_right = right_it.extract ();
298 right_it.forward ();
299 fixed_split_coutline(old_right,
300 chop_coord,
301 pitch_error,
302 &left_it,
303 &new_it);
304 }
305 right_it.add_list_before (&new_outlines);
306 }
307 if (blob != NULL) {
308 blob_it.set_to_list (blob->out_list ());
309 for (blob_it.mark_cycle_pt (); !blob_it.cycled_list ();
310 blob_it.forward ())
311 fixed_split_coutline (blob_it.extract (), chop_coord, pitch_error,
312 &left_it, &right_it);
313 delete blob;
314 }
315 }
316
317
318 /**********************************************************************
319 * fixed_split_outline
320 *
321 * Chop the given outline (if necessary) placing the fragments which
322 * fall either side of the chop line into the appropriate list.
323 **********************************************************************/
324
325 void fixed_split_coutline( //chop the outline
326 C_OUTLINE *srcline, //source outline
327 inT16 chop_coord, //place to chop
328 float pitch_error, //allowed deviation
329 C_OUTLINE_IT *left_it, //left half of chop
330 C_OUTLINE_IT *right_it //right half of chop
331 ) {
332 C_OUTLINE *child; //child outline
333 TBOX srcbox; //box of outline
334 C_OUTLINE_LIST left_ch; //left children
335 C_OUTLINE_LIST right_ch; //right children
336 C_OUTLINE_FRAG_LIST left_frags;//chopped fragments
337 C_OUTLINE_FRAG_LIST right_frags;;
338 C_OUTLINE_IT left_ch_it = &left_ch;
339 //for whole children
340 C_OUTLINE_IT right_ch_it = &right_ch;
341 //for holes
342 C_OUTLINE_IT child_it = srcline->child ();
343
344 srcbox = srcline->bounding_box ();
345 //left of line
346 if (srcbox.left () + srcbox.right () <= chop_coord * 2
347 //and not far over
348 && srcbox.right () < chop_coord + pitch_error)
349 //stick whole in left
350 left_it->add_after_then_move (srcline);
351 else if (srcbox.left () + srcbox.right () > chop_coord * 2
352 && srcbox.left () > chop_coord - pitch_error)
353 //stick whole in right
354 right_it->add_before_stay_put (srcline);
355 else {
356 //needs real chopping
357 if (fixed_chop_coutline (srcline, chop_coord, pitch_error,
358 &left_frags, &right_frags)) {
359 for (child_it.mark_cycle_pt (); !child_it.cycled_list ();
360 child_it.forward ()) {
361 child = child_it.extract ();
362 srcbox = child->bounding_box ();
363 if (srcbox.right () < chop_coord)
364 left_ch_it.add_after_then_move (child);
365 else if (srcbox.left () > chop_coord)
366 right_ch_it.add_after_then_move (child);
367 else {
368 if (fixed_chop_coutline (child, chop_coord, pitch_error,
369 &left_frags, &right_frags))
370 delete child;
371 else {
372 if (srcbox.left () + srcbox.right () <= chop_coord * 2)
373 left_ch_it.add_after_then_move (child);
374 else
375 right_ch_it.add_after_then_move (child);
376 }
377 }
378 }
379 close_chopped_cfragments(&left_frags, &left_ch, pitch_error, left_it);
380 close_chopped_cfragments(&right_frags, &right_ch, pitch_error, right_it);
381 ASSERT_HOST (left_ch.empty () && right_ch.empty ());
382 //no children left
383 delete srcline; //smashed up
384 }
385 else {
386 if (srcbox.left () + srcbox.right () <= chop_coord * 2)
387 //stick whole in left
388 left_it->add_after_then_move (srcline);
389 else
390 right_it->add_before_stay_put (srcline);
391 }
392 }
393 }
394
395
396 /**********************************************************************
397 * fixed_chop_coutline
398 *
399 * Chop the given coutline (if necessary) placing the fragments which
400 * fall either side of the chop line into the appropriate list.
401 * If the coutline lies too heavily to one side to chop, FALSE is returned.
402 **********************************************************************/
403
404 BOOL8 fixed_chop_coutline( //chop the outline
405 C_OUTLINE *srcline, //source outline
406 inT16 chop_coord, //place to chop
407 float pitch_error, //allowed deviation
408 C_OUTLINE_FRAG_LIST *left_frags, //left half of chop
409 C_OUTLINE_FRAG_LIST *right_frags //right half of chop
410 ) {
411 BOOL8 first_frag; //fragment
412 BOOL8 anticlock; //direction of loop
413 inT16 left_edge; //of outline
414 inT16 startindex; //in first fragment
415 inT32 length; //of outline
416 inT16 stepindex; //into outline
417 inT16 head_index; //start of fragment
418 ICOORD head_pos; //start of fragment
419 inT16 tail_index; //end of fragment
420 ICOORD tail_pos; //end of fragment
421 ICOORD pos; //current point
422 inT16 first_index = 0; //first tail
423 ICOORD first_pos; //first tail
424
425 length = srcline->pathlength ();
426 pos = srcline->start_pos ();
427 anticlock = srcline->turn_direction () > 0;
428 left_edge = pos.x ();
429 tail_index = 0;
430 tail_pos = pos;
431 for (stepindex = 0; stepindex < length; stepindex++) {
432 if (pos.x () < left_edge) {
433 left_edge = pos.x ();
434 tail_index = stepindex;
435 tail_pos = pos;
436 }
437 pos += srcline->step (stepindex);
438 }
439 if (left_edge >= chop_coord - pitch_error)
440 return FALSE; //not worth it
441
442 startindex = tail_index;
443 first_frag = TRUE;
444 head_index = tail_index;
445 head_pos = tail_pos;
446 do {
447 do {
448 tail_pos += srcline->step (tail_index);
449 tail_index++;
450 if (tail_index == length)
451 tail_index = 0;
452 }
453 while (tail_pos.x () != chop_coord && tail_index != startindex);
454 if (tail_index == startindex) {
455 if (first_frag)
456 return FALSE; //doesn't cross line
457 else
458 break;
459 }
460 //#ifdef __UNIX__
461 ASSERT_HOST (head_index != tail_index);
462 //#endif
463 if (!first_frag) {
464 save_chop_cfragment(head_index,
465 head_pos,
466 tail_index,
467 tail_pos,
468 srcline,
469 left_frags);
470 }
471 else {
472 first_index = tail_index;
473 first_pos = tail_pos;
474 first_frag = FALSE;
475 }
476 while (srcline->step (tail_index).x () == 0) {
477 tail_pos += srcline->step (tail_index);
478 tail_index++;
479 if (tail_index == length)
480 tail_index = 0;
481 }
482 head_index = tail_index;
483 head_pos = tail_pos;
484 while (srcline->step (tail_index).x () > 0) {
485 do {
486 tail_pos += srcline->step (tail_index);
487 tail_index++;
488 if (tail_index == length)
489 tail_index = 0;
490 }
491 while (tail_pos.x () != chop_coord);
492 //#ifdef __UNIX__
493 ASSERT_HOST (head_index != tail_index);
494 //#endif
495 save_chop_cfragment(head_index,
496 head_pos,
497 tail_index,
498 tail_pos,
499 srcline,
500 right_frags);
501 while (srcline->step (tail_index).x () == 0) {
502 tail_pos += srcline->step (tail_index);
503 tail_index++;
504 if (tail_index == length)
505 tail_index = 0;
506 }
507 head_index = tail_index;
508 head_pos = tail_pos;
509 }
510 }
511 while (tail_index != startindex);
512 save_chop_cfragment(head_index,
513 head_pos,
514 first_index,
515 first_pos,
516 srcline,
517 left_frags);
518 return TRUE; //did some chopping
519 }
520
521
522 /**********************************************************************
523 * next_anti_left_seg
524 *
525 * Search the outline for a suitable point at which it crosses the
526 * chop_coord from left to right.
527 **********************************************************************/
528
529 inT16 next_anti_left_seg( //chop the outline
530 C_OUTLINE *srcline, //source outline
531 inT16 tail_index, //of tailpos
532 inT16 startindex, //end of search
533 inT32 length, //of outline
534 inT16 chop_coord, //place to chop
535 float pitch_error, //allowed deviation
536 ICOORD *tail_pos //current position
537 ) {
538 BOOL8 test_valid; //test pt valid
539 inT16 chop_starty; //test chop pt
540 inT16 test_index; //possible chop pt
541 ICOORD test_pos; //possible chop pt
542 ICOORD prev_step; //in x to tail pos
543
544 test_valid = FALSE;
545 chop_starty = -MAX_INT16;
546 test_index = tail_index; //stop warnings
547 do {
548 *tail_pos += srcline->step (tail_index);
549 prev_step = srcline->step (tail_index);
550 tail_index++;
551 if (tail_index >= length)
552 tail_index = 0;
553 if (test_valid && tail_pos->x () == chop_coord && prev_step.x () < 0) {
554 if (tail_pos->y () >= chop_starty) {
555 chop_starty = -MAX_INT16;
556 test_valid = FALSE;
557 }
558 else {
559 *tail_pos = test_pos;
560 tail_index = test_index;
561 break; //must chop there
562 }
563 }
564 if (tail_pos->x () == chop_coord
565 && srcline->step (tail_index).x () > 0
566 && tail_pos->y () > chop_starty) {
567 chop_starty = tail_pos->y ();
568 test_index = tail_index;
569 test_pos = *tail_pos;
570 test_valid = TRUE;
571 }
572 else if (tail_pos->x () == chop_coord
573 && srcline->step (tail_index).y () < 0
574 && prev_step.x () > 0 && tail_pos->y () > chop_starty)
575 break; //must chop here
576 }
577 while (tail_index != startindex
578 && tail_pos->x () < chop_coord + pitch_error);
579 return tail_index;
580 }
581
582
583 /**********************************************************************
584 * next_anti_right_seg
585 *
586 * Search the outline for a suitable point at which it crosses the
587 * chop_coord from right to left.
588 **********************************************************************/
589
590 inT16 next_anti_right_seg( //chop the outline
591 C_OUTLINE *srcline, //source outline
592 inT16 tail_index, //of tailpos
593 inT16 startindex, //end of search
594 inT32 length, //of outline
595 inT16 chop_coord, //place to chop
596 float pitch_error, //allowed deviation
597 ICOORD *tail_pos //current position
598 ) {
599 BOOL8 test_valid; //test pt valid
600 inT16 chop_starty; //test chop pt
601 inT16 test_index; //possible chop pt
602 ICOORD test_pos; //possible chop pt
603 ICOORD prev_step; //in x to tail pos
604
605 test_valid = FALSE;
606 chop_starty = MAX_INT16;
607 test_index = tail_index; //stop warnings
608 do {
609 //move forward
610 *tail_pos += srcline->step (tail_index);
611 prev_step = srcline->step (tail_index);
612 tail_index++;
613 if (tail_index >= length)
614 tail_index = 0;
615 if (test_valid && tail_pos->x () == chop_coord && prev_step.x () > 0) {
616 if (tail_pos->y () <= chop_starty) {
617 chop_starty = MAX_INT16;
618 test_valid = FALSE;
619 }
620 else {
621 *tail_pos = test_pos;
622 tail_index = test_index;
623 break; //must chop there
624 }
625 }
626 if (tail_pos->x () == chop_coord
627 && srcline->step (tail_index).x () < 0
628 && tail_pos->y () < chop_starty) {
629 chop_starty = tail_pos->y ();
630 test_index = tail_index;
631 test_pos = *tail_pos;
632 test_valid = TRUE; //save possible chop pt
633 }
634 else if (tail_pos->x () == chop_coord
635 && srcline->step (tail_index).y () > 0
636 && prev_step.x () < 0 && tail_pos->y () < chop_starty)
637 break; //must chop here
638 }
639 while (tail_index != startindex
640 && tail_pos->x () > chop_coord - pitch_error);
641 return tail_index;
642 }
643
644
645 /**********************************************************************
646 * next_clock_left_seg
647 *
648 * Search the outline for a suitable point at which it crosses the
649 * chop_coord from left to right.
650 **********************************************************************/
651
652 inT16 next_clock_left_seg( //chop the outline
653 C_OUTLINE *srcline, //source outline
654 inT16 tail_index, //of tailpos
655 inT16 startindex, //end of search
656 inT32 length, //of outline
657 inT16 chop_coord, //place to chop
658 float pitch_error, //allowed deviation
659 ICOORD *tail_pos //current position
660 ) {
661 BOOL8 test_valid; //test pt valid
662 inT16 chop_starty; //test chop pt
663 inT16 test_index; //possible chop pt
664 ICOORD test_pos; //possible chop pt
665 ICOORD prev_step; //in x to tail pos
666
667 test_valid = FALSE;
668 chop_starty = MAX_INT16;
669 test_index = tail_index; //stop warnings
670 do {
671 *tail_pos += srcline->step (tail_index);
672 prev_step = srcline->step (tail_index);
673 tail_index++;
674 if (tail_index >= length)
675 tail_index = 0;
676 if (test_valid && tail_pos->x () == chop_coord && prev_step.x () < 0) {
677 if (tail_pos->y () <= chop_starty) {
678 chop_starty = MAX_INT16;
679 test_valid = FALSE;
680 }
681 else {
682 *tail_pos = test_pos;
683 tail_index = test_index;
684 break; //must chop there
685 }
686 }
687 if (tail_pos->x () == chop_coord
688 && srcline->step (tail_index).x () > 0
689 && tail_pos->y () < chop_starty) {
690 chop_starty = tail_pos->y ();
691 test_index = tail_index;
692 test_pos = *tail_pos;
693 test_valid = TRUE;
694 }
695 else if (tail_pos->x () == chop_coord
696 && srcline->step (tail_index).y () > 0
697 && prev_step.x () > 0 && tail_pos->y () < chop_starty)
698 break; //must chop here
699 }
700 while (tail_index != startindex
701 && tail_pos->x () < chop_coord + pitch_error);
702 return tail_index;
703 }
704
705
706 /**********************************************************************
707 * next_clock_right_seg
708 *
709 * Search the outline for a suitable point at which it crosses the
710 * chop_coord from right to left.
711 **********************************************************************/
712
713 inT16 next_clock_right_seg( //chop the outline
714 C_OUTLINE *srcline, //source outline
715 inT16 tail_index, //of tailpos
716 inT16 startindex, //end of search
717 inT32 length, //of outline
718 inT16 chop_coord, //place to chop
719 float pitch_error, //allowed deviation
720 ICOORD *tail_pos //current position
721 ) {
722 BOOL8 test_valid; //test pt valid
723 inT16 chop_starty; //test chop pt
724 inT16 test_index; //possible chop pt
725 ICOORD test_pos; //possible chop pt
726 ICOORD prev_step; //in x to tail pos
727
728 test_valid = FALSE;
729 chop_starty = MAX_INT16;
730 test_index = tail_index; //stop warnings
731 do {
732 //move forward
733 *tail_pos += srcline->step (tail_index);
734 prev_step = srcline->step (tail_index);
735 tail_index++;
736 if (tail_index >= length)
737 tail_index = 0;
738 if (test_valid && tail_pos->x () == chop_coord && prev_step.x () > 0) {
739 if (tail_pos->y () >= chop_starty) {
740 chop_starty = MAX_INT16;
741 test_valid = FALSE;
742 }
743 else {
744 *tail_pos = test_pos;
745 tail_index = test_index;
746 break; //must chop there
747 }
748 }
749 if (tail_pos->x () == chop_coord
750 && srcline->step (tail_index).x () < 0
751 && tail_pos->y () > chop_starty) {
752 chop_starty = tail_pos->y ();
753 test_index = tail_index;
754 test_pos = *tail_pos;
755 test_valid = TRUE; //save possible chop pt
756 }
757 else if (tail_pos->x () == chop_coord
758 && srcline->step (tail_index).y () < 0
759 && prev_step.x () < 0 && tail_pos->y () > chop_starty)
760 break; //must chop here
761 }
762 while (tail_index != startindex
763 && tail_pos->x () > chop_coord - pitch_error);
764 return tail_index;
765 }
766
767
768 /**********************************************************************
769 * save_chop_cfragment
770 *
771 * Store the given fragment in the given fragment list.
772 **********************************************************************/
773
774 void save_chop_cfragment( //chop the outline
775 inT16 head_index, //head of fragment
776 ICOORD head_pos, //head of fragment
777 inT16 tail_index, //tail of fragment
778 ICOORD tail_pos, //tail of fragment
779 C_OUTLINE *srcline, //source of edgesteps
780 C_OUTLINE_FRAG_LIST *frags //fragment list
781 ) {
782 inT16 jump; //gap across end
783 inT16 stepcount; //total steps
784 C_OUTLINE_FRAG *head; //head of fragment
785 C_OUTLINE_FRAG *tail; //tail of fragment
786 inT16 tail_y; //ycoord of tail
787
788 ASSERT_HOST (tail_pos.x () == head_pos.x ());
789 ASSERT_HOST (tail_index != head_index);
790 stepcount = tail_index - head_index;
791 if (stepcount < 0)
792 stepcount += srcline->pathlength ();
793 jump = tail_pos.y () - head_pos.y ();
794 if (jump < 0)
795 jump = -jump;
796 if (jump == stepcount)
797 return; //its a nop
798 tail_y = tail_pos.y ();
799 head = new C_OUTLINE_FRAG (head_pos, tail_pos, srcline,
800 head_index, tail_index);
801 tail = new C_OUTLINE_FRAG (head, tail_y);
802 head->other_end = tail;
803 add_frag_to_list(head, frags);
804 add_frag_to_list(tail, frags);
805 }
806
807
808 /**********************************************************************
809 * C_OUTLINE_FRAG::C_OUTLINE_FRAG
810 *
811 * Constructors for C_OUTLINE_FRAG.
812 **********************************************************************/
813
814 C_OUTLINE_FRAG::C_OUTLINE_FRAG( //record fragment
815 ICOORD start_pt, //start coord
816 ICOORD end_pt, //end coord
817 C_OUTLINE *outline, //source of steps
818 inT16 start_index,
819 inT16 end_index) {
820 start = start_pt;
821 end = end_pt;
822 ycoord = start_pt.y ();
823 stepcount = end_index - start_index;
824 if (stepcount < 0)
825 stepcount += outline->pathlength ();
826 ASSERT_HOST (stepcount > 0);
827 steps = new DIR128[stepcount];
828 if (end_index > start_index) {
829 for (int i = start_index; i < end_index; ++i)
830 steps[i - start_index] = outline->step_dir(i);
831 }
832 else {
833 int len = outline->pathlength();
834 int i = start_index;
835 for (; i < len; ++i)
836 steps[i - start_index] = outline->step_dir(i);
837 if (end_index > 0)
838 for (; i < end_index + len; ++i)
839 steps[i - start_index] = outline->step_dir(i - len);
840 }
841 other_end = NULL;
842 delete close();
843 }
844
845
846 C_OUTLINE_FRAG::C_OUTLINE_FRAG( //record fragment
847 C_OUTLINE_FRAG *head, //other end
848 inT16 tail_y) {
849 ycoord = tail_y;
850 other_end = head;
851 start = head->start;
852 end = head->end;
853 steps = NULL;
854 stepcount = 0;
855 }
856
857
858 /**********************************************************************
859 * add_frag_to_list
860 *
861 * Insert the fragment in the list at the appropriate place to keep
862 * them in ascending ycoord order.
863 **********************************************************************/
864
865 void add_frag_to_list( //ordered add
866 C_OUTLINE_FRAG *frag, //fragment to add
867 C_OUTLINE_FRAG_LIST *frags //fragment list
868 ) {
869 //output list
870 C_OUTLINE_FRAG_IT frag_it = frags;
871
872 if (!frags->empty ()) {
873 for (frag_it.mark_cycle_pt (); !frag_it.cycled_list ();
874 frag_it.forward ()) {
875 if (frag_it.data ()->ycoord > frag->ycoord
876 || (frag_it.data ()->ycoord == frag->ycoord
877 && frag->other_end->ycoord < frag->ycoord)) {
878 frag_it.add_before_then_move (frag);
879 return;
880 }
881 }
882 }
883 frag_it.add_to_end (frag);
884 }
885
886
887 /**********************************************************************
888 * close_chopped_cfragments
889 *
890 * Clear the given list of fragments joining them up into outlines.
891 * Each outline made soaks up any of the child outlines which it encloses.
892 **********************************************************************/
893
894 void close_chopped_cfragments( //chop the outline
895 C_OUTLINE_FRAG_LIST *frags, //list to clear
896 C_OUTLINE_LIST *children, //potential children
897 float pitch_error, //allowed shrinkage
898 C_OUTLINE_IT *dest_it //output list
899 ) {
900 //iterator
901 C_OUTLINE_FRAG_IT frag_it = frags;
902 C_OUTLINE_FRAG *bottom_frag; //bottom of cut
903 C_OUTLINE_FRAG *top_frag; //top of cut
904 C_OUTLINE *outline; //new outline
905 C_OUTLINE *child; //current child
906 C_OUTLINE_IT child_it = children;
907 C_OUTLINE_IT olchild_it; //children of outline
908
909 while (!frag_it.empty ()) {
910 frag_it.move_to_first ();
911 //get bottom one
912 bottom_frag = frag_it.extract ();
913 frag_it.forward ();
914 top_frag = frag_it.data (); //look at next
915 if ((bottom_frag->steps == 0 && top_frag->steps == 0)
916 || (bottom_frag->steps != 0 && top_frag->steps != 0)) {
917 if (frag_it.data_relative (1)->ycoord == top_frag->ycoord)
918 frag_it.forward ();
919 }
920 top_frag = frag_it.extract ();
921 if (top_frag->other_end != bottom_frag) {
922 outline = join_chopped_fragments (bottom_frag, top_frag);
923 ASSERT_HOST (outline == NULL);
924 }
925 else {
926 outline = join_chopped_fragments (bottom_frag, top_frag);
927 ASSERT_HOST (outline != NULL);
928 olchild_it.set_to_list (outline->child ());
929 for (child_it.mark_cycle_pt (); !child_it.cycled_list ();
930 child_it.forward ()) {
931 child = child_it.data ();
932 if (*child < *outline)
933 olchild_it.add_to_end (child_it.extract ());
934 }
935 if (outline->bounding_box ().width () > pitch_error)
936 dest_it->add_after_then_move (outline);
937 else
938 delete outline; //make it disappear
939 }
940 }
941 while (!child_it.empty ()) {
942 dest_it->add_after_then_move (child_it.extract ());
943 child_it.forward ();
944 }
945 }
946
947
948 /**********************************************************************
949 * join_chopped_fragments
950 *
951 * Join the two lists of POLYPTs such that neither OUTLINE_FRAG
952 * operand keeps responsibility for the fragment.
953 **********************************************************************/
954
955 C_OUTLINE *join_chopped_fragments( //join pieces
956 C_OUTLINE_FRAG *bottom, //bottom of cut
957 C_OUTLINE_FRAG *top //top of cut
958 ) {
959 C_OUTLINE *outline; //closed loop
960
961 if (bottom->other_end == top) {
962 if (bottom->steps == 0)
963 outline = top->close (); //turn to outline
964 else
965 outline = bottom->close ();
966 delete top;
967 delete bottom;
968 return outline;
969 }
970 if (bottom->steps == 0) {
971 ASSERT_HOST (top->steps != 0);
972 join_segments (bottom->other_end, top);
973 }
974 else {
975 ASSERT_HOST (top->steps == 0);
976 join_segments (top->other_end, bottom);
977 }
978 top->other_end->other_end = bottom->other_end;
979 bottom->other_end->other_end = top->other_end;
980 delete bottom;
981 delete top;
982 return NULL;
983 }
984
985
986 /**********************************************************************
987 * join_segments
988 *
989 * Join the two edgestep fragments such that the second comes after
990 * the first and the gap beween them is closed.
991 **********************************************************************/
992
993 void join_segments( //join pieces
994 C_OUTLINE_FRAG *bottom, //bottom of cut
995 C_OUTLINE_FRAG *top //top of cut
996 ) {
997 DIR128 *steps; //new steps
998 inT32 stepcount; //no of steps
999 inT16 fake_count; //fake steps
1000 DIR128 fake_step; //step entry
1001
1002 ASSERT_HOST (bottom->end.x () == top->start.x ());
1003 fake_count = top->start.y () - bottom->end.y ();
1004 if (fake_count < 0) {
1005 fake_count = -fake_count;
1006 fake_step = 32;
1007 }
1008 else
1009 fake_step = 96;
1010
1011 stepcount = bottom->stepcount + fake_count + top->stepcount;
1012 steps = new DIR128[stepcount];
1013 memmove (steps, bottom->steps, bottom->stepcount);
1014 memset (steps + bottom->stepcount, fake_step.get_dir(), fake_count);
1015 memmove (steps + bottom->stepcount + fake_count, top->steps,
1016 top->stepcount);
1017 delete [] bottom->steps;
1018 bottom->steps = steps;
1019 bottom->stepcount = stepcount;
1020 bottom->end = top->end;
1021 bottom->other_end->end = top->end;
1022 }
1023
1024
1025 /**********************************************************************
1026 * C_OUTLINE_FRAG::close
1027 *
1028 * Join the ends of this fragment and turn it into an outline.
1029 **********************************************************************/
1030
1031 C_OUTLINE *C_OUTLINE_FRAG::close() { //join pieces
1032 DIR128 *new_steps; //new steps
1033 inT32 new_stepcount; //no of steps
1034 inT16 fake_count; //fake steps
1035 DIR128 fake_step; //step entry
1036
1037 ASSERT_HOST (start.x () == end.x ());
1038 fake_count = start.y () - end.y ();
1039 if (fake_count < 0) {
1040 fake_count = -fake_count;
1041 fake_step = 32;
1042 }
1043 else
1044 fake_step = 96;
1045
1046 new_stepcount = stepcount + fake_count;
1047 new_steps = new DIR128[new_stepcount];
1048 memmove(new_steps, steps, stepcount);
1049 memset (new_steps + stepcount, fake_step.get_dir(), fake_count);
1050 C_OUTLINE* result = new C_OUTLINE (start, new_steps, new_stepcount);
1051 delete [] new_steps;
1052 return result;
1053 }
1054
1055
1056 /**********************************************************************
1057 * C_OUTLINE_FRAG::operator=
1058 *
1059 * Copy this fragment.
1060 **********************************************************************/
1061
1062 //join pieces
1063 C_OUTLINE_FRAG & C_OUTLINE_FRAG::operator= (
1064 const C_OUTLINE_FRAG & src //fragment to copy
1065 ) {
1066 if (steps != NULL)
1067 delete [] steps;
1068
1069 stepcount = src.stepcount;
1070 steps = new DIR128[stepcount];
1071 memmove (steps, src.steps, stepcount);
1072 start = src.start;
1073 end = src.end;
1074 ycoord = src.ycoord;
1075 return *this;
1076 }