boxfunc1.c

Go to the documentation of this file.

/*====================================================================*
 -  Copyright (C) 2001 Leptonica.  All rights reserved.
 -
 -  Redistribution and use in source and binary forms, with or without
 -  modification, are permitted provided that the following conditions
 -  are met:
 -  1. Redistributions of source code must retain the above copyright
 -     notice, this list of conditions and the following disclaimer.
 -  2. Redistributions in binary form must reproduce the above
 -     copyright notice, this list of conditions and the following
 -     disclaimer in the documentation and/or other materials
 -     provided with the distribution.
 -
 -  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 -  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 -  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 -  A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL ANY
 -  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 -  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 -  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 -  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 -  OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 -  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 -  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *====================================================================*/

#include "allheaders.h"

static l_int32 boxHasOverlapInXorY(l_int32 c1, l_int32 s1, l_int32 c2,
                                   l_int32 s2);
static l_int32 boxGetDistanceInXorY(l_int32 c1, l_int32 s1, l_int32 c2,
                                    l_int32 s2);


/*---------------------------------------------------------------------*
 *                             Box geometry                            *
 *---------------------------------------------------------------------*/
l_int32
boxContains(BOX     *box1,
            BOX     *box2,
            l_int32 *presult)
{
l_int32  x1, y1, w1, h1, x2, y2, w2, h2;

    PROCNAME("boxContains");

    if (!presult)
        return ERROR_INT("&result not defined", procName, 1);
    *presult = 0;
    if (!box1 || !box2)
        return ERROR_INT("box1 and box2 not both defined", procName, 1);

    boxGetGeometry(box1, &x1, &y1, &w1, &h1);
    boxGetGeometry(box2, &x2, &y2, &w2, &h2);
    if (x1 <= x2 && y1 <= y2 && (x1 + w1 >= x2 + w2) && (y1 + h1 >= y2 + h2))
        *presult = 1;
    return 0;
}


l_int32
boxIntersects(BOX      *box1,
              BOX      *box2,
              l_int32  *presult)
{
l_int32  l1, l2, r1, r2, t1, t2, b1, b2, w1, h1, w2, h2;

    PROCNAME("boxIntersects");

    if (!presult)
        return ERROR_INT("&result not defined", procName, 1);
    *presult = 0;
    if (!box1 || !box2)
        return ERROR_INT("box1 and box2 not both defined", procName, 1);

    boxGetGeometry(box1, &l1, &t1, &w1, &h1);
    boxGetGeometry(box2, &l2, &t2, &w2, &h2);
    r1 = l1 + w1 - 1;
    r2 = l2 + w2 - 1;
    b1 = t1 + h1 - 1;
    b2 = t2 + h2 - 1;
    if (b2 < t1 || b1 < t2 || r1 < l2 || r2 < l1)
        *presult = 0;
    else
        *presult = 1;
    return 0;
}


BOXA *
boxaContainedInBox(BOXA  *boxas,
                   BOX   *box)
{
l_int32  i, n, val;
BOX     *boxt;
BOXA    *boxad;

    PROCNAME("boxaContainedInBox");

    if (!boxas)
        return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
    if (!box)
        return (BOXA *)ERROR_PTR("box not defined", procName, NULL);
    if ((n = boxaGetCount(boxas)) == 0)
        return boxaCreate(1);  /* empty */

    boxad = boxaCreate(0);
    for (i = 0; i < n; i++) {
        boxt = boxaGetBox(boxas, i, L_CLONE);
        boxContains(box, boxt, &val);
        if (val == 1)
            boxaAddBox(boxad, boxt, L_COPY);
        boxDestroy(&boxt);  /* destroy the clone */
    }

    return boxad;
}


l_int32
boxaContainedInBoxCount(BOXA     *boxa,
                        BOX      *box,
                        l_int32  *pcount)
{
l_int32  i, n, val;
BOX     *box1;

    PROCNAME("boxaContainedInBoxCount");

    if (!pcount)
        return ERROR_INT("&count not defined", procName, 1);
    *pcount = 0;
    if (!boxa)
        return ERROR_INT("boxa not defined", procName, 1);
    if (!box)
        return ERROR_INT("box not defined", procName, 1);
    if ((n = boxaGetCount(boxa)) == 0)
        return 0;

    for (i = 0; i < n; i++) {
        box1 = boxaGetBox(boxa, i, L_CLONE);
        boxContains(box, box1, &val);
        if (val == 1)
            (*pcount)++;
        boxDestroy(&box1);
    }
    return 0;
}


l_int32
boxaContainedInBoxa(BOXA     *boxa1,
                    BOXA     *boxa2,
                    l_int32  *pcontained)
{
l_int32  i, j, n1, n2, cont, result;
BOX     *box1, *box2;

    PROCNAME("boxaContainedInBoxa");

    if (!pcontained)
        return ERROR_INT("&contained not defined", procName, 1);
    *pcontained = 0;
    if (!boxa1 || !boxa2)
        return ERROR_INT("boxa1 and boxa2 not both defined", procName, 1);

    n1 = boxaGetCount(boxa1);
    n2 = boxaGetCount(boxa2);
    for (i = 0; i < n2; i++) {
        box2 = boxaGetBox(boxa2, i, L_CLONE);
        cont = 0;
        for (j = 0; j < n1; j++) {
            box1 = boxaGetBox(boxa1, j, L_CLONE);
            boxContains(box1, box2, &result);
            boxDestroy(&box1);
            if (result) {
                cont = 1;
                break;
            }
        }
        boxDestroy(&box2);
        if (!cont) return 0;
    }

    *pcontained = 1;
    return 0;
}


BOXA *
boxaIntersectsBox(BOXA  *boxas,
                  BOX   *box)
{
l_int32  i, n, val;
BOX     *boxt;
BOXA    *boxad;

    PROCNAME("boxaIntersectsBox");

    if (!boxas)
        return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
    if (!box)
        return (BOXA *)ERROR_PTR("box not defined", procName, NULL);
    if ((n = boxaGetCount(boxas)) == 0)
        return boxaCreate(1);  /* empty */

    boxad = boxaCreate(0);
    for (i = 0; i < n; i++) {
        boxt = boxaGetBox(boxas, i, L_CLONE);
        boxIntersects(box, boxt, &val);
        if (val == 1)
            boxaAddBox(boxad, boxt, L_COPY);
        boxDestroy(&boxt);  /* destroy the clone */
    }

    return boxad;
}


l_int32
boxaIntersectsBoxCount(BOXA     *boxa,
                       BOX      *box,
                       l_int32  *pcount)
{
l_int32  i, n, val;
BOX     *box1;

    PROCNAME("boxaIntersectsBoxCount");

    if (!pcount)
        return ERROR_INT("&count not defined", procName, 1);
    *pcount = 0;
    if (!boxa)
        return ERROR_INT("boxa not defined", procName, 1);
    if (!box)
        return ERROR_INT("box not defined", procName, 1);
    if ((n = boxaGetCount(boxa)) == 0)
        return 0;

    for (i = 0; i < n; i++) {
        box1 = boxaGetBox(boxa, i, L_CLONE);
        boxIntersects(box, box1, &val);
        if (val == 1)
            (*pcount)++;
        boxDestroy(&box1);
    }
    return 0;
}


