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 "lmedsq.h"
27 #include "statistc.h"
28 #include "drawtord.h"
29 #include "tovars.h"
30 #include "topitch.h"
31 #include "fpchop.h"
32 #include "notdll.h"
33
34 #define EXTERN
35
36 EXTERN INT_VAR (textord_fp_chop_error, 2,
37 "Max allowed bending of chop cells");
38 EXTERN double_VAR (textord_fp_chop_snap, 0.5,
39 "Max distance of chop pt from vertex");
40
ELISTIZE(C_OUTLINE_FRAG)41 ELISTIZE (OUTLINE_FRAG) ELISTIZE (C_OUTLINE_FRAG)
42 //#undef ASSERT_HOST
43 //#define ASSERT_HOST(x) if (!(x)) AfxMessageBox(#x);
44 /**********************************************************************
45 * fixed_pitch_words
46 *
47 * Make a ROW from a fixed pitch TO_ROW.
48 **********************************************************************/
49 ROW *fixed_pitch_words( //find lines
50 TO_ROW *row, //row to do
51 FCOORD rotation //for drawing
52 ) {
53 BOOL8 bol; //start of line
54 uinT8 blanks; //in front of word
55 uinT8 new_blanks; //blanks in empty cell
56 inT16 chop_coord; //chop boundary
57 inT16 prev_chop_coord; //start of cell
58 inT16 rep_left; //left edge of rep word
59 ROW *real_row; //output row
60 OUTLINE_LIST left_outlines; //in current blob
61 OUTLINE_LIST right_outlines; //for next blob
62 C_OUTLINE_LIST left_coutlines;
63 C_OUTLINE_LIST right_coutlines;
64 PBLOB_LIST blobs; //blobs in word
65 C_BLOB_LIST cblobs;
66 PBLOB_IT blob_it = &blobs; //iterator
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_outlines, &left_coutlines,
126 &right_outlines, &right_coutlines);
127 box_it.forward ();
128 while (!box_it.empty ()
129 && box_it.data ()->blob () == NULL
130 && box_it.data ()->cblob () == NULL) {
131 delete box_it.extract ();
132 box_it.forward ();
133 }
134 }
135 if ((!right_outlines.empty () || !right_coutlines.empty ())
136 && left_outlines.empty () && left_coutlines.empty ())
137 split_to_blob (NULL, chop_coord,
138 textord_fp_chop_error + 0.5f,
139 &left_outlines, &left_coutlines,
140 &right_outlines, &right_coutlines);
141 if (!left_outlines.empty ())
142 blob_it.add_after_then_move (new PBLOB (&left_outlines));
143 else if (!left_coutlines.empty ())
144 cblob_it.add_after_then_move (new C_BLOB (&left_coutlines));
145 else {
146 if (rep_left < chop_coord) {
147 if (rep_left > prev_chop_coord)
148 new_blanks = (uinT8) floor ((rep_left - prev_chop_coord)
149 / row->fixed_pitch + 0.5);
150 else
151 new_blanks = 0;
152 }
153 else {
154 if (chop_coord > prev_chop_coord)
155 new_blanks = (uinT8) floor ((chop_coord - prev_chop_coord)
156 / row->fixed_pitch + 0.5);
157 else
158 new_blanks = 0;
159 }
160 if (!blob_it.empty () || !cblob_it.empty ()) {
161 if (blanks < 1 && word != NULL && !word->flag (W_REP_CHAR))
162 blanks = 1;
163 if (!blob_it.empty ()) {
164 //make real word
165 word = new WERD (&blobs, blanks, NULL);
166 blob_it.set_to_list (&blobs);
167 }
168 else {
169 word = new WERD (&cblobs, blanks, NULL);
170 cblob_it.set_to_list (&cblobs);
171 }
172 word->set_flag (W_DONT_CHOP, TRUE);
173 word_it.add_after_then_move (word);
174 if (bol) {
175 word->set_flag (W_BOL, TRUE);
176 bol = FALSE;
177 }
178 blanks = new_blanks;
179 }
180 else
181 blanks += new_blanks;
182 while (rep_left < chop_coord) {
183 word = add_repeated_word (&rep_it, rep_left, prev_chop_coord,
184 blanks, row->fixed_pitch, &word_it);
185 }
186 }
187 if (prev_chop_coord < chop_coord)
188 prev_chop_coord = chop_coord;
189 }
190 if (!blob_it.empty () || !cblob_it.empty ()) {
191 if (!blob_it.empty ())
192 //last word on line
193 word = new WERD (&blobs, blanks, NULL);
194 else
195 word = new WERD (&cblobs, blanks, NULL);
196 word->set_flag (W_DONT_CHOP, TRUE);
197 word_it.add_after_then_move (word);
198 if (bol)
199 word->set_flag (W_BOL, TRUE);
200 }
201 ASSERT_HOST (word != NULL);
202 while (!rep_it.empty ()) {
203 add_repeated_word (&rep_it, rep_left, prev_chop_coord,
204 blanks, row->fixed_pitch, &word_it);
205 }
206 //at end of line
207 word_it.data ()->set_flag (W_EOL, TRUE);
208 if (prev_chop_coord > prev_x)
209 prev_x = prev_chop_coord;
210 xstarts[1] = prev_x + 1;
211 coeffs[0] = 0;
212 coeffs[1] = row->line_m ();
213 coeffs[2] = row->line_c ();
214 real_row = new ROW (row, (inT16) row->kern_size, (inT16) row->space_size);
215 word_it.set_to_list (real_row->word_list ());
216 //put words in row
217 word_it.add_list_after (&words);
218 real_row->recalc_bounding_box ();
219 return real_row;
220 }
221
222
223 /**********************************************************************
224 * add_repeated_word
225 *
226 * Add repeated word into the row at the given point.
227 **********************************************************************/
228
add_repeated_word(WERD_IT * rep_it,inT16 & rep_left,inT16 & prev_chop_coord,uinT8 & blanks,float pitch,WERD_IT * word_it)229 WERD *add_repeated_word( //move repeated word
230 WERD_IT *rep_it, //repeated words
231 inT16 &rep_left, //left edge of word
232 inT16 &prev_chop_coord, //previous word end
233 uinT8 &blanks, //no of blanks
234 float pitch, //char cell size
235 WERD_IT *word_it //list of words
236 ) {
237 WERD *word; //word to move
238 inT16 new_blanks; //extra blanks
239
240 if (rep_left > prev_chop_coord) {
241 new_blanks = (uinT8) floor ((rep_left - prev_chop_coord) / pitch + 0.5);
242 blanks += new_blanks;
243 }
244 word = rep_it->extract ();
245 prev_chop_coord = word->bounding_box ().right ();
246 word_it->add_after_then_move (word);
247 word->set_blanks (blanks);
248 rep_it->forward ();
249 if (rep_it->empty ())
250 rep_left = MAX_INT16;
251 else
252 rep_left = rep_it->data ()->bounding_box ().left ();
253 blanks = 0;
254 return word;
255 }
256
257
258 /**********************************************************************
259 * split_to_blob
260 *
261 * Split a BLOBNBOX across a vertical chop line and put the pieces
262 * into a left outline list and a right outline list.
263 **********************************************************************/
264
split_to_blob(BLOBNBOX * blob,inT16 chop_coord,float pitch_error,OUTLINE_LIST * left_outlines,C_OUTLINE_LIST * left_coutlines,OUTLINE_LIST * right_outlines,C_OUTLINE_LIST * right_coutlines)265 void split_to_blob( //split the blob
266 BLOBNBOX *blob, //blob to split
267 inT16 chop_coord, //place to chop
268 float pitch_error, //allowed deviation
269 OUTLINE_LIST *left_outlines, //left half of chop
270 C_OUTLINE_LIST *left_coutlines, //for cblobs
271 OUTLINE_LIST *right_outlines, //right half of chop
272 C_OUTLINE_LIST *right_coutlines) {
273 PBLOB *real_blob; //blob to chop
274 C_BLOB *real_cblob; //cblob to chop
275
276 if (blob != NULL) {
277 real_blob = blob->blob ();
278 real_cblob = blob->cblob ();
279 }
280 else {
281 real_blob = NULL;
282 real_cblob = NULL;
283 }
284 if (!right_outlines->empty () || real_blob != NULL)
285 fixed_chop_blob(real_blob,
286 chop_coord,
287 pitch_error,
288 left_outlines,
289 right_outlines);
290 else if (!right_coutlines->empty () || real_cblob != NULL)
291 fixed_chop_cblob(real_cblob,
292 chop_coord,
293 pitch_error,
294 left_coutlines,
295 right_coutlines);
296 if (blob != NULL)
297 delete blob; //free it
298 }
299
300
301 /**********************************************************************
302 * fixed_chop_blob
303 *
304 * Chop the given blob (if any) and the existing right outlines to
305 * produce a list of outlines left of the chop point and more to the right.
306 **********************************************************************/
307
fixed_chop_blob(PBLOB * blob,inT16 chop_coord,float pitch_error,OUTLINE_LIST * left_outlines,OUTLINE_LIST * right_outlines)308 void fixed_chop_blob( //split the blob
309 PBLOB *blob, //blob to split
310 inT16 chop_coord, //place to chop
311 float pitch_error, //allowed deviation
312 OUTLINE_LIST *left_outlines, //left half of chop
313 OUTLINE_LIST *right_outlines //right half of chop
314 ) {
315 OUTLINE *old_right; //already there
316 OUTLINE_LIST new_outlines; //new right ones
317 //ouput iterator
318 OUTLINE_IT left_it = left_outlines;
319 //in/out iterator
320 OUTLINE_IT right_it = right_outlines;
321 OUTLINE_IT new_it = &new_outlines;
322 OUTLINE_IT blob_it; //outlines in blob
323
324 if (!right_it.empty ()) {
325 while (!right_it.empty ()) {
326 old_right = right_it.extract ();
327 right_it.forward ();
328 fixed_split_outline(old_right,
329 chop_coord,
330 pitch_error,
331 &left_it,
332 &new_it);
333 }
334 right_it.add_list_before (&new_outlines);
335 }
336 if (blob != NULL) {
337 blob_it.set_to_list (blob->out_list ());
338 for (blob_it.mark_cycle_pt (); !blob_it.cycled_list ();
339 blob_it.forward ())
340 fixed_split_outline (blob_it.extract (), chop_coord, pitch_error,
341 &left_it, &right_it);
342 delete blob;
343 }
344 }
345
346
347 /**********************************************************************
348 * fixed_split_outline
349 *
350 * Chop the given outline (if necessary) placing the fragments which
351 * fall either side of the chop line into the appropriate list.
352 **********************************************************************/
353
fixed_split_outline(OUTLINE * srcline,inT16 chop_coord,float pitch_error,OUTLINE_IT * left_it,OUTLINE_IT * right_it)354 void fixed_split_outline( //chop the outline
355 OUTLINE *srcline, //source outline
356 inT16 chop_coord, //place to chop
357 float pitch_error, //allowed deviation
358 OUTLINE_IT *left_it, //left half of chop
359 OUTLINE_IT *right_it //right half of chop
360 ) {
361 OUTLINE *child; //child outline
362 TBOX srcbox; //box of outline
363 OUTLINE_LIST left_ch; //left children
364 OUTLINE_LIST right_ch; //right children
365 OUTLINE_FRAG_LIST left_frags; //chopped fragments
366 OUTLINE_FRAG_LIST right_frags;;
367 OUTLINE_IT left_ch_it = &left_ch;
368 //for whole children
369 OUTLINE_IT right_ch_it = &right_ch;
370 //for holes
371 OUTLINE_IT child_it = srcline->child ();
372
373 srcbox = srcline->bounding_box ();
374 //left of line
375 if (srcbox.left () + srcbox.right () <= chop_coord * 2
376 //and not far over
377 && srcbox.right () < chop_coord + pitch_error)
378 //stick whole in left
379 left_it->add_after_then_move (srcline);
380 else if (srcbox.left () + srcbox.right () > chop_coord * 2
381 && srcbox.left () > chop_coord - pitch_error)
382 //stick whole in right
383 right_it->add_before_stay_put (srcline);
384 else {
385 //needs real chopping
386 if (fixed_chop_outline (srcline, chop_coord, pitch_error,
387 &left_frags, &right_frags)) {
388 for (child_it.mark_cycle_pt (); !child_it.cycled_list ();
389 child_it.forward ()) {
390 child = child_it.extract ();
391 srcbox = child->bounding_box ();
392 if (srcbox.right () < chop_coord)
393 left_ch_it.add_after_then_move (child);
394 else if (srcbox.left () > chop_coord)
395 right_ch_it.add_after_then_move (child);
396 else {
397 if (fixed_chop_outline (child, chop_coord, pitch_error,
398 &left_frags, &right_frags))
399 delete child;
400 else {
401 if (srcbox.left () + srcbox.right () <= chop_coord * 2)
402 left_ch_it.add_after_then_move (child);
403 else
404 right_ch_it.add_after_then_move (child);
405 }
406 }
407 }
408 close_chopped_fragments(&left_frags, &left_ch, left_it);
409 close_chopped_fragments(&right_frags, &right_ch, right_it);
410 ASSERT_HOST (left_ch.empty () && right_ch.empty ());
411 //no children left
412 delete srcline; //smashed up
413 }
414 else {
415 if (srcbox.left () + srcbox.right () <= chop_coord * 2)
416 //stick whole in left
417 left_it->add_after_then_move (srcline);
418 else
419 right_it->add_before_stay_put (srcline);
420 }
421 }
422 }
423
424
425 /**********************************************************************
426 * fixed_chop_outline
427 *
428 * Chop the given outline (if necessary) placing the fragments which
429 * fall either side of the chop line into the appropriate list.
430 * If the outline lies too heavily to one side to chop, FALSE is returned.
431 **********************************************************************/
432
fixed_chop_outline(OUTLINE * srcline,inT16 chop_coord,float pitch_error,OUTLINE_FRAG_LIST * left_frags,OUTLINE_FRAG_LIST * right_frags)433 BOOL8 fixed_chop_outline( //chop the outline
434 OUTLINE *srcline, //source outline
435 inT16 chop_coord, //place to chop
436 float pitch_error, //allowed deviation
437 OUTLINE_FRAG_LIST *left_frags, //left half of chop
438 OUTLINE_FRAG_LIST *right_frags //right half of chop
439 ) {
440 BOOL8 not_first; //fragment
441 BOOL8 test_valid; //test pt valid
442 float left_edge; //of outline
443 FCOORD chop_pos; //coords of chop
444 float chop_starty; //test chop pt
445 POLYPT *startpt; //in first fragment
446 //general iterator
447 POLYPT_IT poly_it = srcline->polypts ();
448 POLYPT_IT head_it; //head of fragment
449 POLYPT_IT tail_it; //tail of fragment
450 POLYPT_IT test_tail; //possible chop pt
451
452 left_edge = poly_it.data ()->pos.x ();
453 tail_it = poly_it;
454 for (poly_it.mark_cycle_pt (); !poly_it.cycled_list (); poly_it.forward ()) {
455 if (poly_it.data ()->pos.x () < left_edge) {
456 left_edge = poly_it.data ()->pos.x ();
457 tail_it = poly_it; //find leftmost pt
458 }
459 }
460 if (left_edge >= chop_coord - pitch_error)
461 return FALSE; //not worth it
462
463 startpt = tail_it.data ();
464 not_first = FALSE;
465 head_it = tail_it;
466 chop_starty = tail_it.data ()->pos.y ();
467 do {
468 test_valid = FALSE;
469 do {
470 tail_it.forward ();
471 if (test_valid
472 && tail_it.data ()->pos.x () >= chop_coord
473 && tail_it.data ()->pos.x () + tail_it.data ()->vec.x () <=
474 chop_coord) {
475 chop_pos = find_chop_coords (&tail_it, chop_coord);
476 if (chop_pos.y () >= chop_starty)
477 test_valid = FALSE;
478 else {
479 tail_it = test_tail;
480 break; //must chop there
481 }
482 }
483 if (tail_it.data ()->pos.x () <= chop_coord
484 && tail_it.data ()->pos.x () + tail_it.data ()->vec.x () >=
485 chop_coord) {
486 chop_pos = find_chop_coords (&tail_it, chop_coord);
487 chop_starty = chop_pos.y ();
488 test_tail = tail_it; //save possible chop pt
489 test_valid = TRUE;
490 if (tail_it.data ()->vec.x () == 0
491 && tail_it.data ()->vec.y () < 0)
492 break; //must chop here
493 }
494 }
495 while (tail_it.data () != startpt
496 && tail_it.data ()->pos.x () < chop_coord + pitch_error);
497 //back to start
498 if (tail_it.data () == startpt) {
499 if (not_first)
500 break;
501 else
502 return FALSE; //doesn't cross line
503 }
504 while (tail_it.data ()->pos.x () > chop_coord)
505 tail_it.backward ();
506 if (head_it.data () == tail_it.data ())
507 insert_extra_pt(&tail_it);
508 insert_chop_pt(&tail_it, chop_coord);
509 if (not_first) {
510 save_chop_fragment(&head_it, &tail_it, left_frags);
511 }
512 else {
513 tail_it.forward ();
514 head_it = tail_it;
515 }
516 test_valid = FALSE;
517 do {
518 tail_it.forward ();
519 if (test_valid
520 && tail_it.data ()->pos.x () <= chop_coord
521 && tail_it.data ()->pos.x () + tail_it.data ()->vec.x () >=
522 chop_coord) {
523 chop_pos = find_chop_coords (&tail_it, chop_coord);
524 if (chop_pos.y () <= chop_starty)
525 test_valid = FALSE;
526 else {
527 tail_it = test_tail;
528 break; //must chop there
529 }
530 }
531 if (tail_it.data ()->pos.x () >= chop_coord
532 && tail_it.data ()->pos.x () + tail_it.data ()->vec.x () <=
533 chop_coord) {
534 chop_pos = find_chop_coords (&tail_it, chop_coord);
535 chop_starty = chop_pos.y ();
536 test_tail = tail_it;
537 test_valid = TRUE; //save possible chop pt
538 if (tail_it.data ()->vec.x () == 0
539 && tail_it.data ()->vec.y () > 0)
540 break; //must chop here
541 }
542 }
543 while (tail_it.data () != startpt
544 && tail_it.data ()->pos.x () > chop_coord - pitch_error);
545 while (tail_it.data ()->pos.x () < chop_coord)
546 tail_it.backward ();
547 if (head_it.data () == tail_it.data ())
548 insert_extra_pt(&tail_it);
549 insert_chop_pt(&tail_it, chop_coord);
550 save_chop_fragment(&head_it, &tail_it, right_frags);
551 not_first = TRUE;
552 }
553 while (tail_it.data () != startpt);
554 startpt = head_it.data_relative (-1);
555 while (tail_it.data () != startpt)
556 tail_it.forward ();
557 save_chop_fragment(&head_it, &tail_it, left_frags);
558 return TRUE; //did some chopping
559 }
560
561
562 /**********************************************************************
563 * save_chop_fragment
564 *
565 * Store the given fragment in the given fragment list.
566 **********************************************************************/
567
save_chop_fragment(POLYPT_IT * head_it,POLYPT_IT * tail_it,OUTLINE_FRAG_LIST * frags)568 void save_chop_fragment( //chop the outline
569 POLYPT_IT *head_it, //head of fragment
570 POLYPT_IT *tail_it, //tail of fragment
571 OUTLINE_FRAG_LIST *frags //fragment list
572 ) {
573 OUTLINE_FRAG *head; //head of fragment
574 OUTLINE_FRAG *tail; //tail of fragment
575 float tail_y; //ycoord of tail
576
577 tail_y = tail_it->data ()->pos.y ();
578 head = new OUTLINE_FRAG (head_it, tail_it);
579 tail = new OUTLINE_FRAG (head, tail_y);
580 head->other_end = tail;
581 add_frag_to_list(head, frags);
582 add_frag_to_list(tail, frags);
583 head_it->forward ();
584 tail_it->forward ();
585 }
586
587
588 /**********************************************************************
589 * OUTLINE_FRAG::OUTLINE_FRAG
590 *
591 * Constructors for OUTLINE_FRAG.
592 **********************************************************************/
593
OUTLINE_FRAG(POLYPT_IT * head_it,POLYPT_IT * tail_it)594 OUTLINE_FRAG::OUTLINE_FRAG( //record fragment
595 POLYPT_IT *head_it, //head of fragment
596 POLYPT_IT *tail_it //tail of fragment
597 ) {
598 ycoord = head_it->data ()->pos.y ();
599 other_end = NULL;
600 polypts.assign_to_sublist (head_it, tail_it);
601 }
602
603
OUTLINE_FRAG(OUTLINE_FRAG * head,float tail_y)604 OUTLINE_FRAG::OUTLINE_FRAG( //record fragment
605 OUTLINE_FRAG *head, //other end
606 float tail_y) {
607 ycoord = tail_y;
608 other_end = head;
609 }
610
611
612 /**********************************************************************
613 * add_frag_to_list
614 *
615 * Insert the fragment in the list at the appropriate place to keep
616 * them in ascending ycoord order.
617 **********************************************************************/
618
add_frag_to_list(OUTLINE_FRAG * frag,OUTLINE_FRAG_LIST * frags)619 void add_frag_to_list( //ordered add
620 OUTLINE_FRAG *frag, //fragment to add
621 OUTLINE_FRAG_LIST *frags //fragment list
622 ) {
623 //output list
624 OUTLINE_FRAG_IT frag_it = frags;
625
626 if (!frags->empty ()) {
627 for (frag_it.mark_cycle_pt (); !frag_it.cycled_list ();
628 frag_it.forward ()) {
629 if (frag_it.data ()->ycoord >= frag->ycoord) {
630 frag_it.add_before_then_move (frag);
631 return;
632 }
633 }
634 }
635 frag_it.add_to_end (frag);
636 }
637
638
639 /**********************************************************************
640 * insert_chop_pt
641 *
642 * Decide whether or not to use the actual point as chop coord.
643 * Insert either a duplicate of the current point or 2 copies
644 * of the new chop point. Position the iterator at the first.
645 **********************************************************************/
646
insert_chop_pt(POLYPT_IT * it,inT16 chop_coord)647 void insert_chop_pt( //make chop
648 POLYPT_IT *it, //iterator
649 inT16 chop_coord //required chop pt
650 ) {
651 POLYPT *prev_pt; //point befor chop
652 POLYPT *chop_pt; //new vertex
653 FCOORD chop_pos; //coords of chop
654 FCOORD chop_vec; //vector to next
655
656 prev_pt = it->data ();
657 if (prev_pt->pos.x () + textord_fp_chop_snap >= chop_coord
658 && prev_pt->pos.x () - textord_fp_chop_snap <= chop_coord) {
659 chop_pt = new POLYPT (prev_pt->pos, prev_pt->vec);
660 }
661 else {
662 chop_pos = FCOORD (chop_coord, prev_pt->pos.y ()
663 + prev_pt->vec.y () * (chop_coord -
664 prev_pt->pos.x ()) /
665 prev_pt->vec.x ());
666 chop_vec = it->data_relative (1)->pos - chop_pos;
667 chop_pt = new POLYPT (chop_pos, chop_vec);
668 it->add_after_then_move (chop_pt);
669 chop_pt = new POLYPT (chop_pos, chop_vec);
670 }
671 it->add_after_stay_put (chop_pt);
672 }
673
674
675 /**********************************************************************
676 * find_chop_coords
677 *
678 * Decide whether or not to use the actual point as chop coord.
679 * Return the coords of the chop point.
680 **********************************************************************/
681
find_chop_coords(POLYPT_IT * it,inT16 chop_coord)682 FCOORD find_chop_coords( //make chop
683 POLYPT_IT *it, //iterator
684 inT16 chop_coord //required chop pt
685 ) {
686 POLYPT *prev_pt; //point befor chop
687 FCOORD chop_pos; //coords of chop
688
689 prev_pt = it->data ();
690 if (prev_pt->pos.x () + textord_fp_chop_snap >= chop_coord
691 && prev_pt->pos.x () - textord_fp_chop_snap <= chop_coord) {
692 chop_pos = prev_pt->pos;
693 }
694 else {
695 chop_pos = FCOORD (chop_coord, prev_pt->pos.y ()
696 + prev_pt->vec.y () * (chop_coord -
697 prev_pt->pos.x ()) /
698 prev_pt->vec.x ());
699 }
700 return chop_pos;
701 }
702
703
704 /**********************************************************************
705 * insert_extra_pt
706 *
707 * Add an extra pt to prevent single point fragments being made.
708 **********************************************************************/
709
insert_extra_pt(POLYPT_IT * it)710 void insert_extra_pt( //make extra
711 POLYPT_IT *it //iterator
712 ) {
713 POLYPT *prev_pt; //point befor chop
714 POLYPT *chop_pt; //new vertex
715 FCOORD chop_pos; //coords of chop
716 FCOORD chop_vec; //vector to next
717
718 prev_pt = it->data ();
719 if (it->data_relative (1)->pos.y () > it->data_relative (-1)->pos.y ()) {
720 chop_pos = prev_pt->pos + FCOORD (0.0f,
721 static_cast<float>(textord_fp_chop_snap));
722 }
723 else {
724 chop_pos = prev_pt->pos - FCOORD (0.0f,
725 static_cast<float>(textord_fp_chop_snap));
726 }
727 chop_vec = it->data_relative (1)->pos - chop_pos;
728 prev_pt->vec = chop_pos - prev_pt->pos;
729 chop_pt = new POLYPT (chop_pos, chop_vec);
730 it->add_after_then_move (chop_pt);
731 }
732
733
734 /**********************************************************************
735 * close_chopped_fragments
736 *
737 * Clear the given list of fragments joining them up into outlines.
738 * Each outline made soaks up any of the child outlines which it encloses.
739 **********************************************************************/
740
close_chopped_fragments(OUTLINE_FRAG_LIST * frags,OUTLINE_LIST * children,OUTLINE_IT * dest_it)741 void close_chopped_fragments( //chop the outline
742 OUTLINE_FRAG_LIST *frags, //list to clear
743 OUTLINE_LIST *children, //potential children
744 OUTLINE_IT *dest_it //output list
745 ) {
746 //iterator
747 OUTLINE_FRAG_IT frag_it = frags;
748 OUTLINE_FRAG *bottom_frag; //bottom of cut
749 OUTLINE_FRAG *top_frag; //top of cut
750 OUTLINE *outline; //new outline
751 OUTLINE *child; //current child
752 OUTLINE_IT child_it = children;
753 OUTLINE_IT olchild_it; //children of outline
754 POLYPT_IT poly_it; //iterator for constr
755
756 while (!frag_it.empty ()) {
757 frag_it.move_to_first ();
758 //get bottom one
759 bottom_frag = frag_it.extract ();
760 frag_it.forward ();
761 //and one above it
762 top_frag = frag_it.extract ();
763 while (top_frag->other_end != bottom_frag) {
764 do {
765 frag_it.forward ();
766 }
767 //find other end
768 while (frag_it.data () != top_frag->other_end);
769 join_chopped_fragments(bottom_frag, top_frag);
770 delete top_frag;
771 delete frag_it.extract (); //remove middle section
772 frag_it.forward ();
773 top_frag = frag_it.extract ();
774 }
775 join_chopped_fragments(bottom_frag, top_frag);
776 if (bottom_frag->polypts.empty ())
777 poly_it.set_to_list (&top_frag->polypts);
778 else
779 poly_it.set_to_list (&bottom_frag->polypts);
780 outline = new OUTLINE (&poly_it);
781 olchild_it.set_to_list (outline->child ());
782 for (child_it.mark_cycle_pt (); !child_it.cycled_list ();
783 child_it.forward ()) {
784 child = child_it.data ();
785 if (*child < *outline)
786 olchild_it.add_to_end (child_it.extract ());
787 }
788 dest_it->add_after_then_move (outline);
789 }
790 while (!child_it.empty ()) {
791 dest_it->add_after_then_move (child_it.extract ());
792 child_it.forward ();
793 }
794 }
795
796
797 /**********************************************************************
798 * join_chopped_fragments
799 *
800 * Join the two lists of POLYPTs such that the first OUTLINE_FRAG
801 * operand keeps responsibility for the fragment.
802 **********************************************************************/
803
join_chopped_fragments(OUTLINE_FRAG * bottom,OUTLINE_FRAG * top)804 void join_chopped_fragments( //join pieces
805 OUTLINE_FRAG *bottom, //bottom of cut
806 OUTLINE_FRAG *top //top of cut
807 ) {
808 POLYPT_IT master_it; //dest list
809 POLYPT_IT slave_it; //src list
810 POLYPT *cutpt; //vectors to change
811 POLYPT *nextpt; //other end of cut
812
813 if (bottom->polypts.empty ()) {
814 master_it.set_to_list (&bottom->other_end->polypts);
815 cutpt = master_it.data_relative (-1);
816 ASSERT_HOST (!top->polypts.empty ());
817 slave_it.set_to_list (&top->polypts);
818 nextpt = slave_it.data ();
819 if (bottom->other_end != top) {
820 master_it.move_to_last ();
821 master_it.add_list_after (&top->polypts);
822 }
823 }
824 else {
825 master_it.set_to_list (&bottom->polypts);
826 ASSERT_HOST (top->polypts.empty ());
827 slave_it.set_to_list (&top->other_end->polypts);
828 cutpt = slave_it.data_relative (-1);
829 nextpt = master_it.data ();
830 if (bottom->other_end != top)
831 master_it.add_list_before (&top->other_end->polypts);
832 }
833 cutpt->vec = nextpt->pos - cutpt->pos;
834 }
835
836
837 /**********************************************************************
838 * fixed_chop_cblob
839 *
840 * Chop the given cblob (if any) and the existing right outlines to
841 * produce a list of outlines left of the chop point and more to the right.
842 **********************************************************************/
843
fixed_chop_cblob(C_BLOB * blob,inT16 chop_coord,float pitch_error,C_OUTLINE_LIST * left_outlines,C_OUTLINE_LIST * right_outlines)844 void fixed_chop_cblob( //split the blob
845 C_BLOB *blob, //blob to split
846 inT16 chop_coord, //place to chop
847 float pitch_error, //allowed deviation
848 C_OUTLINE_LIST *left_outlines, //left half of chop
849 C_OUTLINE_LIST *right_outlines //right half of chop
850 ) {
851 C_OUTLINE *old_right; //already there
852 C_OUTLINE_LIST new_outlines; //new right ones
853 //ouput iterator
854 C_OUTLINE_IT left_it = left_outlines;
855 //in/out iterator
856 C_OUTLINE_IT right_it = right_outlines;
857 C_OUTLINE_IT new_it = &new_outlines;
858 C_OUTLINE_IT blob_it; //outlines in blob
859
860 if (!right_it.empty ()) {
861 while (!right_it.empty ()) {
862 old_right = right_it.extract ();
863 right_it.forward ();
864 fixed_split_coutline(old_right,
865 chop_coord,
866 pitch_error,
867 &left_it,
868 &new_it);
869 }
870 right_it.add_list_before (&new_outlines);
871 }
872 if (blob != NULL) {
873 blob_it.set_to_list (blob->out_list ());
874 for (blob_it.mark_cycle_pt (); !blob_it.cycled_list ();
875 blob_it.forward ())
876 fixed_split_coutline (blob_it.extract (), chop_coord, pitch_error,
877 &left_it, &right_it);
878 delete blob;
879 }
880 }
881
882
883 /**********************************************************************
884 * fixed_split_outline
885 *
886 * Chop the given outline (if necessary) placing the fragments which
887 * fall either side of the chop line into the appropriate list.
888 **********************************************************************/
889
fixed_split_coutline(C_OUTLINE * srcline,inT16 chop_coord,float pitch_error,C_OUTLINE_IT * left_it,C_OUTLINE_IT * right_it)890 void fixed_split_coutline( //chop the outline
891 C_OUTLINE *srcline, //source outline
892 inT16 chop_coord, //place to chop
893 float pitch_error, //allowed deviation
894 C_OUTLINE_IT *left_it, //left half of chop
895 C_OUTLINE_IT *right_it //right half of chop
896 ) {
897 C_OUTLINE *child; //child outline
898 TBOX srcbox; //box of outline
899 C_OUTLINE_LIST left_ch; //left children
900 C_OUTLINE_LIST right_ch; //right children
901 C_OUTLINE_FRAG_LIST left_frags;//chopped fragments
902 C_OUTLINE_FRAG_LIST right_frags;;
903 C_OUTLINE_IT left_ch_it = &left_ch;
904 //for whole children
905 C_OUTLINE_IT right_ch_it = &right_ch;
906 //for holes
907 C_OUTLINE_IT child_it = srcline->child ();
908
909 srcbox = srcline->bounding_box ();
910 //left of line
911 if (srcbox.left () + srcbox.right () <= chop_coord * 2
912 //and not far over
913 && srcbox.right () < chop_coord + pitch_error)
914 //stick whole in left
915 left_it->add_after_then_move (srcline);
916 else if (srcbox.left () + srcbox.right () > chop_coord * 2
917 && srcbox.left () > chop_coord - pitch_error)
918 //stick whole in right
919 right_it->add_before_stay_put (srcline);
920 else {
921 //needs real chopping
922 if (fixed_chop_coutline (srcline, chop_coord, pitch_error,
923 &left_frags, &right_frags)) {
924 for (child_it.mark_cycle_pt (); !child_it.cycled_list ();
925 child_it.forward ()) {
926 child = child_it.extract ();
927 srcbox = child->bounding_box ();
928 if (srcbox.right () < chop_coord)
929 left_ch_it.add_after_then_move (child);
930 else if (srcbox.left () > chop_coord)
931 right_ch_it.add_after_then_move (child);
932 else {
933 if (fixed_chop_coutline (child, chop_coord, pitch_error,
934 &left_frags, &right_frags))
935 delete child;
936 else {
937 if (srcbox.left () + srcbox.right () <= chop_coord * 2)
938 left_ch_it.add_after_then_move (child);
939 else
940 right_ch_it.add_after_then_move (child);
941 }
942 }
943 }
944 close_chopped_cfragments(&left_frags, &left_ch, pitch_error, left_it);
945 close_chopped_cfragments(&right_frags, &right_ch, pitch_error, right_it);
946 ASSERT_HOST (left_ch.empty () && right_ch.empty ());
947 //no children left
948 delete srcline; //smashed up
949 }
950 else {
951 if (srcbox.left () + srcbox.right () <= chop_coord * 2)
952 //stick whole in left
953 left_it->add_after_then_move (srcline);
954 else
955 right_it->add_before_stay_put (srcline);
956 }
957 }
958 }
959
960
961 /**********************************************************************
962 * fixed_chop_coutline
963 *
964 * Chop the given coutline (if necessary) placing the fragments which
965 * fall either side of the chop line into the appropriate list.
966 * If the coutline lies too heavily to one side to chop, FALSE is returned.
967 **********************************************************************/
968
fixed_chop_coutline(C_OUTLINE * srcline,inT16 chop_coord,float pitch_error,C_OUTLINE_FRAG_LIST * left_frags,C_OUTLINE_FRAG_LIST * right_frags)969 BOOL8 fixed_chop_coutline( //chop the outline
970 C_OUTLINE *srcline, //source outline
971 inT16 chop_coord, //place to chop
972 float pitch_error, //allowed deviation
973 C_OUTLINE_FRAG_LIST *left_frags, //left half of chop
974 C_OUTLINE_FRAG_LIST *right_frags //right half of chop
975 ) {
976 BOOL8 first_frag; //fragment
977 BOOL8 anticlock; //direction of loop
978 inT16 left_edge; //of outline
979 inT16 startindex; //in first fragment
980 inT32 length; //of outline
981 inT16 stepindex; //into outline
982 inT16 head_index; //start of fragment
983 ICOORD head_pos; //start of fragment
984 inT16 tail_index; //end of fragment
985 ICOORD tail_pos; //end of fragment
986 ICOORD pos; //current point
987 inT16 first_index = 0; //first tail
988 ICOORD first_pos; //first tail
989
990 length = srcline->pathlength ();
991 pos = srcline->start_pos ();
992 anticlock = srcline->turn_direction () > 0;
993 left_edge = pos.x ();
994 tail_index = 0;
995 tail_pos = pos;
996 for (stepindex = 0; stepindex < length; stepindex++) {
997 if (pos.x () < left_edge) {
998 left_edge = pos.x ();
999 tail_index = stepindex;
1000 tail_pos = pos;
1001 }
1002 pos += srcline->step (stepindex);
1003 }
1004 if (left_edge >= chop_coord - pitch_error)
1005 return FALSE; //not worth it
1006
1007 startindex = tail_index;
1008 first_frag = TRUE;
1009 head_index = tail_index;
1010 head_pos = tail_pos;
1011 do {
1012 do {
1013 tail_pos += srcline->step (tail_index);
1014 tail_index++;
1015 if (tail_index == length)
1016 tail_index = 0;
1017 }
1018 while (tail_pos.x () != chop_coord && tail_index != startindex);
1019 if (tail_index == startindex) {
1020 if (first_frag)
1021 return FALSE; //doesn't cross line
1022 else
1023 break;
1024 }
1025 //#ifdef __UNIX__
1026 ASSERT_HOST (head_index != tail_index);
1027 //#endif
1028 if (!first_frag) {
1029 save_chop_cfragment(head_index,
1030 head_pos,
1031 tail_index,
1032 tail_pos,
1033 srcline,
1034 left_frags);
1035 }
1036 else {
1037 first_index = tail_index;
1038 first_pos = tail_pos;
1039 first_frag = FALSE;
1040 }
1041 while (srcline->step (tail_index).x () == 0) {
1042 tail_pos += srcline->step (tail_index);
1043 tail_index++;
1044 if (tail_index == length)
1045 tail_index = 0;
1046 }
1047 head_index = tail_index;
1048 head_pos = tail_pos;
1049 while (srcline->step (tail_index).x () > 0) {
1050 do {
1051 tail_pos += srcline->step (tail_index);
1052 tail_index++;
1053 if (tail_index == length)
1054 tail_index = 0;
1055 }
1056 while (tail_pos.x () != chop_coord);
1057 //#ifdef __UNIX__
1058 ASSERT_HOST (head_index != tail_index);
1059 //#endif
1060 save_chop_cfragment(head_index,
1061 head_pos,
1062 tail_index,
1063 tail_pos,
1064 srcline,
1065 right_frags);
1066 while (srcline->step (tail_index).x () == 0) {
1067 tail_pos += srcline->step (tail_index);
1068 tail_index++;
1069 if (tail_index == length)
1070 tail_index = 0;
1071 }
1072 head_index = tail_index;
1073 head_pos = tail_pos;
1074 }
1075 }
1076 while (tail_index != startindex);
1077 save_chop_cfragment(head_index,
1078 head_pos,
1079 first_index,
1080 first_pos,
1081 srcline,
1082 left_frags);
1083 return TRUE; //did some chopping
1084 }
1085
1086
1087 /**********************************************************************
1088 * next_anti_left_seg
1089 *
1090 * Search the outline for a suitable point at which it crosses the
1091 * chop_coord from left to right.
1092 **********************************************************************/
1093
next_anti_left_seg(C_OUTLINE * srcline,inT16 tail_index,inT16 startindex,inT32 length,inT16 chop_coord,float pitch_error,ICOORD * tail_pos)1094 inT16 next_anti_left_seg( //chop the outline
1095 C_OUTLINE *srcline, //source outline
1096 inT16 tail_index, //of tailpos
1097 inT16 startindex, //end of search
1098 inT32 length, //of outline
1099 inT16 chop_coord, //place to chop
1100 float pitch_error, //allowed deviation
1101 ICOORD *tail_pos //current position
1102 ) {
1103 BOOL8 test_valid; //test pt valid
1104 inT16 chop_starty; //test chop pt
1105 inT16 test_index; //possible chop pt
1106 ICOORD test_pos; //possible chop pt
1107 ICOORD prev_step; //in x to tail pos
1108
1109 test_valid = FALSE;
1110 chop_starty = -MAX_INT16;
1111 test_index = tail_index; //stop warnings
1112 do {
1113 *tail_pos += srcline->step (tail_index);
1114 prev_step = srcline->step (tail_index);
1115 tail_index++;
1116 if (tail_index >= length)
1117 tail_index = 0;
1118 if (test_valid && tail_pos->x () == chop_coord && prev_step.x () < 0) {
1119 if (tail_pos->y () >= chop_starty) {
1120 chop_starty = -MAX_INT16;
1121 test_valid = FALSE;
1122 }
1123 else {
1124 *tail_pos = test_pos;
1125 tail_index = test_index;
1126 break; //must chop there
1127 }
1128 }
1129 if (tail_pos->x () == chop_coord
1130 && srcline->step (tail_index).x () > 0
1131 && tail_pos->y () > chop_starty) {
1132 chop_starty = tail_pos->y ();
1133 test_index = tail_index;
1134 test_pos = *tail_pos;
1135 test_valid = TRUE;
1136 }
1137 else if (tail_pos->x () == chop_coord
1138 && srcline->step (tail_index).y () < 0
1139 && prev_step.x () > 0 && tail_pos->y () > chop_starty)
1140 break; //must chop here
1141 }
1142 while (tail_index != startindex
1143 && tail_pos->x () < chop_coord + pitch_error);
1144 return tail_index;
1145 }
1146
1147
1148 /**********************************************************************
1149 * next_anti_right_seg
1150 *
1151 * Search the outline for a suitable point at which it crosses the
1152 * chop_coord from right to left.
1153 **********************************************************************/
1154
next_anti_right_seg(C_OUTLINE * srcline,inT16 tail_index,inT16 startindex,inT32 length,inT16 chop_coord,float pitch_error,ICOORD * tail_pos)1155 inT16 next_anti_right_seg( //chop the outline
1156 C_OUTLINE *srcline, //source outline
1157 inT16 tail_index, //of tailpos
1158 inT16 startindex, //end of search
1159 inT32 length, //of outline
1160 inT16 chop_coord, //place to chop
1161 float pitch_error, //allowed deviation
1162 ICOORD *tail_pos //current position
1163 ) {
1164 BOOL8 test_valid; //test pt valid
1165 inT16 chop_starty; //test chop pt
1166 inT16 test_index; //possible chop pt
1167 ICOORD test_pos; //possible chop pt
1168 ICOORD prev_step; //in x to tail pos
1169
1170 test_valid = FALSE;
1171 chop_starty = MAX_INT16;
1172 test_index = tail_index; //stop warnings
1173 do {
1174 //move forward
1175 *tail_pos += srcline->step (tail_index);
1176 prev_step = srcline->step (tail_index);
1177 tail_index++;
1178 if (tail_index >= length)
1179 tail_index = 0;
1180 if (test_valid && tail_pos->x () == chop_coord && prev_step.x () > 0) {
1181 if (tail_pos->y () <= chop_starty) {
1182 chop_starty = MAX_INT16;
1183 test_valid = FALSE;
1184 }
1185 else {
1186 *tail_pos = test_pos;
1187 tail_index = test_index;
1188 break; //must chop there
1189 }
1190 }
1191 if (tail_pos->x () == chop_coord
1192 && srcline->step (tail_index).x () < 0
1193 && tail_pos->y () < chop_starty) {
1194 chop_starty = tail_pos->y ();
1195 test_index = tail_index;
1196 test_pos = *tail_pos;
1197 test_valid = TRUE; //save possible chop pt
1198 }
1199 else if (tail_pos->x () == chop_coord
1200 && srcline->step (tail_index).y () > 0
1201 && prev_step.x () < 0 && tail_pos->y () < chop_starty)
1202 break; //must chop here
1203 }
1204 while (tail_index != startindex
1205 && tail_pos->x () > chop_coord - pitch_error);
1206 return tail_index;
1207 }
1208
1209
1210 /**********************************************************************
1211 * next_clock_left_seg
1212 *
1213 * Search the outline for a suitable point at which it crosses the
1214 * chop_coord from left to right.
1215 **********************************************************************/
1216
next_clock_left_seg(C_OUTLINE * srcline,inT16 tail_index,inT16 startindex,inT32 length,inT16 chop_coord,float pitch_error,ICOORD * tail_pos)1217 inT16 next_clock_left_seg( //chop the outline
1218 C_OUTLINE *srcline, //source outline
1219 inT16 tail_index, //of tailpos
1220 inT16 startindex, //end of search
1221 inT32 length, //of outline
1222 inT16 chop_coord, //place to chop
1223 float pitch_error, //allowed deviation
1224 ICOORD *tail_pos //current position
1225 ) {
1226 BOOL8 test_valid; //test pt valid
1227 inT16 chop_starty; //test chop pt
1228 inT16 test_index; //possible chop pt
1229 ICOORD test_pos; //possible chop pt
1230 ICOORD prev_step; //in x to tail pos
1231
1232 test_valid = FALSE;
1233 chop_starty = MAX_INT16;
1234 test_index = tail_index; //stop warnings
1235 do {
1236 *tail_pos += srcline->step (tail_index);
1237 prev_step = srcline->step (tail_index);
1238 tail_index++;
1239 if (tail_index >= length)
1240 tail_index = 0;
1241 if (test_valid && tail_pos->x () == chop_coord && prev_step.x () < 0) {
1242 if (tail_pos->y () <= chop_starty) {
1243 chop_starty = MAX_INT16;
1244 test_valid = FALSE;
1245 }
1246 else {
1247 *tail_pos = test_pos;
1248 tail_index = test_index;
1249 break; //must chop there
1250 }
1251 }
1252 if (tail_pos->x () == chop_coord
1253 && srcline->step (tail_index).x () > 0
1254 && tail_pos->y () < chop_starty) {
1255 chop_starty = tail_pos->y ();
1256 test_index = tail_index;
1257 test_pos = *tail_pos;
1258 test_valid = TRUE;
1259 }
1260 else if (tail_pos->x () == chop_coord
1261 && srcline->step (tail_index).y () > 0
1262 && prev_step.x () > 0 && tail_pos->y () < chop_starty)
1263 break; //must chop here
1264 }
1265 while (tail_index != startindex
1266 && tail_pos->x () < chop_coord + pitch_error);
1267 return tail_index;
1268 }
1269
1270
1271 /**********************************************************************
1272 * next_clock_right_seg
1273 *
1274 * Search the outline for a suitable point at which it crosses the
1275 * chop_coord from right to left.
1276 **********************************************************************/
1277
next_clock_right_seg(C_OUTLINE * srcline,inT16 tail_index,inT16 startindex,inT32 length,inT16 chop_coord,float pitch_error,ICOORD * tail_pos)1278 inT16 next_clock_right_seg( //chop the outline
1279 C_OUTLINE *srcline, //source outline
1280 inT16 tail_index, //of tailpos
1281 inT16 startindex, //end of search
1282 inT32 length, //of outline
1283 inT16 chop_coord, //place to chop
1284 float pitch_error, //allowed deviation
1285 ICOORD *tail_pos //current position
1286 ) {
1287 BOOL8 test_valid; //test pt valid
1288 inT16 chop_starty; //test chop pt
1289 inT16 test_index; //possible chop pt
1290 ICOORD test_pos; //possible chop pt
1291 ICOORD prev_step; //in x to tail pos
1292
1293 test_valid = FALSE;
1294 chop_starty = MAX_INT16;
1295 test_index = tail_index; //stop warnings
1296 do {
1297 //move forward
1298 *tail_pos += srcline->step (tail_index);
1299 prev_step = srcline->step (tail_index);
1300 tail_index++;
1301 if (tail_index >= length)
1302 tail_index = 0;
1303 if (test_valid && tail_pos->x () == chop_coord && prev_step.x () > 0) {
1304 if (tail_pos->y () >= chop_starty) {
1305 chop_starty = MAX_INT16;
1306 test_valid = FALSE;
1307 }
1308 else {
1309 *tail_pos = test_pos;
1310 tail_index = test_index;
1311 break; //must chop there
1312 }
1313 }
1314 if (tail_pos->x () == chop_coord
1315 && srcline->step (tail_index).x () < 0
1316 && tail_pos->y () > chop_starty) {
1317 chop_starty = tail_pos->y ();
1318 test_index = tail_index;
1319 test_pos = *tail_pos;
1320 test_valid = TRUE; //save possible chop pt
1321 }
1322 else if (tail_pos->x () == chop_coord
1323 && srcline->step (tail_index).y () < 0
1324 && prev_step.x () < 0 && tail_pos->y () > chop_starty)
1325 break; //must chop here
1326 }
1327 while (tail_index != startindex
1328 && tail_pos->x () > chop_coord - pitch_error);
1329 return tail_index;
1330 }
1331
1332
1333 /**********************************************************************
1334 * save_chop_cfragment
1335 *
1336 * Store the given fragment in the given fragment list.
1337 **********************************************************************/
1338
save_chop_cfragment(inT16 head_index,ICOORD head_pos,inT16 tail_index,ICOORD tail_pos,C_OUTLINE * srcline,C_OUTLINE_FRAG_LIST * frags)1339 void save_chop_cfragment( //chop the outline
1340 inT16 head_index, //head of fragment
1341 ICOORD head_pos, //head of fragment
1342 inT16 tail_index, //tail of fragment
1343 ICOORD tail_pos, //tail of fragment
1344 C_OUTLINE *srcline, //source of edgesteps
1345 C_OUTLINE_FRAG_LIST *frags //fragment list
1346 ) {
1347 inT16 jump; //gap across end
1348 inT16 stepcount; //total steps
1349 C_OUTLINE_FRAG *head; //head of fragment
1350 C_OUTLINE_FRAG *tail; //tail of fragment
1351 inT16 tail_y; //ycoord of tail
1352
1353 ASSERT_HOST (tail_pos.x () == head_pos.x ());
1354 ASSERT_HOST (tail_index != head_index);
1355 stepcount = tail_index - head_index;
1356 if (stepcount < 0)
1357 stepcount += srcline->pathlength ();
1358 jump = tail_pos.y () - head_pos.y ();
1359 if (jump < 0)
1360 jump = -jump;
1361 if (jump == stepcount)
1362 return; //its a nop
1363 tail_y = tail_pos.y ();
1364 head = new C_OUTLINE_FRAG (head_pos, tail_pos, srcline,
1365 head_index, tail_index);
1366 tail = new C_OUTLINE_FRAG (head, tail_y);
1367 head->other_end = tail;
1368 add_frag_to_list(head, frags);
1369 add_frag_to_list(tail, frags);
1370 }
1371
1372
1373 /**********************************************************************
1374 * C_OUTLINE_FRAG::C_OUTLINE_FRAG
1375 *
1376 * Constructors for C_OUTLINE_FRAG.
1377 **********************************************************************/
1378
C_OUTLINE_FRAG(ICOORD start_pt,ICOORD end_pt,C_OUTLINE * outline,inT16 start_index,inT16 end_index)1379 C_OUTLINE_FRAG::C_OUTLINE_FRAG( //record fragment
1380 ICOORD start_pt, //start coord
1381 ICOORD end_pt, //end coord
1382 C_OUTLINE *outline, //source of steps
1383 inT16 start_index,
1384 inT16 end_index) {
1385 start = start_pt;
1386 end = end_pt;
1387 ycoord = start_pt.y ();
1388 stepcount = end_index - start_index;
1389 if (stepcount < 0)
1390 stepcount += outline->pathlength ();
1391 ASSERT_HOST (stepcount > 0);
1392 steps = new DIR128[stepcount];
1393 if (end_index > start_index) {
1394 for (int i = start_index; i < end_index; ++i)
1395 steps[i - start_index] = outline->step_dir(i);
1396 }
1397 else {
1398 int len = outline->pathlength();
1399 int i = start_index;
1400 for (; i < len; ++i)
1401 steps[i - start_index] = outline->step_dir(i);
1402 if (end_index > 0)
1403 for (; i < end_index + len; ++i)
1404 steps[i - start_index] = outline->step_dir(i - len);
1405 }
1406 other_end = NULL;
1407 delete close();
1408 }
1409
1410
C_OUTLINE_FRAG(C_OUTLINE_FRAG * head,inT16 tail_y)1411 C_OUTLINE_FRAG::C_OUTLINE_FRAG( //record fragment
1412 C_OUTLINE_FRAG *head, //other end
1413 inT16 tail_y) {
1414 ycoord = tail_y;
1415 other_end = head;
1416 start = head->start;
1417 end = head->end;
1418 steps = NULL;
1419 stepcount = 0;
1420 }
1421
1422
1423 /**********************************************************************
1424 * add_frag_to_list
1425 *
1426 * Insert the fragment in the list at the appropriate place to keep
1427 * them in ascending ycoord order.
1428 **********************************************************************/
1429
add_frag_to_list(C_OUTLINE_FRAG * frag,C_OUTLINE_FRAG_LIST * frags)1430 void add_frag_to_list( //ordered add
1431 C_OUTLINE_FRAG *frag, //fragment to add
1432 C_OUTLINE_FRAG_LIST *frags //fragment list
1433 ) {
1434 //output list
1435 C_OUTLINE_FRAG_IT frag_it = frags;
1436
1437 if (!frags->empty ()) {
1438 for (frag_it.mark_cycle_pt (); !frag_it.cycled_list ();
1439 frag_it.forward ()) {
1440 if (frag_it.data ()->ycoord > frag->ycoord
1441 || (frag_it.data ()->ycoord == frag->ycoord
1442 && frag->other_end->ycoord < frag->ycoord)) {
1443 frag_it.add_before_then_move (frag);
1444 return;
1445 }
1446 }
1447 }
1448 frag_it.add_to_end (frag);
1449 }
1450
1451
1452 /**********************************************************************
1453 * close_chopped_cfragments
1454 *
1455 * Clear the given list of fragments joining them up into outlines.
1456 * Each outline made soaks up any of the child outlines which it encloses.
1457 **********************************************************************/
1458
close_chopped_cfragments(C_OUTLINE_FRAG_LIST * frags,C_OUTLINE_LIST * children,float pitch_error,C_OUTLINE_IT * dest_it)1459 void close_chopped_cfragments( //chop the outline
1460 C_OUTLINE_FRAG_LIST *frags, //list to clear
1461 C_OUTLINE_LIST *children, //potential children
1462 float pitch_error, //allowed shrinkage
1463 C_OUTLINE_IT *dest_it //output list
1464 ) {
1465 //iterator
1466 C_OUTLINE_FRAG_IT frag_it = frags;
1467 C_OUTLINE_FRAG *bottom_frag; //bottom of cut
1468 C_OUTLINE_FRAG *top_frag; //top of cut
1469 C_OUTLINE *outline; //new outline
1470 C_OUTLINE *child; //current child
1471 C_OUTLINE_IT child_it = children;
1472 C_OUTLINE_IT olchild_it; //children of outline
1473
1474 while (!frag_it.empty ()) {
1475 frag_it.move_to_first ();
1476 //get bottom one
1477 bottom_frag = frag_it.extract ();
1478 frag_it.forward ();
1479 top_frag = frag_it.data (); //look at next
1480 if ((bottom_frag->steps == 0 && top_frag->steps == 0)
1481 || (bottom_frag->steps != 0 && top_frag->steps != 0)) {
1482 if (frag_it.data_relative (1)->ycoord == top_frag->ycoord)
1483 frag_it.forward ();
1484 }
1485 top_frag = frag_it.extract ();
1486 if (top_frag->other_end != bottom_frag) {
1487 outline = join_chopped_fragments (bottom_frag, top_frag);
1488 ASSERT_HOST (outline == NULL);
1489 }
1490 else {
1491 outline = join_chopped_fragments (bottom_frag, top_frag);
1492 ASSERT_HOST (outline != NULL);
1493 olchild_it.set_to_list (outline->child ());
1494 for (child_it.mark_cycle_pt (); !child_it.cycled_list ();
1495 child_it.forward ()) {
1496 child = child_it.data ();
1497 if (*child < *outline)
1498 olchild_it.add_to_end (child_it.extract ());
1499 }
1500 if (outline->bounding_box ().width () > pitch_error)
1501 dest_it->add_after_then_move (outline);
1502 else
1503 delete outline; //make it disappear
1504 }
1505 }
1506 while (!child_it.empty ()) {
1507 dest_it->add_after_then_move (child_it.extract ());
1508 child_it.forward ();
1509 }
1510 }
1511
1512
1513 /**********************************************************************
1514 * join_chopped_fragments
1515 *
1516 * Join the two lists of POLYPTs such that neither OUTLINE_FRAG
1517 * operand keeps responsibility for the fragment.
1518 **********************************************************************/
1519
join_chopped_fragments(C_OUTLINE_FRAG * bottom,C_OUTLINE_FRAG * top)1520 C_OUTLINE *join_chopped_fragments( //join pieces
1521 C_OUTLINE_FRAG *bottom, //bottom of cut
1522 C_OUTLINE_FRAG *top //top of cut
1523 ) {
1524 C_OUTLINE *outline; //closed loop
1525
1526 if (bottom->other_end == top) {
1527 if (bottom->steps == 0)
1528 outline = top->close (); //turn to outline
1529 else
1530 outline = bottom->close ();
1531 delete top;
1532 delete bottom;
1533 return outline;
1534 }
1535 if (bottom->steps == 0) {
1536 ASSERT_HOST (top->steps != 0);
1537 join_segments (bottom->other_end, top);
1538 }
1539 else {
1540 ASSERT_HOST (top->steps == 0);
1541 join_segments (top->other_end, bottom);
1542 }
1543 top->other_end->other_end = bottom->other_end;
1544 bottom->other_end->other_end = top->other_end;
1545 delete bottom;
1546 delete top;
1547 return NULL;
1548 }
1549
1550
1551 /**********************************************************************
1552 * join_segments
1553 *
1554 * Join the two edgestep fragments such that the second comes after
1555 * the first and the gap beween them is closed.
1556 **********************************************************************/
1557
join_segments(C_OUTLINE_FRAG * bottom,C_OUTLINE_FRAG * top)1558 void join_segments( //join pieces
1559 C_OUTLINE_FRAG *bottom, //bottom of cut
1560 C_OUTLINE_FRAG *top //top of cut
1561 ) {
1562 DIR128 *steps; //new steps
1563 inT32 stepcount; //no of steps
1564 inT16 fake_count; //fake steps
1565 DIR128 fake_step; //step entry
1566
1567 ASSERT_HOST (bottom->end.x () == top->start.x ());
1568 fake_count = top->start.y () - bottom->end.y ();
1569 if (fake_count < 0) {
1570 fake_count = -fake_count;
1571 fake_step = 32;
1572 }
1573 else
1574 fake_step = 96;
1575
1576 stepcount = bottom->stepcount + fake_count + top->stepcount;
1577 steps = new DIR128[stepcount];
1578 memmove (steps, bottom->steps, bottom->stepcount);
1579 memset (steps + bottom->stepcount, fake_step.get_dir(), fake_count);
1580 memmove (steps + bottom->stepcount + fake_count, top->steps,
1581 top->stepcount);
1582 delete [] bottom->steps;
1583 bottom->steps = steps;
1584 bottom->stepcount = stepcount;
1585 bottom->end = top->end;
1586 bottom->other_end->end = top->end;
1587 }
1588
1589
1590 /**********************************************************************
1591 * C_OUTLINE_FRAG::close
1592 *
1593 * Join the ends of this fragment and turn it into an outline.
1594 **********************************************************************/
1595
close()1596 C_OUTLINE *C_OUTLINE_FRAG::close() { //join pieces
1597 DIR128 *new_steps; //new steps
1598 inT32 new_stepcount; //no of steps
1599 inT16 fake_count; //fake steps
1600 DIR128 fake_step; //step entry
1601
1602 ASSERT_HOST (start.x () == end.x ());
1603 fake_count = start.y () - end.y ();
1604 if (fake_count < 0) {
1605 fake_count = -fake_count;
1606 fake_step = 32;
1607 }
1608 else
1609 fake_step = 96;
1610
1611 new_stepcount = stepcount + fake_count;
1612 new_steps = new DIR128[new_stepcount];
1613 memmove(new_steps, steps, stepcount);
1614 memset (new_steps + stepcount, fake_step.get_dir(), fake_count);
1615 C_OUTLINE* result = new C_OUTLINE (start, new_steps, new_stepcount);
1616 delete [] new_steps;
1617 return result;
1618 }
1619
1620
1621 /**********************************************************************
1622 * C_OUTLINE_FRAG::operator=
1623 *
1624 * Copy this fragment.
1625 **********************************************************************/
1626
1627 //join pieces
operator =(const C_OUTLINE_FRAG & src)1628 C_OUTLINE_FRAG & C_OUTLINE_FRAG::operator= (
1629 const C_OUTLINE_FRAG & src //fragment to copy
1630 ) {
1631 if (steps != NULL)
1632 delete [] steps;
1633
1634 stepcount = src.stepcount;
1635 steps = new DIR128[stepcount];
1636 memmove (steps, src.steps, stepcount);
1637 start = src.start;
1638 end = src.end;
1639 ycoord = src.ycoord;
1640 return *this;
1641 }
1642