1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 -
4 - Redistribution and use in source and binary forms, with or without
5 - modification, are permitted provided that the following conditions
6 - are met:
7 - 1. Redistributions of source code must retain the above copyright
8 - notice, this list of conditions and the following disclaimer.
9 - 2. Redistributions in binary form must reproduce the above
10 - copyright notice, this list of conditions and the following
11 - disclaimer in the documentation and/or other materials
12 - provided with the distribution.
13 -
14 - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18 - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23 - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 *====================================================================*/
26
27 /*!
28 * \file boxfunc1.c
29 * <pre>
30 *
31 * Box geometry
32 * l_int32 boxContains()
33 * l_int32 boxIntersects()
34 * BOXA *boxaContainedInBox()
35 * l_int32 boxaContainedInBoxCount()
36 * l_int32 boxaContainedInBoxa()
37 * BOXA *boxaIntersectsBox()
38 * l_int32 boxaIntersectsBoxCount()
39 * BOXA *boxaClipToBox()
40 * BOXA *boxaCombineOverlaps()
41 * l_int32 boxaCombineOverlapsInPair()
42 * BOX *boxOverlapRegion()
43 * BOX *boxBoundingRegion()
44 * l_int32 boxOverlapFraction()
45 * l_int32 boxOverlapArea()
46 * BOXA *boxaHandleOverlaps()
47 * l_int32 boxSeparationDistance()
48 * l_int32 boxCompareSize()
49 * l_int32 boxContainsPt()
50 * BOX *boxaGetNearestToPt()
51 * BOX *boxaGetNearestToLine()
52 * l_int32 boxaFindNearestBoxes()
53 * l_int32 boxaGetNearestByDirection()
54 * static l_int32 boxHasOverlapInXorY()
55 * static l_int32 boxGetDistanceInXorY()
56 * l_int32 boxIntersectByLine()
57 * l_int32 boxGetCenter()
58 * BOX *boxClipToRectangle()
59 * l_int32 boxClipToRectangleParams()
60 * BOX *boxRelocateOneSide()
61 * BOXA *boxaAdjustSides()
62 * BOX *boxAdjustSides()
63 * BOXA *boxaSetSide()
64 * BOXA *boxaAdjustWidthToTarget()
65 * BOXA *boxaAdjustHeightToTarget()
66 * l_int32 boxEqual()
67 * l_int32 boxaEqual()
68 * l_int32 boxSimilar()
69 * l_int32 boxaSimilar()
70 *
71 * Boxa combine and split
72 * l_int32 boxaJoin()
73 * l_int32 boxaaJoin()
74 * l_int32 boxaSplitEvenOdd()
75 * BOXA *boxaMergeEvenOdd()
76 * </pre>
77 */
78
79 #include "allheaders.h"
80
81 static l_int32 boxHasOverlapInXorY(l_int32 c1, l_int32 s1, l_int32 c2,
82 l_int32 s2);
83 static l_int32 boxGetDistanceInXorY(l_int32 c1, l_int32 s1, l_int32 c2,
84 l_int32 s2);
85
86
87 /*---------------------------------------------------------------------*
88 * Box geometry *
89 *---------------------------------------------------------------------*/
90 /*!
91 * \brief boxContains()
92 *
93 * \param[in] box1, box2
94 * \param[out] presult 1 if box2 is entirely contained within
95 * box1, and 0 otherwise
96 * \return 0 if OK, 1 on error
97 */
98 l_int32
boxContains(BOX * box1,BOX * box2,l_int32 * presult)99 boxContains(BOX *box1,
100 BOX *box2,
101 l_int32 *presult)
102 {
103 l_int32 x1, y1, w1, h1, x2, y2, w2, h2;
104
105 PROCNAME("boxContains");
106
107 if (!presult)
108 return ERROR_INT("&result not defined", procName, 1);
109 *presult = 0;
110 if (!box1 || !box2)
111 return ERROR_INT("box1 and box2 not both defined", procName, 1);
112
113 boxGetGeometry(box1, &x1, &y1, &w1, &h1);
114 boxGetGeometry(box2, &x2, &y2, &w2, &h2);
115 if (x1 <= x2 && y1 <= y2 && (x1 + w1 >= x2 + w2) && (y1 + h1 >= y2 + h2))
116 *presult = 1;
117 return 0;
118 }
119
120
121 /*!
122 * \brief boxIntersects()
123 *
124 * \param[in] box1, box2
125 * \param[out] presult 1 if any part of box2 is contained
126 * in box1, and 0 otherwise
127 * \return 0 if OK, 1 on error
128 */
129 l_int32
boxIntersects(BOX * box1,BOX * box2,l_int32 * presult)130 boxIntersects(BOX *box1,
131 BOX *box2,
132 l_int32 *presult)
133 {
134 l_int32 l1, l2, r1, r2, t1, t2, b1, b2, w1, h1, w2, h2;
135
136 PROCNAME("boxIntersects");
137
138 if (!presult)
139 return ERROR_INT("&result not defined", procName, 1);
140 *presult = 0;
141 if (!box1 || !box2)
142 return ERROR_INT("box1 and box2 not both defined", procName, 1);
143
144 boxGetGeometry(box1, &l1, &t1, &w1, &h1);
145 boxGetGeometry(box2, &l2, &t2, &w2, &h2);
146 r1 = l1 + w1 - 1;
147 r2 = l2 + w2 - 1;
148 b1 = t1 + h1 - 1;
149 b2 = t2 + h2 - 1;
150 if (b2 < t1 || b1 < t2 || r1 < l2 || r2 < l1)
151 *presult = 0;
152 else
153 *presult = 1;
154 return 0;
155 }
156
157
158 /*!
159 * \brief boxaContainedInBox()
160 *
161 * \param[in] boxas
162 * \param[in] box for containment
163 * \return boxad boxa with all boxes in boxas that are
164 * entirely contained in box, or NULL on error
165 *
166 * <pre>
167 * Notes:
168 * (1) All boxes in boxa that are entirely outside box are removed.
169 * </pre>
170 */
171 BOXA *
boxaContainedInBox(BOXA * boxas,BOX * box)172 boxaContainedInBox(BOXA *boxas,
173 BOX *box)
174 {
175 l_int32 i, n, val;
176 BOX *boxt;
177 BOXA *boxad;
178
179 PROCNAME("boxaContainedInBox");
180
181 if (!boxas)
182 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
183 if (!box)
184 return (BOXA *)ERROR_PTR("box not defined", procName, NULL);
185 if ((n = boxaGetCount(boxas)) == 0)
186 return boxaCreate(1); /* empty */
187
188 boxad = boxaCreate(0);
189 for (i = 0; i < n; i++) {
190 boxt = boxaGetBox(boxas, i, L_CLONE);
191 boxContains(box, boxt, &val);
192 if (val == 1)
193 boxaAddBox(boxad, boxt, L_COPY);
194 boxDestroy(&boxt); /* destroy the clone */
195 }
196
197 return boxad;
198 }
199
200
201 /*!
202 * \brief boxaContainedInBoxCount()
203 *
204 * \param[in] boxa
205 * \param[in] box for selecting contained boxes in %boxa
206 * \param[out] pcount number of boxes intersecting the box
207 * \return 0 if OK, 1 on error
208 */
209 l_int32
boxaContainedInBoxCount(BOXA * boxa,BOX * box,l_int32 * pcount)210 boxaContainedInBoxCount(BOXA *boxa,
211 BOX *box,
212 l_int32 *pcount)
213 {
214 l_int32 i, n, val;
215 BOX *box1;
216
217 PROCNAME("boxaContainedInBoxCount");
218
219 if (!pcount)
220 return ERROR_INT("&count not defined", procName, 1);
221 *pcount = 0;
222 if (!boxa)
223 return ERROR_INT("boxa not defined", procName, 1);
224 if (!box)
225 return ERROR_INT("box not defined", procName, 1);
226 if ((n = boxaGetCount(boxa)) == 0)
227 return 0;
228
229 for (i = 0; i < n; i++) {
230 box1 = boxaGetBox(boxa, i, L_CLONE);
231 boxContains(box, box1, &val);
232 if (val == 1)
233 (*pcount)++;
234 boxDestroy(&box1);
235 }
236 return 0;
237 }
238
239
240 /*!
241 * \brief boxaContainedInBoxa()
242 *
243 * \param[in] boxa1, boxa2
244 * \param[out] pcontained 1 if every box in boxa2 is contained in
245 * some box in boxa1; 0 otherwise
246 * \return 0 if OK, 1 on error
247 */
248 l_int32
boxaContainedInBoxa(BOXA * boxa1,BOXA * boxa2,l_int32 * pcontained)249 boxaContainedInBoxa(BOXA *boxa1,
250 BOXA *boxa2,
251 l_int32 *pcontained)
252 {
253 l_int32 i, j, n1, n2, cont, result;
254 BOX *box1, *box2;
255
256 PROCNAME("boxaContainedInBoxa");
257
258 if (!pcontained)
259 return ERROR_INT("&contained not defined", procName, 1);
260 *pcontained = 0;
261 if (!boxa1 || !boxa2)
262 return ERROR_INT("boxa1 and boxa2 not both defined", procName, 1);
263
264 n1 = boxaGetCount(boxa1);
265 n2 = boxaGetCount(boxa2);
266 for (i = 0; i < n2; i++) {
267 box2 = boxaGetBox(boxa2, i, L_CLONE);
268 cont = 0;
269 for (j = 0; j < n1; j++) {
270 box1 = boxaGetBox(boxa1, j, L_CLONE);
271 boxContains(box1, box2, &result);
272 boxDestroy(&box1);
273 if (result) {
274 cont = 1;
275 break;
276 }
277 }
278 boxDestroy(&box2);
279 if (!cont) return 0;
280 }
281
282 *pcontained = 1;
283 return 0;
284 }
285
286
287 /*!
288 * \brief boxaIntersectsBox()
289 *
290 * \param[in] boxas
291 * \param[in] box for intersecting
292 * \return boxad boxa with all boxes in boxas that intersect box,
293 * or NULL on error
294 *
295 * <pre>
296 * Notes:
297 * (1) All boxes in boxa that intersect with box (i.e., are completely
298 * or partially contained in box) are retained.
299 * </pre>
300 */
301 BOXA *
boxaIntersectsBox(BOXA * boxas,BOX * box)302 boxaIntersectsBox(BOXA *boxas,
303 BOX *box)
304 {
305 l_int32 i, n, val;
306 BOX *boxt;
307 BOXA *boxad;
308
309 PROCNAME("boxaIntersectsBox");
310
311 if (!boxas)
312 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
313 if (!box)
314 return (BOXA *)ERROR_PTR("box not defined", procName, NULL);
315 if ((n = boxaGetCount(boxas)) == 0)
316 return boxaCreate(1); /* empty */
317
318 boxad = boxaCreate(0);
319 for (i = 0; i < n; i++) {
320 boxt = boxaGetBox(boxas, i, L_CLONE);
321 boxIntersects(box, boxt, &val);
322 if (val == 1)
323 boxaAddBox(boxad, boxt, L_COPY);
324 boxDestroy(&boxt); /* destroy the clone */
325 }
326
327 return boxad;
328 }
329
330
331 /*!
332 * \brief boxaIntersectsBoxCount()
333 *
334 * \param[in] boxa
335 * \param[in] box for selecting intersecting boxes in %boxa
336 * \param[out] pcount number of boxes intersecting the box
337 * \return 0 if OK, 1 on error
338 */
339 l_int32
boxaIntersectsBoxCount(BOXA * boxa,BOX * box,l_int32 * pcount)340 boxaIntersectsBoxCount(BOXA *boxa,
341 BOX *box,
342 l_int32 *pcount)
343 {
344 l_int32 i, n, val;
345 BOX *box1;
346
347 PROCNAME("boxaIntersectsBoxCount");
348
349 if (!pcount)
350 return ERROR_INT("&count not defined", procName, 1);
351 *pcount = 0;
352 if (!boxa)
353 return ERROR_INT("boxa not defined", procName, 1);
354 if (!box)
355 return ERROR_INT("box not defined", procName, 1);
356 if ((n = boxaGetCount(boxa)) == 0)
357 return 0;
358
359 for (i = 0; i < n; i++) {
360 box1 = boxaGetBox(boxa, i, L_CLONE);
361 boxIntersects(box, box1, &val);
362 if (val == 1)
363 (*pcount)++;
364 boxDestroy(&box1);
365 }
366 return 0;
367 }
368
369
370 /*!
371 * \brief boxaClipToBox()
372 *
373 * \param[in] boxas
374 * \param[in] box for clipping
375 * \return boxad boxa with boxes in boxas clipped to box,
376 * or NULL on error
377 *
378 * <pre>
379 * Notes:
380 * (1) All boxes in boxa not intersecting with box are removed, and
381 * the remaining boxes are clipped to box.
382 * </pre>
383 */
384 BOXA *
boxaClipToBox(BOXA * boxas,BOX * box)385 boxaClipToBox(BOXA *boxas,
386 BOX *box)
387 {
388 l_int32 i, n;
389 BOX *boxt, *boxo;
390 BOXA *boxad;
391
392 PROCNAME("boxaClipToBox");
393
394 if (!boxas)
395 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
396 if (!box)
397 return (BOXA *)ERROR_PTR("box not defined", procName, NULL);
398 if ((n = boxaGetCount(boxas)) == 0)
399 return boxaCreate(1); /* empty */
400
401 boxad = boxaCreate(0);
402 for (i = 0; i < n; i++) {
403 boxt = boxaGetBox(boxas, i, L_CLONE);
404 if ((boxo = boxOverlapRegion(box, boxt)) != NULL)
405 boxaAddBox(boxad, boxo, L_INSERT);
406 boxDestroy(&boxt);
407 }
408
409 return boxad;
410 }
411
412
413 /*!
414 * \brief boxaCombineOverlaps()
415 *
416 * \param[in] boxas
417 * \param[in,out] pixadb debug output
418 * \return boxad where each set of boxes in boxas that overlap are
419 * combined into a single bounding box in boxad, or
420 * NULL on error.
421 *
422 * <pre>
423 * Notes:
424 * (1) If there are no overlapping boxes, it simply returns a copy
425 * of %boxas.
426 * (2) Input an empty %pixadb, using pixaCreate(0), for debug output.
427 * The output gives 2 visualizations of the boxes per iteration;
428 * boxes in red before, and added boxes in green after. Note that
429 * all pixels in the red boxes are contained in the green ones.
430 * (3) The alternative method of painting each rectangle and finding
431 * the 4-connected components gives a different result in
432 * general, because two non-overlapping (but touching)
433 * rectangles, when rendered, are 4-connected and will be joined.
434 * (4) A bad case computationally is to have n boxes, none of which
435 * overlap. Then you have one iteration with O(n^2) compares.
436 * This is still faster than painting each rectangle and finding
437 * the bounding boxes of the connected components, even for
438 * thousands of rectangles.
439 * </pre>
440 */
441 BOXA *
boxaCombineOverlaps(BOXA * boxas,PIXA * pixadb)442 boxaCombineOverlaps(BOXA *boxas,
443 PIXA *pixadb)
444 {
445 l_int32 i, j, w, h, n1, n2, overlap, niters;
446 BOX *box1, *box2, *box3;
447 BOXA *boxa1, *boxa2;
448 PIX *pix1;
449
450 PROCNAME("boxaCombineOverlaps");
451
452 if (!boxas)
453 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
454
455 if (pixadb) boxaGetExtent(boxas, &w, &h, NULL);
456
457 boxa1 = boxaCopy(boxas, L_COPY);
458 n1 = boxaGetCount(boxa1);
459 niters = 0;
460 while (1) { /* loop until no change from previous iteration */
461 niters++;
462 if (pixadb) {
463 pix1 = pixCreate(w + 5, h + 5, 32);
464 pixSetAll(pix1);
465 pixRenderBoxaArb(pix1, boxa1, 2, 255, 0, 0);
466 pixaAddPix(pixadb, pix1, L_COPY);
467 }
468
469 /* Combine overlaps for this iteration */
470 for (i = 0; i < n1; i++) {
471 if ((box1 = boxaGetValidBox(boxa1, i, L_COPY)) == NULL)
472 continue;
473 for (j = i + 1; j < n1; j++) {
474 if ((box2 = boxaGetValidBox(boxa1, j, L_COPY)) == NULL)
475 continue;
476 boxIntersects(box1, box2, &overlap);
477 if (overlap) {
478 box3 = boxBoundingRegion(box1, box2);
479 boxaReplaceBox(boxa1, i, box3);
480 boxaReplaceBox(boxa1, j, boxCreate(0, 0, 0, 0));
481 boxDestroy(&box1);
482 box1 = boxCopy(box3);
483 }
484 boxDestroy(&box2);
485 }
486 boxDestroy(&box1);
487 }
488 boxa2 = boxaSaveValid(boxa1, L_COPY);
489 n2 = boxaGetCount(boxa2);
490 boxaDestroy(&boxa1);
491 boxa1 = boxa2;
492 if (n1 == n2) {
493 if (pixadb) pixDestroy(&pix1);
494 break;
495 }
496 n1 = n2;
497 if (pixadb) {
498 pixRenderBoxaArb(pix1, boxa1, 2, 0, 255, 0);
499 pixaAddPix(pixadb, pix1, L_INSERT);
500 }
501 }
502
503 if (pixadb)
504 L_INFO("number of iterations: %d\n", procName, niters);
505 return boxa1;
506 }
507
508
509 /*!
510 * \brief boxaCombineOverlapsInPair()
511 *
512 * \param[in] boxas1 input boxa1
513 * \param[in] boxas2 input boxa2
514 * \param[out] pboxad1 output boxa1
515 * \param[out] pboxad2 output boxa2
516 * \param[in,out] pixadb debug output
517 * \return 0 if OK, 1 on error
518 *
519 * <pre>
520 * Notes:
521 * (1) One of three things happens to each box in %boxa1 and %boxa2:
522 * * it gets absorbed into a larger box that it overlaps with
523 * * it absorbs a smaller (by area) box that it overlaps with
524 * and gets larger, using the bounding region of the 2 boxes
525 * * it is unchanged (including absorbing smaller boxes that
526 * are contained within it).
527 * (2) If all the boxes from one of the input boxa are absorbed, this
528 * returns an empty boxa.
529 * (3) Input an empty %pixadb, using pixaCreate(0), for debug output
530 * (4) This is useful if different operations are to be carried out
531 * on possibly overlapping rectangular regions, and it is desired
532 * to have only one operation on any rectangular region.
533 * </pre>
534 */
535 l_int32
boxaCombineOverlapsInPair(BOXA * boxas1,BOXA * boxas2,BOXA ** pboxad1,BOXA ** pboxad2,PIXA * pixadb)536 boxaCombineOverlapsInPair(BOXA *boxas1,
537 BOXA *boxas2,
538 BOXA **pboxad1,
539 BOXA **pboxad2,
540 PIXA *pixadb)
541 {
542 l_int32 i, j, w, h, w2, h2, n1, n2, n1i, n2i, niters;
543 l_int32 overlap, bigger, area1, area2;
544 BOX *box1, *box2, *box3;
545 BOXA *boxa1, *boxa2, *boxac1, *boxac2;
546 PIX *pix1;
547
548 PROCNAME("boxaCombineOverlapsInPair");
549
550 if (pboxad1) *pboxad1 = NULL;
551 if (pboxad2) *pboxad2 = NULL;
552 if (!boxas1 || !boxas2)
553 return ERROR_INT("boxas1 and boxas2 not both defined", procName, 1);
554 if (!pboxad1 || !pboxad2)
555 return ERROR_INT("&boxad1 and &boxad2 not both defined", procName, 1);
556
557 if (pixadb) {
558 boxaGetExtent(boxas1, &w, &h, NULL);
559 boxaGetExtent(boxas2, &w2, &h2, NULL);
560 w = L_MAX(w, w2);
561 h = L_MAX(h, w2);
562 }
563
564 /* Let the boxa with the largest area have first crack at the other */
565 boxaGetArea(boxas1, &area1);
566 boxaGetArea(boxas2, &area2);
567 if (area1 >= area2) {
568 boxac1 = boxaCopy(boxas1, L_COPY);
569 boxac2 = boxaCopy(boxas2, L_COPY);
570 } else {
571 boxac1 = boxaCopy(boxas2, L_COPY);
572 boxac2 = boxaCopy(boxas1, L_COPY);
573 }
574
575 n1i = boxaGetCount(boxac1);
576 n2i = boxaGetCount(boxac2);
577 niters = 0;
578 while (1) {
579 niters++;
580 if (pixadb) {
581 pix1 = pixCreate(w + 5, h + 5, 32);
582 pixSetAll(pix1);
583 pixRenderBoxaArb(pix1, boxac1, 2, 255, 0, 0);
584 pixRenderBoxaArb(pix1, boxac2, 2, 0, 255, 0);
585 pixaAddPix(pixadb, pix1, L_INSERT);
586 }
587
588 /* First combine boxes in each set */
589 boxa1 = boxaCombineOverlaps(boxac1, NULL);
590 boxa2 = boxaCombineOverlaps(boxac2, NULL);
591
592 /* Now combine boxes between sets */
593 n1 = boxaGetCount(boxa1);
594 n2 = boxaGetCount(boxa2);
595 for (i = 0; i < n1; i++) { /* 1 eats 2 */
596 if ((box1 = boxaGetValidBox(boxa1, i, L_COPY)) == NULL)
597 continue;
598 for (j = 0; j < n2; j++) {
599 if ((box2 = boxaGetValidBox(boxa2, j, L_COPY)) == NULL)
600 continue;
601 boxIntersects(box1, box2, &overlap);
602 boxCompareSize(box1, box2, L_SORT_BY_AREA, &bigger);
603 if (overlap && (bigger == 1)) {
604 box3 = boxBoundingRegion(box1, box2);
605 boxaReplaceBox(boxa1, i, box3);
606 boxaReplaceBox(boxa2, j, boxCreate(0, 0, 0, 0));
607 boxDestroy(&box1);
608 box1 = boxCopy(box3);
609 }
610 boxDestroy(&box2);
611 }
612 boxDestroy(&box1);
613 }
614 for (i = 0; i < n2; i++) { /* 2 eats 1 */
615 if ((box2 = boxaGetValidBox(boxa2, i, L_COPY)) == NULL)
616 continue;
617 for (j = 0; j < n1; j++) {
618 if ((box1 = boxaGetValidBox(boxa1, j, L_COPY)) == NULL)
619 continue;
620 boxIntersects(box1, box2, &overlap);
621 boxCompareSize(box2, box1, L_SORT_BY_AREA, &bigger);
622 if (overlap && (bigger == 1)) {
623 box3 = boxBoundingRegion(box1, box2);
624 boxaReplaceBox(boxa2, i, box3);
625 boxaReplaceBox(boxa1, j, boxCreate(0, 0, 0, 0));
626 boxDestroy(&box2);
627 box2 = boxCopy(box3);
628 }
629 boxDestroy(&box1);
630 }
631 boxDestroy(&box2);
632 }
633 boxaDestroy(&boxac1);
634 boxaDestroy(&boxac2);
635 boxac1 = boxaSaveValid(boxa1, L_COPY); /* remove invalid boxes */
636 boxac2 = boxaSaveValid(boxa2, L_COPY);
637 boxaDestroy(&boxa1);
638 boxaDestroy(&boxa2);
639 n1 = boxaGetCount(boxac1);
640 n2 = boxaGetCount(boxac2);
641 if (n1 == n1i && n2 == n2i) break;
642 n1i = n1;
643 n2i = n2;
644 if (pixadb) {
645 pix1 = pixCreate(w + 5, h + 5, 32);
646 pixSetAll(pix1);
647 pixRenderBoxaArb(pix1, boxac1, 2, 255, 0, 0);
648 pixRenderBoxaArb(pix1, boxac2, 2, 0, 255, 0);
649 pixaAddPix(pixadb, pix1, L_INSERT);
650 }
651 }
652
653 if (pixadb)
654 L_INFO("number of iterations: %d\n", procName, niters);
655 *pboxad1 = boxac1;
656 *pboxad2 = boxac2;
657 return 0;
658 }
659
660
661 /*!
662 * \brief boxOverlapRegion()
663 *
664 * \param[in] box1, box2 two boxes
665 * \return box of overlap region between input boxes,
666 * or NULL if no overlap or on error
667 *
668 * <pre>
669 * Notes:
670 * (1) This is the geometric intersection of the two rectangles.
671 * </pre>
672 */
673 BOX *
boxOverlapRegion(BOX * box1,BOX * box2)674 boxOverlapRegion(BOX *box1,
675 BOX *box2)
676 {
677 l_int32 l1, l2, r1, r2, t1, t2, b1, b2, w1, h1, w2, h2, ld, td, rd, bd;
678
679 PROCNAME("boxOverlapRegion");
680
681 if (!box1)
682 return (BOX *)ERROR_PTR("box1 not defined", procName, NULL);
683 if (!box2)
684 return (BOX *)ERROR_PTR("box2 not defined", procName, NULL);
685
686 boxGetGeometry(box1, &l1, &t1, &w1, &h1);
687 boxGetGeometry(box2, &l2, &t2, &w2, &h2);
688 r1 = l1 + w1 - 1;
689 r2 = l2 + w2 - 1;
690 b1 = t1 + h1 - 1;
691 b2 = t2 + h2 - 1;
692 if (b2 < t1 || b1 < t2 || r1 < l2 || r2 < l1)
693 return NULL;
694
695 ld = L_MAX(l1, l2);
696 td = L_MAX(t1, t2);
697 rd = L_MIN(r1, r2);
698 bd = L_MIN(b1, b2);
699 return boxCreate(ld, td, rd - ld + 1, bd - td + 1);
700 }
701
702
703 /*!
704 * \brief boxBoundingRegion()
705 *
706 * \param[in] box1, box2 two boxes
707 * \return box of bounding region containing the input boxes,
708 * or NULL on error
709 *
710 * <pre>
711 * Notes:
712 * (1) This is the geometric union of the two rectangles.
713 * </pre>
714 */
715 BOX *
boxBoundingRegion(BOX * box1,BOX * box2)716 boxBoundingRegion(BOX *box1,
717 BOX *box2)
718 {
719 l_int32 l1, l2, r1, r2, t1, t2, b1, b2, w1, h1, w2, h2, ld, td, rd, bd;
720
721 PROCNAME("boxBoundingRegion");
722
723 if (!box1)
724 return (BOX *)ERROR_PTR("box1 not defined", procName, NULL);
725 if (!box2)
726 return (BOX *)ERROR_PTR("box2 not defined", procName, NULL);
727
728 boxGetGeometry(box1, &l1, &t1, &w1, &h1);
729 boxGetGeometry(box2, &l2, &t2, &w2, &h2);
730 r1 = l1 + w1 - 1;
731 r2 = l2 + w2 - 1;
732 b1 = t1 + h1 - 1;
733 b2 = t2 + h2 - 1;
734 ld = L_MIN(l1, l2);
735 td = L_MIN(t1, t2);
736 rd = L_MAX(r1, r2);
737 bd = L_MAX(b1, b2);
738 return boxCreate(ld, td, rd - ld + 1, bd - td + 1);
739 }
740
741
742 /*!
743 * \brief boxOverlapFraction()
744 *
745 * \param[in] box1, box2 two boxes
746 * \param[out] pfract the fraction of box2 overlapped by box1
747 * \return 0 if OK, 1 on error.
748 *
749 * <pre>
750 * Notes:
751 * (1) The result depends on the order of the input boxes,
752 * because the overlap is taken as a fraction of box2.
753 * </pre>
754 */
755 l_int32
boxOverlapFraction(BOX * box1,BOX * box2,l_float32 * pfract)756 boxOverlapFraction(BOX *box1,
757 BOX *box2,
758 l_float32 *pfract)
759 {
760 l_int32 w2, h2, w, h;
761 BOX *boxo;
762
763 PROCNAME("boxOverlapFraction");
764
765 if (!pfract)
766 return ERROR_INT("&fract not defined", procName, 1);
767 *pfract = 0.0;
768 if (!box1)
769 return ERROR_INT("box1 not defined", procName, 1);
770 if (!box2)
771 return ERROR_INT("box2 not defined", procName, 1);
772
773 if ((boxo = boxOverlapRegion(box1, box2)) == NULL) /* no overlap */
774 return 0;
775
776 boxGetGeometry(box2, NULL, NULL, &w2, &h2);
777 boxGetGeometry(boxo, NULL, NULL, &w, &h);
778 *pfract = (l_float32)(w * h) / (l_float32)(w2 * h2);
779 boxDestroy(&boxo);
780 return 0;
781 }
782
783
784 /*!
785 * \brief boxOverlapArea()
786 *
787 * \param[in] box1, box2 two boxes
788 * \param[out] parea the number of pixels in the overlap
789 * \return 0 if OK, 1 on error.
790 */
791 l_int32
boxOverlapArea(BOX * box1,BOX * box2,l_int32 * parea)792 boxOverlapArea(BOX *box1,
793 BOX *box2,
794 l_int32 *parea)
795 {
796 l_int32 w, h;
797 BOX *box;
798
799 PROCNAME("boxOverlapArea");
800
801 if (!parea)
802 return ERROR_INT("&area not defined", procName, 1);
803 *parea = 0;
804 if (!box1)
805 return ERROR_INT("box1 not defined", procName, 1);
806 if (!box2)
807 return ERROR_INT("box2 not defined", procName, 1);
808
809 if ((box = boxOverlapRegion(box1, box2)) == NULL) /* no overlap */
810 return 0;
811
812 boxGetGeometry(box, NULL, NULL, &w, &h);
813 *parea = w * h;
814 boxDestroy(&box);
815 return 0;
816 }
817
818
819 /*!
820 * \brief boxaHandleOverlaps()
821 *
822 * \param[in] boxas
823 * \param[in] op L_COMBINE, L_REMOVE_SMALL
824 * \param[in] range > 0, forward distance over which overlaps are checked
825 * \param[in] min_overlap minimum fraction of smaller box required for
826 * overlap to count; 0.0 to ignore
827 * \param[in] max_ratio maximum fraction of small/large areas for
828 * overlap to count; 1.0 to ignore
829 * \param[out] pnamap [optional] combining map
830 * \return boxad, or NULL on error.
831 *
832 * <pre>
833 * Notes:
834 * (1) For all n(n-1)/2 box pairings, if two boxes overlap, either:
835 * (a) op == L_COMBINE: get the bounding region for the two,
836 * replace the larger with the bounding region, and remove
837 * the smaller of the two, or
838 * (b) op == L_REMOVE_SMALL: just remove the smaller.
839 * (2) If boxas is 2D sorted, range can be small, but if it is
840 * not spatially sorted, range should be large to allow all
841 * pairwise comparisons to be made.
842 * (3) The %min_overlap parameter allows ignoring small overlaps.
843 * If %min_overlap == 1.0, only boxes fully contained in larger
844 * boxes can be considered for removal; if %min_overlap == 0.0,
845 * this constraint is ignored.
846 * (4) The %max_ratio parameter allows ignoring overlaps between
847 * boxes that are not too different in size. If %max_ratio == 0.0,
848 * no boxes can be removed; if %max_ratio == 1.0, this constraint
849 * is ignored.
850 * </pre>
851 */
852 BOXA *
boxaHandleOverlaps(BOXA * boxas,l_int32 op,l_int32 range,l_float32 min_overlap,l_float32 max_ratio,NUMA ** pnamap)853 boxaHandleOverlaps(BOXA *boxas,
854 l_int32 op,
855 l_int32 range,
856 l_float32 min_overlap,
857 l_float32 max_ratio,
858 NUMA **pnamap)
859 {
860 l_int32 i, j, n, w, h, area1, area2, val;
861 l_int32 overlap_area;
862 l_float32 overlap_ratio, area_ratio;
863 BOX *box1, *box2, *box3;
864 BOXA *boxat, *boxad;
865 NUMA *namap;
866
867 PROCNAME("boxaHandleOverlaps");
868
869 if (pnamap) *pnamap = NULL;
870 if (!boxas)
871 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
872 if (op != L_COMBINE && op != L_REMOVE_SMALL)
873 return (BOXA *)ERROR_PTR("invalid op", procName, NULL);
874
875 n = boxaGetCount(boxas);
876 if (n == 0)
877 return boxaCreate(1); /* empty */
878 if (range == 0) {
879 L_WARNING("range is 0\n", procName);
880 return boxaCopy(boxas, L_COPY);
881 }
882
883 /* Identify smaller boxes in overlap pairs, and mark to eliminate. */
884 namap = numaMakeConstant(-1, n);
885 for (i = 0; i < n; i++) {
886 box1 = boxaGetBox(boxas, i, L_CLONE);
887 boxGetGeometry(box1, NULL, NULL, &w, &h);
888 area1 = w * h;
889 if (area1 == 0) {
890 boxDestroy(&box1);
891 continue;
892 }
893 for (j = i + 1; j < i + 1 + range && j < n; j++) {
894 box2 = boxaGetBox(boxas, j, L_CLONE);
895 boxOverlapArea(box1, box2, &overlap_area);
896 if (overlap_area > 0) {
897 boxGetGeometry(box2, NULL, NULL, &w, &h);
898 area2 = w * h;
899 if (area2 == 0) {
900 /* do nothing */
901 } else if (area1 >= area2) {
902 overlap_ratio = (l_float32)overlap_area / (l_float32)area2;
903 area_ratio = (l_float32)area2 / (l_float32)area1;
904 if (overlap_ratio >= min_overlap &&
905 area_ratio <= max_ratio) {
906 numaSetValue(namap, j, i);
907 }
908 } else {
909 overlap_ratio = (l_float32)overlap_area / (l_float32)area1;
910 area_ratio = (l_float32)area1 / (l_float32)area2;
911 if (overlap_ratio >= min_overlap &&
912 area_ratio <= max_ratio) {
913 numaSetValue(namap, i, j);
914 }
915 }
916 }
917 boxDestroy(&box2);
918 }
919 boxDestroy(&box1);
920 }
921
922 boxat = boxaCopy(boxas, L_COPY);
923 if (op == L_COMBINE) {
924 /* Resize the larger of the pair to the bounding region */
925 for (i = 0; i < n; i++) {
926 numaGetIValue(namap, i, &val);
927 if (val >= 0) {
928 box1 = boxaGetBox(boxas, i, L_CLONE); /* smaller */
929 box2 = boxaGetBox(boxas, val, L_CLONE); /* larger */
930 box3 = boxBoundingRegion(box1, box2);
931 boxaReplaceBox(boxat, val, box3);
932 boxDestroy(&box1);
933 boxDestroy(&box2);
934 }
935 }
936 }
937
938 /* Remove the smaller of the pairs */
939 boxad = boxaCreate(n);
940 for (i = 0; i < n; i++) {
941 numaGetIValue(namap, i, &val);
942 if (val == -1) {
943 box1 = boxaGetBox(boxat, i, L_COPY);
944 boxaAddBox(boxad, box1, L_INSERT);
945 }
946 }
947 boxaDestroy(&boxat);
948 if (pnamap)
949 *pnamap = namap;
950 else
951 numaDestroy(&namap);
952 return boxad;
953 }
954
955
956 /*!
957 * \brief boxSeparationDistance()
958 *
959 * \param[in] box1, box2 two boxes, in any order
960 * \param[out] ph_sep [optional] horizontal separation
961 * \param[out] pv_sep [optional] vertical separation
962 * \return 0 if OK, 1 on error
963 *
964 * <pre>
965 * Notes:
966 * (1) This measures horizontal and vertical separation of the
967 * two boxes. If the boxes are touching but have no pixels
968 * in common, the separation is 0. If the boxes overlap by
969 * a distance d, the returned separation is -d.
970 * </pre>
971 */
972 l_int32
boxSeparationDistance(BOX * box1,BOX * box2,l_int32 * ph_sep,l_int32 * pv_sep)973 boxSeparationDistance(BOX *box1,
974 BOX *box2,
975 l_int32 *ph_sep,
976 l_int32 *pv_sep)
977 {
978 l_int32 l1, t1, w1, h1, r1, b1, l2, t2, w2, h2, r2, b2;
979
980 PROCNAME("boxSeparationDistance");
981
982 if (!ph_sep && !pv_sep)
983 return ERROR_INT("nothing to do", procName, 1);
984 if (ph_sep) *ph_sep = 0;
985 if (pv_sep) *pv_sep = 0;
986 if (!box1 || !box2)
987 return ERROR_INT("box1 and box2 not both defined", procName, 1);
988
989 if (ph_sep) {
990 boxGetGeometry(box1, &l1, NULL, &w1, NULL);
991 boxGetGeometry(box2, &l2, NULL, &w2, NULL);
992 r1 = l1 + w1; /* 1 pixel to the right of box 1 */
993 r2 = l2 + w2;
994 if (l2 >= l1)
995 *ph_sep = l2 - r1;
996 else
997 *ph_sep = l1 - r2;
998 }
999 if (pv_sep) {
1000 boxGetGeometry(box1, NULL, &t1, NULL, &h1);
1001 boxGetGeometry(box2, NULL, &t2, NULL, &h2);
1002 b1 = t1 + h1; /* 1 pixel below box 1 */
1003 b2 = t2 + h2;
1004 if (t2 >= t1)
1005 *pv_sep = t2 - b1;
1006 else
1007 *pv_sep = t1 - b2;
1008 }
1009 return 0;
1010 }
1011
1012
1013 /*!
1014 * \brief boxCompareSize()
1015 *
1016 * \param[in] box1, box2
1017 * \param[in] type L_SORT_BY_WIDTH, L_SORT_BY_HEIGHT,
1018 * L_SORT_BY_MAX_DIMENSION, L_SORT_BY_PERIMETER,
1019 * L_SORT_BY_AREA,
1020 * \param[out] prel 1 if box1 > box2, 0 if the same, -1 if box1 < box2
1021 * \return 0 if OK, 1 on error
1022 *
1023 * <pre>
1024 * Notes:
1025 * (1) We're re-using the SORT enum for these comparisons.
1026 * </pre>
1027 */
1028 l_int32
boxCompareSize(BOX * box1,BOX * box2,l_int32 type,l_int32 * prel)1029 boxCompareSize(BOX *box1,
1030 BOX *box2,
1031 l_int32 type,
1032 l_int32 *prel)
1033 {
1034 l_int32 w1, h1, w2, h2, size1, size2;
1035
1036 PROCNAME("boxCompareSize");
1037
1038 if (!prel)
1039 return ERROR_INT("&rel not defined", procName, 1);
1040 *prel = 0;
1041 if (!box1 || !box2)
1042 return ERROR_INT("box1 and box2 not both defined", procName, 1);
1043 if (type != L_SORT_BY_WIDTH && type != L_SORT_BY_HEIGHT &&
1044 type != L_SORT_BY_MAX_DIMENSION && type != L_SORT_BY_PERIMETER &&
1045 type != L_SORT_BY_AREA)
1046 return ERROR_INT("invalid compare type", procName, 1);
1047
1048 boxGetGeometry(box1, NULL, NULL, &w1, &h1);
1049 boxGetGeometry(box2, NULL, NULL, &w2, &h2);
1050 if (type == L_SORT_BY_WIDTH) {
1051 *prel = (w1 > w2) ? 1 : ((w1 == w2) ? 0 : -1);
1052 } else if (type == L_SORT_BY_HEIGHT) {
1053 *prel = (h1 > h2) ? 1 : ((h1 == h2) ? 0 : -1);
1054 } else if (type == L_SORT_BY_MAX_DIMENSION) {
1055 size1 = L_MAX(w1, h1);
1056 size2 = L_MAX(w2, h2);
1057 *prel = (size1 > size2) ? 1 : ((size1 == size2) ? 0 : -1);
1058 } else if (type == L_SORT_BY_PERIMETER) {
1059 size1 = w1 + h1;
1060 size2 = w2 + h2;
1061 *prel = (size1 > size2) ? 1 : ((size1 == size2) ? 0 : -1);
1062 } else if (type == L_SORT_BY_AREA) {
1063 size1 = w1 * h1;
1064 size2 = w2 * h2;
1065 *prel = (size1 > size2) ? 1 : ((size1 == size2) ? 0 : -1);
1066 }
1067 return 0;
1068 }
1069
1070
1071 /*!
1072 * \brief boxContainsPt()
1073 *
1074 * \param[in] box
1075 * \param[in] x, y a point
1076 * \param[out] pcontains 1 if box contains point; 0 otherwise
1077 * \return 0 if OK, 1 on error.
1078 */
1079 l_int32
boxContainsPt(BOX * box,l_float32 x,l_float32 y,l_int32 * pcontains)1080 boxContainsPt(BOX *box,
1081 l_float32 x,
1082 l_float32 y,
1083 l_int32 *pcontains)
1084 {
1085 l_int32 bx, by, bw, bh;
1086
1087 PROCNAME("boxContainsPt");
1088
1089 if (!pcontains)
1090 return ERROR_INT("&contains not defined", procName, 1);
1091 *pcontains = 0;
1092 if (!box)
1093 return ERROR_INT("&box not defined", procName, 1);
1094 boxGetGeometry(box, &bx, &by, &bw, &bh);
1095 if (x >= bx && x < bx + bw && y >= by && y < by + bh)
1096 *pcontains = 1;
1097 return 0;
1098 }
1099
1100
1101 /*!
1102 * \brief boxaGetNearestToPt()
1103 *
1104 * \param[in] boxa
1105 * \param[in] x, y point
1106 * \return box with centroid closest to the given point [x,y],
1107 * or NULL if no boxes in boxa
1108 *
1109 * <pre>
1110 * Notes:
1111 * (1) Uses euclidean distance between centroid and point.
1112 * </pre>
1113 */
1114 BOX *
boxaGetNearestToPt(BOXA * boxa,l_int32 x,l_int32 y)1115 boxaGetNearestToPt(BOXA *boxa,
1116 l_int32 x,
1117 l_int32 y)
1118 {
1119 l_int32 i, n, minindex;
1120 l_float32 delx, dely, dist, mindist, cx, cy;
1121 BOX *box;
1122
1123 PROCNAME("boxaGetNearestToPt");
1124
1125 if (!boxa)
1126 return (BOX *)ERROR_PTR("boxa not defined", procName, NULL);
1127 if ((n = boxaGetCount(boxa)) == 0)
1128 return (BOX *)ERROR_PTR("n = 0", procName, NULL);
1129
1130 mindist = 1000000000.;
1131 minindex = 0;
1132 for (i = 0; i < n; i++) {
1133 box = boxaGetBox(boxa, i, L_CLONE);
1134 boxGetCenter(box, &cx, &cy);
1135 delx = (l_float32)(cx - x);
1136 dely = (l_float32)(cy - y);
1137 dist = delx * delx + dely * dely;
1138 if (dist < mindist) {
1139 minindex = i;
1140 mindist = dist;
1141 }
1142 boxDestroy(&box);
1143 }
1144
1145 return boxaGetBox(boxa, minindex, L_COPY);
1146 }
1147
1148
1149 /*!
1150 * \brief boxaGetNearestToLine()
1151 *
1152 * \param[in] boxa
1153 * \param[in] x, y (y = -1 for vertical line; x = -1 for horiz line)
1154 * \return box with centroid closest to the given line,
1155 * or NULL if no boxes in boxa
1156 *
1157 * <pre>
1158 * Notes:
1159 * (1) For a horizontal line at some value y, get the minimum of the
1160 * distance |yc - y| from the box centroid yc value to y;
1161 * likewise minimize |xc - x| for a vertical line at x.
1162 * (2) Input y < 0, x >= 0 to indicate a vertical line at x, and
1163 * x < 0, y >= 0 for a horizontal line at y.
1164 * </pre>
1165 */
1166 BOX *
boxaGetNearestToLine(BOXA * boxa,l_int32 x,l_int32 y)1167 boxaGetNearestToLine(BOXA *boxa,
1168 l_int32 x,
1169 l_int32 y)
1170 {
1171 l_int32 i, n, minindex;
1172 l_float32 dist, mindist, cx, cy;
1173 BOX *box;
1174
1175 PROCNAME("boxaGetNearestToLine");
1176
1177 if (!boxa)
1178 return (BOX *)ERROR_PTR("boxa not defined", procName, NULL);
1179 if ((n = boxaGetCount(boxa)) == 0)
1180 return (BOX *)ERROR_PTR("n = 0", procName, NULL);
1181 if (y >= 0 && x >= 0)
1182 return (BOX *)ERROR_PTR("either x or y must be < 0", procName, NULL);
1183 if (y < 0 && x < 0)
1184 return (BOX *)ERROR_PTR("either x or y must be >= 0", procName, NULL);
1185
1186 mindist = 1000000000.;
1187 minindex = 0;
1188 for (i = 0; i < n; i++) {
1189 box = boxaGetBox(boxa, i, L_CLONE);
1190 boxGetCenter(box, &cx, &cy);
1191 if (x >= 0)
1192 dist = L_ABS(cx - (l_float32)x);
1193 else /* y >= 0 */
1194 dist = L_ABS(cy - (l_float32)y);
1195 if (dist < mindist) {
1196 minindex = i;
1197 mindist = dist;
1198 }
1199 boxDestroy(&box);
1200 }
1201
1202 return boxaGetBox(boxa, minindex, L_COPY);
1203 }
1204
1205
1206 /*!
1207 * \brief boxaFindNearestBoxes()
1208 *
1209 * \param[in] boxa either unsorted, or 2D sorted in LR/TB scan order
1210 * \param[in] dist_select L_NON_NEGATIVE, L_ALL
1211 * \param[in] range search distance from box i; use 0 to search
1212 * entire boxa (e.g., if it's not 2D sorted)
1213 * \param[out] pnaaindex for each box in %boxa, contains a numa of 4
1214 * box indices (per direction) of the nearest box
1215 * \param[out] pnaadist for each box in %boxa, this contains a numa
1216 * \return 0 if OK, 1 on error
1217 * <pre>
1218 * Notes:
1219 * (1) See boxaGetNearestByDirection() for usage of %dist_select
1220 * and %range.
1221 * </pre>
1222 */
1223 l_int32
boxaFindNearestBoxes(BOXA * boxa,l_int32 dist_select,l_int32 range,NUMAA ** pnaaindex,NUMAA ** pnaadist)1224 boxaFindNearestBoxes(BOXA *boxa,
1225 l_int32 dist_select,
1226 l_int32 range,
1227 NUMAA **pnaaindex,
1228 NUMAA **pnaadist)
1229 {
1230 l_int32 i, n, index, dist;
1231 NUMA *nai, *nad;
1232 NUMAA *naai, *naad;
1233
1234 PROCNAME("boxaFindNearestBoxes");
1235
1236 if (pnaaindex) *pnaaindex = NULL;
1237 if (pnaadist) *pnaadist = NULL;
1238 if (!pnaaindex)
1239 return ERROR_INT("&naaindex not defined", procName, 1);
1240 if (!pnaadist)
1241 return ERROR_INT("&naadist not defined", procName, 1);
1242 if (!boxa)
1243 return ERROR_INT("boxa not defined", procName, 1);
1244
1245 n = boxaGetCount(boxa);
1246 naai = numaaCreate(n);
1247 naad = numaaCreate(n);
1248 *pnaaindex = naai;
1249 *pnaadist = naad;
1250 for (i = 0; i < n; i++) {
1251 nai = numaCreate(4);
1252 nad = numaCreate(4);
1253 boxaGetNearestByDirection(boxa, i, L_FROM_LEFT, dist_select,
1254 range, &index, &dist);
1255 numaAddNumber(nai, index);
1256 numaAddNumber(nad, dist);
1257 boxaGetNearestByDirection(boxa, i, L_FROM_RIGHT, dist_select,
1258 range, &index, &dist);
1259 numaAddNumber(nai, index);
1260 numaAddNumber(nad, dist);
1261 boxaGetNearestByDirection(boxa, i, L_FROM_TOP, dist_select,
1262 range, &index, &dist);
1263 numaAddNumber(nai, index);
1264 numaAddNumber(nad, dist);
1265 boxaGetNearestByDirection(boxa, i, L_FROM_BOT, dist_select,
1266 range, &index, &dist);
1267 numaAddNumber(nai, index);
1268 numaAddNumber(nad, dist);
1269 numaaAddNuma(naai, nai, L_INSERT);
1270 numaaAddNuma(naad, nad, L_INSERT);
1271 }
1272 return 0;
1273 }
1274
1275
1276 /*!
1277 * \brief boxaGetNearestByDirection()
1278 *
1279 * \param[in] boxa either unsorted, or 2D sorted in LR/TB scan order
1280 * \param[in] i box we test against
1281 * \param[in] dir direction to look: L_FROM_LEFT, L_FROM_RIGHT,
1282 * L_FROM_TOP, L_FROM_BOT
1283 * \param[in] dist_select L_NON_NEGATIVE, L_ALL
1284 * \param[in] range search distance from box i; use 0 to search
1285 * entire boxa (e.g., if it's not 2D sorted)
1286 * \param[out] pindex index in boxa of nearest box with overlapping
1287 * coordinates in the indicated direction;
1288 * -1 if there is no box
1289 * \param[out] pdist distance of the nearest box in the indicated
1290 * direction; 100000 if no box
1291 * \return 0 if OK, 1 on error
1292 *
1293 * <pre>
1294 * Notes:
1295 * (1) For efficiency, use a LR/TD sorted %boxa, which can be
1296 * made by flattening a 2D sorted boxaa. In that case,
1297 * %range can be some positive integer like 50.
1298 * (2) If boxes overlap, the distance will be < 0. Use %dist_select
1299 * to determine if these should count or not. If L_ALL, then
1300 * one box will match as the nearest to another in 2 or more
1301 * directions.
1302 * </pre>
1303 */
1304 l_int32
boxaGetNearestByDirection(BOXA * boxa,l_int32 i,l_int32 dir,l_int32 dist_select,l_int32 range,l_int32 * pindex,l_int32 * pdist)1305 boxaGetNearestByDirection(BOXA *boxa,
1306 l_int32 i,
1307 l_int32 dir,
1308 l_int32 dist_select,
1309 l_int32 range,
1310 l_int32 *pindex,
1311 l_int32 *pdist)
1312 {
1313 l_int32 j, jmin, jmax, n, mindist, dist, index;
1314 l_int32 x, y, w, h, bx, by, bw, bh;
1315
1316 PROCNAME("boxaGetNearestByDirection");
1317
1318 if (pindex) *pindex = -1;
1319 if (pdist) *pdist = 100000;
1320 if (!pindex)
1321 return ERROR_INT("&index not defined", procName, 1);
1322 if (!pdist)
1323 return ERROR_INT("&dist not defined", procName, 1);
1324 if (!boxa)
1325 return ERROR_INT("boxa not defined", procName, 1);
1326 if (dir != L_FROM_LEFT && dir != L_FROM_RIGHT &&
1327 dir != L_FROM_TOP && dir != L_FROM_BOT)
1328 return ERROR_INT("invalid dir", procName, 1);
1329 if (dist_select != L_NON_NEGATIVE && dist_select != L_ALL)
1330 return ERROR_INT("invalid dist_select", procName, 1);
1331 n = boxaGetCount(boxa);
1332 if (i < 0 || i >= n)
1333 return ERROR_INT("invalid box index", procName, 1);
1334
1335 jmin = (range <= 0) ? 0 : L_MAX(0, i - range);
1336 jmax = (range <= 0) ? n - 1 : L_MIN(n -1, i + range);
1337 boxaGetBoxGeometry(boxa, i, &x, &y, &w, &h);
1338 mindist = 100000;
1339 index = -1;
1340 if (dir == L_FROM_LEFT || dir == L_FROM_RIGHT) {
1341 for (j = jmin; j <= jmax; j++) {
1342 if (j == i) continue;
1343 boxaGetBoxGeometry(boxa, j, &bx, &by, &bw, &bh);
1344 if ((bx >= x && dir == L_FROM_LEFT) || /* not to the left */
1345 (x >= bx && dir == L_FROM_RIGHT)) /* not to the right */
1346 continue;
1347 if (boxHasOverlapInXorY(y, h, by, bh) == 1) {
1348 dist = boxGetDistanceInXorY(x, w, bx, bw);
1349 if (dist_select == L_NON_NEGATIVE && dist < 0) continue;
1350 if (dist < mindist) {
1351 mindist = dist;
1352 index = j;
1353 }
1354 }
1355 }
1356 } else if (dir == L_FROM_TOP || dir == L_FROM_BOT) {
1357 for (j = jmin; j <= jmax; j++) {
1358 if (j == i) continue;
1359 boxaGetBoxGeometry(boxa, j, &bx, &by, &bw, &bh);
1360 if ((by >= y && dir == L_FROM_TOP) || /* not above */
1361 (y >= by && dir == L_FROM_BOT)) /* not below */
1362 continue;
1363 if (boxHasOverlapInXorY(x, w, bx, bw) == 1) {
1364 dist = boxGetDistanceInXorY(y, h, by, bh);
1365 if (dist_select == L_NON_NEGATIVE && dist < 0) continue;
1366 if (dist < mindist) {
1367 mindist = dist;
1368 index = j;
1369 }
1370 }
1371 }
1372 }
1373 *pindex = index;
1374 *pdist = mindist;
1375 return 0;
1376 }
1377
1378
1379 /*!
1380 * \brief boxHasOverlapInXorY()
1381 *
1382 * \param[in] c1 left or top coordinate of box1
1383 * \param[in] s1 width or height of box1
1384 * \param[in] c2 left or top coordinate of box2
1385 * \param[in] s2 width or height of box2
1386 * \return 0 if no overlap; 1 if any overlap
1387 *
1388 * <pre>
1389 * Notes:
1390 * (1) Like boxGetDistanceInXorY(), this is used for overlaps both in
1391 * x (which projected vertically) and in y (projected horizontally)
1392 * </pre>
1393 */
1394 static l_int32
boxHasOverlapInXorY(l_int32 c1,l_int32 s1,l_int32 c2,l_int32 s2)1395 boxHasOverlapInXorY(l_int32 c1,
1396 l_int32 s1,
1397 l_int32 c2,
1398 l_int32 s2)
1399 {
1400 l_int32 ovlp;
1401
1402 if (c1 > c2)
1403 ovlp = c2 + s2 - 1 - c1;
1404 else
1405 ovlp = c1 + s1 - 1 - c2;
1406 return (ovlp < 0) ? 0 : 1;
1407 }
1408
1409
1410 /*!
1411 * \brief boxGetDistanceInXorY()
1412 *
1413 * \param[in] c1 left or top coordinate of box1
1414 * \param[in] s1 width or height of box1
1415 * \param[in] c2 left or top coordinate of box2
1416 * \param[in] s2 width or height of box2
1417 * \return distance between them (if < 0, box2 overlaps box1 in the
1418 * dimension considered)
1419 */
1420 static l_int32
boxGetDistanceInXorY(l_int32 c1,l_int32 s1,l_int32 c2,l_int32 s2)1421 boxGetDistanceInXorY(l_int32 c1,
1422 l_int32 s1,
1423 l_int32 c2,
1424 l_int32 s2)
1425 {
1426 l_int32 dist;
1427
1428 if (c1 > c2)
1429 dist = c1 - (c2 + s2 - 1);
1430 else
1431 dist = c2 - (c1 + s1 - 1);
1432 return dist;
1433 }
1434
1435
1436 /*!
1437 * \brief boxGetCenter()
1438 *
1439 * \param[in] box
1440 * \param[out] pcx, pcy location of center of box
1441 * \return 0 if OK, 1 on error
1442 */
1443 l_int32
boxGetCenter(BOX * box,l_float32 * pcx,l_float32 * pcy)1444 boxGetCenter(BOX *box,
1445 l_float32 *pcx,
1446 l_float32 *pcy)
1447 {
1448 l_int32 x, y, w, h;
1449
1450 PROCNAME("boxGetCenter");
1451
1452 if (pcx) *pcx = 0;
1453 if (pcy) *pcy = 0;
1454 if (!pcx || !pcy)
1455 return ERROR_INT("&cx, &cy not both defined", procName, 1);
1456 if (!box)
1457 return ERROR_INT("box not defined", procName, 1);
1458 boxGetGeometry(box, &x, &y, &w, &h);
1459 *pcx = (l_float32)(x + 0.5 * w);
1460 *pcy = (l_float32)(y + 0.5 * h);
1461
1462 return 0;
1463 }
1464
1465
1466 /*!
1467 * \brief boxIntersectByLine()
1468 *
1469 * \param[in] box
1470 * \param[in] x, y point that line goes through
1471 * \param[in] slope of line
1472 * \param[out] px1, py1 1st point of intersection with box
1473 * \param[out] px2, py2 2nd point of intersection with box
1474 * \param[out] pn number of points of intersection
1475 * \return 0 if OK, 1 on error
1476 *
1477 * <pre>
1478 * Notes:
1479 * (1) If the intersection is at only one point (a corner), the
1480 * coordinates are returned in (x1, y1).
1481 * (2) Represent a vertical line by one with a large but finite slope.
1482 * </pre>
1483 */
1484 l_int32
boxIntersectByLine(BOX * box,l_int32 x,l_int32 y,l_float32 slope,l_int32 * px1,l_int32 * py1,l_int32 * px2,l_int32 * py2,l_int32 * pn)1485 boxIntersectByLine(BOX *box,
1486 l_int32 x,
1487 l_int32 y,
1488 l_float32 slope,
1489 l_int32 *px1,
1490 l_int32 *py1,
1491 l_int32 *px2,
1492 l_int32 *py2,
1493 l_int32 *pn)
1494 {
1495 l_int32 bx, by, bw, bh, xp, yp, xt, yt, i, n;
1496 l_float32 invslope;
1497 PTA *pta;
1498
1499 PROCNAME("boxIntersectByLine");
1500
1501 if (px1) *px1 = 0;
1502 if (px2) *px2 = 0;
1503 if (py1) *py1 = 0;
1504 if (py2) *py2 = 0;
1505 if (pn) *pn = 0;
1506 if (!px1 || !py1 || !px2 || !py2)
1507 return ERROR_INT("&x1, &y1, &x2, &y2 not all defined", procName, 1);
1508 if (!pn)
1509 return ERROR_INT("&n not defined", procName, 1);
1510 if (!box)
1511 return ERROR_INT("box not defined", procName, 1);
1512 boxGetGeometry(box, &bx, &by, &bw, &bh);
1513
1514 if (slope == 0.0) {
1515 if (y >= by && y < by + bh) {
1516 *py1 = *py2 = y;
1517 *px1 = bx;
1518 *px2 = bx + bw - 1;
1519 }
1520 return 0;
1521 }
1522
1523 if (slope > 1000000.0) {
1524 if (x >= bx && x < bx + bw) {
1525 *px1 = *px2 = x;
1526 *py1 = by;
1527 *py2 = by + bh - 1;
1528 }
1529 return 0;
1530 }
1531
1532 /* Intersection with top and bottom lines of box */
1533 pta = ptaCreate(2);
1534 invslope = 1.0 / slope;
1535 xp = (l_int32)(x + invslope * (y - by));
1536 if (xp >= bx && xp < bx + bw)
1537 ptaAddPt(pta, xp, by);
1538 xp = (l_int32)(x + invslope * (y - by - bh + 1));
1539 if (xp >= bx && xp < bx + bw)
1540 ptaAddPt(pta, xp, by + bh - 1);
1541
1542 /* Intersection with left and right lines of box */
1543 yp = (l_int32)(y + slope * (x - bx));
1544 if (yp >= by && yp < by + bh)
1545 ptaAddPt(pta, bx, yp);
1546 yp = (l_int32)(y + slope * (x - bx - bw + 1));
1547 if (yp >= by && yp < by + bh)
1548 ptaAddPt(pta, bx + bw - 1, yp);
1549
1550 /* There is a maximum of 2 unique points; remove duplicates. */
1551 n = ptaGetCount(pta);
1552 if (n > 0) {
1553 ptaGetIPt(pta, 0, px1, py1); /* accept the first one */
1554 *pn = 1;
1555 }
1556 for (i = 1; i < n; i++) {
1557 ptaGetIPt(pta, i, &xt, &yt);
1558 if ((*px1 != xt) || (*py1 != yt)) {
1559 *px2 = xt;
1560 *py2 = yt;
1561 *pn = 2;
1562 break;
1563 }
1564 }
1565
1566 ptaDestroy(&pta);
1567 return 0;
1568 }
1569
1570
1571 /*!
1572 * \brief boxClipToRectangle()
1573 *
1574 * \param[in] box
1575 * \param[in] wi, hi rectangle representing image
1576 * \return part of box within given rectangle, or NULL on error
1577 * or if box is entirely outside the rectangle
1578 *
1579 * <pre>
1580 * Notes:
1581 * (1) This can be used to clip a rectangle to an image.
1582 * The clipping rectangle is assumed to have a UL corner at (0, 0),
1583 * and a LR corner at (wi - 1, hi - 1).
1584 * </pre>
1585 */
1586 BOX *
boxClipToRectangle(BOX * box,l_int32 wi,l_int32 hi)1587 boxClipToRectangle(BOX *box,
1588 l_int32 wi,
1589 l_int32 hi)
1590 {
1591 BOX *boxd;
1592
1593 PROCNAME("boxClipToRectangle");
1594
1595 if (!box)
1596 return (BOX *)ERROR_PTR("box not defined", procName, NULL);
1597 if (box->x >= wi || box->y >= hi ||
1598 box->x + box->w <= 0 || box->y + box->h <= 0)
1599 return (BOX *)ERROR_PTR("box outside rectangle", procName, NULL);
1600
1601 boxd = boxCopy(box);
1602 if (boxd->x < 0) {
1603 boxd->w += boxd->x;
1604 boxd->x = 0;
1605 }
1606 if (boxd->y < 0) {
1607 boxd->h += boxd->y;
1608 boxd->y = 0;
1609 }
1610 if (boxd->x + boxd->w > wi)
1611 boxd->w = wi - boxd->x;
1612 if (boxd->y + boxd->h > hi)
1613 boxd->h = hi - boxd->y;
1614 return boxd;
1615 }
1616
1617
1618 /*!
1619 * \brief boxClipToRectangleParams()
1620 *
1621 * \param[in] box [optional] requested box; can be null
1622 * \param[in] w, h clipping box size; typ. the size of an image
1623 * \param[out] pxstart start x coordinate
1624 * \param[out] pystart start y coordinate
1625 * \param[out] pxend one pixel beyond clipping box
1626 * \param[out] pyend one pixel beyond clipping box
1627 * \param[out] pbw [optional] clipped width
1628 * \param[out] pbh [optional] clipped height
1629 * \return 0 if OK; 1 on error
1630 *
1631 * <pre>
1632 * Notes:
1633 * (1) The return value should be checked. If it is 1, the
1634 * returned parameter values are bogus.
1635 * (2) This simplifies the selection of pixel locations within
1636 * a given rectangle:
1637 * for (i = ystart; i < yend; i++ {
1638 * ...
1639 * for (j = xstart; j < xend; j++ {
1640 * ....
1641 * </pre>
1642 */
1643 l_int32
boxClipToRectangleParams(BOX * box,l_int32 w,l_int32 h,l_int32 * pxstart,l_int32 * pystart,l_int32 * pxend,l_int32 * pyend,l_int32 * pbw,l_int32 * pbh)1644 boxClipToRectangleParams(BOX *box,
1645 l_int32 w,
1646 l_int32 h,
1647 l_int32 *pxstart,
1648 l_int32 *pystart,
1649 l_int32 *pxend,
1650 l_int32 *pyend,
1651 l_int32 *pbw,
1652 l_int32 *pbh)
1653 {
1654 l_int32 bw, bh;
1655 BOX *boxc;
1656
1657 PROCNAME("boxClipToRectangleParams");
1658
1659 if (pxstart) *pxstart = 0;
1660 if (pystart) *pystart = 0;
1661 if (pxend) *pxend = w;
1662 if (pyend) *pyend = h;
1663 if (pbw) *pbw = w;
1664 if (pbh) *pbh = h;
1665 if (!pxstart || !pystart || !pxend || !pyend)
1666 return ERROR_INT("invalid ptr input", procName, 1);
1667 if (!box) return 0;
1668
1669 if ((boxc = boxClipToRectangle(box, w, h)) == NULL)
1670 return ERROR_INT("box outside image", procName, 1);
1671 boxGetGeometry(boxc, pxstart, pystart, &bw, &bh);
1672 boxDestroy(&boxc);
1673
1674 if (pbw) *pbw = bw;
1675 if (pbh) *pbh = bh;
1676 if (bw == 0 || bh == 0)
1677 return ERROR_INT("invalid clipping box", procName, 1);
1678 *pxend = *pxstart + bw; /* 1 past the end */
1679 *pyend = *pystart + bh; /* 1 past the end */
1680 return 0;
1681 }
1682
1683
1684 /*!
1685 * \brief boxRelocateOneSide()
1686 *
1687 * \param[in] boxd [optional]; this can be null, equal to boxs,
1688 * or different from boxs;
1689 * \param[in] boxs starting box; to have one side relocated
1690 * \param[in] loc new location of the side that is changing
1691 * \param[in] sideflag L_FROM_LEFT, etc., indicating the side that moves
1692 * \return boxd, or NULL on error or if the computed boxd has
1693 * width or height <= 0.
1694 *
1695 * <pre>
1696 * Notes:
1697 * (1) Set boxd == NULL to get new box; boxd == boxs for in-place;
1698 * or otherwise to resize existing boxd.
1699 * (2) For usage, suggest one of these:
1700 * boxd = boxRelocateOneSide(NULL, boxs, ...); // new
1701 * boxRelocateOneSide(boxs, boxs, ...); // in-place
1702 * boxRelocateOneSide(boxd, boxs, ...); // other
1703 * </pre>
1704 */
1705 BOX *
boxRelocateOneSide(BOX * boxd,BOX * boxs,l_int32 loc,l_int32 sideflag)1706 boxRelocateOneSide(BOX *boxd,
1707 BOX *boxs,
1708 l_int32 loc,
1709 l_int32 sideflag)
1710 {
1711 l_int32 x, y, w, h;
1712
1713 PROCNAME("boxRelocateOneSide");
1714
1715 if (!boxs)
1716 return (BOX *)ERROR_PTR("boxs not defined", procName, NULL);
1717 if (!boxd)
1718 boxd = boxCopy(boxs);
1719
1720 boxGetGeometry(boxs, &x, &y, &w, &h);
1721 if (sideflag == L_FROM_LEFT)
1722 boxSetGeometry(boxd, loc, -1, w + x - loc, -1);
1723 else if (sideflag == L_FROM_RIGHT)
1724 boxSetGeometry(boxd, -1, -1, loc - x + 1, -1);
1725 else if (sideflag == L_FROM_TOP)
1726 boxSetGeometry(boxd, -1, loc, -1, h + y - loc);
1727 else if (sideflag == L_FROM_BOT)
1728 boxSetGeometry(boxd, -1, -1, -1, loc - y + 1);
1729 return boxd;
1730 }
1731
1732
1733 /*!
1734 * \brief boxaAdjustSides()
1735 *
1736 * \param[in] boxas
1737 * \param[in] delleft, delright, deltop, delbot changes in location of
1738 * each side for each box
1739 * \return boxad, or NULL on error
1740 *
1741 * <pre>
1742 * Notes:
1743 * (1) New box dimensions are cropped at left and top to x >= 0 and y >= 0.
1744 * (2) If the width or height of a box goes to 0, we generate a box with
1745 * w == 1 and h == 1, as a placeholder.
1746 * (3) See boxAdjustSides().
1747 * </pre>
1748 */
1749 BOXA *
boxaAdjustSides(BOXA * boxas,l_int32 delleft,l_int32 delright,l_int32 deltop,l_int32 delbot)1750 boxaAdjustSides(BOXA *boxas,
1751 l_int32 delleft,
1752 l_int32 delright,
1753 l_int32 deltop,
1754 l_int32 delbot)
1755 {
1756 l_int32 n, i, x, y;
1757 BOX *box1, *box2;
1758 BOXA *boxad;
1759
1760 PROCNAME("boxaAdjustSides");
1761
1762 if (!boxas)
1763 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
1764
1765 n = boxaGetCount(boxas);
1766 boxad = boxaCreate(n);
1767 for (i = 0; i < n; i++) {
1768 box1 = boxaGetBox(boxas, i, L_COPY);
1769 box2 = boxAdjustSides(NULL, box1, delleft, delright, deltop, delbot);
1770 if (!box2) {
1771 boxGetGeometry(box1, &x, &y, NULL, NULL);
1772 box2 = boxCreate(x, y, 1, 1);
1773 }
1774 boxaAddBox(boxad, box2, L_INSERT);
1775 boxDestroy(&box1);
1776 }
1777
1778 return boxad;
1779 }
1780
1781
1782 /*!
1783 * \brief boxAdjustSides()
1784 *
1785 * \param[in] boxd [optional]; this can be null, equal to boxs,
1786 * or different from boxs
1787 * \param[in] boxs starting box; to have sides adjusted
1788 * \param[in] delleft, delright, deltop, delbot changes in location of
1789 * each side
1790 * \return boxd, or NULL on error or if the computed boxd has
1791 * width or height <= 0.
1792 *
1793 * <pre>
1794 * Notes:
1795 * (1) Set boxd == NULL to get new box; boxd == boxs for in-place;
1796 * or otherwise to resize existing boxd.
1797 * (2) For usage, suggest one of these:
1798 * boxd = boxAdjustSides(NULL, boxs, ...); // new
1799 * boxAdjustSides(boxs, boxs, ...); // in-place
1800 * boxAdjustSides(boxd, boxs, ...); // other
1801 * (3) New box dimensions are cropped at left and top to x >= 0 and y >= 0.
1802 * (4) For example, to expand in-place by 20 pixels on each side, use
1803 * boxAdjustSides(box, box, -20, 20, -20, 20);
1804 * </pre>
1805 */
1806 BOX *
boxAdjustSides(BOX * boxd,BOX * boxs,l_int32 delleft,l_int32 delright,l_int32 deltop,l_int32 delbot)1807 boxAdjustSides(BOX *boxd,
1808 BOX *boxs,
1809 l_int32 delleft,
1810 l_int32 delright,
1811 l_int32 deltop,
1812 l_int32 delbot)
1813 {
1814 l_int32 x, y, w, h, xl, xr, yt, yb, wnew, hnew;
1815
1816 PROCNAME("boxAdjustSides");
1817
1818 if (!boxs)
1819 return (BOX *)ERROR_PTR("boxs not defined", procName, NULL);
1820
1821 boxGetGeometry(boxs, &x, &y, &w, &h);
1822 xl = L_MAX(0, x + delleft);
1823 yt = L_MAX(0, y + deltop);
1824 xr = x + w + delright; /* one pixel beyond right edge */
1825 yb = y + h + delbot; /* one pixel below bottom edge */
1826 wnew = xr - xl;
1827 hnew = yb - yt;
1828
1829 if (wnew < 1 || hnew < 1)
1830 return (BOX *)ERROR_PTR("boxd has 0 area", procName, NULL);
1831 if (!boxd)
1832 return boxCreate(xl, yt, wnew, hnew);
1833
1834 boxSetGeometry(boxd, xl, yt, wnew, hnew);
1835 return boxd;
1836 }
1837
1838
1839 /*!
1840 * \brief boxaSetSide()
1841 *
1842 * \param[in] boxad use NULL to get a new one; same as boxas for in-place
1843 * \param[in] boxas
1844 * \param[in] side L_SET_LEFT, L_SET_RIGHT, L_SET_TOP, L_SET_BOT
1845 * \param[in] val location to set for given side, for each box
1846 * \param[in] thresh min abs difference to cause resetting to %val
1847 * \return boxad, or NULL on error
1848 *
1849 * <pre>
1850 * Notes:
1851 * (1) Sets the given side of each box. Use boxad == NULL for a new
1852 * boxa, and boxad == boxas for in-place.
1853 * (2) Use one of these:
1854 * boxad = boxaSetSide(NULL, boxas, ...); // new
1855 * boxaSetSide(boxas, boxas, ...); // in-place
1856 * </pre>
1857 */
1858 BOXA *
boxaSetSide(BOXA * boxad,BOXA * boxas,l_int32 side,l_int32 val,l_int32 thresh)1859 boxaSetSide(BOXA *boxad,
1860 BOXA *boxas,
1861 l_int32 side,
1862 l_int32 val,
1863 l_int32 thresh)
1864 {
1865 l_int32 x, y, w, h, n, i, diff;
1866 BOX *box;
1867
1868 PROCNAME("boxaSetSide");
1869
1870 if (!boxas)
1871 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
1872 if (boxad && (boxas != boxad))
1873 return (BOXA *)ERROR_PTR("not in-place", procName, NULL);
1874 if (side != L_SET_LEFT && side != L_SET_RIGHT &&
1875 side != L_SET_TOP && side != L_SET_BOT)
1876 return (BOXA *)ERROR_PTR("invalid side", procName, NULL);
1877 if (val < 0)
1878 return (BOXA *)ERROR_PTR("val < 0", procName, NULL);
1879
1880 if (!boxad)
1881 boxad = boxaCopy(boxas, L_COPY);
1882 n = boxaGetCount(boxad);
1883 for (i = 0; i < n; i++) {
1884 box = boxaGetBox(boxad, i, L_CLONE);
1885 boxGetGeometry(box, &x, &y, &w, &h);
1886 if (side == L_SET_LEFT) {
1887 diff = x - val;
1888 if (L_ABS(diff) >= thresh)
1889 boxSetGeometry(box, val, y, w + diff, h);
1890 } else if (side == L_SET_RIGHT) {
1891 diff = x + w -1 - val;
1892 if (L_ABS(diff) >= thresh)
1893 boxSetGeometry(box, x, y, val - x + 1, h);
1894 } else if (side == L_SET_TOP) {
1895 diff = y - val;
1896 if (L_ABS(diff) >= thresh)
1897 boxSetGeometry(box, x, val, w, h + diff);
1898 } else { /* side == L_SET_BOT */
1899 diff = y + h - 1 - val;
1900 if (L_ABS(diff) >= thresh)
1901 boxSetGeometry(box, x, y, w, val - y + 1);
1902 }
1903 boxDestroy(&box);
1904 }
1905
1906 return boxad;
1907 }
1908
1909
1910 /*!
1911 * \brief boxaAdjustWidthToTarget()
1912 *
1913 * \param[in] boxad use NULL to get a new one; same as boxas for in-place
1914 * \param[in] boxas
1915 * \param[in] sides L_ADJUST_LEFT, L_ADJUST_RIGHT, L_ADJUST_LEFT_AND_RIGHT
1916 * \param[in] target target width if differs by more than thresh
1917 * \param[in] thresh min abs difference in width to cause adjustment
1918 * \return boxad, or NULL on error
1919 *
1920 * <pre>
1921 * Notes:
1922 * (1) Conditionally adjusts the width of each box, by moving
1923 * the indicated edges (left and/or right) if the width differs
1924 * by %thresh or more from %target.
1925 * (2) Use boxad == NULL for a new boxa, and boxad == boxas for in-place.
1926 * Use one of these:
1927 * boxad = boxaAdjustWidthToTarget(NULL, boxas, ...); // new
1928 * boxaAdjustWidthToTarget(boxas, boxas, ...); // in-place
1929 * </pre>
1930 */
1931 BOXA *
boxaAdjustWidthToTarget(BOXA * boxad,BOXA * boxas,l_int32 sides,l_int32 target,l_int32 thresh)1932 boxaAdjustWidthToTarget(BOXA *boxad,
1933 BOXA *boxas,
1934 l_int32 sides,
1935 l_int32 target,
1936 l_int32 thresh)
1937 {
1938 l_int32 x, y, w, h, n, i, diff;
1939 BOX *box;
1940
1941 PROCNAME("boxaAdjustWidthToTarget");
1942
1943 if (!boxas)
1944 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
1945 if (boxad && (boxas != boxad))
1946 return (BOXA *)ERROR_PTR("not in-place", procName, NULL);
1947 if (sides != L_ADJUST_LEFT && sides != L_ADJUST_RIGHT &&
1948 sides != L_ADJUST_LEFT_AND_RIGHT)
1949 return (BOXA *)ERROR_PTR("invalid sides", procName, NULL);
1950 if (target < 1)
1951 return (BOXA *)ERROR_PTR("target < 1", procName, NULL);
1952
1953 if (!boxad)
1954 boxad = boxaCopy(boxas, L_COPY);
1955 n = boxaGetCount(boxad);
1956 for (i = 0; i < n; i++) {
1957 box = boxaGetBox(boxad, i, L_CLONE);
1958 boxGetGeometry(box, &x, &y, &w, &h);
1959 diff = w - target;
1960 if (sides == L_ADJUST_LEFT) {
1961 if (L_ABS(diff) >= thresh)
1962 boxSetGeometry(box, L_MAX(0, x + diff), y, target, h);
1963 } else if (sides == L_ADJUST_RIGHT) {
1964 if (L_ABS(diff) >= thresh)
1965 boxSetGeometry(box, x, y, target, h);
1966 } else { /* sides == L_ADJUST_LEFT_AND_RIGHT */
1967 if (L_ABS(diff) >= thresh)
1968 boxSetGeometry(box, L_MAX(0, x + diff/2), y, target, h);
1969 }
1970 boxDestroy(&box);
1971 }
1972
1973 return boxad;
1974 }
1975
1976
1977 /*!
1978 * \brief boxaAdjustHeightToTarget()
1979 *
1980 * \param[in] boxad use NULL to get a new one
1981 * \param[in] boxas
1982 * \param[in] sides L_ADJUST_TOP, L_ADJUST_BOT, L_ADJUST_TOP_AND_BOT
1983 * \param[in] target target height if differs by more than thresh
1984 * \param[in] thresh min abs difference in height to cause adjustment
1985 * \return boxad, or NULL on error
1986 *
1987 * <pre>
1988 * Notes:
1989 * (1) Conditionally adjusts the height of each box, by moving
1990 * the indicated edges (top and/or bot) if the height differs
1991 * by %thresh or more from %target.
1992 * (2) Use boxad == NULL for a new boxa, and boxad == boxas for in-place.
1993 * Use one of these:
1994 * boxad = boxaAdjustHeightToTarget(NULL, boxas, ...); // new
1995 * boxaAdjustHeightToTarget(boxas, boxas, ...); // in-place
1996 * </pre>
1997 */
1998 BOXA *
boxaAdjustHeightToTarget(BOXA * boxad,BOXA * boxas,l_int32 sides,l_int32 target,l_int32 thresh)1999 boxaAdjustHeightToTarget(BOXA *boxad,
2000 BOXA *boxas,
2001 l_int32 sides,
2002 l_int32 target,
2003 l_int32 thresh)
2004 {
2005 l_int32 x, y, w, h, n, i, diff;
2006 BOX *box;
2007
2008 PROCNAME("boxaAdjustHeightToTarget");
2009
2010 if (!boxas)
2011 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
2012 if (boxad && (boxas != boxad))
2013 return (BOXA *)ERROR_PTR("not in-place", procName, NULL);
2014 if (sides != L_ADJUST_TOP && sides != L_ADJUST_BOT &&
2015 sides != L_ADJUST_TOP_AND_BOT)
2016 return (BOXA *)ERROR_PTR("invalid sides", procName, NULL);
2017 if (target < 1)
2018 return (BOXA *)ERROR_PTR("target < 1", procName, NULL);
2019
2020 if (!boxad)
2021 boxad = boxaCopy(boxas, L_COPY);
2022 n = boxaGetCount(boxad);
2023 for (i = 0; i < n; i++) {
2024 box = boxaGetBox(boxad, i, L_CLONE);
2025 boxGetGeometry(box, &x, &y, &w, &h);
2026 if (w == 0 || h == 0) { /* invalid; do not alter */
2027 boxDestroy(&box);
2028 continue;
2029 }
2030 diff = h - target;
2031 if (sides == L_ADJUST_TOP) {
2032 if (L_ABS(diff) >= thresh)
2033 boxSetGeometry(box, x, L_MAX(0, y + diff), w, target);
2034 } else if (sides == L_ADJUST_BOT) {
2035 if (L_ABS(diff) >= thresh)
2036 boxSetGeometry(box, x, y, w, target);
2037 } else { /* sides == L_ADJUST_TOP_AND_BOT */
2038 if (L_ABS(diff) >= thresh)
2039 boxSetGeometry(box, x, L_MAX(0, y + diff/2), w, target);
2040 }
2041 boxDestroy(&box);
2042 }
2043
2044 return boxad;
2045 }
2046
2047
2048 /*!
2049 * \brief boxEqual()
2050 *
2051 * \param[in] box1
2052 * \param[in] box2
2053 * \param[out] psame 1 if equal; 0 otherwise
2054 * \return 0 if OK, 1 on error
2055 */
2056 l_int32
boxEqual(BOX * box1,BOX * box2,l_int32 * psame)2057 boxEqual(BOX *box1,
2058 BOX *box2,
2059 l_int32 *psame)
2060 {
2061 PROCNAME("boxEqual");
2062
2063 if (!psame)
2064 return ERROR_INT("&same not defined", procName, 1);
2065 *psame = 0;
2066 if (!box1 || !box2)
2067 return ERROR_INT("box1 and box2 not both defined", procName, 1);
2068 if (box1->x == box2->x && box1->y == box2->y &&
2069 box1->w == box2->w && box1->h == box2->h)
2070 *psame = 1;
2071 return 0;
2072 }
2073
2074
2075 /*!
2076 * \brief boxaEqual()
2077 *
2078 * \param[in] boxa1
2079 * \param[in] boxa2
2080 * \param[in] maxdist
2081 * \param[out] pnaindex [optional] index array of correspondences
2082 * \param[out] psame (1 if equal; 0 otherwise
2083 * \return 0 if OK, 1 on error
2084 *
2085 * <pre>
2086 * Notes:
2087 * (1) The two boxa are the "same" if they contain the same
2088 * boxes and each box is within %maxdist of its counterpart
2089 * in their positions within the boxa. This allows for
2090 * small rearrangements. Use 0 for maxdist if the boxa
2091 * must be identical.
2092 * (2) This applies only to geometry and ordering; refcounts
2093 * are not considered.
2094 * (3) %maxdist allows some latitude in the ordering of the boxes.
2095 * For the boxa to be the "same", corresponding boxes must
2096 * be within %maxdist of each other. Note that for large
2097 * %maxdist, we should use a hash function for efficiency.
2098 * (4) naindex[i] gives the position of the box in boxa2 that
2099 * corresponds to box i in boxa1. It is only returned if the
2100 * boxa are equal.
2101 * </pre>
2102 */
2103 l_int32
boxaEqual(BOXA * boxa1,BOXA * boxa2,l_int32 maxdist,NUMA ** pnaindex,l_int32 * psame)2104 boxaEqual(BOXA *boxa1,
2105 BOXA *boxa2,
2106 l_int32 maxdist,
2107 NUMA **pnaindex,
2108 l_int32 *psame)
2109 {
2110 l_int32 i, j, n, jstart, jend, found, samebox;
2111 l_int32 *countarray;
2112 BOX *box1, *box2;
2113 NUMA *na;
2114
2115 PROCNAME("boxaEqual");
2116
2117 if (pnaindex) *pnaindex = NULL;
2118 if (!psame)
2119 return ERROR_INT("&same not defined", procName, 1);
2120 *psame = 0;
2121 if (!boxa1 || !boxa2)
2122 return ERROR_INT("boxa1 and boxa2 not both defined", procName, 1);
2123 n = boxaGetCount(boxa1);
2124 if (n != boxaGetCount(boxa2))
2125 return 0;
2126
2127 if ((countarray = (l_int32 *)LEPT_CALLOC(n, sizeof(l_int32))) == NULL)
2128 return ERROR_INT("calloc fail for countarray", procName, 1);
2129 na = numaMakeConstant(0.0, n);
2130
2131 for (i = 0; i < n; i++) {
2132 box1 = boxaGetBox(boxa1, i, L_CLONE);
2133 jstart = L_MAX(0, i - maxdist);
2134 jend = L_MIN(n-1, i + maxdist);
2135 found = FALSE;
2136 for (j = jstart; j <= jend; j++) {
2137 box2 = boxaGetBox(boxa2, j, L_CLONE);
2138 boxEqual(box1, box2, &samebox);
2139 if (samebox && countarray[j] == 0) {
2140 countarray[j] = 1;
2141 numaReplaceNumber(na, i, j);
2142 found = TRUE;
2143 boxDestroy(&box2);
2144 break;
2145 }
2146 boxDestroy(&box2);
2147 }
2148 boxDestroy(&box1);
2149 if (!found) {
2150 numaDestroy(&na);
2151 LEPT_FREE(countarray);
2152 return 0;
2153 }
2154 }
2155
2156 *psame = 1;
2157 if (pnaindex)
2158 *pnaindex = na;
2159 else
2160 numaDestroy(&na);
2161 LEPT_FREE(countarray);
2162 return 0;
2163 }
2164
2165
2166 /*!
2167 * \brief boxSimilar()
2168 *
2169 * \param[in] box1
2170 * \param[in] box2
2171 * \param[in] leftdiff, rightdiff, topdiff, botdiff
2172 * \param[out] psimilar 1 if similar; 0 otherwise
2173 * \return 0 if OK, 1 on error
2174 *
2175 * <pre>
2176 * Notes:
2177 * (1) The values of leftdiff (etc) are the maximum allowed deviations
2178 * between the locations of the left (etc) sides. If any side
2179 * pairs differ by more than this amount, the boxes are not similar.
2180 * </pre>
2181 */
2182 l_int32
boxSimilar(BOX * box1,BOX * box2,l_int32 leftdiff,l_int32 rightdiff,l_int32 topdiff,l_int32 botdiff,l_int32 * psimilar)2183 boxSimilar(BOX *box1,
2184 BOX *box2,
2185 l_int32 leftdiff,
2186 l_int32 rightdiff,
2187 l_int32 topdiff,
2188 l_int32 botdiff,
2189 l_int32 *psimilar)
2190 {
2191 l_int32 l1, l2, r1, r2, t1, t2, b1, b2;
2192
2193 PROCNAME("boxSimilar");
2194
2195 if (!psimilar)
2196 return ERROR_INT("&similar not defined", procName, 1);
2197 *psimilar = 0;
2198 if (!box1 || !box2)
2199 return ERROR_INT("box1 and box2 not both defined", procName, 1);
2200
2201 boxGetSideLocations(box1, &l1, &r1, &t1, &b1);
2202 boxGetSideLocations(box2, &l2, &r2, &t2, &b2);
2203 if (L_ABS(l1 - l2) > leftdiff)
2204 return 0;
2205 if (L_ABS(r1 - r2) > rightdiff)
2206 return 0;
2207 if (L_ABS(t1 - t2) > topdiff)
2208 return 0;
2209 if (L_ABS(b1 - b2) > botdiff)
2210 return 0;
2211
2212 *psimilar = 1;
2213 return 0;
2214 }
2215
2216
2217 /*!
2218 * \brief boxaSimilar()
2219 *
2220 * \param[in] boxa1
2221 * \param[in] boxa2
2222 * \param[in] leftdiff, rightdiff, topdiff, botdiff
2223 * \param[in] debug output details of non-similar boxes
2224 * \param[out] psimilar 1 if similar; 0 otherwise
2225 * \param[out] pnasim [optional] na containing 1 if similar; else 0
2226 * \return 0 if OK, 1 on error
2227 *
2228 * <pre>
2229 * Notes:
2230 * (1) See boxSimilar() for parameter usage.
2231 * (2) Corresponding boxes are taken in order in the two boxa.
2232 * (3) %nasim is an indicator array with a (0/1) for each box pair.
2233 * (4) With %nasim or debug == 1, boxes continue to be tested
2234 * after failure.
2235 * </pre>
2236 */
2237 l_int32
boxaSimilar(BOXA * boxa1,BOXA * boxa2,l_int32 leftdiff,l_int32 rightdiff,l_int32 topdiff,l_int32 botdiff,l_int32 debug,l_int32 * psimilar,NUMA ** pnasim)2238 boxaSimilar(BOXA *boxa1,
2239 BOXA *boxa2,
2240 l_int32 leftdiff,
2241 l_int32 rightdiff,
2242 l_int32 topdiff,
2243 l_int32 botdiff,
2244 l_int32 debug,
2245 l_int32 *psimilar,
2246 NUMA **pnasim)
2247 {
2248 l_int32 i, n1, n2, match, mismatch;
2249 BOX *box1, *box2;
2250
2251 PROCNAME("boxaSimilar");
2252
2253 if (psimilar) *psimilar = 0;
2254 if (pnasim) *pnasim = NULL;
2255 if (!boxa1 || !boxa2)
2256 return ERROR_INT("boxa1 and boxa2 not both defined", procName, 1);
2257 if (!psimilar)
2258 return ERROR_INT("&similar not defined", procName, 1);
2259 n1 = boxaGetCount(boxa1);
2260 n2 = boxaGetCount(boxa2);
2261 if (n1 != n2) {
2262 L_ERROR("boxa counts differ: %d vs %d\n", procName, n1, n2);
2263 return 1;
2264 }
2265 if (pnasim) *pnasim = numaCreate(n1);
2266
2267 mismatch = FALSE;
2268 for (i = 0; i < n1; i++) {
2269 box1 = boxaGetBox(boxa1, i, L_CLONE);
2270 box2 = boxaGetBox(boxa2, i, L_CLONE);
2271 boxSimilar(box1, box2, leftdiff, rightdiff, topdiff, botdiff,
2272 &match);
2273 boxDestroy(&box1);
2274 boxDestroy(&box2);
2275 if (pnasim)
2276 numaAddNumber(*pnasim, match);
2277 if (!match) {
2278 mismatch = TRUE;
2279 if (!debug && pnasim == NULL)
2280 return 0;
2281 else if (debug)
2282 L_INFO("box %d not similar\n", procName, i);
2283 }
2284 }
2285
2286 if (!mismatch) *psimilar = 1;
2287 return 0;
2288 }
2289
2290
2291 /*----------------------------------------------------------------------*
2292 * Boxa combine and split *
2293 *----------------------------------------------------------------------*/
2294 /*!
2295 * \brief boxaJoin()
2296 *
2297 * \param[in] boxad dest boxa; add to this one
2298 * \param[in] boxas source boxa; add from this one
2299 * \param[in] istart starting index in boxas
2300 * \param[in] iend ending index in boxas; use -1 to cat all
2301 * \return 0 if OK, 1 on error
2302 *
2303 * <pre>
2304 * Notes:
2305 * (1) This appends a clone of each indicated box in boxas to boxad
2306 * (2) istart < 0 is taken to mean 'read from the start' (istart = 0)
2307 * (3) iend < 0 means 'read to the end'
2308 * (4) if boxas == NULL or has no boxes, this is a no-op.
2309 * </pre>
2310 */
2311 l_int32
boxaJoin(BOXA * boxad,BOXA * boxas,l_int32 istart,l_int32 iend)2312 boxaJoin(BOXA *boxad,
2313 BOXA *boxas,
2314 l_int32 istart,
2315 l_int32 iend)
2316 {
2317 l_int32 n, i;
2318 BOX *box;
2319
2320 PROCNAME("boxaJoin");
2321
2322 if (!boxad)
2323 return ERROR_INT("boxad not defined", procName, 1);
2324 if (!boxas || ((n = boxaGetCount(boxas)) == 0))
2325 return 0;
2326
2327 if (istart < 0)
2328 istart = 0;
2329 if (iend < 0 || iend >= n)
2330 iend = n - 1;
2331 if (istart > iend)
2332 return ERROR_INT("istart > iend; nothing to add", procName, 1);
2333
2334 for (i = istart; i <= iend; i++) {
2335 box = boxaGetBox(boxas, i, L_CLONE);
2336 boxaAddBox(boxad, box, L_INSERT);
2337 }
2338
2339 return 0;
2340 }
2341
2342
2343 /*!
2344 * \brief boxaaJoin()
2345 *
2346 * \param[in] baad dest boxaa; add to this one
2347 * \param[in] baas source boxaa; add from this one
2348 * \param[in] istart starting index in baas
2349 * \param[in] iend ending index in baas; use -1 to cat all
2350 * \return 0 if OK, 1 on error
2351 *
2352 * <pre>
2353 * Notes:
2354 * (1) This appends a clone of each indicated boxa in baas to baad
2355 * (2) istart < 0 is taken to mean 'read from the start' (istart = 0)
2356 * (3) iend < 0 means 'read to the end'
2357 * (4) if baas == NULL, this is a no-op.
2358 * </pre>
2359 */
2360 l_int32
boxaaJoin(BOXAA * baad,BOXAA * baas,l_int32 istart,l_int32 iend)2361 boxaaJoin(BOXAA *baad,
2362 BOXAA *baas,
2363 l_int32 istart,
2364 l_int32 iend)
2365 {
2366 l_int32 n, i;
2367 BOXA *boxa;
2368
2369 PROCNAME("boxaaJoin");
2370
2371 if (!baad)
2372 return ERROR_INT("baad not defined", procName, 1);
2373 if (!baas)
2374 return 0;
2375
2376 if (istart < 0)
2377 istart = 0;
2378 n = boxaaGetCount(baas);
2379 if (iend < 0 || iend >= n)
2380 iend = n - 1;
2381 if (istart > iend)
2382 return ERROR_INT("istart > iend; nothing to add", procName, 1);
2383
2384 for (i = istart; i <= iend; i++) {
2385 boxa = boxaaGetBoxa(baas, i, L_CLONE);
2386 boxaaAddBoxa(baad, boxa, L_INSERT);
2387 }
2388
2389 return 0;
2390 }
2391
2392
2393 /*!
2394 * \brief boxaSplitEvenOdd()
2395 *
2396 * \param[in] boxa
2397 * \param[in] fillflag 1 to put invalid boxes in place; 0 to omit
2398 * \param[out] pboxae, pboxao save even and odd boxes in their
2399 * separate boxa, setting the other type to invalid boxes.
2400 * \return 0 if OK, 1 on error
2401 *
2402 * <pre>
2403 * Notes:
2404 * (1) If %fillflag == 1, boxae has copies of the even boxes
2405 * in their original location, and nvalid boxes are placed
2406 * in the odd array locations. And v.v.
2407 * (2) If %fillflag == 0, boxae has only copies of the even boxes.
2408 * </pre>
2409 */
2410 l_int32
boxaSplitEvenOdd(BOXA * boxa,l_int32 fillflag,BOXA ** pboxae,BOXA ** pboxao)2411 boxaSplitEvenOdd(BOXA *boxa,
2412 l_int32 fillflag,
2413 BOXA **pboxae,
2414 BOXA **pboxao)
2415 {
2416 l_int32 i, n;
2417 BOX *box, *boxt;
2418
2419 PROCNAME("boxaSplitEvenOdd");
2420
2421 if (pboxae) *pboxae = NULL;
2422 if (pboxao) *pboxao = NULL;
2423 if (!pboxae || !pboxao)
2424 return ERROR_INT("&boxae and &boxao not both defined", procName, 1);
2425 if (!boxa)
2426 return ERROR_INT("boxa not defined", procName, 1);
2427
2428 n = boxaGetCount(boxa);
2429 *pboxae = boxaCreate(n);
2430 *pboxao = boxaCreate(n);
2431 if (fillflag == 0) {
2432 /* don't fill with invalid boxes; end up with half-size boxa */
2433 for (i = 0; i < n; i++) {
2434 box = boxaGetBox(boxa, i, L_COPY);
2435 if ((i & 1) == 0)
2436 boxaAddBox(*pboxae, box, L_INSERT);
2437 else
2438 boxaAddBox(*pboxao, box, L_INSERT);
2439 }
2440 } else {
2441 for (i = 0; i < n; i++) {
2442 box = boxaGetBox(boxa, i, L_COPY);
2443 boxt = boxCreate(0, 0, 0, 0); /* empty placeholder */
2444 if ((i & 1) == 0) {
2445 boxaAddBox(*pboxae, box, L_INSERT);
2446 boxaAddBox(*pboxao, boxt, L_INSERT);
2447 } else {
2448 boxaAddBox(*pboxae, boxt, L_INSERT);
2449 boxaAddBox(*pboxao, box, L_INSERT);
2450 }
2451 }
2452 }
2453 return 0;
2454 }
2455
2456
2457 /*!
2458 * \brief boxaMergeEvenOdd()
2459 *
2460 * \param[in] boxae boxes to go in even positions in merged boxa
2461 * \param[in] boxao boxes to go in odd positions in merged boxa
2462 * \param[in] fillflag 1 if there are invalid boxes in placeholders
2463 * \return boxad merged, or NULL on error
2464 *
2465 * <pre>
2466 * Notes:
2467 * (1) This is essentially the inverse of boxaSplitEvenOdd().
2468 * Typically, boxae and boxao were generated by boxaSplitEvenOdd(),
2469 * and the value of %fillflag needs to be the same in both calls.
2470 * (2) If %fillflag == 1, both boxae and boxao are of the same size;
2471 * otherwise boxae may have one more box than boxao.
2472 * </pre>
2473 */
2474 BOXA *
boxaMergeEvenOdd(BOXA * boxae,BOXA * boxao,l_int32 fillflag)2475 boxaMergeEvenOdd(BOXA *boxae,
2476 BOXA *boxao,
2477 l_int32 fillflag)
2478 {
2479 l_int32 i, n, ne, no;
2480 BOX *box;
2481 BOXA *boxad;
2482
2483 PROCNAME("boxaMergeEvenOdd");
2484
2485 if (!boxae || !boxao)
2486 return (BOXA *)ERROR_PTR("boxae and boxao not defined", procName, NULL);
2487 ne = boxaGetCount(boxae);
2488 no = boxaGetCount(boxao);
2489 if (ne < no || ne > no + 1)
2490 return (BOXA *)ERROR_PTR("boxa sizes invalid", procName, NULL);
2491
2492 boxad = boxaCreate(ne);
2493 if (fillflag == 0) { /* both are approx. half-sized; all valid boxes */
2494 n = ne + no;
2495 for (i = 0; i < n; i++) {
2496 if ((i & 1) == 0)
2497 box = boxaGetBox(boxae, i / 2, L_COPY);
2498 else
2499 box = boxaGetBox(boxao, i / 2, L_COPY);
2500 boxaAddBox(boxad, box, L_INSERT);
2501 }
2502 } else { /* both are full size and have invalid placeholders */
2503 for (i = 0; i < ne; i++) {
2504 if ((i & 1) == 0)
2505 box = boxaGetBox(boxae, i, L_COPY);
2506 else
2507 box = boxaGetBox(boxao, i, L_COPY);
2508 boxaAddBox(boxad, box, L_INSERT);
2509 }
2510 }
2511 return boxad;
2512 }
2513