BOXA *
boxaClipToBox(BOXA  *boxas,
              BOX   *box)
{
l_int32  i, n;
BOX     *boxt, *boxo;
BOXA    *boxad;

    PROCNAME("boxaClipToBox");

    if (!boxas)
        return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
    if (!box)
        return (BOXA *)ERROR_PTR("box not defined", procName, NULL);
    if ((n = boxaGetCount(boxas)) == 0)
        return boxaCreate(1);  /* empty */

    boxad = boxaCreate(0);
    for (i = 0; i < n; i++) {
        boxt = boxaGetBox(boxas, i, L_CLONE);
        if ((boxo = boxOverlapRegion(box, boxt)) != NULL)
            boxaAddBox(boxad, boxo, L_INSERT);
        boxDestroy(&boxt);
    }

    return boxad;
}


BOXA *
boxaCombineOverlaps(BOXA  *boxas,
                    PIXA  *pixadb)
{
l_int32  i, j, w, h, n1, n2, overlap, niters;
BOX     *box1, *box2, *box3;
BOXA    *boxa1, *boxa2;
PIX     *pix1;

    PROCNAME("boxaCombineOverlaps");

    if (!boxas)
        return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);

    if (pixadb) boxaGetExtent(boxas, &w, &h, NULL);

    boxa1 = boxaCopy(boxas, L_COPY);
    n1 = boxaGetCount(boxa1);
    niters = 0;
    while (1) {  /* loop until no change from previous iteration */
        niters++;
        if (pixadb) {
            pix1 = pixCreate(w + 5, h + 5, 32);
            pixSetAll(pix1);
            pixRenderBoxaArb(pix1, boxa1, 2, 255, 0, 0);
            pixaAddPix(pixadb, pix1, L_COPY);
        }

            /* Combine overlaps for this iteration */
        for (i = 0; i < n1; i++) {
            if ((box1 = boxaGetValidBox(boxa1, i, L_COPY)) == NULL)
                continue;
            for (j = i + 1; j < n1; j++) {
                if ((box2 = boxaGetValidBox(boxa1, j, L_COPY)) == NULL)
                    continue;
                boxIntersects(box1, box2, &overlap);
                if (overlap) {
                    box3 = boxBoundingRegion(box1, box2);
                    boxaReplaceBox(boxa1, i, box3);
                    boxaReplaceBox(boxa1, j, boxCreate(0, 0, 0, 0));
                    boxDestroy(&box1);
                    box1 = boxCopy(box3);
                }
                boxDestroy(&box2);
            }
            boxDestroy(&box1);
        }
        boxa2 = boxaSaveValid(boxa1, L_COPY);
        n2 = boxaGetCount(boxa2);
        boxaDestroy(&boxa1);
        boxa1 = boxa2;
        if (n1 == n2) {
            if (pixadb) pixDestroy(&pix1);
            break;
        }
        n1 = n2;
        if (pixadb) {
            pixRenderBoxaArb(pix1, boxa1, 2, 0, 255, 0);
            pixaAddPix(pixadb, pix1, L_INSERT);
        }
    }

    if (pixadb)
        L_INFO("number of iterations: %d\n", procName, niters);
    return boxa1;
}


l_int32
boxaCombineOverlapsInPair(BOXA   *boxas1,
                          BOXA   *boxas2,
                          BOXA  **pboxad1,
                          BOXA  **pboxad2,
                          PIXA   *pixadb)
{
l_int32  i, j, w, h, w2, h2, n1, n2, n1i, n2i, niters;
l_int32  overlap, bigger, area1, area2;
BOX     *box1, *box2, *box3;
BOXA    *boxa1, *boxa2, *boxac1, *boxac2;
PIX     *pix1;

    PROCNAME("boxaCombineOverlapsInPair");

    if (pboxad1) *pboxad1 = NULL;
    if (pboxad2) *pboxad2 = NULL;
    if (!boxas1 || !boxas2)
        return ERROR_INT("boxas1 and boxas2 not both defined", procName, 1);
    if (!pboxad1 || !pboxad2)
        return ERROR_INT("&boxad1 and &boxad2 not both defined", procName, 1);

    if (pixadb) {
        boxaGetExtent(boxas1, &w, &h, NULL);
        boxaGetExtent(boxas2, &w2, &h2, NULL);
        w = L_MAX(w, w2);
        h = L_MAX(h, w2);
    }

        /* Let the boxa with the largest area have first crack at the other */
    boxaGetArea(boxas1, &area1);
    boxaGetArea(boxas2, &area2);
    if (area1 >= area2) {
        boxac1 = boxaCopy(boxas1, L_COPY);
        boxac2 = boxaCopy(boxas2, L_COPY);
    } else {
        boxac1 = boxaCopy(boxas2, L_COPY);
        boxac2 = boxaCopy(boxas1, L_COPY);
    }

    n1i = boxaGetCount(boxac1);
    n2i = boxaGetCount(boxac2);
    niters = 0;
    while (1) {
        niters++;
        if (pixadb) {
            pix1 = pixCreate(w + 5, h + 5, 32);
            pixSetAll(pix1);
            pixRenderBoxaArb(pix1, boxac1, 2, 255, 0, 0);
            pixRenderBoxaArb(pix1, boxac2, 2, 0, 255, 0);
            pixaAddPix(pixadb, pix1, L_INSERT);
        }

            /* First combine boxes in each set */
        boxa1 = boxaCombineOverlaps(boxac1, NULL);
        boxa2 = boxaCombineOverlaps(boxac2, NULL);

            /* Now combine boxes between sets */
        n1 = boxaGetCount(boxa1);
        n2 = boxaGetCount(boxa2);
        for (i = 0; i < n1; i++) {  /* 1 eats 2 */
            if ((box1 = boxaGetValidBox(boxa1, i, L_COPY)) == NULL)
                continue;
            for (j = 0; j < n2; j++) {
                if ((box2 = boxaGetValidBox(boxa2, j, L_COPY)) == NULL)
                    continue;
                boxIntersects(box1, box2, &overlap);
                boxCompareSize(box1, box2, L_SORT_BY_AREA, &bigger);
                if (overlap && (bigger == 1)) {
                    box3 = boxBoundingRegion(box1, box2);
                    boxaReplaceBox(boxa1, i, box3);
                    boxaReplaceBox(boxa2, j, boxCreate(0, 0, 0, 0));
                    boxDestroy(&box1);
                    box1 = boxCopy(box3);
                }
                boxDestroy(&box2);
            }
            boxDestroy(&box1);
        }
        for (i = 0; i < n2; i++) {  /* 2 eats 1 */
            if ((box2 = boxaGetValidBox(boxa2, i, L_COPY)) == NULL)
                continue;
            for (j = 0; j < n1; j++) {
                if ((box1 = boxaGetValidBox(boxa1, j, L_COPY)) == NULL)
                    continue;
                boxIntersects(box1, box2, &overlap);
                boxCompareSize(box2, box1, L_SORT_BY_AREA, &bigger);
                if (overlap && (bigger == 1)) {
                    box3 = boxBoundingRegion(box1, box2);
                    boxaReplaceBox(boxa2, i, box3);
                    boxaReplaceBox(boxa1, j, boxCreate(0, 0, 0, 0));
                    boxDestroy(&box2);
                    box2 = boxCopy(box3);
                }
                boxDestroy(&box1);
            }
            boxDestroy(&box2);
        }
        boxaDestroy(&boxac1);
        boxaDestroy(&boxac2);
        boxac1 = boxaSaveValid(boxa1, L_COPY);  /* remove invalid boxes */
        boxac2 = boxaSaveValid(boxa2, L_COPY);
        boxaDestroy(&boxa1);
        boxaDestroy(&boxa2);
        n1 = boxaGetCount(boxac1);
        n2 = boxaGetCount(boxac2);
        if (n1 == n1i && n2 == n2i) break;
        n1i = n1;
        n2i = n2;
        if (pixadb) {
            pix1 = pixCreate(w + 5, h + 5, 32);
            pixSetAll(pix1);
            pixRenderBoxaArb(pix1, boxac1, 2, 255, 0, 0);
            pixRenderBoxaArb(pix1, boxac2, 2, 0, 255, 0);
            pixaAddPix(pixadb, pix1, L_INSERT);
        }
    }

    if (pixadb)
        L_INFO("number of iterations: %d\n", procName, niters);
    *pboxad1 = boxac1;
    *pboxad2 = boxac2;
    return 0;
}


