Coverage Report

Created: 2025-06-13 07:02

/src/leptonica/src/boxfunc1.c
Line
Count
Source (jump to first uncovered line)
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
0
{
111
0
l_int32  x1, y1, w1, h1, x2, y2, w2, h2, valid1, valid2;
112
113
0
    if (!presult)
114
0
        return ERROR_INT("&result not defined", __func__, 1);
115
0
    *presult = 0;
116
0
    if (!box1 || !box2)
117
0
        return ERROR_INT("boxes not both defined", __func__, 1);
118
0
    boxIsValid(box1, &valid1);
119
0
    boxIsValid(box2, &valid2);
120
0
    if (!valid1 || !valid2)
121
0
        return ERROR_INT("boxes not both valid", __func__, 1);
122
123
0
    boxGetGeometry(box1, &x1, &y1, &w1, &h1);
124
0
    boxGetGeometry(box2, &x2, &y2, &w2, &h2);
125
0
    if (x1 <= x2 && y1 <= y2 && (x1 + w1 >= x2 + w2) && (y1 + h1 >= y2 + h2))
126
0
        *presult = 1;
127
0
    return 0;
128
0
}
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
0
{
144
0
l_int32  l1, l2, r1, r2, t1, t2, b1, b2, w1, h1, w2, h2, valid1, valid2;
145
146
0
    if (!presult)
147
0
        return ERROR_INT("&result not defined", __func__, 1);
148
0
    *presult = 0;
149
0
    if (!box1 || !box2)
150
0
        return ERROR_INT("boxes not both defined", __func__, 1);
151
0
    boxIsValid(box1, &valid1);
152
0
    boxIsValid(box2, &valid2);
153
0
    if (!valid1 || !valid2)
154
0
        return ERROR_INT("boxes not both valid", __func__, 1);
155
156
0
    boxGetGeometry(box1, &l1, &t1, &w1, &h1);
157
0
    boxGetGeometry(box2, &l2, &t2, &w2, &h2);
158
0
    r1 = l1 + w1 - 1;
159
0
    r2 = l2 + w2 - 1;
160
0
    b1 = t1 + h1 - 1;
161
0
    b2 = t2 + h2 - 1;
162
0
    if (b2 < t1 || b1 < t2 || r1 < l2 || r2 < l1)
163
0
        *presult = 0;
164
0
    else
165
0
        *presult = 1;
166
0
    return 0;
167
0
}
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
0
{
188
0
l_int32  i, n, val, valid;
189
0
BOX     *box1;
190
0
BOXA    *boxad;
191
192
0
    if (!boxas)
193
0
        return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
194
0
    if (!box)
195
0
        return (BOXA *)ERROR_PTR("box not defined", __func__, NULL);
196
0
    n = boxaGetCount(boxas);
197
0
    boxIsValid(box, &valid);
198
0
    if (n == 0 || !valid)
199
0
        return boxaCreate(1);  /* empty */
200
201
0
    boxad = boxaCreate(0);
202
0
    for (i = 0; i < n; i++) {
203
0
        if ((box1 = boxaGetValidBox(boxas, i, L_CLONE)) == NULL)
204
0
            continue;
205
0
        boxContains(box, box1, &val);
206
0
        if (val == 1)
207
0
            boxaAddBox(boxad, box1, L_COPY);
208
0
        boxDestroy(&box1);  /* destroy the clone */
209
0
    }
210
211
0
    return boxad;
212
0
}
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
0
{
233
0
l_int32  i, n, val, valid;
234
0
BOX     *box1;
235
236
0
    if (!pcount)
237
0
        return ERROR_INT("&count not defined", __func__, 1);
238
0
    *pcount = 0;
239
0
    if (!boxa)
240
0
        return ERROR_INT("boxa not defined", __func__, 1);
241
0
    if (!box)
242
0
        return ERROR_INT("box not defined", __func__, 1);
243
0
    n = boxaGetCount(boxa);
244
0
    boxIsValid(box, &valid);
245
0
    if (n == 0 || !valid)
246
0
        return 0;
247
248
0
    for (i = 0; i < n; i++) {
249
0
        if ((box1 = boxaGetValidBox(boxa, i, L_CLONE)) == NULL)
250
0
            continue;
251
0
        boxContains(box, box1, &val);
252
0
        if (val == 1)
253
0
            (*pcount)++;
254
0
        boxDestroy(&box1);
255
0
    }
256
0
    return 0;
257
0
}
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
0
{
273
0
l_int32  i, j, n1, n2, cont, result;
274
0
BOX     *box1, *box2;
275
276
0
    if (!pcontained)
277
0
        return ERROR_INT("&contained not defined", __func__, 1);
278
0
    *pcontained = 0;
279
0
    if (!boxa1 || !boxa2)
280
0
        return ERROR_INT("boxa1 and boxa2 not both defined", __func__, 1);
281
282
0
    n1 = boxaGetCount(boxa1);
283
0
    n2 = boxaGetCount(boxa2);
284
0
    for (i = 0; i < n2; i++) {
285
0
        if ((box2 = boxaGetValidBox(boxa2, i, L_CLONE)) == NULL)
286
0
            continue;
287
0
        cont = 0;
288
0
        for (j = 0; j < n1; j++) {
289
0
            if ((box1 = boxaGetValidBox(boxa1, j, L_CLONE)) == NULL)
290
0
                continue;
291
0
            boxContains(box1, box2, &result);
292
0
            boxDestroy(&box1);
293
0
            if (result) {
294
0
                cont = 1;
295
0
                break;
296
0
            }
297
0
        }
298
0
        boxDestroy(&box2);
299
0
        if (!cont) return 0;
300
0
    }
301
302
0
    *pcontained = 1;
303
0
    return 0;
304
0
}
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
0
{
325
0
l_int32  i, n, val, valid;
326
0
BOX     *box1;
327
0
BOXA    *boxad;
328
329
0
    if (!boxas)
330
0
        return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
331
0
    if (!box)
332
0
        return (BOXA *)ERROR_PTR("box not defined", __func__, NULL);
333
0
    n = boxaGetCount(boxas);
334
0
    boxIsValid(box, &valid);
335
0
    if (n == 0 || !valid)
336
0
        return boxaCreate(1);  /* empty */
337
338
0
    boxad = boxaCreate(0);
339
0
    for (i = 0; i < n; i++) {
340
0
        if ((box1 = boxaGetValidBox(boxas, i, L_CLONE)) == NULL)
341
0
            continue;
342
0
        boxIntersects(box, box1, &val);
343
0
        if (val == 1)
344
0
            boxaAddBox(boxad, box1, L_COPY);
345
0
        boxDestroy(&box1);  /* destroy the clone */
346
0
    }
347
348
0
    return boxad;
349
0
}
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
0
{
365
0
l_int32  i, n, val, valid;
366
0
BOX     *box1;
367
368
0
    if (!pcount)
369
0
        return ERROR_INT("&count not defined", __func__, 1);
370
0
    *pcount = 0;
371
0
    if (!boxa)
372
0
        return ERROR_INT("boxa not defined", __func__, 1);
373
0
    if (!box)
374
0
        return ERROR_INT("box not defined", __func__, 1);
375
0
    n = boxaGetCount(boxa);
376
0
    boxIsValid(box, &valid);
377
0
    if (n == 0 || !valid)
378
0
        return 0;
379
380
0
    for (i = 0; i < n; i++) {
381
0
        if ((box1 = boxaGetValidBox(boxa, i, L_CLONE)) == NULL)
382
0
            continue;
383
0
        boxIntersects(box, box1, &val);
384
0
        if (val == 1)
385
0
            (*pcount)++;
386
0
        boxDestroy(&box1);
387
0
    }
388
0
    return 0;
389
0
}
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
0
{
409
0
l_int32  i, n, valid;
410
0
BOX     *box1, *boxo;
411
0
BOXA    *boxad;
412
413
0
    if (!boxas)
414
0
        return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
415
0
    if (!box)
416
0
        return (BOXA *)ERROR_PTR("box not defined", __func__, NULL);
417
0
    n = boxaGetCount(boxas);
418
0
    boxIsValid(box, &valid);
419
0
    if (n == 0 || !valid)
420
0
        return boxaCreate(1);  /* empty */
421
422
0
    boxad = boxaCreate(0);
423
0
    for (i = 0; i < n; i++) {
424
0
        if ((box1 = boxaGetValidBox(boxas, i, L_CLONE)) == NULL)
425
0
            continue;
426
0
        if ((boxo = boxOverlapRegion(box, box1)) != NULL)
427
0
            boxaAddBox(boxad, boxo, L_INSERT);
428
0
        boxDestroy(&box1);
429
0
    }
430
431
0
    return boxad;
432
0
}
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
0
{
466
0
l_int32  i, j, w, h, n1, n2, overlap, niters;
467
0
BOX     *box1, *box2, *box3;
468
0
BOXA    *boxa1, *boxa2;
469
0
PIX     *pix1 = NULL;
470
471
0
    if (!boxas)
472
0
        return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
473
474
0
    if (pixadb) boxaGetExtent(boxas, &w, &h, NULL);
475
476
0
    boxa1 = boxaCopy(boxas, L_COPY);
477
0
    n1 = boxaGetCount(boxa1);
478
0
    niters = 0;
479
0
    while (1) {  /* loop until no change from previous iteration */
480
0
        niters++;
481
0
        if (pixadb) {
482
0
            pix1 = pixCreate(w + 5, h + 5, 32);
483
0
            pixSetAll(pix1);
484
0
            pixRenderBoxaArb(pix1, boxa1, 2, 255, 0, 0);
485
0
            pixaAddPix(pixadb, pix1, L_COPY);
486
0
        }
487
488
            /* Combine overlaps for this iteration */
489
0
        for (i = 0; i < n1; i++) {
490
0
            if ((box1 = boxaGetValidBox(boxa1, i, L_COPY)) == NULL)
491
0
                continue;
492
0
            for (j = i + 1; j < n1; j++) {
493
0
                if ((box2 = boxaGetValidBox(boxa1, j, L_COPY)) == NULL)
494
0
                    continue;
495
0
                boxIntersects(box1, box2, &overlap);
496
0
                if (overlap) {
497
0
                    box3 = boxBoundingRegion(box1, box2);
498
0
                    boxaReplaceBox(boxa1, i, box3);
499
0
                    boxaReplaceBox(boxa1, j, boxCreate(0, 0, 0, 0));
500
0
                    boxDestroy(&box1);
501
0
                    box1 = boxCopy(box3);
502
0
                }
503
0
                boxDestroy(&box2);
504
0
            }
505
0
            boxDestroy(&box1);
506
0
        }
507
0
        boxa2 = boxaSaveValid(boxa1, L_COPY);
508
0
        n2 = boxaGetCount(boxa2);
509
0
        boxaDestroy(&boxa1);
510
0
        boxa1 = boxa2;
511
0
        if (n1 == n2) {
512
0
            if (pixadb) pixDestroy(&pix1);
513
0
            break;
514
0
        }
515
0
        n1 = n2;
516
0
        if (pixadb) {
517
0
            pixRenderBoxaArb(pix1, boxa1, 2, 0, 255, 0);
518
0
            pixaAddPix(pixadb, pix1, L_INSERT);
519
0
        }
520
0
    }
521
522
0
    if (pixadb)
523
0
        L_INFO("number of iterations: %d\n", __func__, niters);
524
0
    return boxa1;
525
0
}
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
0
{
561
0
l_int32  i, j, w, h, w2, h2, n1, n2, n1i, n2i, niters;
562
0
l_int32  overlap, bigger, area1, area2;
563
0
BOX     *box1, *box2, *box3;
564
0
BOXA    *boxa1, *boxa2, *boxac1, *boxac2;
565
0
PIX     *pix1;
566
567
0
    if (pboxad1) *pboxad1 = NULL;
568
0
    if (pboxad2) *pboxad2 = NULL;
569
0
    if (!boxas1 || !boxas2)
570
0
        return ERROR_INT("boxas1 and boxas2 not both defined", __func__, 1);
571
0
    if (!pboxad1 || !pboxad2)
572
0
        return ERROR_INT("&boxad1 and &boxad2 not both defined", __func__, 1);
573
574
0
    if (pixadb) {
575
0
        boxaGetExtent(boxas1, &w, &h, NULL);
576
0
        boxaGetExtent(boxas2, &w2, &h2, NULL);
577
0
        w = L_MAX(w, w2);
578
0
        h = L_MAX(h, w2);
579
0
    }
580
581
        /* Let the boxa with the largest area have first crack at the other */
582
0
    boxaGetArea(boxas1, &area1);
583
0
    boxaGetArea(boxas2, &area2);
584
0
    if (area1 >= area2) {
585
0
        boxac1 = boxaCopy(boxas1, L_COPY);
586
0
        boxac2 = boxaCopy(boxas2, L_COPY);
587
0
    } else {
588
0
        boxac1 = boxaCopy(boxas2, L_COPY);
589
0
        boxac2 = boxaCopy(boxas1, L_COPY);
590
0
    }
591
592
0
    n1i = boxaGetCount(boxac1);
593
0
    n2i = boxaGetCount(boxac2);
594
0
    niters = 0;
595
0
    while (1) {
596
0
        niters++;
597
0
        if (pixadb) {
598
0
            pix1 = pixCreate(w + 5, h + 5, 32);
599
0
            pixSetAll(pix1);
600
0
            pixRenderBoxaArb(pix1, boxac1, 2, 255, 0, 0);
601
0
            pixRenderBoxaArb(pix1, boxac2, 2, 0, 255, 0);
602
0
            pixaAddPix(pixadb, pix1, L_INSERT);
603
0
        }
604
605
            /* First combine boxes in each set */
606
0
        boxa1 = boxaCombineOverlaps(boxac1, NULL);
607
0
        boxa2 = boxaCombineOverlaps(boxac2, NULL);
608
609
            /* Now combine boxes between sets */
610
0
        n1 = boxaGetCount(boxa1);
611
0
        n2 = boxaGetCount(boxa2);
612
0
        for (i = 0; i < n1; i++) {  /* 1 eats 2 */
613
0
            if ((box1 = boxaGetValidBox(boxa1, i, L_COPY)) == NULL)
614
0
                continue;
615
0
            for (j = 0; j < n2; j++) {
616
0
                if ((box2 = boxaGetValidBox(boxa2, j, L_COPY)) == NULL)
617
0
                    continue;
618
0
                boxIntersects(box1, box2, &overlap);
619
0
                boxCompareSize(box1, box2, L_SORT_BY_AREA, &bigger);
620
0
                if (overlap && (bigger == 1)) {
621
0
                    box3 = boxBoundingRegion(box1, box2);
622
0
                    boxaReplaceBox(boxa1, i, box3);
623
0
                    boxaReplaceBox(boxa2, j, boxCreate(0, 0, 0, 0));
624
0
                    boxDestroy(&box1);
625
0
                    box1 = boxCopy(box3);
626
0
                }
627
0
                boxDestroy(&box2);
628
0
            }
629
0
            boxDestroy(&box1);
630
0
        }
631
0
        for (i = 0; i < n2; i++) {  /* 2 eats 1 */
632
0
            if ((box2 = boxaGetValidBox(boxa2, i, L_COPY)) == NULL)
633
0
                continue;
634
0
            for (j = 0; j < n1; j++) {
635
0
                if ((box1 = boxaGetValidBox(boxa1, j, L_COPY)) == NULL)
636
0
                    continue;
637
0
                boxIntersects(box1, box2, &overlap);
638
0
                boxCompareSize(box2, box1, L_SORT_BY_AREA, &bigger);
639
0
                if (overlap && (bigger == 1)) {
640
0
                    box3 = boxBoundingRegion(box1, box2);
641
0
                    boxaReplaceBox(boxa2, i, box3);
642
0
                    boxaReplaceBox(boxa1, j, boxCreate(0, 0, 0, 0));
643
0
                    boxDestroy(&box2);
644
0
                    box2 = boxCopy(box3);
645
0
                }
646
0
                boxDestroy(&box1);
647
0
            }
648
0
            boxDestroy(&box2);
649
0
        }
650
0
        boxaDestroy(&boxac1);
651
0
        boxaDestroy(&boxac2);
652
0
        boxac1 = boxaSaveValid(boxa1, L_COPY);  /* remove invalid boxes */
653
0
        boxac2 = boxaSaveValid(boxa2, L_COPY);
654
0
        boxaDestroy(&boxa1);
655
0
        boxaDestroy(&boxa2);
656
0
        n1 = boxaGetCount(boxac1);
657
0
        n2 = boxaGetCount(boxac2);
658
0
        if (n1 == n1i && n2 == n2i) break;
659
0
        n1i = n1;
660
0
        n2i = n2;
661
0
        if (pixadb) {
662
0
            pix1 = pixCreate(w + 5, h + 5, 32);
663
0
            pixSetAll(pix1);
664
0
            pixRenderBoxaArb(pix1, boxac1, 2, 255, 0, 0);
665
0
            pixRenderBoxaArb(pix1, boxac2, 2, 0, 255, 0);
666
0
            pixaAddPix(pixadb, pix1, L_INSERT);
667
0
        }
668
0
    }
669
670
0
    if (pixadb)
671
0
        L_INFO("number of iterations: %d\n", __func__, niters);
672
0
    *pboxad1 = boxac1;
673
0
    *pboxad2 = boxac2;
674
0
    return 0;
675
0
}
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
0
{
694
0
l_int32  l1, l2, r1, r2, t1, t2, b1, b2, w1, h1, w2, h2, ld, td, rd, bd;
695
0
l_int32  valid1, valid2;
696
697
0
    if (!box1 || !box2)
698
0
        return (BOX *)ERROR_PTR("boxes not both defined", __func__, NULL);
699
0
    boxIsValid(box1, &valid1);
700
0
    boxIsValid(box2, &valid2);
701
0
    if (!valid1 || !valid2) {
702
0
        L_WARNING("at least one box is invalid\n", __func__);
703
0
        return NULL;
704
0
    }
705
706
0
    boxGetGeometry(box1, &l1, &t1, &w1, &h1);
707
0
    boxGetGeometry(box2, &l2, &t2, &w2, &h2);
708
0
    r1 = l1 + w1 - 1;
709
0
    r2 = l2 + w2 - 1;
710
0
    b1 = t1 + h1 - 1;
711
0
    b2 = t2 + h2 - 1;
712
0
    if (b2 < t1 || b1 < t2 || r1 < l2 || r2 < l1)
713
0
        return NULL;
714
715
0
    ld = L_MAX(l1, l2);
716
0
    td = L_MAX(t1, t2);
717
0
    rd = L_MIN(r1, r2);
718
0
    bd = L_MIN(b1, b2);
719
0
    return boxCreate(ld, td, rd - ld + 1, bd - td + 1);
720
0
}
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
0
{
742
0
l_int32  l1, l2, r1, r2, t1, t2, b1, b2, w1, h1, w2, h2, ld, td, rd, bd;
743
0
l_int32  valid1, valid2;
744
745
0
    if (!box1 || !box2)
746
0
        return (BOX *)ERROR_PTR("boxes not both defined", __func__, NULL);
747
0
    boxIsValid(box1, &valid1);
748
0
    boxIsValid(box2, &valid2);
749
0
    if (!valid1 && !valid2) {
750
0
        L_WARNING("both boxes are invalid\n", __func__);
751
0
        return boxCreate(0, 0, 0, 0);
752
0
    }
753
0
    if (valid1 && !valid2)
754
0
        return boxCopy(box1);
755
0
    if (!valid1 && valid2)
756
0
        return boxCopy(box2);
757
758
0
    boxGetGeometry(box1, &l1, &t1, &w1, &h1);
759
0
    boxGetGeometry(box2, &l2, &t2, &w2, &h2);
760
0
    r1 = l1 + w1 - 1;
761
0
    r2 = l2 + w2 - 1;
762
0
    b1 = t1 + h1 - 1;
763
0
    b2 = t2 + h2 - 1;
764
0
    ld = L_MIN(l1, l2);
765
0
    td = L_MIN(t1, t2);
766
0
    rd = L_MAX(r1, r2);
767
0
    bd = L_MAX(b1, b2);
768
0
    return boxCreate(ld, td, rd - ld + 1, bd - td + 1);
769
0
}
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
0
{
791
0
l_int32  w2, h2, w, h, valid1, valid2;
792
0
BOX     *boxo;
793
794
0
    if (!pfract)
795
0
        return ERROR_INT("&fract not defined", __func__, 1);
796
0
    *pfract = 0.0;
797
0
    if (!box1 || !box2)
798
0
        return ERROR_INT("boxes not both defined", __func__, 1);
799
0
    boxIsValid(box1, &valid1);
800
0
    boxIsValid(box2, &valid2);
801
0
    if (!valid1 || !valid2) {
802
0
        L_WARNING("boxes not both valid\n", __func__);
803
0
        return 0;
804
0
    }
805
806
0
    if ((boxo = boxOverlapRegion(box1, box2)) == NULL)  /* no overlap */
807
0
        return 0;
808
809
0
    boxGetGeometry(box2, NULL, NULL, &w2, &h2);
810
0
    boxGetGeometry(boxo, NULL, NULL, &w, &h);
811
0
    *pfract = (l_float32)(w * h) / (l_float32)(w2 * h2);
812
0
    boxDestroy(&boxo);
813
0
    return 0;
814
0
}
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
0
{
829
0
l_int32  w, h, valid1, valid2;
830
0
BOX     *box;
831
832
0
    if (!parea)
833
0
        return ERROR_INT("&area not defined", __func__, 1);
834
0
    *parea = 0;
835
0
    if (!box1 || !box2)
836
0
        return ERROR_INT("boxes not both defined", __func__, 1);
837
0
    boxIsValid(box1, &valid1);
838
0
    boxIsValid(box2, &valid2);
839
0
    if (!valid1 || !valid2)
840
0
        return ERROR_INT("boxes not both valid", __func__, 1);
841
842
0
    if ((box = boxOverlapRegion(box1, box2)) == NULL)  /* no overlap */
843
0
        return 0;
844
845
0
    boxGetGeometry(box, NULL, NULL, &w, &h);
846
0
    *parea = w * h;
847
0
    boxDestroy(&box);
848
0
    return 0;
849
0
}
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
0
{
894
0
l_int32    i, j, n, w, h, area1, area2, val;
895
0
l_int32    overlap_area;
896
0
l_float32  overlap_ratio, area_ratio;
897
0
BOX       *box1, *box2, *box3;
898
0
BOXA      *boxat, *boxad;
899
0
NUMA      *namap;
900
901
0
    if (pnamap) *pnamap = NULL;
902
0
    if (!boxas)
903
0
        return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
904
0
    if (op != L_COMBINE && op != L_REMOVE_SMALL)
905
0
        return (BOXA *)ERROR_PTR("invalid op", __func__, NULL);
906
907
0
    n = boxaGetCount(boxas);
908
0
    if (n == 0)
909
0
        return boxaCreate(1);  /* empty */
910
0
    if (range == 0) {
911
0
        L_WARNING("range is 0\n", __func__);
912
0
        return boxaCopy(boxas, L_COPY);
913
0
    }
914
915
        /* Identify smaller boxes in overlap pairs, and mark to eliminate. */
916
0
    namap = numaMakeConstant(-1, n);
917
0
    for (i = 0; i < n; i++) {
918
0
        if ((box1 = boxaGetValidBox(boxas, i, L_CLONE)) == NULL)
919
0
            continue;
920
0
        boxGetGeometry(box1, NULL, NULL, &w, &h);
921
0
        area1 = w * h;
922
0
        if (area1 == 0) {
923
0
            boxDestroy(&box1);
924
0
            continue;
925
0
        }
926
0
        for (j = i + 1; j < i + 1 + range && j < n; j++) {
927
0
            if ((box2 = boxaGetValidBox(boxas, j, L_CLONE)) == NULL)
928
0
                continue;
929
0
            boxOverlapArea(box1, box2, &overlap_area);
930
0
            if (overlap_area > 0) {
931
0
                boxGetGeometry(box2, NULL, NULL, &w, &h);
932
0
                area2 = w * h;
933
0
                if (area2 == 0) {
934
                    /* do nothing */
935
0
                } else if (area1 >= area2) {
936
0
                    overlap_ratio = (l_float32)overlap_area / (l_float32)area2;
937
0
                    area_ratio = (l_float32)area2 / (l_float32)area1;
938
0
                    if (overlap_ratio >= min_overlap &&
939
0
                        area_ratio <= max_ratio) {
940
0
                        numaSetValue(namap, j, i);
941
0
                    }
942
0
                } else {
943
0
                    overlap_ratio = (l_float32)overlap_area / (l_float32)area1;
944
0
                    area_ratio = (l_float32)area1 / (l_float32)area2;
945
0
                    if (overlap_ratio >= min_overlap &&
946
0
                        area_ratio <= max_ratio) {
947
0
                        numaSetValue(namap, i, j);
948
0
                    }
949
0
                }
950
0
            }
951
0
            boxDestroy(&box2);
952
0
        }
953
0
        boxDestroy(&box1);
954
0
    }
955
956
0
    boxat = boxaCopy(boxas, L_COPY);
957
0
    if (op == L_COMBINE) {
958
            /* Resize the larger of the pair to the bounding region */
959
0
        for (i = 0; i < n; i++) {
960
0
            numaGetIValue(namap, i, &val);
961
0
            if (val >= 0) {
962
0
                box1 = boxaGetBox(boxas, i, L_CLONE);  /* smaller */
963
0
                box2 = boxaGetBox(boxas, val, L_CLONE);  /* larger */
964
0
                box3 = boxBoundingRegion(box1, box2);
965
0
                boxaReplaceBox(boxat, val, box3);
966
0
                boxDestroy(&box1);
967
0
                boxDestroy(&box2);
968
0
            }
969
0
        }
970
0
    }
971
972
        /* Remove the smaller of the pairs */
973
0
    boxad = boxaCreate(n);
974
0
    for (i = 0; i < n; i++) {
975
0
        numaGetIValue(namap, i, &val);
976
0
        if (val == -1) {
977
0
            box1 = boxaGetBox(boxat, i, L_COPY);
978
0
            boxaAddBox(boxad, box1, L_INSERT);
979
0
        }
980
0
    }
981
0
    boxaDestroy(&boxat);
982
0
    if (pnamap)
983
0
        *pnamap = namap;
984
0
    else
985
0
        numaDestroy(&namap);
986
0
    return boxad;
987
0
}
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
0
{
1020
0
l_int32  l1, t1, w1, h1, r1, b1, l2, t2, w2, h2, r2, b2, valid1, valid2;
1021
1022
0
    if (!ph_ovl && !pv_ovl)
1023
0
        return ERROR_INT("nothing to do", __func__, 1);
1024
0
    if (ph_ovl) *ph_ovl = 0;
1025
0
    if (pv_ovl) *pv_ovl = 0;
1026
0
    if (!box1 || !box2)
1027
0
        return ERROR_INT("boxes not both defined", __func__, 1);
1028
0
    boxIsValid(box1, &valid1);
1029
0
    boxIsValid(box2, &valid2);
1030
0
    if (!valid1 || !valid2)
1031
0
        return ERROR_INT("boxes not both valid", __func__, 1);
1032
1033
0
    if (ph_ovl) {
1034
0
        boxGetGeometry(box1, &l1, NULL, &w1, NULL);
1035
0
        boxGetGeometry(box2, &l2, NULL, &w2, NULL);
1036
0
        r1 = l1 + w1;  /* 1 pixel to the right of box 1 */
1037
0
        r2 = l2 + w2;
1038
0
        if (l2 >= l1)
1039
0
            *ph_ovl = r1 - l2;
1040
0
        else
1041
0
            *ph_ovl = r2 - l1;
1042
0
    }
1043
0
    if (pv_ovl) {
1044
0
        boxGetGeometry(box1, NULL, &t1, NULL, &h1);
1045
0
        boxGetGeometry(box2, NULL, &t2, NULL, &h2);
1046
0
        b1 = t1 + h1;  /* 1 pixel below box 1 */
1047
0
        b2 = t2 + h2;
1048
0
        if (t2 >= t1)
1049
0
            *pv_ovl = b1 - t2;
1050
0
        else
1051
0
            *pv_ovl = b2 - t1;
1052
0
    }
1053
0
    return 0;
1054
0
}
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
0
{
1091
0
l_int32  h_ovl, v_ovl, valid1, valid2;
1092
1093
0
    if (ph_sep) *ph_sep = 0;
1094
0
    if (pv_sep) *pv_sep = 0;
1095
0
    if (!ph_sep || !pv_sep)
1096
0
        return ERROR_INT("&h_sep and &v_sep not both defined", __func__, 1);
1097
0
    if (!box1 || !box2)
1098
0
        return ERROR_INT("boxes not both defined", __func__, 1);
1099
0
    boxIsValid(box1, &valid1);
1100
0
    boxIsValid(box2, &valid2);
1101
0
    if (!valid1 || !valid2)
1102
0
        return ERROR_INT("boxes not both valid", __func__, 1);
1103
1104
0
    boxOverlapDistance(box1, box2, &h_ovl, &v_ovl);
1105
0
    if (h_ovl <= 0)
1106
0
      *ph_sep = -h_ovl + 1;
1107
0
    if (v_ovl <= 0)
1108
0
      *pv_sep = -v_ovl + 1;
1109
0
    return 0;
1110
0
}
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
0
{
1134
0
l_int32  w1, h1, w2, h2, size1, size2, valid1, valid2;
1135
1136
0
    if (!prel)
1137
0
        return ERROR_INT("&rel not defined", __func__, 1);
1138
0
    *prel = 0;
1139
0
    if (!box1 || !box2)
1140
0
        return ERROR_INT("boxes not both defined", __func__, 1);
1141
0
    boxIsValid(box1, &valid1);
1142
0
    boxIsValid(box2, &valid2);
1143
0
    if (!valid1 || !valid2)
1144
0
        return ERROR_INT("boxes not both valid", __func__, 1);
1145
0
    if (type != L_SORT_BY_WIDTH && type != L_SORT_BY_HEIGHT &&
1146
0
        type != L_SORT_BY_MAX_DIMENSION && type != L_SORT_BY_PERIMETER &&
1147
0
        type != L_SORT_BY_AREA)
1148
0
        return ERROR_INT("invalid compare type", __func__, 1);
1149
1150
0
    boxGetGeometry(box1, NULL, NULL, &w1, &h1);
1151
0
    boxGetGeometry(box2, NULL, NULL, &w2, &h2);
1152
0
    if (type == L_SORT_BY_WIDTH) {
1153
0
        *prel = (w1 > w2) ? 1 : ((w1 == w2) ? 0 : -1);
1154
0
    } else if (type == L_SORT_BY_HEIGHT) {
1155
0
        *prel = (h1 > h2) ? 1 : ((h1 == h2) ? 0 : -1);
1156
0
    } else if (type == L_SORT_BY_MAX_DIMENSION) {
1157
0
        size1 = L_MAX(w1, h1);
1158
0
        size2 = L_MAX(w2, h2);
1159
0
        *prel = (size1 > size2) ? 1 : ((size1 == size2) ? 0 : -1);
1160
0
    } else if (type == L_SORT_BY_PERIMETER) {
1161
0
        size1 = w1 + h1;
1162
0
        size2 = w2 + h2;
1163
0
        *prel = (size1 > size2) ? 1 : ((size1 == size2) ? 0 : -1);
1164
0
    } else if (type == L_SORT_BY_AREA) {
1165
0
        size1 = w1 * h1;
1166
0
        size2 = w2 * h2;
1167
0
        *prel = (size1 > size2) ? 1 : ((size1 == size2) ? 0 : -1);
1168
0
    }
1169
0
    return 0;
1170
0
}
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
0
{
1187
0
l_int32  bx, by, bw, bh;
1188
1189
0
    if (!pcontains)
1190
0
        return ERROR_INT("&contains not defined", __func__, 1);
1191
0
    *pcontains = 0;
1192
0
    if (!box)
1193
0
        return ERROR_INT("&box not defined", __func__, 1);
1194
0
    boxGetGeometry(box, &bx, &by, &bw, &bh);
1195
0
    if (x >= bx && x < bx + bw && y >= by && y < by + bh)
1196
0
        *pcontains = 1;
1197
0
    return 0;
1198
0
}
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
0
{
1219
0
l_int32    i, n, minindex;
1220
0
l_float32  delx, dely, dist, mindist, cx, cy;
1221
0
BOX       *box;
1222
1223
0
    if (!boxa)
1224
0
        return (BOX *)ERROR_PTR("boxa not defined", __func__, NULL);
1225
0
    if ((n = boxaGetCount(boxa)) == 0)
1226
0
        return (BOX *)ERROR_PTR("n = 0", __func__, NULL);
1227
1228
0
    mindist = 1000000000.;
1229
0
    minindex = 0;
1230
0
    for (i = 0; i < n; i++) {
1231
0
        if ((box = boxaGetValidBox(boxa, i, L_CLONE)) == NULL)
1232
0
            continue;
1233
0
        boxGetCenter(box, &cx, &cy);
1234
0
        delx = (l_float32)(cx - x);
1235
0
        dely = (l_float32)(cy - y);
1236
0
        dist = delx * delx + dely * dely;
1237
0
        if (dist < mindist) {
1238
0
            minindex = i;
1239
0
            mindist = dist;
1240
0
        }
1241
0
        boxDestroy(&box);
1242
0
    }
1243
1244
0
    return boxaGetBox(boxa, minindex, L_COPY);
1245
0
}
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
0
{
1270
0
l_int32    i, n, minindex;
1271
0
l_float32  dist, mindist, cx, cy;
1272
0
BOX       *box;
1273
1274
0
    if (!boxa)
1275
0
        return (BOX *)ERROR_PTR("boxa not defined", __func__, NULL);
1276
0
    if ((n = boxaGetCount(boxa)) == 0)
1277
0
        return (BOX *)ERROR_PTR("n = 0", __func__, NULL);
1278
0
    if (y >= 0 && x >= 0)
1279
0
        return (BOX *)ERROR_PTR("either x or y must be < 0", __func__, NULL);
1280
0
    if (y < 0 && x < 0)
1281
0
        return (BOX *)ERROR_PTR("either x or y must be >= 0", __func__, NULL);
1282
1283
0
    mindist = 1000000000.;
1284
0
    minindex = 0;
1285
0
    for (i = 0; i < n; i++) {
1286
0
        if ((box = boxaGetValidBox(boxa, i, L_CLONE)) == NULL)
1287
0
            continue;
1288
0
        boxGetCenter(box, &cx, &cy);
1289
0
        if (x >= 0)
1290
0
            dist = L_ABS(cx - (l_float32)x);
1291
0
        else  /* y >= 0 */
1292
0
            dist = L_ABS(cy - (l_float32)y);
1293
0
        if (dist < mindist) {
1294
0
            minindex = i;
1295
0
            mindist = dist;
1296
0
        }
1297
0
        boxDestroy(&box);
1298
0
    }
1299
1300
0
    return boxaGetBox(boxa, minindex, L_COPY);
1301
0
}
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
0
{
1328
0
l_int32  i, n, index, dist;
1329
0
NUMA    *nai, *nad;
1330
0
NUMAA   *naai, *naad;
1331
1332
0
    if (pnaaindex) *pnaaindex = NULL;
1333
0
    if (pnaadist) *pnaadist = NULL;
1334
0
    if (!pnaaindex)
1335
0
        return ERROR_INT("&naaindex not defined", __func__, 1);
1336
0
    if (!pnaadist)
1337
0
        return ERROR_INT("&naadist not defined", __func__, 1);
1338
0
    if (!boxa)
1339
0
        return ERROR_INT("boxa not defined", __func__, 1);
1340
1341
0
    n = boxaGetCount(boxa);
1342
0
    naai = numaaCreate(n);
1343
0
    naad = numaaCreate(n);
1344
0
    *pnaaindex = naai;
1345
0
    *pnaadist = naad;
1346
0
    for (i = 0; i < n; i++) {
1347
0
        nai = numaCreate(4);
1348
0
        nad = numaCreate(4);
1349
0
        boxaGetNearestByDirection(boxa, i, L_FROM_LEFT, dist_select,
1350
0
                                  range, &index, &dist);
1351
0
        numaAddNumber(nai, index);
1352
0
        numaAddNumber(nad, dist);
1353
0
        boxaGetNearestByDirection(boxa, i, L_FROM_RIGHT, dist_select,
1354
0
                                  range, &index, &dist);
1355
0
        numaAddNumber(nai, index);
1356
0
        numaAddNumber(nad, dist);
1357
0
        boxaGetNearestByDirection(boxa, i, L_FROM_TOP, dist_select,
1358
0
                                  range, &index, &dist);
1359
0
        numaAddNumber(nai, index);
1360
0
        numaAddNumber(nad, dist);
1361
0
        boxaGetNearestByDirection(boxa, i, L_FROM_BOT, dist_select,
1362
0
                                  range, &index, &dist);
1363
0
        numaAddNumber(nai, index);
1364
0
        numaAddNumber(nad, dist);
1365
0
        numaaAddNuma(naai, nai, L_INSERT);
1366
0
        numaaAddNuma(naad, nad, L_INSERT);
1367
0
    }
1368
0
    return 0;
1369
0
}
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
0
{
1409
0
l_int32  j, jmin, jmax, n, mindist, dist, index;
1410
0
l_int32  x, y, w, h, bx, by, bw, bh;
1411
1412
0
    if (pindex) *pindex = -1;
1413
0
    if (pdist) *pdist = 100000;
1414
0
    if (!pindex)
1415
0
        return ERROR_INT("&index not defined", __func__, 1);
1416
0
    if (!pdist)
1417
0
        return ERROR_INT("&dist not defined", __func__, 1);
1418
0
    if (!boxa)
1419
0
        return ERROR_INT("boxa not defined", __func__, 1);
1420
0
    if (dir != L_FROM_LEFT && dir != L_FROM_RIGHT &&
1421
0
        dir != L_FROM_TOP && dir != L_FROM_BOT)
1422
0
        return ERROR_INT("invalid dir", __func__, 1);
1423
0
    if (dist_select != L_NON_NEGATIVE && dist_select != L_ALL)
1424
0
        return ERROR_INT("invalid dist_select", __func__, 1);
1425
0
    n = boxaGetCount(boxa);
1426
0
    if (i < 0 || i >= n)
1427
0
        return ERROR_INT("invalid box index", __func__, 1);
1428
1429
0
    jmin = (range <= 0) ? 0 : L_MAX(0, i - range);
1430
0
    jmax = (range <= 0) ? n - 1 : L_MIN(n -1, i + range);
1431
0
    boxaGetBoxGeometry(boxa, i, &x, &y, &w, &h);
1432
0
    mindist = 100000;
1433
0
    index = -1;
1434
0
    if (dir == L_FROM_LEFT || dir == L_FROM_RIGHT) {
1435
0
        for (j = jmin; j <= jmax; j++) {
1436
0
            if (j == i) continue;
1437
0
            boxaGetBoxGeometry(boxa, j, &bx, &by, &bw, &bh);
1438
0
            if ((bx >= x && dir == L_FROM_LEFT) ||  /* not to the left */
1439
0
                (x >= bx && dir == L_FROM_RIGHT))   /* not to the right */
1440
0
                continue;
1441
0
            if (boxHasOverlapInXorY(y, h, by, bh) == 1) {
1442
0
                dist = boxGetDistanceInXorY(x, w, bx, bw);
1443
0
                if (dist_select == L_NON_NEGATIVE && dist < 0) continue;
1444
0
                if (dist < mindist) {
1445
0
                    mindist = dist;
1446
0
                    index = j;
1447
0
                }
1448
0
            }
1449
0
        }
1450
0
    } else if (dir == L_FROM_TOP || dir == L_FROM_BOT) {
1451
0
        for (j = jmin; j <= jmax; j++) {
1452
0
            if (j == i) continue;
1453
0
            boxaGetBoxGeometry(boxa, j, &bx, &by, &bw, &bh);
1454
0
            if ((by >= y && dir == L_FROM_TOP) ||  /* not above */
1455
0
                (y >= by && dir == L_FROM_BOT))   /* not below */
1456
0
                continue;
1457
0
            if (boxHasOverlapInXorY(x, w, bx, bw) == 1) {
1458
0
                dist = boxGetDistanceInXorY(y, h, by, bh);
1459
0
                if (dist_select == L_NON_NEGATIVE && dist < 0) continue;
1460
0
                if (dist < mindist) {
1461
0
                    mindist = dist;
1462
0
                    index = j;
1463
0
                }
1464
0
            }
1465
0
        }
1466
0
    }
1467
0
    *pindex = index;
1468
0
    *pdist = mindist;
1469
0
    return 0;
1470
0
}
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
0
{
1494
0
l_int32  ovlp;
1495
1496
0
    if (c1 > c2)
1497
0
        ovlp = c2 + s2 - 1 - c1;
1498
0
    else
1499
0
        ovlp = c1 + s1 - 1 - c2;
1500
0
    return (ovlp < 0) ? 0 : 1;
1501
0
}
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
0
{
1520
0
l_int32  dist;
1521
1522
0
    if (c1 > c2)
1523
0
        dist = c1 - (c2 + s2 - 1);
1524
0
    else
1525
0
        dist = c2 - (c1 + s1 - 1);
1526
0
    return dist;
1527
0
}
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
0
{
1542
0
l_int32  x, y, w, h;
1543
1544
0
    if (pcx) *pcx = 0;
1545
0
    if (pcy) *pcy = 0;
1546
0
    if (!pcx || !pcy)
1547
0
        return ERROR_INT("&cx, &cy not both defined", __func__, 1);
1548
0
    if (!box)
1549
0
        return ERROR_INT("box not defined", __func__, 1);
1550
0
    boxGetGeometry(box, &x, &y, &w, &h);
1551
0
    if (w == 0 || h == 0) return 1;
1552
0
    *pcx = (l_float32)(x + 0.5 * w);
1553
0
    *pcy = (l_float32)(y + 0.5 * h);
1554
1555
0
    return 0;
1556
0
}
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
0
{
1588
0
l_int32    bx, by, bw, bh, xp, yp, xt, yt, i, n;
1589
0
l_float32  invslope;
1590
0
PTA       *pta;
1591
1592
0
    if (px1) *px1 = 0;
1593
0
    if (px2) *px2 = 0;
1594
0
    if (py1) *py1 = 0;
1595
0
    if (py2) *py2 = 0;
1596
0
    if (pn) *pn = 0;
1597
0
    if (!px1 || !py1 || !px2 || !py2)
1598
0
        return ERROR_INT("&x1, &y1, &x2, &y2 not all defined", __func__, 1);
1599
0
    if (!pn)
1600
0
        return ERROR_INT("&n not defined", __func__, 1);
1601
0
    if (!box)
1602
0
        return ERROR_INT("box not defined", __func__, 1);
1603
0
    boxGetGeometry(box, &bx, &by, &bw, &bh);
1604
0
    if (bw == 0 || bh == 0) return 1;
1605
1606
0
    if (slope == 0.0) {
1607
0
        if (y >= by && y < by + bh) {
1608
0
            *py1 = *py2 = y;
1609
0
            *px1 = bx;
1610
0
            *px2 = bx + bw - 1;
1611
0
        }
1612
0
        return 0;
1613
0
    }
1614
1615
0
    if (slope > 1000000.0) {
1616
0
        if (x >= bx && x < bx + bw) {
1617
0
            *px1 = *px2 = x;
1618
0
            *py1 = by;
1619
0
            *py2 = by + bh - 1;
1620
0
        }
1621
0
        return 0;
1622
0
    }
1623
1624
        /* Intersection with top and bottom lines of box */
1625
0
    pta = ptaCreate(2);
1626
0
    invslope = 1.0 / slope;
1627
0
    xp = (l_int32)(x + invslope * (y - by));
1628
0
    if (xp >= bx && xp < bx + bw)
1629
0
        ptaAddPt(pta, xp, by);
1630
0
    xp = (l_int32)(x + invslope * (y - by - bh + 1));
1631
0
    if (xp >= bx && xp < bx + bw)
1632
0
        ptaAddPt(pta, xp, by + bh - 1);
1633
1634
        /* Intersection with left and right lines of box */
1635
0
    yp = (l_int32)(y + slope * (x - bx));
1636
0
    if (yp >= by && yp < by + bh)
1637
0
        ptaAddPt(pta, bx, yp);
1638
0
    yp = (l_int32)(y + slope * (x - bx - bw + 1));
1639
0
    if (yp >= by && yp < by + bh)
1640
0
        ptaAddPt(pta, bx + bw - 1, yp);
1641
1642
        /* There is a maximum of 2 unique points; remove duplicates.  */
1643
0
    n = ptaGetCount(pta);
1644
0
    if (n > 0) {
1645
0
        ptaGetIPt(pta, 0, px1, py1);  /* accept the first one */
1646
0
        *pn = 1;
1647
0
    }
1648
0
    for (i = 1; i < n; i++) {
1649
0
        ptaGetIPt(pta, i, &xt, &yt);
1650
0
        if ((*px1 != xt) || (*py1 != yt)) {
1651
0
            *px2 = xt;
1652
0
            *py2 = yt;
1653
0
            *pn = 2;
1654
0
            break;
1655
0
        }
1656
0
    }
1657
1658
0
    ptaDestroy(&pta);
1659
0
    return 0;
1660
0
}
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
603k
{
1683
603k
BOX  *boxd;
1684
1685
603k
    if (!box)
1686
0
        return (BOX *)ERROR_PTR("box not defined", __func__, NULL);
1687
603k
    if (box->x >= wi || box->y >= hi ||
1688
603k
        box->x + box->w <= 0 || box->y + box->h <= 0)
1689
0
        return (BOX *)ERROR_PTR("box outside rectangle", __func__, NULL);
1690
1691
603k
    boxd = boxCopy(box);
1692
603k
    if (boxd->x < 0) {
1693
0
        boxd->w += boxd->x;
1694
0
        boxd->x = 0;
1695
0
    }
1696
603k
    if (boxd->y < 0) {
1697
0
        boxd->h += boxd->y;
1698
0
        boxd->y = 0;
1699
0
    }
1700
603k
    if (boxd->x + boxd->w > wi)
1701
0
        boxd->w = wi - boxd->x;
1702
603k
    if (boxd->y + boxd->h > hi)
1703
0
        boxd->h = hi - boxd->y;
1704
603k
    return boxd;
1705
603k
}
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
0
{
1744
0
l_int32  bw, bh;
1745
0
BOX     *boxc;
1746
1747
0
    if (pxstart) *pxstart = 0;
1748
0
    if (pystart) *pystart = 0;
1749
0
    if (pxend) *pxend = w;
1750
0
    if (pyend) *pyend = h;
1751
0
    if (pbw) *pbw = w;
1752
0
    if (pbh) *pbh = h;
1753
0
    if (!pxstart || !pystart || !pxend || !pyend)
1754
0
        return ERROR_INT("invalid ptr input", __func__, 1);
1755
0
    if (!box) return 0;
1756
1757
0
    if ((boxc = boxClipToRectangle(box, w, h)) == NULL)
1758
0
        return ERROR_INT("box outside image", __func__, 1);
1759
0
    boxGetGeometry(boxc, pxstart, pystart, &bw, &bh);
1760
0
    boxDestroy(&boxc);
1761
1762
0
    if (pbw) *pbw = bw;
1763
0
    if (pbh) *pbh = bh;
1764
0
    if (bw == 0 || bh == 0)
1765
0
        return ERROR_INT("invalid clipping box", __func__, 1);
1766
0
    *pxend = *pxstart + bw;  /* 1 past the end */
1767
0
    *pyend = *pystart + bh;  /* 1 past the end */
1768
0
    return 0;
1769
0
}
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
0
{
1799
0
l_int32  x, y, w, h;
1800
1801
0
    if (!boxs)
1802
0
        return (BOX *)ERROR_PTR("boxs not defined", __func__, NULL);
1803
0
    if (!boxd)
1804
0
        boxd = boxCopy(boxs);
1805
1806
0
    boxGetGeometry(boxs, &x, &y, &w, &h);
1807
0
    if (w == 0 || h == 0)
1808
0
        return boxd;
1809
0
    if (sideflag == L_FROM_LEFT)
1810
0
        boxSetGeometry(boxd, loc, -1, w + x - loc, -1);
1811
0
    else if (sideflag == L_FROM_RIGHT)
1812
0
        boxSetGeometry(boxd, -1, -1, loc - x + 1, -1);
1813
0
    else if (sideflag == L_FROM_TOP)
1814
0
        boxSetGeometry(boxd, -1, loc, -1, h + y - loc);
1815
0
    else if (sideflag == L_FROM_BOT)
1816
0
        boxSetGeometry(boxd, -1, -1, -1, loc - y + 1);
1817
0
    return boxd;
1818
0
}
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
0
{
1844
0
l_int32  n, i, x, y;
1845
0
BOX     *box1, *box2;
1846
0
BOXA    *boxad;
1847
1848
0
    if (!boxas)
1849
0
        return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
1850
1851
0
    n = boxaGetCount(boxas);
1852
0
    boxad = boxaCreate(n);
1853
0
    for (i = 0; i < n; i++) {
1854
0
        box1 = boxaGetBox(boxas, i, L_COPY);
1855
0
        box2 = boxAdjustSides(NULL, box1, delleft, delright, deltop, delbot);
1856
0
        if (!box2) {
1857
0
            boxGetGeometry(box1, &x, &y, NULL, NULL);
1858
0
            box2 = boxCreate(x, y, 1, 1);
1859
0
        }
1860
0
        boxaAddBox(boxad, box2, L_INSERT);
1861
0
        boxDestroy(&box1);
1862
0
    }
1863
1864
0
    return boxad;
1865
0
}
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
0
{
1893
0
BOX  *box;
1894
1895
0
    if (!boxa)
1896
0
        return ERROR_INT("boxa not defined", __func__, 1);
1897
1898
0
    if ((box = boxaGetBox(boxa, index, L_CLONE)) == NULL)
1899
0
        return ERROR_INT("invalid index", __func__, 1);
1900
1901
0
    boxAdjustSides(box, box, delleft, delright, deltop, delbot);
1902
0
    boxDestroy(&box);  /* the clone */
1903
0
    return 0;
1904
0
}
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
0
{
1939
0
l_int32  x, y, w, h, xl, xr, yt, yb, wnew, hnew;
1940
1941
0
    if (!boxs)
1942
0
        return (BOX *)ERROR_PTR("boxs not defined", __func__, NULL);
1943
1944
0
    boxGetGeometry(boxs, &x, &y, &w, &h);
1945
0
    xl = L_MAX(0, x + delleft);
1946
0
    yt = L_MAX(0, y + deltop);
1947
0
    xr = x + w + delright;  /* one pixel beyond right edge */
1948
0
    yb = y + h + delbot;    /* one pixel below bottom edge */
1949
0
    wnew = xr - xl;
1950
0
    hnew = yb - yt;
1951
1952
0
    if (wnew < 1 || hnew < 1)
1953
0
        return (BOX *)ERROR_PTR("boxd has 0 area", __func__, NULL);
1954
0
    if (!boxd)
1955
0
        return boxCreate(xl, yt, wnew, hnew);
1956
1957
0
    boxSetGeometry(boxd, xl, yt, wnew, hnew);
1958
0
    return boxd;
1959
0
}
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
0
{
1988
0
l_int32  n, i;
1989
0
BOX     *box;
1990
1991
0
    if (!boxas)
1992
0
        return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
1993
0
    if (boxad && (boxas != boxad))
1994
0
        return (BOXA *)ERROR_PTR("not in-place", __func__, NULL);
1995
0
    if (side != L_SET_LEFT && side != L_SET_RIGHT &&
1996
0
        side != L_SET_TOP && side != L_SET_BOT)
1997
0
        return (BOXA *)ERROR_PTR("invalid side", __func__, NULL);
1998
0
    if (val < 0)
1999
0
        return (BOXA *)ERROR_PTR("val < 0", __func__, NULL);
2000
2001
0
    if (!boxad)
2002
0
        boxad = boxaCopy(boxas, L_COPY);
2003
0
    n = boxaGetCount(boxad);
2004
0
    for (i = 0; i < n; i++) {
2005
0
        box = boxaGetBox(boxad, i, L_CLONE);
2006
0
        boxSetSide(box, side, val, thresh);
2007
0
        boxDestroy(&box);  /* the clone */
2008
0
    }
2009
2010
0
    return boxad;
2011
0
}
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
0
{
2035
0
l_int32  x, y, w, h, diff;
2036
2037
0
    if (!boxs)
2038
0
        return ERROR_INT("box not defined", __func__, 1);
2039
0
    if (side != L_SET_LEFT && side != L_SET_RIGHT &&
2040
0
        side != L_SET_TOP && side != L_SET_BOT)
2041
0
        return ERROR_INT("invalid side", __func__, 1);
2042
0
    if (val < 0)
2043
0
        return ERROR_INT("val < 0", __func__, 1);
2044
2045
0
    boxGetGeometry(boxs, &x, &y, &w, &h);
2046
0
    if (side == L_SET_LEFT) {
2047
0
        diff = x - val;
2048
0
        if (L_ABS(diff) >= thresh)
2049
0
            boxSetGeometry(boxs, val, y, w + diff, h);
2050
0
    } else if (side == L_SET_RIGHT) {
2051
0
        diff = x + w -1 - val;
2052
0
        if (L_ABS(diff) >= thresh)
2053
0
            boxSetGeometry(boxs, x, y, val - x + 1, h);
2054
0
    } else if (side == L_SET_TOP) {
2055
0
        diff = y - val;
2056
0
        if (L_ABS(diff) >= thresh)
2057
0
            boxSetGeometry(boxs, x, val, w, h + diff);
2058
0
    } else { /* side == L_SET_BOT */
2059
0
        diff = y + h - 1 - val;
2060
0
        if (L_ABS(diff) >= thresh)
2061
0
            boxSetGeometry(boxs, x, y, w, val - y + 1);
2062
0
    }
2063
2064
0
    return 0;
2065
0
}
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
0
{
2096
0
l_int32  x, y, w, h, n, i, diff;
2097
0
BOX     *box;
2098
2099
0
    if (!boxas)
2100
0
        return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
2101
0
    if (boxad && (boxas != boxad))
2102
0
        return (BOXA *)ERROR_PTR("not in-place", __func__, NULL);
2103
0
    if (sides != L_ADJUST_LEFT && sides != L_ADJUST_RIGHT &&
2104
0
        sides != L_ADJUST_LEFT_AND_RIGHT)
2105
0
        return (BOXA *)ERROR_PTR("invalid sides", __func__, NULL);
2106
0
    if (target < 1)
2107
0
        return (BOXA *)ERROR_PTR("target < 1", __func__, NULL);
2108
2109
0
    if (!boxad)
2110
0
        boxad = boxaCopy(boxas, L_COPY);
2111
0
    n = boxaGetCount(boxad);
2112
0
    for (i = 0; i < n; i++) {
2113
0
        if ((box = boxaGetValidBox(boxad, i, L_CLONE)) == NULL)
2114
0
            continue;
2115
0
        boxGetGeometry(box, &x, &y, &w, &h);
2116
0
        diff = w - target;
2117
0
        if (sides == L_ADJUST_LEFT) {
2118
0
            if (L_ABS(diff) >= thresh)
2119
0
                boxSetGeometry(box, L_MAX(0, x + diff), y, target, h);
2120
0
        } else if (sides == L_ADJUST_RIGHT) {
2121
0
            if (L_ABS(diff) >= thresh)
2122
0
                boxSetGeometry(box, x, y, target, h);
2123
0
        } else { /* sides == L_ADJUST_LEFT_AND_RIGHT */
2124
0
            if (L_ABS(diff) >= thresh)
2125
0
                boxSetGeometry(box, L_MAX(0, x + diff/2), y, target, h);
2126
0
        }
2127
0
        boxDestroy(&box);
2128
0
    }
2129
2130
0
    return boxad;
2131
0
}
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
0
{
2162
0
l_int32  x, y, w, h, n, i, diff;
2163
0
BOX     *box;
2164
2165
0
    if (!boxas)
2166
0
        return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
2167
0
    if (boxad && (boxas != boxad))
2168
0
        return (BOXA *)ERROR_PTR("not in-place", __func__, NULL);
2169
0
    if (sides != L_ADJUST_TOP && sides != L_ADJUST_BOT &&
2170
0
        sides != L_ADJUST_TOP_AND_BOT)
2171
0
        return (BOXA *)ERROR_PTR("invalid sides", __func__, NULL);
2172
0
    if (target < 1)
2173
0
        return (BOXA *)ERROR_PTR("target < 1", __func__, NULL);
2174
2175
0
    if (!boxad)
2176
0
        boxad = boxaCopy(boxas, L_COPY);
2177
0
    n = boxaGetCount(boxad);
2178
0
    for (i = 0; i < n; i++) {
2179
0
        if ((box = boxaGetValidBox(boxad, i, L_CLONE)) == NULL)
2180
0
            continue;
2181
0
        boxGetGeometry(box, &x, &y, &w, &h);
2182
0
        diff = h - target;
2183
0
        if (sides == L_ADJUST_TOP) {
2184
0
            if (L_ABS(diff) >= thresh)
2185
0
                boxSetGeometry(box, x, L_MAX(0, y + diff), w, target);
2186
0
        } else if (sides == L_ADJUST_BOT) {
2187
0
            if (L_ABS(diff) >= thresh)
2188
0
                boxSetGeometry(box, x, y, w, target);
2189
0
        } else { /* sides == L_ADJUST_TOP_AND_BOT */
2190
0
            if (L_ABS(diff) >= thresh)
2191
0
                boxSetGeometry(box, x, L_MAX(0, y + diff/2), w, target);
2192
0
        }
2193
0
        boxDestroy(&box);
2194
0
    }
2195
2196
0
    return boxad;
2197
0
}
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
0
{
2213
0
    if (!psame)
2214
0
        return ERROR_INT("&same not defined", __func__, 1);
2215
0
    *psame = 0;
2216
0
    if (!box1 || !box2)
2217
0
        return ERROR_INT("boxes not both defined", __func__, 1);
2218
0
    if (box1->x == box2->x && box1->y == box2->y &&
2219
0
        box1->w == box2->w && box1->h == box2->h)
2220
0
        *psame = 1;
2221
0
    return 0;
2222
0
}
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
0
{
2260
0
l_int32   i, j, n, jstart, jend, found, samebox;
2261
0
l_int32  *countarray;
2262
0
BOX      *box1, *box2;
2263
0
NUMA     *na;
2264
2265
0
    if (pnaindex) *pnaindex = NULL;
2266
0
    if (!psame)
2267
0
        return ERROR_INT("&same not defined", __func__, 1);
2268
0
    *psame = 0;
2269
0
    if (!boxa1 || !boxa2)
2270
0
        return ERROR_INT("boxa1 and boxa2 not both defined", __func__, 1);
2271
0
    n = boxaGetCount(boxa1);
2272
0
    if (n != boxaGetCount(boxa2))
2273
0
        return 0;
2274
2275
0
    if ((countarray = (l_int32 *)LEPT_CALLOC(n, sizeof(l_int32))) == NULL)
2276
0
        return ERROR_INT("calloc fail for countarray", __func__, 1);
2277
0
    na = numaMakeConstant(0.0, n);
2278
2279
0
    for (i = 0; i < n; i++) {
2280
0
        box1 = boxaGetBox(boxa1, i, L_CLONE);
2281
0
        jstart = L_MAX(0, i - maxdist);
2282
0
        jend = L_MIN(n-1, i + maxdist);
2283
0
        found = FALSE;
2284
0
        for (j = jstart; j <= jend; j++) {
2285
0
            box2 = boxaGetBox(boxa2, j, L_CLONE);
2286
0
            boxEqual(box1, box2, &samebox);
2287
0
            if (samebox && countarray[j] == 0) {
2288
0
                countarray[j] = 1;
2289
0
                numaReplaceNumber(na, i, j);
2290
0
                found = TRUE;
2291
0
                boxDestroy(&box2);
2292
0
                break;
2293
0
            }
2294
0
            boxDestroy(&box2);
2295
0
        }
2296
0
        boxDestroy(&box1);
2297
0
        if (!found) {
2298
0
            numaDestroy(&na);
2299
0
            LEPT_FREE(countarray);
2300
0
            return 0;
2301
0
        }
2302
0
    }
2303
2304
0
    *psame = 1;
2305
0
    if (pnaindex)
2306
0
        *pnaindex = na;
2307
0
    else
2308
0
        numaDestroy(&na);
2309
0
    LEPT_FREE(countarray);
2310
0
    return 0;
2311
0
}
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
0
{
2339
0
l_int32  l1, l2, r1, r2, t1, t2, b1, b2, valid1, valid2;
2340
2341
0
    if (!psimilar)
2342
0
        return ERROR_INT("&similar not defined", __func__, 1);
2343
0
    *psimilar = 0;
2344
0
    if (!box1 || !box2)
2345
0
        return ERROR_INT("boxes not both defined", __func__, 1);
2346
0
    boxIsValid(box1, &valid1);
2347
0
    boxIsValid(box2, &valid2);
2348
0
    if (!valid1 || !valid2)
2349
0
        return ERROR_INT("boxes not both valid", __func__, 1);
2350
2351
0
    boxGetSideLocations(box1, &l1, &r1, &t1, &b1);
2352
0
    boxGetSideLocations(box2, &l2, &r2, &t2, &b2);
2353
0
    if (L_ABS(l1 - l2) > leftdiff)
2354
0
        return 0;
2355
0
    if (L_ABS(r1 - r2) > rightdiff)
2356
0
        return 0;
2357
0
    if (L_ABS(t1 - t2) > topdiff)
2358
0
        return 0;
2359
0
    if (L_ABS(b1 - b2) > botdiff)
2360
0
        return 0;
2361
2362
0
    *psimilar = 1;
2363
0
    return 0;
2364
0
}
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
0
{
2398
0
l_int32  i, n1, n2, match, mismatch;
2399
0
BOX     *box1, *box2;
2400
2401
0
    if (psimilar) *psimilar = 0;
2402
0
    if (pnasim) *pnasim = NULL;
2403
0
    if (!boxa1 || !boxa2)
2404
0
        return ERROR_INT("boxa1 and boxa2 not both defined", __func__, 1);
2405
0
    if (!psimilar)
2406
0
        return ERROR_INT("&similar not defined", __func__, 1);
2407
0
    n1 = boxaGetCount(boxa1);
2408
0
    n2 = boxaGetCount(boxa2);
2409
0
    if (n1 != n2) {
2410
0
        L_ERROR("boxa counts differ: %d vs %d\n", __func__, n1, n2);
2411
0
        return 1;
2412
0
    }
2413
0
    if (pnasim) *pnasim = numaCreate(n1);
2414
2415
0
    mismatch = FALSE;
2416
0
    for (i = 0; i < n1; i++) {
2417
0
        box1 = boxaGetBox(boxa1, i, L_CLONE);
2418
0
        box2 = boxaGetBox(boxa2, i, L_CLONE);
2419
0
        boxSimilar(box1, box2, leftdiff, rightdiff, topdiff, botdiff,
2420
0
                   &match);
2421
0
        boxDestroy(&box1);
2422
0
        boxDestroy(&box2);
2423
0
        if (pnasim)
2424
0
            numaAddNumber(*pnasim, match);
2425
0
        if (!match) {
2426
0
            mismatch = TRUE;
2427
0
            if (!debug && pnasim == NULL)
2428
0
                return 0;
2429
0
            else if (debug)
2430
0
                L_INFO("box %d not similar\n", __func__, i);
2431
0
        }
2432
0
    }
2433
2434
0
    if (!mismatch) *psimilar = 1;
2435
0
    return 0;
2436
0
}
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
0
{
2465
0
l_int32  n, i;
2466
0
BOX     *box;
2467
2468
0
    if (!boxad)
2469
0
        return ERROR_INT("boxad not defined", __func__, 1);
2470
0
    if (!boxas || ((n = boxaGetCount(boxas)) == 0))
2471
0
        return 0;
2472
2473
0
    if (istart < 0)
2474
0
        istart = 0;
2475
0
    if (iend < 0 || iend >= n)
2476
0
        iend = n - 1;
2477
0
    if (istart > iend)
2478
0
        return ERROR_INT("istart > iend; nothing to add", __func__, 1);
2479
2480
0
    for (i = istart; i <= iend; i++) {
2481
0
        box = boxaGetBox(boxas, i, L_CLONE);
2482
0
        boxaAddBox(boxad, box, L_INSERT);
2483
0
    }
2484
2485
0
    return 0;
2486
0
}
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
0
{
2512
0
l_int32  n, i;
2513
0
BOXA    *boxa;
2514
2515
0
    if (!baad)
2516
0
        return ERROR_INT("baad not defined", __func__, 1);
2517
0
    if (!baas)
2518
0
        return 0;
2519
2520
0
    if (istart < 0)
2521
0
        istart = 0;
2522
0
    n = boxaaGetCount(baas);
2523
0
    if (iend < 0 || iend >= n)
2524
0
        iend = n - 1;
2525
0
    if (istart > iend)
2526
0
        return ERROR_INT("istart > iend; nothing to add", __func__, 1);
2527
2528
0
    for (i = istart; i <= iend; i++) {
2529
0
        boxa = boxaaGetBoxa(baas, i, L_CLONE);
2530
0
        boxaaAddBoxa(baad, boxa, L_INSERT);
2531
0
    }
2532
2533
0
    return 0;
2534
0
}
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
0
{
2560
0
l_int32  i, n;
2561
0
BOX     *box, *box1;
2562
2563
0
    if (pboxae) *pboxae = NULL;
2564
0
    if (pboxao) *pboxao = NULL;
2565
0
    if (!pboxae || !pboxao)
2566
0
        return ERROR_INT("&boxae and &boxao not both defined", __func__, 1);
2567
0
    if (!boxa)
2568
0
        return ERROR_INT("boxa not defined", __func__, 1);
2569
2570
0
    n = boxaGetCount(boxa);
2571
0
    *pboxae = boxaCreate(n);
2572
0
    *pboxao = boxaCreate(n);
2573
0
    if (fillflag == 0) {
2574
            /* don't fill with invalid boxes; end up with half-size boxa */
2575
0
        for (i = 0; i < n; i++) {
2576
0
            box = boxaGetBox(boxa, i, L_COPY);
2577
0
            if ((i & 1) == 0)
2578
0
                boxaAddBox(*pboxae, box, L_INSERT);
2579
0
            else
2580
0
                boxaAddBox(*pboxao, box, L_INSERT);
2581
0
        }
2582
0
    } else {
2583
0
        for (i = 0; i < n; i++) {
2584
0
            box = boxaGetBox(boxa, i, L_COPY);
2585
0
            box1 = boxCreate(0, 0, 0, 0);  /* empty placeholder */
2586
0
            if ((i & 1) == 0) {
2587
0
                boxaAddBox(*pboxae, box, L_INSERT);
2588
0
                boxaAddBox(*pboxao, box1, L_INSERT);
2589
0
            } else {
2590
0
                boxaAddBox(*pboxae, box1, L_INSERT);
2591
0
                boxaAddBox(*pboxao, box, L_INSERT);
2592
0
            }
2593
0
        }
2594
0
    }
2595
0
    return 0;
2596
0
}
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
0
{
2621
0
l_int32  i, n, ne, no;
2622
0
BOX     *box;
2623
0
BOXA    *boxad;
2624
2625
0
    if (!boxae || !boxao)
2626
0
        return (BOXA *)ERROR_PTR("boxae and boxao not defined", __func__, NULL);
2627
0
    ne = boxaGetCount(boxae);
2628
0
    no = boxaGetCount(boxao);
2629
0
    if (ne < no || ne > no + 1)
2630
0
        return (BOXA *)ERROR_PTR("boxa sizes invalid", __func__, NULL);
2631
2632
0
    boxad = boxaCreate(ne);
2633
0
    if (fillflag == 0) {  /* both are approx. half-sized; all valid boxes */
2634
0
        n = ne + no;
2635
0
        for (i = 0; i < n; i++) {
2636
0
            if ((i & 1) == 0)
2637
0
                box = boxaGetBox(boxae, i / 2, L_COPY);
2638
0
            else
2639
0
                box = boxaGetBox(boxao, i / 2, L_COPY);
2640
0
            boxaAddBox(boxad, box, L_INSERT);
2641
0
        }
2642
0
    } else {  /* both are full size and have invalid placeholders */
2643
0
        for (i = 0; i < ne; i++) {
2644
0
            if ((i & 1) == 0)
2645
0
                box = boxaGetBox(boxae, i, L_COPY);
2646
0
            else
2647
0
                box = boxaGetBox(boxao, i, L_COPY);
2648
0
            boxaAddBox(boxad, box, L_INSERT);
2649
0
        }
2650
0
    }
2651
0
    return boxad;
2652
0
}