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
pithsync.cpp
Go to the documentation of this file.
1 /**********************************************************************
2 * File: pithsync.cpp (Formerly pitsync2.c)
3 * Description: Code to find the optimum fixed pitch segmentation of some blobs.
4 * Author: Ray Smith
5 * Created: Thu Nov 19 11:48:05 GMT 1992
6 *
7 * (C) Copyright 1992, 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 <math.h>
25 #include "memry.h"
26 #include "makerow.h"
27 #include "pitsync1.h"
28 #include "topitch.h"
29 #include "pithsync.h"
30 #include "tprintf.h"
31
32 #define PROJECTION_MARGIN 10 //arbitrary
33
34 #define EXTERN
35
36 /**********************************************************************
37 * FPCUTPT::setup
38 *
39 * Constructor to make a new FPCUTPT.
40 **********************************************************************/
41
42 void FPCUTPT::setup( //constructor
43 FPCUTPT *cutpts, //predecessors
44 inT16 array_origin, //start coord
45 STATS *projection, //vertical occupation
46 inT16 zero_count, //official zero
47 inT16 pitch, //proposed pitch
48 inT16 x, //position
49 inT16 offset //dist to gap
50 ) {
51 //half of pitch
52 inT16 half_pitch = pitch / 2 - 1;
53 uinT32 lead_flag; //new flag
54 inT32 ind; //current position
55
56 if (half_pitch > 31)
57 half_pitch = 31;
58 else if (half_pitch < 0)
59 half_pitch = 0;
60 lead_flag = 1 << half_pitch;
61
62 pred = NULL;
63 mean_sum = 0;
64 sq_sum = offset * offset;
65 cost = sq_sum;
66 faked = FALSE;
67 terminal = FALSE;
68 fake_count = 0;
69 xpos = x;
70 region_index = 0;
71 mid_cuts = 0;
72 if (x == array_origin) {
73 back_balance = 0;
74 fwd_balance = 0;
75 for (ind = 0; ind <= half_pitch; ind++) {
76 fwd_balance >>= 1;
77 if (projection->pile_count (ind) > zero_count)
78 fwd_balance |= lead_flag;
79 }
80 }
81 else {
82 back_balance = cutpts[x - 1 - array_origin].back_balance << 1;
83 back_balance &= lead_flag + lead_flag - 1;
84 if (projection->pile_count (x) > zero_count)
85 back_balance |= 1;
86 fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1;
87 if (projection->pile_count (x + half_pitch) > zero_count)
88 fwd_balance |= lead_flag;
89 }
90 }
91
92
93 /**********************************************************************
94 * FPCUTPT::assign
95 *
96 * Constructor to make a new FPCUTPT.
97 **********************************************************************/
98
99 void FPCUTPT::assign( //constructor
100 FPCUTPT *cutpts, //predecessors
101 inT16 array_origin, //start coord
102 inT16 x, //position
103 BOOL8 faking, //faking this one
104 BOOL8 mid_cut, //cheap cut.
105 inT16 offset, //dist to gap
106 STATS *projection, //vertical occupation
107 float projection_scale, //scaling
108 inT16 zero_count, //official zero
109 inT16 pitch, //proposed pitch
110 inT16 pitch_error //allowed tolerance
111 ) {
112 int index; //test index
113 int balance_index; //for balance factor
114 inT16 balance_count; //ding factor
115 inT16 r_index; //test cut number
116 FPCUTPT *segpt; //segment point
117 inT32 dist; //from prev segment
118 double sq_dist; //squared distance
119 double mean; //mean pitch
120 double total; //total dists
121 double factor; //cost function
122 //half of pitch
123 inT16 half_pitch = pitch / 2 - 1;
124 uinT32 lead_flag; //new flag
125
126 if (half_pitch > 31)
127 half_pitch = 31;
128 else if (half_pitch < 0)
129 half_pitch = 0;
130 lead_flag = 1 << half_pitch;
131
132 back_balance = cutpts[x - 1 - array_origin].back_balance << 1;
133 back_balance &= lead_flag + lead_flag - 1;
134 if (projection->pile_count (x) > zero_count)
135 back_balance |= 1;
136 fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1;
137 if (projection->pile_count (x + half_pitch) > zero_count)
138 fwd_balance |= lead_flag;
139
140 xpos = x;
141 cost = MAX_FLOAT32;
142 pred = NULL;
143 faked = faking;
144 terminal = FALSE;
145 region_index = 0;
146 fake_count = MAX_INT16;
147 for (index = x - pitch - pitch_error; index <= x - pitch + pitch_error;
148 index++) {
149 if (index >= array_origin) {
150 segpt = &cutpts[index - array_origin];
151 dist = x - segpt->xpos;
152 if (!segpt->terminal && segpt->fake_count < MAX_INT16) {
153 balance_count = 0;
154 if (textord_balance_factor > 0) {
155 if (textord_fast_pitch_test) {
156 lead_flag = back_balance ^ segpt->fwd_balance;
157 balance_count = 0;
158 while (lead_flag != 0) {
159 balance_count++;
160 lead_flag &= lead_flag - 1;
161 }
162 }
163 else {
164 for (balance_index = 0;
165 index + balance_index < x - balance_index;
166 balance_index++)
167 balance_count +=
168 (projection->pile_count (index + balance_index) <=
169 zero_count) ^ (projection->pile_count (x -
170 balance_index)
171 <= zero_count);
172 }
173 balance_count =
174 (inT16) (balance_count * textord_balance_factor /
175 projection_scale);
176 }
177 r_index = segpt->region_index + 1;
178 total = segpt->mean_sum + dist;
179 balance_count += offset;
180 sq_dist =
181 dist * dist + segpt->sq_sum + balance_count * balance_count;
182 mean = total / r_index;
183 factor = mean - pitch;
184 factor *= factor;
185 factor += sq_dist / (r_index) - mean * mean;
186 if (factor < cost && segpt->fake_count + faked <= fake_count) {
187 cost = factor; //find least cost
188 pred = segpt; //save path
189 mean_sum = total;
190 sq_sum = sq_dist;
191 fake_count = segpt->fake_count + faked;
192 mid_cuts = segpt->mid_cuts + mid_cut;
193 region_index = r_index;
194 }
195 }
196 }
197 }
198 }
199
200
201 /**********************************************************************
202 * FPCUTPT::assign_cheap
203 *
204 * Constructor to make a new FPCUTPT on the cheap.
205 **********************************************************************/
206
207 void FPCUTPT::assign_cheap( //constructor
208 FPCUTPT *cutpts, //predecessors
209 inT16 array_origin, //start coord
210 inT16 x, //position
211 BOOL8 faking, //faking this one
212 BOOL8 mid_cut, //cheap cut.
213 inT16 offset, //dist to gap
214 STATS *projection, //vertical occupation
215 float projection_scale, //scaling
216 inT16 zero_count, //official zero
217 inT16 pitch, //proposed pitch
218 inT16 pitch_error //allowed tolerance
219 ) {
220 int index; //test index
221 inT16 balance_count; //ding factor
222 inT16 r_index; //test cut number
223 FPCUTPT *segpt; //segment point
224 inT32 dist; //from prev segment
225 double sq_dist; //squared distance
226 double mean; //mean pitch
227 double total; //total dists
228 double factor; //cost function
229 //half of pitch
230 inT16 half_pitch = pitch / 2 - 1;
231 uinT32 lead_flag; //new flag
232
233 if (half_pitch > 31)
234 half_pitch = 31;
235 else if (half_pitch < 0)
236 half_pitch = 0;
237 lead_flag = 1 << half_pitch;
238
239 back_balance = cutpts[x - 1 - array_origin].back_balance << 1;
240 back_balance &= lead_flag + lead_flag - 1;
241 if (projection->pile_count (x) > zero_count)
242 back_balance |= 1;
243 fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1;
244 if (projection->pile_count (x + half_pitch) > zero_count)
245 fwd_balance |= lead_flag;
246
247 xpos = x;
248 cost = MAX_FLOAT32;
249 pred = NULL;
250 faked = faking;
251 terminal = FALSE;
252 region_index = 0;
253 fake_count = MAX_INT16;
254 index = x - pitch;
255 if (index >= array_origin) {
256 segpt = &cutpts[index - array_origin];
257 dist = x - segpt->xpos;
258 if (!segpt->terminal && segpt->fake_count < MAX_INT16) {
259 balance_count = 0;
260 if (textord_balance_factor > 0) {
261 lead_flag = back_balance ^ segpt->fwd_balance;
262 balance_count = 0;
263 while (lead_flag != 0) {
264 balance_count++;
265 lead_flag &= lead_flag - 1;
266 }
267 balance_count = (inT16) (balance_count * textord_balance_factor
268 / projection_scale);
269 }
270 r_index = segpt->region_index + 1;
271 total = segpt->mean_sum + dist;
272 balance_count += offset;
273 sq_dist =
274 dist * dist + segpt->sq_sum + balance_count * balance_count;
275 mean = total / r_index;
276 factor = mean - pitch;
277 factor *= factor;
278 factor += sq_dist / (r_index) - mean * mean;
279 cost = factor; //find least cost
280 pred = segpt; //save path
281 mean_sum = total;
282 sq_sum = sq_dist;
283 fake_count = segpt->fake_count + faked;
284 mid_cuts = segpt->mid_cuts + mid_cut;
285 region_index = r_index;
286 }
287 }
288 }
289
290
291 /**********************************************************************
292 * check_pitch_sync
293 *
294 * Construct the lattice of possible segmentation points and choose the
295 * optimal path. Return the optimal path only.
296 * The return value is a measure of goodness of the sync.
297 **********************************************************************/
298
299 double check_pitch_sync2( //find segmentation
300 BLOBNBOX_IT *blob_it, //blobs to do
301 inT16 blob_count, //no of blobs
302 inT16 pitch, //pitch estimate
303 inT16 pitch_error, //tolerance
304 STATS *projection, //vertical
305 inT16 projection_left, //edges //scale factor
306 inT16 projection_right,
307 float projection_scale,
308 inT16 &occupation_count, //no of occupied cells
309 FPSEGPT_LIST *seg_list, //output list
310 inT16 start, //start of good range
311 inT16 end //end of good range
312 ) {
313 BOOL8 faking; //illegal cut pt
314 BOOL8 mid_cut; //cheap cut pt.
315 inT16 x; //current coord
316 inT16 blob_index; //blob number
317 inT16 left_edge; //of word
318 inT16 right_edge; //of word
319 inT16 array_origin; //x coord of array
320 inT16 offset; //dist to legal area
321 inT16 zero_count; //projection zero
322 inT16 best_left_x = 0; //for equals
323 inT16 best_right_x = 0; //right edge
324 TBOX this_box; //bounding box
325 TBOX next_box; //box of next blob
326 FPSEGPT *segpt; //segment point
327 FPCUTPT *cutpts; //array of points
328 double best_cost; //best path
329 double mean_sum; //computes result
330 FPCUTPT *best_end; //end of best path
331 inT16 best_fake; //best fake level
332 inT16 best_count; //no of cuts
333 BLOBNBOX_IT this_it; //copy iterator
334 FPSEGPT_IT seg_it = seg_list; //output iterator
335
336 // tprintf("Computing sync on word of %d blobs with pitch %d\n",
337 // blob_count, pitch);
338 // if (blob_count==8 && pitch==27)
339 // projection->print(stdout,TRUE);
340 zero_count = 0;
341 if (pitch < 3)
342 pitch = 3; //nothing ludicrous
343 if ((pitch - 3) / 2 < pitch_error)
344 pitch_error = (pitch - 3) / 2;
345 this_it = *blob_it;
346 this_box = box_next (&this_it);//get box
347 // left_edge=this_box.left(); //left of word
348 // right_edge=this_box.right();
349 // for (blob_index=1;blob_index<blob_count;blob_index++)
350 // {
351 // this_box=box_next(&this_it);
352 // if (this_box.right()>right_edge)
353 // right_edge=this_box.right();
354 // }
355 for (left_edge = projection_left; projection->pile_count (left_edge) == 0
356 && left_edge < projection_right; left_edge++);
357 for (right_edge = projection_right; projection->pile_count (right_edge) == 0
358 && right_edge > left_edge; right_edge--);
359 ASSERT_HOST (right_edge >= left_edge);
360 if (pitsync_linear_version >= 4)
361 return check_pitch_sync3 (projection_left, projection_right, zero_count,
362 pitch, pitch_error, projection,
363 projection_scale, occupation_count, seg_list,
364 start, end);
365 array_origin = left_edge - pitch;
366 cutpts = (FPCUTPT *) alloc_mem ((right_edge - left_edge + pitch * 2 + 1)
367 * sizeof (FPCUTPT));
368 for (x = array_origin; x < left_edge; x++)
369 //free cuts
370 cutpts[x - array_origin].setup (cutpts, array_origin, projection, zero_count, pitch, x, 0);
371 for (offset = 0; offset <= pitch_error; offset++, x++)
372 //not quite free
373 cutpts[x - array_origin].setup (cutpts, array_origin, projection, zero_count, pitch, x, offset);
374
375 this_it = *blob_it;
376 best_cost = MAX_FLOAT32;
377 best_end = NULL;
378 this_box = box_next (&this_it);//first box
379 next_box = box_next (&this_it);//second box
380 blob_index = 1;
381 while (x < right_edge - pitch_error) {
382 if (x > this_box.right () + pitch_error && blob_index < blob_count) {
383 this_box = next_box;
384 next_box = box_next (&this_it);
385 blob_index++;
386 }
387 faking = FALSE;
388 mid_cut = FALSE;
389 if (x <= this_box.left ())
390 offset = 0;
391 else if (x <= this_box.left () + pitch_error)
392 offset = x - this_box.left ();
393 else if (x >= this_box.right ())
394 offset = 0;
395 else if (x >= next_box.left () && blob_index < blob_count) {
396 offset = x - next_box.left ();
397 if (this_box.right () - x < offset)
398 offset = this_box.right () - x;
399 }
400 else if (x >= this_box.right () - pitch_error)
401 offset = this_box.right () - x;
402 else if (x - this_box.left () > pitch * pitsync_joined_edge
403 && this_box.right () - x > pitch * pitsync_joined_edge) {
404 mid_cut = TRUE;
405 offset = 0;
406 }
407 else {
408 faking = TRUE;
409 offset = projection->pile_count (x);
410 }
411 cutpts[x - array_origin].assign (cutpts, array_origin, x,
412 faking, mid_cut, offset, projection,
413 projection_scale, zero_count, pitch,
414 pitch_error);
415 x++;
416 }
417
418 best_fake = MAX_INT16;
419 best_cost = MAX_INT32;
420 best_count = MAX_INT16;
421 while (x < right_edge + pitch) {
422 offset = x < right_edge ? right_edge - x : 0;
423 cutpts[x - array_origin].assign (cutpts, array_origin, x,
424 FALSE, FALSE, offset, projection,
425 projection_scale, zero_count, pitch,
426 pitch_error);
427 cutpts[x - array_origin].terminal = TRUE;
428 if (cutpts[x - array_origin].index () +
429 cutpts[x - array_origin].fake_count <= best_count + best_fake) {
430 if (cutpts[x - array_origin].fake_count < best_fake
431 || (cutpts[x - array_origin].fake_count == best_fake
432 && cutpts[x - array_origin].cost_function () < best_cost)) {
433 best_fake = cutpts[x - array_origin].fake_count;
434 best_cost = cutpts[x - array_origin].cost_function ();
435 best_left_x = x;
436 best_right_x = x;
437 best_count = cutpts[x - array_origin].index ();
438 }
439 else if (cutpts[x - array_origin].fake_count == best_fake
440 && x == best_right_x + 1
441 && cutpts[x - array_origin].cost_function () == best_cost) {
442 //exactly equal
443 best_right_x = x;
444 }
445 }
446 x++;
447 }
448 ASSERT_HOST (best_fake < MAX_INT16);
449
450 best_end = &cutpts[(best_left_x + best_right_x) / 2 - array_origin];
451 if (this_box.right () == textord_test_x
452 && this_box.top () == textord_test_y) {
453 for (x = left_edge - pitch; x < right_edge + pitch; x++) {
454 tprintf ("x=%d, C=%g, s=%g, sq=%g, prev=%d\n",
455 x, cutpts[x - array_origin].cost_function (),
456 cutpts[x - array_origin].sum (),
457 cutpts[x - array_origin].squares (),
458 cutpts[x - array_origin].previous ()->position ());
459 }
460 }
461 occupation_count = -1;
462 do {
463 for (x = best_end->position () - pitch + pitch_error;
464 x < best_end->position () - pitch_error
465 && projection->pile_count (x) == 0; x++);
466 if (x < best_end->position () - pitch_error)
467 occupation_count++;
468 //copy it
469 segpt = new FPSEGPT (best_end);
470 seg_it.add_before_then_move (segpt);
471 best_end = best_end->previous ();
472 }
473 while (best_end != NULL);
474 seg_it.move_to_last ();
475 mean_sum = seg_it.data ()->sum ();
476 mean_sum = mean_sum * mean_sum / best_count;
477 if (seg_it.data ()->squares () - mean_sum < 0)
478 tprintf ("Impossible sqsum=%g, mean=%g, total=%d\n",
479 seg_it.data ()->squares (), seg_it.data ()->sum (), best_count);
480 free_mem(cutpts);
481 // tprintf("blob_count=%d, pitch=%d, sync=%g, occ=%d\n",
482 // blob_count,pitch,seg_it.data()->squares()-mean_sum,
483 // occupation_count);
484 return seg_it.data ()->squares () - mean_sum;
485 }
486
487
488 /**********************************************************************
489 * check_pitch_sync
490 *
491 * Construct the lattice of possible segmentation points and choose the
492 * optimal path. Return the optimal path only.
493 * The return value is a measure of goodness of the sync.
494 **********************************************************************/
495
496 double check_pitch_sync3( //find segmentation
497 inT16 projection_left, //edges //to be considered 0
498 inT16 projection_right,
499 inT16 zero_count,
500 inT16 pitch, //pitch estimate
501 inT16 pitch_error, //tolerance
502 STATS *projection, //vertical
503 float projection_scale, //scale factor
504 inT16 &occupation_count, //no of occupied cells
505 FPSEGPT_LIST *seg_list, //output list
506 inT16 start, //start of good range
507 inT16 end //end of good range
508 ) {
509 BOOL8 faking; //illegal cut pt
510 BOOL8 mid_cut; //cheap cut pt.
511 inT16 left_edge; //of word
512 inT16 right_edge; //of word
513 inT16 x; //current coord
514 inT16 array_origin; //x coord of array
515 inT16 offset; //dist to legal area
516 inT16 projection_offset; //from scaled projection
517 inT16 prev_zero; //previous zero dist
518 inT16 next_zero; //next zero dist
519 inT16 zero_offset; //scan window
520 inT16 best_left_x = 0; //for equals
521 inT16 best_right_x = 0; //right edge
522 FPSEGPT *segpt; //segment point
523 FPCUTPT *cutpts; //array of points
524 BOOL8 *mins; //local min results
525 int minindex; //next input position
526 int test_index; //index to mins
527 double best_cost; //best path
528 double mean_sum; //computes result
529 FPCUTPT *best_end; //end of best path
530 inT16 best_fake; //best fake level
531 inT16 best_count; //no of cuts
532 FPSEGPT_IT seg_it = seg_list; //output iterator
533
534 end = (end - start) % pitch;
535 if (pitch < 3)
536 pitch = 3; //nothing ludicrous
537 if ((pitch - 3) / 2 < pitch_error)
538 pitch_error = (pitch - 3) / 2;
539 //min dist of zero
540 zero_offset = (inT16) (pitch * pitsync_joined_edge);
541 for (left_edge = projection_left; projection->pile_count (left_edge) == 0
542 && left_edge < projection_right; left_edge++);
543 for (right_edge = projection_right; projection->pile_count (right_edge) == 0
544 && right_edge > left_edge; right_edge--);
545 array_origin = left_edge - pitch;
546 cutpts = (FPCUTPT *) alloc_mem ((right_edge - left_edge + pitch * 2 + 1)
547 * sizeof (FPCUTPT));
548 mins = (BOOL8 *) alloc_mem ((pitch_error * 2 + 1) * sizeof (BOOL8));
549 for (x = array_origin; x < left_edge; x++)
550 //free cuts
551 cutpts[x - array_origin].setup (cutpts, array_origin, projection, zero_count, pitch, x, 0);
552 prev_zero = left_edge - 1;
553 for (offset = 0; offset <= pitch_error; offset++, x++)
554 //not quite free
555 cutpts[x - array_origin].setup (cutpts, array_origin, projection, zero_count, pitch, x, offset);
556
557 best_cost = MAX_FLOAT32;
558 best_end = NULL;
559 for (offset = -pitch_error, minindex = 0; offset < pitch_error;
560 offset++, minindex++)
561 mins[minindex] = projection->local_min (x + offset);
562 next_zero = x + zero_offset + 1;
563 for (offset = next_zero - 1; offset >= x; offset--) {
564 if (projection->pile_count (offset) <= zero_count) {
565 next_zero = offset;
566 break;
567 }
568 }
569 while (x < right_edge - pitch_error) {
570 mins[minindex] = projection->local_min (x + pitch_error);
571 minindex++;
572 if (minindex > pitch_error * 2)
573 minindex = 0;
574 faking = FALSE;
575 mid_cut = FALSE;
576 offset = 0;
577 if (projection->pile_count (x) <= zero_count) {
578 prev_zero = x;
579 }
580 else {
581 for (offset = 1; offset <= pitch_error; offset++)
582 if (projection->pile_count (x + offset) <= zero_count
583 || projection->pile_count (x - offset) <= zero_count)
584 break;
585 }
586 if (offset > pitch_error) {
587 if (x - prev_zero > zero_offset && next_zero - x > zero_offset) {
588 for (offset = 0; offset <= pitch_error; offset++) {
589 test_index = minindex + pitch_error + offset;
590 if (test_index > pitch_error * 2)
591 test_index -= pitch_error * 2 + 1;
592 if (mins[test_index])
593 break;
594 test_index = minindex + pitch_error - offset;
595 if (test_index > pitch_error * 2)
596 test_index -= pitch_error * 2 + 1;
597 if (mins[test_index])
598 break;
599 }
600 }
601 if (offset > pitch_error) {
602 offset = projection->pile_count (x);
603 faking = TRUE;
604 }
605 else {
606 projection_offset =
607 (inT16) (projection->pile_count (x) / projection_scale);
608 if (projection_offset > offset)
609 offset = projection_offset;
610 mid_cut = TRUE;
611 }
612 }
613 if ((start == 0 && end == 0)
614 || !textord_fast_pitch_test
615 || (x - projection_left - start) % pitch <= end)
616 cutpts[x - array_origin].assign (cutpts, array_origin, x,
617 faking, mid_cut, offset, projection,
618 projection_scale, zero_count, pitch,
619 pitch_error);
620 else
621 cutpts[x - array_origin].assign_cheap (cutpts, array_origin, x,
622 faking, mid_cut, offset,
623 projection, projection_scale,
624 zero_count, pitch,
625 pitch_error);
626 x++;
627 if (next_zero < x || next_zero == x + zero_offset)
628 next_zero = x + zero_offset + 1;
629 if (projection->pile_count (x + zero_offset) <= zero_count)
630 next_zero = x + zero_offset;
631 }
632
633 best_fake = MAX_INT16;
634 best_cost = MAX_INT32;
635 best_count = MAX_INT16;
636 while (x < right_edge + pitch) {
637 offset = x < right_edge ? right_edge - x : 0;
638 cutpts[x - array_origin].assign (cutpts, array_origin, x,
639 FALSE, FALSE, offset, projection,
640 projection_scale, zero_count, pitch,
641 pitch_error);
642 cutpts[x - array_origin].terminal = TRUE;
643 if (cutpts[x - array_origin].index () +
644 cutpts[x - array_origin].fake_count <= best_count + best_fake) {
645 if (cutpts[x - array_origin].fake_count < best_fake
646 || (cutpts[x - array_origin].fake_count == best_fake
647 && cutpts[x - array_origin].cost_function () < best_cost)) {
648 best_fake = cutpts[x - array_origin].fake_count;
649 best_cost = cutpts[x - array_origin].cost_function ();
650 best_left_x = x;
651 best_right_x = x;
652 best_count = cutpts[x - array_origin].index ();
653 }
654 else if (cutpts[x - array_origin].fake_count == best_fake
655 && x == best_right_x + 1
656 && cutpts[x - array_origin].cost_function () == best_cost) {
657 //exactly equal
658 best_right_x = x;
659 }
660 }
661 x++;
662 }
663 ASSERT_HOST (best_fake < MAX_INT16);
664
665 best_end = &cutpts[(best_left_x + best_right_x) / 2 - array_origin];
666 // for (x=left_edge-pitch;x<right_edge+pitch;x++)
667 // {
668 // tprintf("x=%d, C=%g, s=%g, sq=%g, prev=%d\n",
669 // x,cutpts[x-array_origin].cost_function(),
670 // cutpts[x-array_origin].sum(),
671 // cutpts[x-array_origin].squares(),
672 // cutpts[x-array_origin].previous()->position());
673 // }
674 occupation_count = -1;
675 do {
676 for (x = best_end->position () - pitch + pitch_error;
677 x < best_end->position () - pitch_error
678 && projection->pile_count (x) == 0; x++);
679 if (x < best_end->position () - pitch_error)
680 occupation_count++;
681 //copy it
682 segpt = new FPSEGPT (best_end);
683 seg_it.add_before_then_move (segpt);
684 best_end = best_end->previous ();
685 }
686 while (best_end != NULL);
687 seg_it.move_to_last ();
688 mean_sum = seg_it.data ()->sum ();
689 mean_sum = mean_sum * mean_sum / best_count;
690 if (seg_it.data ()->squares () - mean_sum < 0)
691 tprintf ("Impossible sqsum=%g, mean=%g, total=%d\n",
692 seg_it.data ()->squares (), seg_it.data ()->sum (), best_count);
693 free_mem(mins);
694 free_mem(cutpts);
695 return seg_it.data ()->squares () - mean_sum;
696 }