BOX *
boxOverlapRegion(BOX  *box1,
                 BOX  *box2)
{
l_int32  l1, l2, r1, r2, t1, t2, b1, b2, w1, h1, w2, h2, ld, td, rd, bd;

    PROCNAME("boxOverlapRegion");

    if (!box1)
        return (BOX *)ERROR_PTR("box1 not defined", procName, NULL);
    if (!box2)
        return (BOX *)ERROR_PTR("box2 not defined", procName, NULL);

    boxGetGeometry(box1, &l1, &t1, &w1, &h1);
    boxGetGeometry(box2, &l2, &t2, &w2, &h2);
    r1 = l1 + w1 - 1;
    r2 = l2 + w2 - 1;
    b1 = t1 + h1 - 1;
    b2 = t2 + h2 - 1;
    if (b2 < t1 || b1 < t2 || r1 < l2 || r2 < l1)
        return NULL;

    ld = L_MAX(l1, l2);
    td = L_MAX(t1, t2);
    rd = L_MIN(r1, r2);
    bd = L_MIN(b1, b2);
    return boxCreate(ld, td, rd - ld + 1, bd - td + 1);
}


BOX *
boxBoundingRegion(BOX  *box1,
                  BOX  *box2)
{
l_int32  l1, l2, r1, r2, t1, t2, b1, b2, w1, h1, w2, h2, ld, td, rd, bd;

    PROCNAME("boxBoundingRegion");

    if (!box1)
        return (BOX *)ERROR_PTR("box1 not defined", procName, NULL);
    if (!box2)
        return (BOX *)ERROR_PTR("box2 not defined", procName, NULL);

    boxGetGeometry(box1, &l1, &t1, &w1, &h1);
    boxGetGeometry(box2, &l2, &t2, &w2, &h2);
    r1 = l1 + w1 - 1;
    r2 = l2 + w2 - 1;
    b1 = t1 + h1 - 1;
    b2 = t2 + h2 - 1;
    ld = L_MIN(l1, l2);
    td = L_MIN(t1, t2);
    rd = L_MAX(r1, r2);
    bd = L_MAX(b1, b2);
    return boxCreate(ld, td, rd - ld + 1, bd - td + 1);
}


l_int32
boxOverlapFraction(BOX        *box1,
                   BOX        *box2,
                   l_float32  *pfract)
{
l_int32  w2, h2, w, h;
BOX     *boxo;

    PROCNAME("boxOverlapFraction");

    if (!pfract)
        return ERROR_INT("&fract not defined", procName, 1);
    *pfract = 0.0;
    if (!box1)
        return ERROR_INT("box1 not defined", procName, 1);
    if (!box2)
        return ERROR_INT("box2 not defined", procName, 1);

    if ((boxo = boxOverlapRegion(box1, box2)) == NULL)  /* no overlap */
        return 0;

    boxGetGeometry(box2, NULL, NULL, &w2, &h2);
    boxGetGeometry(boxo, NULL, NULL, &w, &h);
    *pfract = (l_float32)(w * h) / (l_float32)(w2 * h2);
    boxDestroy(&boxo);
    return 0;
}


l_int32
boxOverlapArea(BOX      *box1,
               BOX      *box2,
               l_int32  *parea)
{
l_int32  w, h;
BOX     *box;

    PROCNAME("boxOverlapArea");

    if (!parea)
        return ERROR_INT("&area not defined", procName, 1);
    *parea = 0;
    if (!box1)
        return ERROR_INT("box1 not defined", procName, 1);
    if (!box2)
        return ERROR_INT("box2 not defined", procName, 1);

    if ((box = boxOverlapRegion(box1, box2)) == NULL)  /* no overlap */
        return 0;

    boxGetGeometry(box, NULL, NULL, &w, &h);
    *parea = w * h;
    boxDestroy(&box);
    return 0;
}


BOXA *
boxaHandleOverlaps(BOXA    *boxas,
                   l_int32  op,
                   l_int32  range,
                   l_float32  min_overlap,
                   l_float32  max_ratio,
                   NUMA   **pnamap)
{
l_int32    i, j, n, w, h, area1, area2, val;
l_int32    overlap_area;
l_float32  overlap_ratio, area_ratio;
BOX       *box1, *box2, *box3;
BOXA      *boxat, *boxad;
NUMA      *namap;

    PROCNAME("boxaHandleOverlaps");

    if (pnamap) *pnamap = NULL;
    if (!boxas)
        return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
    if (op != L_COMBINE && op != L_REMOVE_SMALL)
        return (BOXA *)ERROR_PTR("invalid op", procName, NULL);

    n = boxaGetCount(boxas);
    if (n == 0)
        return boxaCreate(1);  /* empty */
    if (range == 0) {
        L_WARNING("range is 0\n", procName);
        return boxaCopy(boxas, L_COPY);
    }

        /* Identify smaller boxes in overlap pairs, and mark to eliminate. */
    namap = numaMakeConstant(-1, n);
    for (i = 0; i < n; i++) {
        box1 = boxaGetBox(boxas, i, L_CLONE);
        boxGetGeometry(box1, NULL, NULL, &w, &h);
        area1 = w * h;
        if (area1 == 0) {
            boxDestroy(&box1);
            continue;
        }
        for (j = i + 1; j < i + 1 + range && j < n; j++) {
            box2 = boxaGetBox(boxas, j, L_CLONE);
            boxOverlapArea(box1, box2, &overlap_area);
            if (overlap_area > 0) {
                boxGetGeometry(box2, NULL, NULL, &w, &h);
                area2 = w * h;
                if (area2 == 0) {
                    /* do nothing */
                } else if (area1 >= area2) {
                    overlap_ratio = (l_float32)overlap_area / (l_float32)area2;
                    area_ratio = (l_float32)area2 / (l_float32)area1;
                    if (overlap_ratio >= min_overlap &&
                        area_ratio <= max_ratio) {
                        numaSetValue(namap, j, i);
                    }
                } else {
                    overlap_ratio = (l_float32)overlap_area / (l_float32)area1;
                    area_ratio = (l_float32)area1 / (l_float32)area2;
                    if (overlap_ratio >= min_overlap &&
                        area_ratio <= max_ratio) {
                        numaSetValue(namap, i, j);
                    }
                }
            }
            boxDestroy(&box2);
        }
        boxDestroy(&box1);
    }

    boxat = boxaCopy(boxas, L_COPY);
    if (op == L_COMBINE) {
            /* Resize the larger of the pair to the bounding region */
        for (i = 0; i < n; i++) {
            numaGetIValue(namap, i, &val);
            if (val >= 0) {
                box1 = boxaGetBox(boxas, i, L_CLONE);  /* smaller */
                box2 = boxaGetBox(boxas, val, L_CLONE);  /* larger */
                box3 = boxBoundingRegion(box1, box2);
                boxaReplaceBox(boxat, val, box3);
                boxDestroy(&box1);
                boxDestroy(&box2);
            }
        }
    }

        /* Remove the smaller of the pairs */
    boxad = boxaCreate(n);
    for (i = 0; i < n; i++) {
        numaGetIValue(namap, i, &val);
        if (val == -1) {
            box1 = boxaGetBox(boxat, i, L_COPY);
            boxaAddBox(boxad, box1, L_INSERT);
        }
    }
    boxaDestroy(&boxat);
    if (pnamap)
        *pnamap = namap;
    else
        numaDestroy(&namap);
    return boxad;
}


