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
blobs.cpp
Go to the documentation of this file.
1 /* -*-C-*-
2 ********************************************************************************
3 *
4 * File: blobs.c (Formerly blobs.c)
5 * Description: Blob definition
6 * Author: Mark Seaman, OCR Technology
7 * Created: Fri Oct 27 15:39:52 1989
8 * Modified: Thu Mar 28 15:33:26 1991 (Mark Seaman) marks@hpgrlt
9 * Language: C
10 * Package: N/A
11 * Status: Experimental (Do Not Distribute)
12 *
13 * (c) Copyright 1989, Hewlett-Packard Company.
14 ** Licensed under the Apache License, Version 2.0 (the "License");
15 ** you may not use this file except in compliance with the License.
16 ** You may obtain a copy of the License at
17 ** http://www.apache.org/licenses/LICENSE-2.0
18 ** Unless required by applicable law or agreed to in writing, software
19 ** distributed under the License is distributed on an "AS IS" BASIS,
20 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
21 ** See the License for the specific language governing permissions and
22 ** limitations under the License.
23 *
24 *********************************************************************************/
25
26 /*----------------------------------------------------------------------
27 I n c l u d e s
28 ----------------------------------------------------------------------*/
29 // Include automatically generated configuration file if running autoconf.
30 #ifdef HAVE_CONFIG_H
31 #include "config_auto.h"
32 #endif
33
34 #include "mfcpch.h"
35 #include "blobs.h"
36 #include "ccstruct.h"
37 #include "clst.h"
38 #include "cutil.h"
39 #include "emalloc.h"
40 #include "helpers.h"
41 #include "ndminx.h"
42 #include "normalis.h"
43 #include "ocrblock.h"
44 #include "ocrrow.h"
45 #include "points.h"
46 #include "polyaprx.h"
47 #include "structures.h"
48 #include "werd.h"
49
50 using tesseract::CCStruct;
51
52 // A Vector representing the "vertical" direction when measuring the
53 // divisiblity of blobs into multiple blobs just by separating outlines.
54 // See divisible_blob below for the use.
55 const TPOINT kDivisibleVerticalUpright(0, 1);
56 // A vector representing the "vertical" direction for italic text for use
57 // when separating outlines. Using it actually deteriorates final accuracy,
58 // so it is only used for ApplyBoxes chopping to get a better segmentation.
59 const TPOINT kDivisibleVerticalItalic(1, 5);
60
61 /*----------------------------------------------------------------------
62 F u n c t i o n s
63 ----------------------------------------------------------------------*/
64
65 CLISTIZE(EDGEPT);
66
67 // Consume the circular list of EDGEPTs to make a TESSLINE.
68 TESSLINE* TESSLINE::BuildFromOutlineList(EDGEPT* outline) {
69 TESSLINE* result = new TESSLINE;
70 result->loop = outline;
71 result->SetupFromPos();
72 return result;
73 }
74
75 // Copies the data and the outline, but leaves next untouched.
76 void TESSLINE::CopyFrom(const TESSLINE& src) {
77 Clear();
78 topleft = src.topleft;
79 botright = src.botright;
80 start = src.start;
81 is_hole = src.is_hole;
82 if (src.loop != NULL) {
83 EDGEPT* prevpt = NULL;
84 EDGEPT* newpt = NULL;
85 EDGEPT* srcpt = src.loop;
86 do {
87 newpt = new EDGEPT(*srcpt);
88 if (prevpt == NULL) {
89 loop = newpt;
90 } else {
91 newpt->prev = prevpt;
92 prevpt->next = newpt;
93 }
94 prevpt = newpt;
95 srcpt = srcpt->next;
96 } while (srcpt != src.loop);
97 loop->prev = newpt;
98 newpt->next = loop;
99 }
100 }
101
102 // Deletes owned data.
103 void TESSLINE::Clear() {
104 if (loop == NULL)
105 return;
106
107 EDGEPT* this_edge = loop;
108 do {
109 EDGEPT* next_edge = this_edge->next;
110 delete this_edge;
111 this_edge = next_edge;
112 } while (this_edge != loop);
113 loop = NULL;
114 }
115
116 // Normalize in-place using the DENORM.
117 void TESSLINE::Normalize(const DENORM& denorm) {
118 EDGEPT* pt = loop;
119 do {
120 denorm.LocalNormTransform(pt->pos, &pt->pos);
121 pt = pt->next;
122 } while (pt != loop);
123 SetupFromPos();
124 }
125
126 // Rotates by the given rotation in place.
127 void TESSLINE::Rotate(const FCOORD rot) {
128 EDGEPT* pt = loop;
129 do {
130 int tmp = static_cast<int>(floor(pt->pos.x * rot.x() -
131 pt->pos.y * rot.y() + 0.5));
132 pt->pos.y = static_cast<int>(floor(pt->pos.y * rot.x() +
133 pt->pos.x * rot.y() + 0.5));
134 pt->pos.x = tmp;
135 pt = pt->next;
136 } while (pt != loop);
137 SetupFromPos();
138 }
139
140 // Moves by the given vec in place.
141 void TESSLINE::Move(const ICOORD vec) {
142 EDGEPT* pt = loop;
143 do {
144 pt->pos.x += vec.x();
145 pt->pos.y += vec.y();
146 pt = pt->next;
147 } while (pt != loop);
148 SetupFromPos();
149 }
150
151 // Scales by the given factor in place.
152 void TESSLINE::Scale(float factor) {
153 EDGEPT* pt = loop;
154 do {
155 pt->pos.x = static_cast<int>(floor(pt->pos.x * factor + 0.5));
156 pt->pos.y = static_cast<int>(floor(pt->pos.y * factor + 0.5));
157 pt = pt->next;
158 } while (pt != loop);
159 SetupFromPos();
160 }
161
162 // Sets up the start and vec members of the loop from the pos members.
163 void TESSLINE::SetupFromPos() {
164 EDGEPT* pt = loop;
165 do {
166 pt->vec.x = pt->next->pos.x - pt->pos.x;
167 pt->vec.y = pt->next->pos.y - pt->pos.y;
168 pt = pt->next;
169 } while (pt != loop);
170 start = pt->pos;
171 ComputeBoundingBox();
172 }
173
174 // Recomputes the bounding box from the points in the loop.
175 void TESSLINE::ComputeBoundingBox() {
176 int minx = MAX_INT32;
177 int miny = MAX_INT32;
178 int maxx = -MAX_INT32;
179 int maxy = -MAX_INT32;
180
181 // Find boundaries.
182 start = loop->pos;
183 EDGEPT* this_edge = loop;
184 do {
185 if (!this_edge->IsHidden() || !this_edge->prev->IsHidden()) {
186 if (this_edge->pos.x < minx)
187 minx = this_edge->pos.x;
188 if (this_edge->pos.y < miny)
189 miny = this_edge->pos.y;
190 if (this_edge->pos.x > maxx)
191 maxx = this_edge->pos.x;
192 if (this_edge->pos.y > maxy)
193 maxy = this_edge->pos.y;
194 }
195 this_edge = this_edge->next;
196 } while (this_edge != loop);
197 // Reset bounds.
198 topleft.x = minx;
199 topleft.y = maxy;
200 botright.x = maxx;
201 botright.y = miny;
202 }
203
204 // Computes the min and max cross product of the outline points with the
205 // given vec and returns the results in min_xp and max_xp. Geometrically
206 // this is the left and right edge of the outline perpendicular to the
207 // given direction, but to get the distance units correct, you would
208 // have to divide by the modulus of vec.
209 void TESSLINE::MinMaxCrossProduct(const TPOINT vec,
210 int* min_xp, int* max_xp) const {
211 *min_xp = MAX_INT32;
212 *max_xp = MIN_INT32;
213 EDGEPT* this_edge = loop;
214 do {
215 if (!this_edge->IsHidden() || !this_edge->prev->IsHidden()) {
216 int product = CROSS(this_edge->pos, vec);
217 UpdateRange(product, min_xp, max_xp);
218 }
219 this_edge = this_edge->next;
220 } while (this_edge != loop);
221 }
222
223 TBOX TESSLINE::bounding_box() const {
224 return TBOX(topleft.x, botright.y, botright.x, topleft.y);
225 }
226
227 #ifndef GRAPHICS_DISABLED
228 void TESSLINE::plot(ScrollView* window, ScrollView::Color color,
229 ScrollView::Color child_color) {
230 if (is_hole)
231 window->Pen(child_color);
232 else
233 window->Pen(color);
234 window->SetCursor(start.x, start.y);
235 EDGEPT* pt = loop;
236 do {
237 bool prev_hidden = pt->IsHidden();
238 pt = pt->next;
239 if (prev_hidden)
240 window->SetCursor(pt->pos.x, pt->pos.y);
241 else
242 window->DrawTo(pt->pos.x, pt->pos.y);
243 } while (pt != loop);
244 }
245 #endif // GRAPHICS_DISABLED
246
247 // Iterate the given list of outlines, converting to TESSLINE by polygonal
248 // approximation and recursively any children, returning the current tail
249 // of the resulting list of TESSLINEs.
250 static TESSLINE** ApproximateOutlineList(C_OUTLINE_LIST* outlines,
251 bool children,
252 TESSLINE** tail) {
253 C_OUTLINE_IT ol_it(outlines);
254 for (ol_it.mark_cycle_pt(); !ol_it.cycled_list(); ol_it.forward()) {
255 C_OUTLINE* outline = ol_it.data();
256 TESSLINE* tessline = ApproximateOutline(outline);
257 tessline->is_hole = children;
258 *tail = tessline;
259 tail = &tessline->next;
260 if (!outline->child()->empty()) {
261 tail = ApproximateOutlineList(outline->child(), true, tail);
262 }
263 }
264 return tail;
265 }
266
267 // Factory to build a TBLOB from a C_BLOB with polygonal
268 // approximation along the way.
269 TBLOB* TBLOB::PolygonalCopy(C_BLOB* src) {
270 C_OUTLINE_IT ol_it = src->out_list();
271 TBLOB* tblob = new TBLOB;
272 ApproximateOutlineList(src->out_list(), false, &tblob->outlines);
273 return tblob;
274 }
275
276 // Normalizes the blob for classification only if needed.
277 // (Normally this means a non-zero classify rotation.)
278 // If no Normalization is needed, then NULL is returned, and the denorm is
279 // unchanged. Otherwise a new TBLOB is returned and the denorm points to
280 // a new DENORM. In this case, both the TBLOB and DENORM must be deleted.
281 TBLOB* TBLOB::ClassifyNormalizeIfNeeded(const DENORM** denorm) const {
282 TBLOB* rotated_blob = NULL;
283 // If necessary, copy the blob and rotate it. The rotation is always
284 // +/- 90 degrees, as 180 was already taken care of.
285 if ((*denorm)->block() != NULL &&
286 (*denorm)->block()->classify_rotation().y() != 0.0) {
287 TBOX box = bounding_box();
288 int x_middle = (box.left() + box.right()) / 2;
289 int y_middle = (box.top() + box.bottom()) / 2;
290 rotated_blob = new TBLOB(*this);
291 const FCOORD& rotation = (*denorm)->block()->classify_rotation();
292 DENORM* norm = new DENORM;
293 // Move the rotated blob back to the same y-position so that we
294 // can still distinguish similar glyphs with differeny y-position.
295 float target_y = kBlnBaselineOffset +
296 (rotation.y() > 0 ? x_middle - box.left() : box.right() - x_middle);
297 norm->SetupNormalization(NULL, NULL, &rotation, *denorm, NULL, 0,
298 x_middle, y_middle, 1.0f, 1.0f, 0.0f, target_y);
299 // x_middle, y_middle, 1.0f, 1.0f, 0.0f, y_middle);
300 rotated_blob->Normalize(*norm);
301 *denorm = norm;
302 }
303 return rotated_blob;
304 }
305
306 // Copies the data and the outline, but leaves next untouched.
307 void TBLOB::CopyFrom(const TBLOB& src) {
308 Clear();
309 TESSLINE* prev_outline = NULL;
310 for (TESSLINE* srcline = src.outlines; srcline != NULL;
311 srcline = srcline->next) {
312 TESSLINE* new_outline = new TESSLINE(*srcline);
313 if (outlines == NULL)
314 outlines = new_outline;
315 else
316 prev_outline->next = new_outline;
317 prev_outline = new_outline;
318 }
319 }
320
321 // Deletes owned data.
322 void TBLOB::Clear() {
323 for (TESSLINE* next_outline = NULL; outlines != NULL;
324 outlines = next_outline) {
325 next_outline = outlines->next;
326 delete outlines;
327 }
328 }
329 // Normalize in-place using the DENORM.
330 void TBLOB::Normalize(const DENORM& denorm) {
331 // TODO(rays) outline->Normalize is more accurate, but breaks tests due
332 // the changes it makes. Reinstate this code with a retraining.
333 #if 1
334 for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next) {
335 outline->Normalize(denorm);
336 }
337 #else
338 denorm.LocalNormBlob(this);
339 #endif
340 }
341
342 // Rotates by the given rotation in place.
343 void TBLOB::Rotate(const FCOORD rotation) {
344 for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next) {
345 outline->Rotate(rotation);
346 }
347 }
348
349 // Moves by the given vec in place.
350 void TBLOB::Move(const ICOORD vec) {
351 for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next) {
352 outline->Move(vec);
353 }
354 }
355
356 // Scales by the given factor in place.
357 void TBLOB::Scale(float factor) {
358 for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next) {
359 outline->Scale(factor);
360 }
361 }
362
363 // Recomputes the bounding boxes of the outlines.
364 void TBLOB::ComputeBoundingBoxes() {
365 for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next) {
366 outline->ComputeBoundingBox();
367 }
368 }
369
370 // Returns the number of outlines.
371 int TBLOB::NumOutlines() const {
372 int result = 0;
373 for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next)
374 ++result;
375 return result;
376 }
377
378 /**********************************************************************
379 * TBLOB::bounding_box()
380 *
381 * Compute the bounding_box of a compound blob, defined to be the
382 * bounding box of the union of all top-level outlines in the blob.
383 **********************************************************************/
384 TBOX TBLOB::bounding_box() const {
385 if (outlines == NULL)
386 return TBOX(0, 0, 0, 0);
387 TESSLINE *outline = outlines;
388 TBOX box = outline->bounding_box();
389 for (outline = outline->next; outline != NULL; outline = outline->next) {
390 box += outline->bounding_box();
391 }
392 return box;
393 }
394
395 #ifndef GRAPHICS_DISABLED
396 void TBLOB::plot(ScrollView* window, ScrollView::Color color,
397 ScrollView::Color child_color) {
398 for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next)
399 outline->plot(window, color, child_color);
400 }
401 #endif // GRAPHICS_DISABLED
402
403 // Factory to build a TWERD from a (C_BLOB) WERD, with polygonal
404 // approximation along the way.
405 TWERD* TWERD::PolygonalCopy(WERD* src) {
406 TWERD* tessword = new TWERD;
407 tessword->latin_script = src->flag(W_SCRIPT_IS_LATIN);
408 C_BLOB_IT b_it(src->cblob_list());
409 TBLOB *tail = NULL;
410 for (b_it.mark_cycle_pt(); !b_it.cycled_list(); b_it.forward()) {
411 C_BLOB* blob = b_it.data();
412 TBLOB* tblob = TBLOB::PolygonalCopy(blob);
413 if (tail == NULL) {
414 tessword->blobs = tblob;
415 } else {
416 tail->next = tblob;
417 }
418 tail = tblob;
419 }
420 return tessword;
421 }
422
423 // Normalize in-place and record the normalization in the DENORM.
424 void TWERD::SetupBLNormalize(const BLOCK* block, const ROW* row,
425 float x_height, bool numeric_mode,
426 DENORM* denorm) const {
427 int num_segments = 0;
428 DENORM_SEG* segs = NULL;
429 if (numeric_mode) {
430 segs = new DENORM_SEG[NumBlobs()];
431 for (TBLOB* blob = blobs; blob != NULL; blob = blob->next) {
432 TBOX blob_box = blob->bounding_box();
433 float factor = kBlnXHeight / x_height;
434 factor = ClipToRange(kBlnXHeight * 4.0f / (3 * blob_box.height()),
435 factor, factor * 1.5f);
436 segs[num_segments].xstart = blob_box.left();
437 segs[num_segments].ycoord = blob_box.bottom();
438 segs[num_segments++].scale_factor = factor;
439 }
440 }
441 denorm->SetupBLNormalize(block, row, x_height, bounding_box(),
442 num_segments, segs);
443 delete [] segs;
444 }
445
446 // Normalize in-place using the DENORM.
447 void TWERD::Normalize(const DENORM& denorm) {
448 for (TBLOB* blob = blobs; blob != NULL; blob = blob->next) {
449 blob->Normalize(denorm);
450 }
451 }
452
453 // Copies the data and the blobs, but leaves next untouched.
454 void TWERD::CopyFrom(const TWERD& src) {
455 Clear();
456 latin_script = src.latin_script;
457 TBLOB* prev_blob = NULL;
458 for (TBLOB* srcblob = src.blobs; srcblob != NULL; srcblob = srcblob->next) {
459 TBLOB* new_blob = new TBLOB(*srcblob);
460 if (blobs == NULL)
461 blobs = new_blob;
462 else
463 prev_blob->next = new_blob;
464 prev_blob = new_blob;
465 }
466 }
467
468 // Deletes owned data.
469 void TWERD::Clear() {
470 for (TBLOB* next_blob = NULL; blobs != NULL; blobs = next_blob) {
471 next_blob = blobs->next;
472 delete blobs;
473 }
474 }
475
476 // Recomputes the bounding boxes of the blobs.
477 void TWERD::ComputeBoundingBoxes() {
478 for (TBLOB* blob = blobs; blob != NULL; blob = blob->next) {
479 blob->ComputeBoundingBoxes();
480 }
481 }
482
483 TBOX TWERD::bounding_box() const {
484 TBOX result;
485 for (TBLOB* blob = blobs; blob != NULL; blob = blob->next) {
486 TBOX box = blob->bounding_box();
487 result += box;
488 }
489 return result;
490 }
491
492 // Merges the blobs from start to end, not including end, and deletes
493 // the blobs between start and end.
494 void TWERD::MergeBlobs(int start, int end) {
495 TBLOB* blob = blobs;
496 for (int i = 0; i < start && blob != NULL; ++i)
497 blob = blob->next;
498 if (blob == NULL || blob->next == NULL)
499 return;
500 TBLOB* next_blob = blob->next;
501 TESSLINE* outline = blob->outlines;
502 for (int i = start + 1; i < end && next_blob != NULL; ++i) {
503 // Take the outlines from the next blob.
504 if (outline == NULL) {
505 blob->outlines = next_blob->outlines;
506 outline = blob->outlines;
507 } else {
508 while (outline->next != NULL)
509 outline = outline->next;
510 outline->next = next_blob->outlines;
511 next_blob->outlines = NULL;
512 }
513 // Delete the next blob and move on.
514 TBLOB* dead_blob = next_blob;
515 next_blob = next_blob->next;
516 blob->next = next_blob;
517 delete dead_blob;
518 }
519 }
520
521 #ifndef GRAPHICS_DISABLED
522 void TWERD::plot(ScrollView* window) {
523 ScrollView::Color color = WERD::NextColor(ScrollView::BLACK);
524 for (TBLOB* blob = blobs; blob != NULL; blob = blob->next) {
525 blob->plot(window, color, ScrollView::BROWN);
526 color = WERD::NextColor(color);
527 }
528 }
529 #endif // GRAPHICS_DISABLED
530
531 /**********************************************************************
532 * blob_origin
533 *
534 * Compute the origin of a compound blob, define to be the centre
535 * of the bounding box.
536 **********************************************************************/
537 void blob_origin(TBLOB *blob, /*blob to compute on */
538 TPOINT *origin) { /*return value */
539 TBOX bbox = blob->bounding_box();
540 *origin = (bbox.topleft() + bbox.botright()) / 2;
541 }
542
543 /**********************************************************************
544 * blobs_widths
545 *
546 * Compute the widths of a list of blobs. Return an array of the widths
547 * and gaps.
548 **********************************************************************/
549 WIDTH_RECORD *blobs_widths(TBLOB *blobs) { /*blob to compute on */
550 WIDTH_RECORD *width_record;
551 TPOINT topleft; /*bounding box */
552 TPOINT botright;
553 int i = 0;
554 int blob_end;
555 int num_blobs = count_blobs (blobs);
556
557 /* Get memory */
558 width_record = (WIDTH_RECORD *) memalloc (sizeof (int) * num_blobs * 2);
559 width_record->num_chars = num_blobs;
560
561 TBOX bbox = blobs->bounding_box();
562 width_record->widths[i++] = bbox.width();
563 /* First width */
564 blob_end = bbox.right();
565
566 for (TBLOB* blob = blobs->next; blob != NULL; blob = blob->next) {
567 TBOX curbox = blob->bounding_box();
568 width_record->widths[i++] = curbox.left() - blob_end;
569 width_record->widths[i++] = curbox.width();
570 blob_end = curbox.right();
571 }
572 return width_record;
573 }
574
575
576 /**********************************************************************
577 * count_blobs
578 *
579 * Return a count of the number of blobs attached to this one.
580 **********************************************************************/
581 int count_blobs(TBLOB *blobs) {
582 int x = 0;
583
584 for (TBLOB* b = blobs; b != NULL; b = b->next)
585 x++;
586 return x;
587 }
588
589 /**********************************************************************
590 * divisible_blob
591 *
592 * Returns true if the blob contains multiple outlines than can be
593 * separated using divide_blobs. Sets the location to be used in the
594 * call to divide_blobs.
595 **********************************************************************/
596 bool divisible_blob(TBLOB *blob, bool italic_blob, TPOINT* location) {
597 if (blob->outlines == NULL || blob->outlines->next == NULL)
598 return false; // Need at least 2 outlines for it to be possible.
599 int max_gap = 0;
600 TPOINT vertical = italic_blob ? kDivisibleVerticalItalic
601 : kDivisibleVerticalUpright;
602 for (TESSLINE* outline1 = blob->outlines; outline1 != NULL;
603 outline1 = outline1->next) {
604 if (outline1->is_hole)
605 continue; // Holes do not count as separable.
606 TPOINT mid_pt1(
607 static_cast<inT16>((outline1->topleft.x + outline1->botright.x) / 2),
608 static_cast<inT16>((outline1->topleft.y + outline1->botright.y) / 2));
609 int mid_prod1 = CROSS(mid_pt1, vertical);
610 int min_prod1, max_prod1;
611 outline1->MinMaxCrossProduct(vertical, &min_prod1, &max_prod1);
612 for (TESSLINE* outline2 = outline1->next; outline2 != NULL;
613 outline2 = outline2->next) {
614 if (outline2->is_hole)
615 continue; // Holes do not count as separable.
616 TPOINT mid_pt2(
617 static_cast<inT16>((outline2->topleft.x + outline2->botright.x) / 2),
618 static_cast<inT16>((outline2->topleft.y + outline2->botright.y) / 2));
619 int mid_prod2 = CROSS(mid_pt2, vertical);
620 int min_prod2, max_prod2;
621 outline2->MinMaxCrossProduct(vertical, &min_prod2, &max_prod2);
622 int mid_gap = abs(mid_prod2 - mid_prod1);
623 int overlap = MIN(max_prod1, max_prod2) - MAX(min_prod1, min_prod2);
624 if (mid_gap - overlap / 4 > max_gap) {
625 max_gap = mid_gap - overlap / 4;
626 *location = mid_pt1;
627 *location += mid_pt2;
628 *location /= 2;
629 }
630 }
631 }
632 // Use the y component of the vertical vector as an approximation to its
633 // length.
634 return max_gap > vertical.y;
635 }
636
637 /**********************************************************************
638 * divide_blobs
639 *
640 * Create two blobs by grouping the outlines in the appropriate blob.
641 * The outlines that are beyond the location point are moved to the
642 * other blob. The ones whose x location is less than that point are
643 * retained in the original blob.
644 **********************************************************************/
645 void divide_blobs(TBLOB *blob, TBLOB *other_blob, bool italic_blob,
646 const TPOINT& location) {
647 TPOINT vertical = italic_blob ? kDivisibleVerticalItalic
648 : kDivisibleVerticalUpright;
649 TESSLINE *outline1 = NULL;
650 TESSLINE *outline2 = NULL;
651
652 TESSLINE *outline = blob->outlines;
653 blob->outlines = NULL;
654 int location_prod = CROSS(location, vertical);
655
656 while (outline != NULL) {
657 TPOINT mid_pt(
658 static_cast<inT16>((outline->topleft.x + outline->botright.x) / 2),
659 static_cast<inT16>((outline->topleft.y + outline->botright.y) / 2));
660 int mid_prod = CROSS(mid_pt, vertical);
661 if (mid_prod < location_prod) {
662 // Outline is in left blob.
663 if (outline1)
664 outline1->next = outline;
665 else
666 blob->outlines = outline;
667 outline1 = outline;
668 } else {
669 // Outline is in right blob.
670 if (outline2)
671 outline2->next = outline;
672 else
673 other_blob->outlines = outline;
674 outline2 = outline;
675 }
676 outline = outline->next;
677 }
678
679 if (outline1)
680 outline1->next = NULL;
681 if (outline2)
682 outline2->next = NULL;
683 }