Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/boxfunc1.c @ 2:b50eed0cc0ef upstream

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