l_int32
boxSeparationDistance(BOX      *box1,
                      BOX      *box2,
                      l_int32  *ph_sep,
                      l_int32  *pv_sep)
{
l_int32  l1, t1, w1, h1, r1, b1, l2, t2, w2, h2, r2, b2;

    PROCNAME("boxSeparationDistance");

    if (!ph_sep && !pv_sep)
        return ERROR_INT("nothing to do", procName, 1);
    if (ph_sep) *ph_sep = 0;
    if (pv_sep) *pv_sep = 0;
    if (!box1 || !box2)
        return ERROR_INT("box1 and box2 not both defined", procName, 1);

    if (ph_sep) {
        boxGetGeometry(box1, &l1, NULL, &w1, NULL);
        boxGetGeometry(box2, &l2, NULL, &w2, NULL);
        r1 = l1 + w1;  /* 1 pixel to the right of box 1 */
        r2 = l2 + w2;
        if (l2 >= l1)
            *ph_sep = l2 - r1;
        else
            *ph_sep = l1 - r2;
    }
    if (pv_sep) {
        boxGetGeometry(box1, NULL, &t1, NULL, &h1);
        boxGetGeometry(box2, NULL, &t2, NULL, &h2);
        b1 = t1 + h1;  /* 1 pixel below box 1 */
        b2 = t2 + h2;
        if (t2 >= t1)
            *pv_sep = t2 - b1;
        else
            *pv_sep = t1 - b2;
    }
    return 0;
}


l_int32
boxCompareSize(BOX      *box1,
               BOX      *box2,
               l_int32   type,
               l_int32  *prel)
{
l_int32  w1, h1, w2, h2, size1, size2;

    PROCNAME("boxCompareSize");

    if (!prel)
        return ERROR_INT("&rel not defined", procName, 1);
    *prel = 0;
    if (!box1 || !box2)
        return ERROR_INT("box1 and box2 not both defined", procName, 1);
    if (type != L_SORT_BY_WIDTH && type != L_SORT_BY_HEIGHT &&
        type != L_SORT_BY_MAX_DIMENSION && type != L_SORT_BY_PERIMETER &&
        type != L_SORT_BY_AREA)
        return ERROR_INT("invalid compare type", procName, 1);

    boxGetGeometry(box1, NULL, NULL, &w1, &h1);
    boxGetGeometry(box2, NULL, NULL, &w2, &h2);
    if (type == L_SORT_BY_WIDTH) {
        *prel = (w1 > w2) ? 1 : ((w1 == w2) ? 0 : -1);
    } else if (type == L_SORT_BY_HEIGHT) {
        *prel = (h1 > h2) ? 1 : ((h1 == h2) ? 0 : -1);
    } else if (type == L_SORT_BY_MAX_DIMENSION) {
        size1 = L_MAX(w1, h1);
        size2 = L_MAX(w2, h2);
        *prel = (size1 > size2) ? 1 : ((size1 == size2) ? 0 : -1);
    } else if (type == L_SORT_BY_PERIMETER) {
        size1 = w1 + h1;
        size2 = w2 + h2;
        *prel = (size1 > size2) ? 1 : ((size1 == size2) ? 0 : -1);
    } else if (type == L_SORT_BY_AREA) {
        size1 = w1 * h1;
        size2 = w2 * h2;
        *prel = (size1 > size2) ? 1 : ((size1 == size2) ? 0 : -1);
    }
    return 0;
}


l_int32
boxContainsPt(BOX       *box,
              l_float32  x,
              l_float32  y,
              l_int32   *pcontains)
{
l_int32  bx, by, bw, bh;

    PROCNAME("boxContainsPt");

    if (!pcontains)
        return ERROR_INT("&contains not defined", procName, 1);
    *pcontains = 0;
    if (!box)
        return ERROR_INT("&box not defined", procName, 1);
    boxGetGeometry(box, &bx, &by, &bw, &bh);
    if (x >= bx && x < bx + bw && y >= by && y < by + bh)
        *pcontains = 1;
    return 0;
}


BOX *
boxaGetNearestToPt(BOXA    *boxa,
                   l_int32  x,
                   l_int32  y)
{
l_int32    i, n, minindex;
l_float32  delx, dely, dist, mindist, cx, cy;
BOX       *box;

    PROCNAME("boxaGetNearestToPt");

    if (!boxa)
        return (BOX *)ERROR_PTR("boxa not defined", procName, NULL);
    if ((n = boxaGetCount(boxa)) == 0)
        return (BOX *)ERROR_PTR("n = 0", procName, NULL);

    mindist = 1000000000.;
    minindex = 0;
    for (i = 0; i < n; i++) {
        box = boxaGetBox(boxa, i, L_CLONE);
        boxGetCenter(box, &cx, &cy);
        delx = (l_float32)(cx - x);
        dely = (l_float32)(cy - y);
        dist = delx * delx + dely * dely;
        if (dist < mindist) {
            minindex = i;
            mindist = dist;
        }
        boxDestroy(&box);
    }

    return boxaGetBox(boxa, minindex, L_COPY);
}


BOX *
boxaGetNearestToLine(BOXA    *boxa,
                     l_int32  x,
                     l_int32  y)
{
l_int32    i, n, minindex;
l_float32  dist, mindist, cx, cy;
BOX       *box;

    PROCNAME("boxaGetNearestToLine");

    if (!boxa)
        return (BOX *)ERROR_PTR("boxa not defined", procName, NULL);
    if ((n = boxaGetCount(boxa)) == 0)
        return (BOX *)ERROR_PTR("n = 0", procName, NULL);
    if (y >= 0 && x >= 0)
        return (BOX *)ERROR_PTR("either x or y must be < 0", procName, NULL);
    if (y < 0 && x < 0)
        return (BOX *)ERROR_PTR("either x or y must be >= 0", procName, NULL);

    mindist = 1000000000.;
    minindex = 0;
    for (i = 0; i < n; i++) {
        box = boxaGetBox(boxa, i, L_CLONE);
        boxGetCenter(box, &cx, &cy);
        if (x >= 0)
            dist = L_ABS(cx - (l_float32)x);
        else  /* y >= 0 */
            dist = L_ABS(cy - (l_float32)y);
        if (dist < mindist) {
            minindex = i;
            mindist = dist;
        }
        boxDestroy(&box);
    }

    return boxaGetBox(boxa, minindex, L_COPY);
}


