Tesseract  3.02
 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 
41 "Max allowed bending of chop cells");
43 "Max distance of chop pt from vertex");
44 
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
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,
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 
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 
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 
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 
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
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 }