l_int32
boxaFindNearestBoxes(BOXA     *boxa,
                     l_int32   dist_select,
                     l_int32   range,
                     NUMAA   **pnaaindex,
                     NUMAA   **pnaadist)
{
l_int32  i, n, index, dist;
NUMA    *nai, *nad;
NUMAA   *naai, *naad;

    PROCNAME("boxaFindNearestBoxes");

    if (pnaaindex) *pnaaindex = NULL;
    if (pnaadist) *pnaadist = NULL;
    if (!pnaaindex)
        return ERROR_INT("&naaindex not defined", procName, 1);
    if (!pnaadist)
        return ERROR_INT("&naadist not defined", procName, 1);
    if (!boxa)
        return ERROR_INT("boxa not defined", procName, 1);

    n = boxaGetCount(boxa);
    naai = numaaCreate(n);
    naad = numaaCreate(n);
    *pnaaindex = naai;
    *pnaadist = naad;
    for (i = 0; i < n; i++) {
        nai = numaCreate(4);
        nad = numaCreate(4);
        boxaGetNearestByDirection(boxa, i, L_FROM_LEFT, dist_select,
                                  range, &index, &dist);
        numaAddNumber(nai, index);
        numaAddNumber(nad, dist);
        boxaGetNearestByDirection(boxa, i, L_FROM_RIGHT, dist_select,
                                  range, &index, &dist);
        numaAddNumber(nai, index);
        numaAddNumber(nad, dist);
        boxaGetNearestByDirection(boxa, i, L_FROM_TOP, dist_select,
                                  range, &index, &dist);
        numaAddNumber(nai, index);
        numaAddNumber(nad, dist);
        boxaGetNearestByDirection(boxa, i, L_FROM_BOT, dist_select,
                                  range, &index, &dist);
        numaAddNumber(nai, index);
        numaAddNumber(nad, dist);
        numaaAddNuma(naai, nai, L_INSERT);
        numaaAddNuma(naad, nad, L_INSERT);
    }
    return 0;
}


l_int32
boxaGetNearestByDirection(BOXA     *boxa,
                          l_int32   i,
                          l_int32   dir,
                          l_int32   dist_select,
                          l_int32   range,
                          l_int32  *pindex,
                          l_int32  *pdist)
{
l_int32  j, jmin, jmax, n, mindist, dist, index;
l_int32  x, y, w, h, bx, by, bw, bh;

    PROCNAME("boxaGetNearestByDirection");

    if (pindex) *pindex = -1;
    if (pdist) *pdist = 100000;
    if (!pindex)
        return ERROR_INT("&index not defined", procName, 1);
    if (!pdist)
        return ERROR_INT("&dist not defined", procName, 1);
    if (!boxa)
        return ERROR_INT("boxa not defined", procName, 1);
    if (dir != L_FROM_LEFT && dir != L_FROM_RIGHT &&
        dir != L_FROM_TOP && dir != L_FROM_BOT)
        return ERROR_INT("invalid dir", procName, 1);
    if (dist_select != L_NON_NEGATIVE && dist_select != L_ALL)
        return ERROR_INT("invalid dist_select", procName, 1);
    n = boxaGetCount(boxa);
    if (i < 0 || i >= n)
        return ERROR_INT("invalid box index", procName, 1);

    jmin = (range <= 0) ? 0 : L_MAX(0, i - range);
    jmax = (range <= 0) ? n - 1 : L_MIN(n -1, i + range);
    boxaGetBoxGeometry(boxa, i, &x, &y, &w, &h);
    mindist = 100000;
    index = -1;
    if (dir == L_FROM_LEFT || dir == L_FROM_RIGHT) {
        for (j = jmin; j <= jmax; j++) {
            if (j == i) continue;
            boxaGetBoxGeometry(boxa, j, &bx, &by, &bw, &bh);
            if ((bx >= x && dir == L_FROM_LEFT) ||  /* not to the left */
                (x >= bx && dir == L_FROM_RIGHT))   /* not to the right */
                continue;
            if (boxHasOverlapInXorY(y, h, by, bh) == 1) {
                dist = boxGetDistanceInXorY(x, w, bx, bw);
                if (dist_select == L_NON_NEGATIVE && dist < 0) continue;
                if (dist < mindist) {
                    mindist = dist;
                    index = j;
                }
            }
        }
    } else if (dir == L_FROM_TOP || dir == L_FROM_BOT) {
        for (j = jmin; j <= jmax; j++) {
            if (j == i) continue;
            boxaGetBoxGeometry(boxa, j, &bx, &by, &bw, &bh);
            if ((by >= y && dir == L_FROM_TOP) ||  /* not above */
                (y >= by && dir == L_FROM_BOT))   /* not below */
                continue;
            if (boxHasOverlapInXorY(x, w, bx, bw) == 1) {
                dist = boxGetDistanceInXorY(y, h, by, bh);
                if (dist_select == L_NON_NEGATIVE && dist < 0) continue;
                if (dist < mindist) {
                    mindist = dist;
                    index = j;
                }
            }
        }
    }
    *pindex = index;
    *pdist = mindist;
    return 0;
}


static l_int32
boxHasOverlapInXorY(l_int32  c1,
                    l_int32  s1,
                    l_int32  c2,
                    l_int32  s2)
{
l_int32  ovlp;

    if (c1 > c2)
        ovlp = c2 + s2 - 1 - c1;
    else
        ovlp = c1 + s1 - 1 - c2;
    return (ovlp < 0) ? 0 : 1;
}


static l_int32
boxGetDistanceInXorY(l_int32  c1,
                     l_int32  s1,
                     l_int32  c2,
                     l_int32  s2)
{
l_int32  dist;

    if (c1 > c2)
        dist = c1 - (c2 + s2 - 1);
    else
        dist = c2 - (c1 + s1 - 1);
    return dist;
}


l_int32
boxGetCenter(BOX        *box,
             l_float32  *pcx,
             l_float32  *pcy)
{
l_int32  x, y, w, h;

    PROCNAME("boxGetCenter");

    if (pcx) *pcx = 0;
    if (pcy) *pcy = 0;
    if (!pcx || !pcy)
        return ERROR_INT("&cx, &cy not both defined", procName, 1);
    if (!box)
        return ERROR_INT("box not defined", procName, 1);
    boxGetGeometry(box, &x, &y, &w, &h);
    *pcx = (l_float32)(x + 0.5 * w);
    *pcy = (l_float32)(y + 0.5 * h);

    return 0;
}


l_int32
boxIntersectByLine(BOX       *box,
                   l_int32    x,
                   l_int32    y,
                   l_float32  slope,
                   l_int32   *px1,
                   l_int32   *py1,
                   l_int32   *px2,
                   l_int32   *py2,
                   l_int32   *pn)
{
l_int32    bx, by, bw, bh, xp, yp, xt, yt, i, n;
l_float32  invslope;
PTA       *pta;

    PROCNAME("boxIntersectByLine");

    if (px1) *px1 = 0;
    if (px2) *px2 = 0;
    if (py1) *py1 = 0;
    if (py2) *py2 = 0;
    if (pn) *pn = 0;
    if (!px1 || !py1 || !px2 || !py2)
        return ERROR_INT("&x1, &y1, &x2, &y2 not all defined", procName, 1);
    if (!pn)
        return ERROR_INT("&n not defined", procName, 1);
    if (!box)
        return ERROR_INT("box not defined", procName, 1);
    boxGetGeometry(box, &bx, &by, &bw, &bh);

    if (slope == 0.0) {
        if (y >= by && y < by + bh) {
            *py1 = *py2 = y;
            *px1 = bx;
            *px2 = bx + bw - 1;
        }
        return 0;
    }

    if (slope > 1000000.0) {
        if (x >= bx && x < bx + bw) {
            *px1 = *px2 = x;
            *py1 = by;
            *py2 = by + bh - 1;
        }
        return 0;
    }

        /* Intersection with top and bottom lines of box */
    pta = ptaCreate(2);
    invslope = 1.0 / slope;
    xp = (l_int32)(x + invslope * (y - by));
    if (xp >= bx && xp < bx + bw)
        ptaAddPt(pta, xp, by);
    xp = (l_int32)(x + invslope * (y - by - bh + 1));
    if (xp >= bx && xp < bx + bw)
        ptaAddPt(pta, xp, by + bh - 1);

        /* Intersection with left and right lines of box */
    yp = (l_int32)(y + slope * (x - bx));
    if (yp >= by && yp < by + bh)
        ptaAddPt(pta, bx, yp);
    yp = (l_int32)(y + slope * (x - bx - bw + 1));
    if (yp >= by && yp < by + bh)
        ptaAddPt(pta, bx + bw - 1, yp);

        /* There is a maximum of 2 unique points; remove duplicates.  */
    n = ptaGetCount(pta);
    if (n > 0) {
        ptaGetIPt(pta, 0, px1, py1);  /* accept the first one */
        *pn = 1;
    }
    for (i = 1; i < n; i++) {
        ptaGetIPt(pta, i, &xt, &yt);
        if ((*px1 != xt) || (*py1 != yt)) {
            *px2 = xt;
            *py2 = yt;
            *pn = 2;
            break;
        }
    }

    ptaDestroy(&pta);
    return 0;
}


BOX *
boxClipToRectangle(BOX     *box,
                   l_int32  wi,
                   l_int32  hi)
{
BOX  *boxd;

    PROCNAME("boxClipToRectangle");

    if (!box)
        return (BOX *)ERROR_PTR("box not defined", procName, NULL);
    if (box->x >= wi || box->y >= hi ||
        box->x + box->w <= 0 || box->y + box->h <= 0)
        return (BOX *)ERROR_PTR("box outside rectangle", procName, NULL);

    boxd = boxCopy(box);
    if (boxd->x < 0) {
        boxd->w += boxd->x;
        boxd->x = 0;
    }
    if (boxd->y < 0) {
        boxd->h += boxd->y;
        boxd->y = 0;
    }
    if (boxd->x + boxd->w > wi)
        boxd->w = wi - boxd->x;
    if (boxd->y + boxd->h > hi)
        boxd->h = hi - boxd->y;
    return boxd;
}


l_int32
boxClipToRectangleParams(BOX      *box,
                         l_int32   w,
                         l_int32   h,
                         l_int32  *pxstart,
                         l_int32  *pystart,
                         l_int32  *pxend,
                         l_int32  *pyend,
                         l_int32  *pbw,
                         l_int32  *pbh)
{
l_int32  bw, bh;
BOX     *boxc;

    PROCNAME("boxClipToRectangleParams");

    if (pxstart) *pxstart = 0;
    if (pystart) *pystart = 0;
    if (pxend) *pxend = w;
    if (pyend) *pyend = h;
    if (pbw) *pbw = w;
    if (pbh) *pbh = h;
    if (!pxstart || !pystart || !pxend || !pyend)
        return ERROR_INT("invalid ptr input", procName, 1);
    if (!box) return 0;

    if ((boxc = boxClipToRectangle(box, w, h)) == NULL)
        return ERROR_INT("box outside image", procName, 1);
    boxGetGeometry(boxc, pxstart, pystart, &bw, &bh);
    boxDestroy(&boxc);

    if (pbw) *pbw = bw;
    if (pbh) *pbh = bh;
    if (bw == 0 || bh == 0)
        return ERROR_INT("invalid clipping box", procName, 1);
    *pxend = *pxstart + bw;  /* 1 past the end */
    *pyend = *pystart + bh;  /* 1 past the end */
    return 0;
}


BOX *
boxRelocateOneSide(BOX     *boxd,
                   BOX     *boxs,
                   l_int32  loc,
                   l_int32  sideflag)
{
l_int32  x, y, w, h;

    PROCNAME("boxRelocateOneSide");

    if (!boxs)
        return (BOX *)ERROR_PTR("boxs not defined", procName, NULL);
    if (!boxd)
        boxd = boxCopy(boxs);

    boxGetGeometry(boxs, &x, &y, &w, &h);
    if (sideflag == L_FROM_LEFT)
        boxSetGeometry(boxd, loc, -1, w + x - loc, -1);
    else if (sideflag == L_FROM_RIGHT)
        boxSetGeometry(boxd, -1, -1, loc - x + 1, -1);
    else if (sideflag == L_FROM_TOP)
        boxSetGeometry(boxd, -1, loc, -1, h + y - loc);
    else if (sideflag == L_FROM_BOT)
        boxSetGeometry(boxd, -1, -1, -1, loc - y + 1);
    return boxd;
}


BOXA *
boxaAdjustSides(BOXA    *boxas,
                l_int32  delleft,
                l_int32  delright,
                l_int32  deltop,
                l_int32  delbot)
{
l_int32  n, i, x, y;
BOX     *box1, *box2;
BOXA    *boxad;

    PROCNAME("boxaAdjustSides");

    if (!boxas)
        return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);

    n = boxaGetCount(boxas);
    boxad = boxaCreate(n);
    for (i = 0; i < n; i++) {
        box1 = boxaGetBox(boxas, i, L_COPY);
        box2 = boxAdjustSides(NULL, box1, delleft, delright, deltop, delbot);
        if (!box2) {
            boxGetGeometry(box1, &x, &y, NULL, NULL);
            box2 = boxCreate(x, y, 1, 1);
        }
        boxaAddBox(boxad, box2, L_INSERT);
        boxDestroy(&box1);
    }

    return boxad;
}


BOX *
boxAdjustSides(BOX     *boxd,
               BOX     *boxs,
               l_int32  delleft,
               l_int32  delright,
               l_int32  deltop,
               l_int32  delbot)
{
l_int32  x, y, w, h, xl, xr, yt, yb, wnew, hnew;

    PROCNAME("boxAdjustSides");

    if (!boxs)
        return (BOX *)ERROR_PTR("boxs not defined", procName, NULL);

    boxGetGeometry(boxs, &x, &y, &w, &h);
    xl = L_MAX(0, x + delleft);
    yt = L_MAX(0, y + deltop);
    xr = x + w + delright;  /* one pixel beyond right edge */
    yb = y + h + delbot;    /* one pixel below bottom edge */
    wnew = xr - xl;
    hnew = yb - yt;

    if (wnew < 1 || hnew < 1)
        return (BOX *)ERROR_PTR("boxd has 0 area", procName, NULL);
    if (!boxd)
        return boxCreate(xl, yt, wnew, hnew);

    boxSetGeometry(boxd, xl, yt, wnew, hnew);
    return boxd;
}


BOXA *
boxaSetSide(BOXA    *boxad,
            BOXA    *boxas,
            l_int32  side,
            l_int32  val,
            l_int32  thresh)
{
l_int32  x, y, w, h, n, i, diff;
BOX     *box;

    PROCNAME("boxaSetSide");

    if (!boxas)
        return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
    if (boxad && (boxas != boxad))
        return (BOXA *)ERROR_PTR("not in-place", procName, NULL);
    if (side != L_SET_LEFT && side != L_SET_RIGHT &&
        side != L_SET_TOP && side != L_SET_BOT)
        return (BOXA *)ERROR_PTR("invalid side", procName, NULL);
    if (val < 0)
        return (BOXA *)ERROR_PTR("val < 0", procName, NULL);

    if (!boxad)
        boxad = boxaCopy(boxas, L_COPY);
    n = boxaGetCount(boxad);
    for (i = 0; i < n; i++) {
        box = boxaGetBox(boxad, i, L_CLONE);
        boxGetGeometry(box, &x, &y, &w, &h);
        if (side == L_SET_LEFT) {
            diff = x - val;
            if (L_ABS(diff) >= thresh)
                boxSetGeometry(box, val, y, w + diff, h);
        } else if (side == L_SET_RIGHT) {
            diff = x + w -1 - val;
            if (L_ABS(diff) >= thresh)
                boxSetGeometry(box, x, y, val - x + 1, h);
        } else if (side == L_SET_TOP) {
            diff = y - val;
            if (L_ABS(diff) >= thresh)
                boxSetGeometry(box, x, val, w, h + diff);
        } else { /* side == L_SET_BOT */
            diff = y + h - 1 - val;
            if (L_ABS(diff) >= thresh)
                boxSetGeometry(box, x, y, w, val - y + 1);
        }
        boxDestroy(&box);
    }

    return boxad;
}


BOXA *
boxaAdjustWidthToTarget(BOXA    *boxad,
                        BOXA    *boxas,
                        l_int32  sides,
                        l_int32  target,
                        l_int32  thresh)
{
l_int32  x, y, w, h, n, i, diff;
BOX     *box;

    PROCNAME("boxaAdjustWidthToTarget");

    if (!boxas)
        return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
    if (boxad && (boxas != boxad))
        return (BOXA *)ERROR_PTR("not in-place", procName, NULL);
    if (sides != L_ADJUST_LEFT && sides != L_ADJUST_RIGHT &&
        sides != L_ADJUST_LEFT_AND_RIGHT)
        return (BOXA *)ERROR_PTR("invalid sides", procName, NULL);
    if (target < 1)
        return (BOXA *)ERROR_PTR("target < 1", procName, NULL);

    if (!boxad)
        boxad = boxaCopy(boxas, L_COPY);
    n = boxaGetCount(boxad);
    for (i = 0; i < n; i++) {
        box = boxaGetBox(boxad, i, L_CLONE);
        boxGetGeometry(box, &x, &y, &w, &h);
        diff = w - target;
        if (sides == L_ADJUST_LEFT) {
            if (L_ABS(diff) >= thresh)
                boxSetGeometry(box, L_MAX(0, x + diff), y, target, h);
        } else if (sides == L_ADJUST_RIGHT) {
            if (L_ABS(diff) >= thresh)
                boxSetGeometry(box, x, y, target, h);
        } else { /* sides == L_ADJUST_LEFT_AND_RIGHT */
            if (L_ABS(diff) >= thresh)
                boxSetGeometry(box, L_MAX(0, x + diff/2), y, target, h);
        }
        boxDestroy(&box);
    }

    return boxad;
}


BOXA *
boxaAdjustHeightToTarget(BOXA    *boxad,
                         BOXA    *boxas,
                        l_int32  sides,
                        l_int32  target,
                        l_int32  thresh)
{
l_int32  x, y, w, h, n, i, diff;
BOX     *box;

    PROCNAME("boxaAdjustHeightToTarget");

    if (!boxas)
        return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
    if (boxad && (boxas != boxad))
        return (BOXA *)ERROR_PTR("not in-place", procName, NULL);
    if (sides != L_ADJUST_TOP && sides != L_ADJUST_BOT &&
        sides != L_ADJUST_TOP_AND_BOT)
        return (BOXA *)ERROR_PTR("invalid sides", procName, NULL);
    if (target < 1)
        return (BOXA *)ERROR_PTR("target < 1", procName, NULL);

    if (!boxad)
        boxad = boxaCopy(boxas, L_COPY);
    n = boxaGetCount(boxad);
    for (i = 0; i < n; i++) {
        box = boxaGetBox(boxad, i, L_CLONE);
        boxGetGeometry(box, &x, &y, &w, &h);
        if (w == 0 || h == 0) {  /* invalid; do not alter */
            boxDestroy(&box);
            continue;
        }
        diff = h - target;
        if (sides == L_ADJUST_TOP) {
            if (L_ABS(diff) >= thresh)
                boxSetGeometry(box, x, L_MAX(0, y + diff), w, target);
        } else if (sides == L_ADJUST_BOT) {
            if (L_ABS(diff) >= thresh)
                boxSetGeometry(box, x, y, w, target);
        } else { /* sides == L_ADJUST_TOP_AND_BOT */
            if (L_ABS(diff) >= thresh)
                boxSetGeometry(box, x, L_MAX(0, y + diff/2), w, target);
        }
        boxDestroy(&box);
    }

    return boxad;
}


l_int32
boxEqual(BOX      *box1,
         BOX      *box2,
         l_int32  *psame)
{
    PROCNAME("boxEqual");

    if (!psame)
        return ERROR_INT("&same not defined", procName, 1);
    *psame = 0;
    if (!box1 || !box2)
        return ERROR_INT("box1 and box2 not both defined", procName, 1);
    if (box1->x == box2->x && box1->y == box2->y &&
        box1->w == box2->w && box1->h == box2->h)
        *psame = 1;
    return 0;
}


l_int32
boxaEqual(BOXA     *boxa1,
          BOXA     *boxa2,
          l_int32   maxdist,
          NUMA    **pnaindex,
          l_int32  *psame)
{
l_int32   i, j, n, jstart, jend, found, samebox;
l_int32  *countarray;
BOX      *box1, *box2;
NUMA     *na;

    PROCNAME("boxaEqual");

    if (pnaindex) *pnaindex = NULL;
    if (!psame)
        return ERROR_INT("&same not defined", procName, 1);
    *psame = 0;
    if (!boxa1 || !boxa2)
        return ERROR_INT("boxa1 and boxa2 not both defined", procName, 1);
    n = boxaGetCount(boxa1);
    if (n != boxaGetCount(boxa2))
        return 0;

    if ((countarray = (l_int32 *)LEPT_CALLOC(n, sizeof(l_int32))) == NULL)
        return ERROR_INT("calloc fail for countarray", procName, 1);
    na = numaMakeConstant(0.0, n);

    for (i = 0; i < n; i++) {
        box1 = boxaGetBox(boxa1, i, L_CLONE);
        jstart = L_MAX(0, i - maxdist);
        jend = L_MIN(n-1, i + maxdist);
        found = FALSE;
        for (j = jstart; j <= jend; j++) {
            box2 = boxaGetBox(boxa2, j, L_CLONE);
            boxEqual(box1, box2, &samebox);
            if (samebox && countarray[j] == 0) {
                countarray[j] = 1;
                numaReplaceNumber(na, i, j);
                found = TRUE;
                boxDestroy(&box2);
                break;
            }
            boxDestroy(&box2);
        }
        boxDestroy(&box1);
        if (!found) {
            numaDestroy(&na);
            LEPT_FREE(countarray);
            return 0;
        }
    }

    *psame = 1;
    if (pnaindex)
        *pnaindex = na;
    else
        numaDestroy(&na);
    LEPT_FREE(countarray);
    return 0;
}


l_int32
boxSimilar(BOX      *box1,
           BOX      *box2,
           l_int32   leftdiff,
           l_int32   rightdiff,
           l_int32   topdiff,
           l_int32   botdiff,
           l_int32  *psimilar)
{
l_int32  l1, l2, r1, r2, t1, t2, b1, b2;

    PROCNAME("boxSimilar");

    if (!psimilar)
        return ERROR_INT("&similar not defined", procName, 1);
    *psimilar = 0;
    if (!box1 || !box2)
        return ERROR_INT("box1 and box2 not both defined", procName, 1);

    boxGetSideLocations(box1, &l1, &r1, &t1, &b1);
    boxGetSideLocations(box2, &l2, &r2, &t2, &b2);
    if (L_ABS(l1 - l2) > leftdiff)
        return 0;
    if (L_ABS(r1 - r2) > rightdiff)
        return 0;
    if (L_ABS(t1 - t2) > topdiff)
        return 0;
    if (L_ABS(b1 - b2) > botdiff)
        return 0;

    *psimilar = 1;
    return 0;
}


l_int32
boxaSimilar(BOXA     *boxa1,
            BOXA     *boxa2,
            l_int32   leftdiff,
            l_int32   rightdiff,
            l_int32   topdiff,
            l_int32   botdiff,
            l_int32   debug,
            l_int32  *psimilar,
            NUMA    **pnasim)
{
l_int32  i, n1, n2, match, mismatch;
BOX     *box1, *box2;

    PROCNAME("boxaSimilar");

    if (psimilar) *psimilar = 0;
    if (pnasim) *pnasim = NULL;
    if (!boxa1 || !boxa2)
        return ERROR_INT("boxa1 and boxa2 not both defined", procName, 1);
    if (!psimilar)
        return ERROR_INT("&similar not defined", procName, 1);
    n1 = boxaGetCount(boxa1);
    n2 = boxaGetCount(boxa2);
    if (n1 != n2) {
        L_ERROR("boxa counts differ: %d vs %d\n", procName, n1, n2);
        return 1;
    }
    if (pnasim) *pnasim = numaCreate(n1);

    mismatch = FALSE;
    for (i = 0; i < n1; i++) {
        box1 = boxaGetBox(boxa1, i, L_CLONE);
        box2 = boxaGetBox(boxa2, i, L_CLONE);
        boxSimilar(box1, box2, leftdiff, rightdiff, topdiff, botdiff,
                   &match);
        boxDestroy(&box1);
        boxDestroy(&box2);
        if (pnasim)
            numaAddNumber(*pnasim, match);
        if (!match) {
            mismatch = TRUE;
            if (!debug && pnasim == NULL)
                return 0;
            else if (debug)
                L_INFO("box %d not similar\n", procName, i);
        }
    }

    if (!mismatch) *psimilar = 1;
    return 0;
}


/*----------------------------------------------------------------------*
 *                      Boxa combine and split                          *
 *----------------------------------------------------------------------*/
l_int32
boxaJoin(BOXA    *boxad,
         BOXA    *boxas,
         l_int32  istart,
         l_int32  iend)
{
l_int32  n, i;
BOX     *box;

    PROCNAME("boxaJoin");

    if (!boxad)
        return ERROR_INT("boxad not defined", procName, 1);
    if (!boxas || ((n = boxaGetCount(boxas)) == 0))
        return 0;

    if (istart < 0)
        istart = 0;
    if (iend < 0 || iend >= n)
        iend = n - 1;
    if (istart > iend)
        return ERROR_INT("istart > iend; nothing to add", procName, 1);

    for (i = istart; i <= iend; i++) {
        box = boxaGetBox(boxas, i, L_CLONE);
        boxaAddBox(boxad, box, L_INSERT);
    }

    return 0;
}


l_int32
boxaaJoin(BOXAA   *baad,
          BOXAA   *baas,
          l_int32  istart,
          l_int32  iend)
{
l_int32  n, i;
BOXA    *boxa;

    PROCNAME("boxaaJoin");

    if (!baad)
        return ERROR_INT("baad not defined", procName, 1);
    if (!baas)
        return 0;

    if (istart < 0)
        istart = 0;
    n = boxaaGetCount(baas);
    if (iend < 0 || iend >= n)
        iend = n - 1;
    if (istart > iend)
        return ERROR_INT("istart > iend; nothing to add", procName, 1);

    for (i = istart; i <= iend; i++) {
        boxa = boxaaGetBoxa(baas, i, L_CLONE);
        boxaaAddBoxa(baad, boxa, L_INSERT);
    }

    return 0;
}


l_int32
boxaSplitEvenOdd(BOXA    *boxa,
                 l_int32  fillflag,
                 BOXA   **pboxae,
                 BOXA   **pboxao)
{
l_int32  i, n;
BOX     *box, *boxt;

    PROCNAME("boxaSplitEvenOdd");

    if (pboxae) *pboxae = NULL;
    if (pboxao) *pboxao = NULL;
    if (!pboxae || !pboxao)
        return ERROR_INT("&boxae and &boxao not both defined", procName, 1);
    if (!boxa)
        return ERROR_INT("boxa not defined", procName, 1);

    n = boxaGetCount(boxa);
    *pboxae = boxaCreate(n);
    *pboxao = boxaCreate(n);
    if (fillflag == 0) {
            /* don't fill with invalid boxes; end up with half-size boxa */
        for (i = 0; i < n; i++) {
            box = boxaGetBox(boxa, i, L_COPY);
            if ((i & 1) == 0)
                boxaAddBox(*pboxae, box, L_INSERT);
            else
                boxaAddBox(*pboxao, box, L_INSERT);
        }
    } else {
        for (i = 0; i < n; i++) {
            box = boxaGetBox(boxa, i, L_COPY);
            boxt = boxCreate(0, 0, 0, 0);  /* empty placeholder */
            if ((i & 1) == 0) {
                boxaAddBox(*pboxae, box, L_INSERT);
                boxaAddBox(*pboxao, boxt, L_INSERT);
            } else {
                boxaAddBox(*pboxae, boxt, L_INSERT);
                boxaAddBox(*pboxao, box, L_INSERT);
            }
        }
    }
    return 0;
}


BOXA *
boxaMergeEvenOdd(BOXA    *boxae,
                 BOXA    *boxao,
                 l_int32  fillflag)
{
l_int32  i, n, ne, no;
BOX     *box;
BOXA    *boxad;

    PROCNAME("boxaMergeEvenOdd");

    if (!boxae || !boxao)
        return (BOXA *)ERROR_PTR("boxae and boxao not defined", procName, NULL);
    ne = boxaGetCount(boxae);
    no = boxaGetCount(boxao);
    if (ne < no || ne > no + 1)
        return (BOXA *)ERROR_PTR("boxa sizes invalid", procName, NULL);

    boxad = boxaCreate(ne);
    if (fillflag == 0) {  /* both are approx. half-sized; all valid boxes */
        n = ne + no;
        for (i = 0; i < n; i++) {
            if ((i & 1) == 0)
                box = boxaGetBox(boxae, i / 2, L_COPY);
            else
                box = boxaGetBox(boxao, i / 2, L_COPY);
            boxaAddBox(boxad, box, L_INSERT);
        }
    } else {  /* both are full size and have invalid placeholders */
        for (i = 0; i < ne; i++) {
            if ((i & 1) == 0)
                box = boxaGetBox(boxae, i, L_COPY);
            else
                box = boxaGetBox(boxao, i, L_COPY);
            boxaAddBox(boxad, box, L_INSERT);
        }
    }
    return boxad;
}