Leptonica 1.68
C Image Processing Library

boxfunc1.c

Go to the documentation of this file.
00001 /*====================================================================*
00002  -  Copyright (C) 2001 Leptonica.  All rights reserved.
00003  -  This software is distributed in the hope that it will be
00004  -  useful, but with NO WARRANTY OF ANY KIND.
00005  -  No author or distributor accepts responsibility to anyone for the
00006  -  consequences of using this software, or for whether it serves any
00007  -  particular purpose or works at all, unless he or she says so in
00008  -  writing.  Everyone is granted permission to copy, modify and
00009  -  redistribute this source code, for commercial or non-commercial
00010  -  purposes, with the following restrictions: (1) the origin of this
00011  -  source code must not be misrepresented; (2) modified versions must
00012  -  be plainly marked as such; and (3) this notice may not be removed
00013  -  or altered from any source or modified source distribution.
00014  *====================================================================*/
00015 
00016 /*
00017  *   boxfunc1.c
00018  *
00019  *      Box geometry
00020  *           l_int32   boxContains()
00021  *           l_int32   boxIntersects()
00022  *           BOXA     *boxaContainedInBox()
00023  *           BOXA     *boxaIntersectsBox()
00024  *           BOXA     *boxaClipToBox()
00025  *           BOXA     *boxaCombineOverlaps()
00026  *           BOX      *boxOverlapRegion()
00027  *           BOX      *boxBoundingRegion()
00028  *           l_int32   boxOverlapFraction()
00029  *           l_int32   boxContainsPt()
00030  *           BOX      *boxaGetNearestToPt()
00031  *           l_int32   boxIntersectByLine()
00032  *           l_int32   boxGetCenter()
00033  *           BOX      *boxClipToRectangle()
00034  *           BOX      *boxRelocateOneSide()
00035  *           BOX      *boxAdjustSides()
00036  *           l_int32   boxEqual()
00037  *           l_int32   boxaEqual()
00038  *
00039  *      Boxa combination
00040  *           l_int32   boxaJoin()
00041  *
00042  *      Other boxa functions
00043  *           l_int32   boxaGetExtent()
00044  *           l_int32   boxaGetCoverage()
00045  *           l_int32   boxaSizeRange()
00046  *           l_int32   boxaLocationRange()
00047  *           BOXA     *boxaSelectBySize()
00048  *           NUMA     *boxaMakeSizeIndicator()
00049  *           BOXA     *boxaSelectWithIndicator()
00050  *           BOXA     *boxaPermutePseudorandom()
00051  *           BOXA     *boxaPermuteRandom()
00052  *           l_int32   boxaSwapBoxes()
00053  *           PTA      *boxaConvertToPta()
00054  *           BOXA     *ptaConvertToBoxa()
00055  *
00056  */
00057 
00058 #include "allheaders.h"
00059 
00060 /*---------------------------------------------------------------------*
00061  *                             Box geometry                            *
00062  *---------------------------------------------------------------------*/
00063 /*!
00064  *  boxContains()
00065  *
00066  *      Input:  box1, box2
00067  *              &result (<return> 1 if box2 is entirely contained within
00068  *                       box1, and 0 otherwise)
00069  *      Return: 0 if OK, 1 on error
00070  */
00071 l_int32
00072 boxContains(BOX     *box1,
00073             BOX     *box2,
00074             l_int32 *presult)
00075 {
00076     PROCNAME("boxContains");
00077 
00078     if (!box1 || !box2)
00079         return ERROR_INT("box1 and box2 not both defined", procName, 1);
00080 
00081     if ((box1->x <= box2->x) &&
00082         (box1->y <= box2->y) &&
00083         (box1->x + box1->w >= box2->x + box2->w) &&
00084         (box1->y + box1->h >= box2->y + box2->h))
00085         *presult = 1;
00086     else
00087         *presult = 0;
00088     return 0;
00089 }
00090                 
00091 
00092 
00093 /*!
00094  *  boxIntersects()
00095  *
00096  *      Input:  box1, box2
00097  *              &result (<return> 1 if any part of box2 is contained
00098  *                      in box1, and 0 otherwise)
00099  *      Return: 0 if OK, 1 on error
00100  */
00101 l_int32
00102 boxIntersects(BOX      *box1,
00103               BOX      *box2,
00104               l_int32  *presult)
00105 {
00106 l_int32  left1, left2, top1, top2, right1, right2, bot1, bot2;
00107 
00108     PROCNAME("boxIntersects");
00109 
00110     if (!box1 || !box2)
00111         return ERROR_INT("box1 and box2 not both defined", procName, 1);
00112 
00113     left1 = box1->x;
00114     left2 = box2->x;
00115     top1 = box1->y;
00116     top2 = box2->y;
00117     right1 = box1->x + box1->w - 1;
00118     bot1 = box1->y + box1->h - 1;
00119     right2 = box2->x + box2->w - 1;
00120     bot2 = box2->y + box2->h - 1;
00121     if ((bot2 >= top1) && (bot1 >= top2) &&
00122          (right1 >= left2) && (right2 >= left1))
00123         *presult = 1;
00124     else
00125         *presult = 0;
00126     return 0;
00127 }
00128                 
00129 
00130 /*!
00131  *  boxaContainedInBox()
00132  *
00133  *      Input:  boxas
00134  *              box (for containment)
00135  *      Return: boxad (boxa with all boxes in boxas that are
00136  *                     entirely contained in box), or null on error
00137  *
00138  *  Notes:
00139  *      (1) All boxes in boxa that are entirely outside box are removed.
00140  */
00141 BOXA *
00142 boxaContainedInBox(BOXA  *boxas,
00143                    BOX   *box)
00144 {
00145 l_int32  i, n, val;
00146 BOX     *boxt;
00147 BOXA    *boxad;
00148 
00149     PROCNAME("boxaContainedInBox");
00150 
00151     if (!boxas)
00152         return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
00153     if (!box)
00154         return (BOXA *)ERROR_PTR("box not defined", procName, NULL);
00155     if ((n = boxaGetCount(boxas)) == 0)
00156         return boxaCreate(1);  /* empty */
00157 
00158     boxad = boxaCreate(0);
00159     for (i = 0; i < n; i++) {
00160         boxt = boxaGetBox(boxas, i, L_CLONE);
00161         boxContains(box, boxt, &val);
00162         if (val == 1)
00163             boxaAddBox(boxad, boxt, L_COPY);
00164         boxDestroy(&boxt);  /* destroy the clone */
00165     }
00166 
00167     return boxad;
00168 }
00169 
00170 
00171 /*!
00172  *  boxaIntersectsBox()
00173  *
00174  *      Input:  boxas
00175  *              box (for intersecting)
00176  *      Return  boxad (boxa with all boxes in boxas that intersect box),
00177  *                     or null on error
00178  *
00179  *  Notes:
00180  *      (1) All boxes in boxa that intersect with box (i.e., are completely
00181  *          or partially contained in box) are retained.
00182  */
00183 BOXA *
00184 boxaIntersectsBox(BOXA  *boxas,
00185                   BOX   *box)
00186 {
00187 l_int32  i, n, val;
00188 BOX     *boxt;
00189 BOXA    *boxad;
00190 
00191     PROCNAME("boxaIntersectsBox");
00192 
00193     if (!boxas)
00194         return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
00195     if (!box)
00196         return (BOXA *)ERROR_PTR("box not defined", procName, NULL);
00197     if ((n = boxaGetCount(boxas)) == 0)
00198         return boxaCreate(1);  /* empty */
00199 
00200     boxad = boxaCreate(0);
00201     for (i = 0; i < n; i++) {
00202         boxt = boxaGetBox(boxas, i, L_CLONE);
00203         boxIntersects(box, boxt, &val);
00204         if (val == 1)
00205             boxaAddBox(boxad, boxt, L_COPY);
00206         boxDestroy(&boxt);  /* destroy the clone */
00207     }
00208 
00209     return boxad;
00210 }
00211 
00212 
00213 /*!
00214  *  boxaClipToBox()
00215  *
00216  *      Input:  boxas
00217  *              box (for clipping)
00218  *      Return  boxad (boxa with boxes in boxas clipped to box),
00219  *                     or null on error
00220  *
00221  *  Notes:
00222  *      (1) All boxes in boxa not intersecting with box are removed, and
00223  *          the remaining boxes are clipped to box.
00224  */
00225 BOXA *
00226 boxaClipToBox(BOXA  *boxas,
00227               BOX   *box)
00228 {
00229 l_int32  i, n;
00230 BOX     *boxt, *boxo;
00231 BOXA    *boxad;
00232 
00233     PROCNAME("boxaClipToBox");
00234 
00235     if (!boxas)
00236         return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
00237     if (!box)
00238         return (BOXA *)ERROR_PTR("box not defined", procName, NULL);
00239     if ((n = boxaGetCount(boxas)) == 0)
00240         return boxaCreate(1);  /* empty */
00241 
00242     boxad = boxaCreate(0);
00243     for (i = 0; i < n; i++) {
00244         boxt = boxaGetBox(boxas, i, L_CLONE);
00245         if ((boxo = boxOverlapRegion(box, boxt)) != NULL)
00246             boxaAddBox(boxad, boxo, L_INSERT);
00247         boxDestroy(&boxt);
00248     }
00249 
00250     return boxad;
00251 }
00252 
00253 
00254 /*!
00255  *  boxaCombineOverlaps()
00256  *
00257  *      Input:  boxas
00258  *      Return: boxad (where each set of boxes in boxas that overlap are
00259  *                     combined into a single bounding box in boxad), or
00260  *                     null on error.
00261  *
00262  *  Notes:
00263  *      (1) If there are no overlapping boxes, it simply returns a copy
00264  *          of @boxas.
00265  *      (2) The alternative method of painting each rectanle and finding
00266  *          the 4-connected components gives the wrong result, because
00267  *          two non-overlapping rectangles, when rendered, can still
00268  *          be 4-connected, and hence they will be joined. 
00269  *      (3) A bad case is to have n boxes, none of which overlap.
00270  *          Then you have one iteration with O(n^2) compares.  This
00271  *          is still faster than painting each rectangle and finding
00272  *          the connected components, even for thousands of rectangles.
00273  */
00274 BOXA *
00275 boxaCombineOverlaps(BOXA  *boxas)
00276 {
00277 l_int32  i, j, n1, n2, inter, interfound, niters;
00278 BOX     *box1, *box2, *box3;
00279 BOXA    *boxat1, *boxat2;
00280 
00281     PROCNAME("boxaCombineOverlaps");
00282 
00283     if (!boxas)
00284         return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
00285 
00286     boxat1 = boxaCopy(boxas, L_COPY);
00287     n1 = boxaGetCount(boxat1);
00288     niters = 0;
00289 /*    fprintf(stderr, "%d iters: %d boxes\n", niters, n1); */
00290     while (1) {  /* loop until no change from previous iteration */
00291         niters++;
00292         boxat2 = boxaCreate(n1);
00293         for (i = 0; i < n1; i++) {
00294             box1 = boxaGetBox(boxat1, i, L_COPY);
00295             if (i == 0) {
00296                 boxaAddBox(boxat2, box1, L_INSERT);
00297                 continue;
00298             }
00299             n2 = boxaGetCount(boxat2);
00300                 /* Now test box1 against all boxes already put in boxat2.
00301                  * If it is found to intersect with an existing box,
00302                  * replace that box by the union of the two boxes,
00303                  * and break to the outer loop.  If no overlap is
00304                  * found, add box1 to boxat2. */
00305             interfound = FALSE;
00306             for (j = 0; j < n2; j++) {
00307                 box2 = boxaGetBox(boxat2, j, L_CLONE);
00308                 boxIntersects(box1, box2, &inter);
00309                 if (inter == 1) {
00310                     box3 = boxBoundingRegion(box1, box2);
00311                     boxaReplaceBox(boxat2, j, box3);
00312                     boxDestroy(&box1);
00313                     boxDestroy(&box2);
00314                     interfound = TRUE;
00315                     break;
00316                 }
00317                 boxDestroy(&box2);
00318             }
00319             if (interfound == FALSE)
00320                 boxaAddBox(boxat2, box1, L_INSERT);
00321         }
00322         n2 = boxaGetCount(boxat2);
00323 /*        fprintf(stderr, "%d iters: %d boxes\n", niters, n2); */
00324         if (n2 == n1)  /* we're done */
00325             break;
00326         else {
00327             n1 = n2;
00328             boxaDestroy(&boxat1);
00329             boxat1 = boxat2;
00330         }
00331     }
00332     boxaDestroy(&boxat1);
00333     return boxat2;
00334 }
00335 
00336 
00337 /*!
00338  *  boxOverlapRegion()
00339  *
00340  *      Input:  box1, box2 (two boxes)
00341  *      Return: box (of overlap region between input boxes),
00342  *              or null if no overlap or on error
00343  */
00344 BOX *
00345 boxOverlapRegion(BOX  *box1,
00346                  BOX  *box2)
00347 {
00348 l_int32  x, y, w, h, left1, left2, top1, top2, right1, right2, bot1, bot2;
00349 
00350     PROCNAME("boxOverlapRegion");
00351 
00352     if (!box1)
00353         return (BOX *)ERROR_PTR("box1 not defined", procName, NULL);
00354     if (!box2)
00355         return (BOX *)ERROR_PTR("box2 not defined", procName, NULL);
00356 
00357     left1 = box1->x;
00358     left2 = box2->x;
00359     top1 = box1->y;
00360     top2 = box2->y;
00361     right1 = box1->x + box1->w - 1;
00362     bot1 = box1->y + box1->h - 1;
00363     right2 = box2->x + box2->w - 1;
00364     bot2 = box2->y + box2->h - 1;
00365     if ((bot2 < top1) || (bot1 < top2) ||
00366          (right1 < left2) || (right2 < left1))
00367         return NULL;
00368 
00369     x = (left1 > left2) ? left1 : left2;
00370     y = (top1 > top2) ? top1 : top2;
00371     w = L_MIN(right1 - x + 1, right2 - x + 1);
00372     h = L_MIN(bot1 - y + 1, bot2 - y + 1);
00373     return boxCreate(x, y, w, h);
00374 }
00375 
00376 
00377 /*!
00378  *  boxBoundingRegion()
00379  *
00380  *      Input:  box1, box2 (two boxes)
00381  *      Return: box (of bounding region containing the input boxes),
00382  *              or null on error
00383  */
00384 BOX *
00385 boxBoundingRegion(BOX  *box1,
00386                   BOX  *box2)
00387 {
00388 l_int32  left, top, right1, right2, right, bot1, bot2, bot;
00389 
00390     PROCNAME("boxBoundingRegion");
00391 
00392     if (!box1)
00393         return (BOX *)ERROR_PTR("box1 not defined", procName, NULL);
00394     if (!box2)
00395         return (BOX *)ERROR_PTR("box2 not defined", procName, NULL);
00396 
00397     left = L_MIN(box1->x, box2->x);
00398     top = L_MIN(box1->y, box2->y);
00399     right1 = box1->x + box1->w - 1;
00400     right2 = box2->x + box2->w - 1;
00401     right = L_MAX(right1, right2);
00402     bot1 = box1->y + box1->h - 1;
00403     bot2 = box2->y + box2->h - 1;
00404     bot = L_MAX(bot1, bot2);
00405     return boxCreate(left, top, right - left + 1, bot - top + 1);
00406 }
00407 
00408 
00409 /*!
00410  *  boxOverlapFraction()
00411  *
00412  *      Input:  box1, box2 (two boxes)
00413  *              &fract (<return> the fraction of box2 overlapped by box1)
00414  *      Return: 0 if OK, 1 on error.
00415  *
00416  *  Notes:
00417  *      (1) The result depends on the order of the input boxes,
00418  *          because the overlap is taken as a fraction of box2.
00419  */
00420 l_int32
00421 boxOverlapFraction(BOX        *box1,
00422                    BOX        *box2,
00423                    l_float32  *pfract)
00424 {
00425 l_int32  w2, h2, w, h;
00426 BOX     *boxo;
00427 
00428     PROCNAME("boxOverlapFraction");
00429 
00430     if (!pfract)
00431         return ERROR_INT("&fract not defined", procName, 1);
00432     *pfract = 0.0;
00433     if (!box1)
00434         return ERROR_INT("box1 not defined", procName, 1);
00435     if (!box2)
00436         return ERROR_INT("box2 not defined", procName, 1);
00437 
00438     if ((boxo = boxOverlapRegion(box1, box2)) == NULL)  /* no overlap */
00439         return 0;
00440 
00441     boxGetGeometry(box2, NULL, NULL, &w2, &h2);
00442     boxGetGeometry(boxo, NULL, NULL, &w, &h);
00443     *pfract = (l_float32)(w * h) / (l_float32)(w2 * h2);
00444     boxDestroy(&boxo);
00445     return 0;
00446 }
00447 
00448 
00449 /*!
00450  *  boxContainsPt()
00451  *
00452  *      Input:  box
00453  *              x, y (a point)
00454  *              &contains (<return> 1 if box contains point; 0 otherwise)
00455  *      Return: 0 if OK, 1 on error.
00456  */
00457 l_int32
00458 boxContainsPt(BOX       *box,
00459               l_float32  x,
00460               l_float32  y,
00461               l_int32   *pcontains)
00462 {
00463 l_int32  bx, by, bw, bh;
00464 
00465     PROCNAME("boxContainsPt");
00466 
00467     if (!pcontains)
00468         return ERROR_INT("&contains not defined", procName, 1);
00469     *pcontains = 0;
00470     if (!box)
00471         return ERROR_INT("&box not defined", procName, 1);
00472     boxGetGeometry(box, &bx, &by, &bw, &bh);
00473     if (x >= bx && x < bx + bw && y >= by && y < by + bh)
00474         *pcontains = 1;
00475     return 0;
00476 }
00477 
00478 
00479 /*!
00480  *  boxaGetNearestToPt()
00481  *
00482  *      Input:  boxa
00483  *              x, y  (point)
00484  *      Return  box (box with centroid closest to the given point [x,y]),
00485  *              or NULL if no boxes in boxa)
00486  *
00487  *  Notes:
00488  *      (1) Uses euclidean distance between centroid and point.
00489  */
00490 BOX *
00491 boxaGetNearestToPt(BOXA    *boxa,
00492                    l_int32  x,
00493                    l_int32  y)
00494 {
00495 l_int32    i, n, minindex;
00496 l_float32  delx, dely, dist, mindist, cx, cy;
00497 BOX       *box;
00498 
00499     PROCNAME("boxaGetNearestToPt");
00500 
00501     if (!boxa)
00502         return (BOX *)ERROR_PTR("boxa not defined", procName, NULL);
00503     if ((n = boxaGetCount(boxa)) == 0)
00504         return (BOX *)ERROR_PTR("n = 0", procName, NULL);
00505     
00506     mindist = 1000000000.;
00507     minindex = 0;
00508     for (i = 0; i < n; i++) {
00509         box = boxaGetBox(boxa, i, L_CLONE);
00510         boxGetCenter(box, &cx, &cy);
00511         delx = (l_float32)(cx - x);
00512         dely = (l_float32)(cy - y);
00513         dist = delx * delx + dely * dely;
00514         if (dist < mindist) {
00515             minindex = i;
00516             mindist = dist;
00517         }
00518         boxDestroy(&box);
00519     }
00520 
00521     return boxaGetBox(boxa, minindex, L_COPY);
00522 }
00523 
00524 
00525 /*!
00526  *  boxGetCenter()
00527  *
00528  *      Input:  box
00529  *              &cx, &cy (<return> location of center of box)
00530  *      Return  0 if OK, 1 on error
00531  */
00532 l_int32
00533 boxGetCenter(BOX        *box,
00534              l_float32  *pcx,
00535              l_float32  *pcy)
00536 {
00537 l_int32  x, y, w, h;
00538 
00539     PROCNAME("boxGetCenter");
00540 
00541     if (!pcx || !pcy)
00542         return ERROR_INT("&cx, &cy not both defined", procName, 1);
00543     *pcx = *pcy = 0;
00544     if (!box)
00545         return ERROR_INT("box not defined", procName, 1);
00546     boxGetGeometry(box, &x, &y, &w, &h);
00547     *pcx = (l_float32)(x + 0.5 * w);
00548     *pcy = (l_float32)(y + 0.5 * h);
00549 
00550     return 0;
00551 }
00552 
00553 
00554 /*!
00555  *  boxIntersectByLine()
00556  *
00557  *      Input:  box
00558  *              x, y (point that line goes through)
00559  *              slope (of line)
00560  *              (&x1, &y1) (<return> 1st point of intersection with box)
00561  *              (&x2, &y2) (<return> 2nd point of intersection with box)
00562  *              &n (<return> number of points of intersection)
00563  *      Return: 0 if OK, 1 on error
00564  *
00565  *  Notes:
00566  *      (1) If the intersection is at only one point (a corner), the
00567  *          coordinates are returned in (x1, y1).
00568  *      (2) Represent a vertical line by one with a large but finite slope.
00569  */
00570 l_int32
00571 boxIntersectByLine(BOX       *box,
00572                    l_int32    x,
00573                    l_int32    y,
00574                    l_float32  slope,
00575                    l_int32   *px1,
00576                    l_int32   *py1,
00577                    l_int32   *px2,
00578                    l_int32   *py2,
00579                    l_int32   *pn)
00580 {
00581 l_int32    bx, by, bw, bh, xp, yp, xt, yt, i, n;
00582 l_float32  invslope;
00583 PTA       *pta;
00584 
00585     PROCNAME("boxIntersectByLine");
00586 
00587     if (!px1 || !py1 || !px2 || !py2)
00588         return ERROR_INT("&x1, &y1, &x2, &y2 not all defined", procName, 1);
00589     *px1 = *py1 = *px2 = *py2 = 0;
00590     if (!pn)
00591         return ERROR_INT("&n not defined", procName, 1);
00592     *pn = 0;
00593     if (!box)
00594         return ERROR_INT("box not defined", procName, 1);
00595     boxGetGeometry(box, &bx, &by, &bw, &bh);
00596 
00597     if (slope == 0.0) {
00598         if (y >= by && y < by + bh) {
00599             *py1 = *py2 = y; 
00600             *px1 = bx;
00601             *px2 = bx + bw - 1;
00602         }
00603         return 0;
00604     }
00605 
00606     if (slope > 1000000.0) {
00607         if (x >= bx && x < bx + bw) {
00608             *px1 = *px2 = x; 
00609             *py1 = by;
00610             *py2 = by + bh - 1;
00611         }
00612         return 0;
00613     }
00614 
00615         /* Intersection with top and bottom lines of box */
00616     pta = ptaCreate(2);
00617     invslope = 1.0 / slope;
00618     xp = (l_int32)(x + invslope * (y - by));
00619     if (xp >= bx && xp < bx + bw)
00620         ptaAddPt(pta, xp, by); 
00621     xp = (l_int32)(x + invslope * (y - by - bh + 1));
00622     if (xp >= bx && xp < bx + bw)
00623         ptaAddPt(pta, xp, by + bh - 1); 
00624 
00625         /* Intersection with left and right lines of box */
00626     yp = (l_int32)(y + slope * (x - bx));
00627     if (yp >= by && yp < by + bh)
00628         ptaAddPt(pta, bx, yp); 
00629     yp = (l_int32)(y + slope * (x - bx - bw + 1));
00630     if (yp >= by && yp < by + bh)
00631         ptaAddPt(pta, bx + bw - 1, yp); 
00632 
00633         /* There is a maximum of 2 unique points; remove duplicates.  */
00634     n = ptaGetCount(pta);
00635     if (n > 0) {
00636         ptaGetIPt(pta, 0, px1, py1);  /* accept the first one */
00637         *pn = 1;
00638     }
00639     for (i = 1; i < n; i++) {
00640         ptaGetIPt(pta, i, &xt, &yt);
00641         if ((*px1 != xt) || (*py1 != yt)) {
00642             *px2 = xt;
00643             *py2 = yt;
00644             *pn = 2;
00645             break;
00646         }
00647     }
00648 
00649     ptaDestroy(&pta);
00650     return 0;
00651 }
00652 
00653 
00654 /*!
00655  *  boxClipToRectangle()
00656  *
00657  *      Input:  box
00658  *              wi, hi (rectangle representing image)
00659  *      Return: part of box within given rectangle, or NULL on error
00660  *              or if box is entirely outside the rectangle
00661  *
00662  *  Notes:
00663  *      (1) This can be used to clip a rectangle to an image.
00664  *          The clipping rectangle is assumed to have a UL corner at (0, 0),
00665  *          and a LR corner at (wi - 1, hi - 1).
00666  */
00667 BOX *
00668 boxClipToRectangle(BOX     *box,
00669                    l_int32  wi,
00670                    l_int32  hi)
00671 {
00672 BOX  *boxd;
00673 
00674     PROCNAME("boxClipToRectangle");
00675 
00676     if (!box)
00677         return (BOX *)ERROR_PTR("box not defined", procName, NULL);
00678     if (box->x >= wi || box->y >= hi ||
00679         box->x + box->w <= 0 || box->y + box->h <= 0)
00680         return (BOX *)ERROR_PTR("box outside rectangle", procName, NULL);
00681 
00682     boxd = boxCopy(box);
00683     if (boxd->x < 0) {
00684         boxd->w += boxd->x;
00685         boxd->x = 0;
00686     }
00687     if (boxd->y < 0) {
00688         boxd->h += boxd->y;
00689         boxd->y = 0;
00690     }
00691     if (boxd->x + boxd->w > wi)
00692         boxd->w = wi - boxd->x;
00693     if (boxd->y + boxd->h > hi)
00694         boxd->h = hi - boxd->y;
00695     return boxd;
00696 }
00697 
00698 
00699 /*!
00700  *  boxRelocateOneSide()
00701  *
00702  *      Input:  boxd (<optional>; this can be null, equal to boxs,
00703  *                    or different from boxs);
00704  *              boxs (starting box; to have one side relocated)
00705  *              loc (new location of the side that is changing)
00706  *              sideflag (L_FROM_LEFT, etc., indicating the side that moves)
00707  *      Return: boxd, or null on error or if the computed boxd has
00708  *              width or height <= 0.
00709  *
00710  *  Notes:
00711  *      (1) Set boxd == NULL to get new box; boxd == boxs for in-place;
00712  *          or otherwise to resize existing boxd.
00713  *      (2) For usage, suggest one of these:
00714  *               boxd = boxRelocateOneSide(NULL, boxs, ...);   // new
00715  *               boxRelocateOneSide(boxs, boxs, ...);          // in-place
00716  *               boxRelocateOneSide(boxd, boxs, ...);          // other
00717  */
00718 BOX *
00719 boxRelocateOneSide(BOX     *boxd,
00720                    BOX     *boxs,
00721                    l_int32  loc,
00722                    l_int32  sideflag)
00723 {
00724 l_int32  x, y, w, h;
00725 
00726     PROCNAME("boxRelocateOneSide");
00727 
00728     if (!boxs)
00729         return (BOX *)ERROR_PTR("boxs not defined", procName, NULL);
00730     if (!boxd)
00731         boxd = boxCopy(boxs);
00732 
00733     boxGetGeometry(boxs, &x, &y, &w, &h);
00734     if (sideflag == L_FROM_LEFT)
00735         boxSetGeometry(boxd, loc, -1, w + x - loc, -1);
00736     else if (sideflag == L_FROM_RIGHT)
00737         boxSetGeometry(boxd, -1, -1, loc - x + 1, -1);
00738     else if (sideflag == L_FROM_TOP)
00739         boxSetGeometry(boxd, -1, loc, -1, h + y - loc);
00740     else if (sideflag == L_FROM_BOTTOM)
00741         boxSetGeometry(boxd, -1, -1, -1, loc - y + 1);
00742     return boxd;
00743 }
00744 
00745 
00746 /*!
00747  *  boxAdjustSides()
00748  *
00749  *      Input:  boxd  (<optional>; this can be null, equal to boxs,
00750  *                     or different from boxs)
00751  *              boxs  (starting box; to have sides adjusted)
00752  *              delleft, delright, deltop, delbot (changes in location of
00753  *                                                 each side)
00754  *      Return: boxd, or null on error or if the computed boxd has
00755  *              width or height <= 0.
00756  *
00757  *  Notes:
00758  *      (1) Set boxd == NULL to get new box; boxd == boxs for in-place;
00759  *          or otherwise to resize existing boxd.
00760  *      (2) For usage, suggest one of these:
00761  *               boxd = boxAdjustSides(NULL, boxs, ...);   // new
00762  *               boxAdjustSides(boxs, boxs, ...);          // in-place
00763  *               boxAdjustSides(boxd, boxs, ...);          // other
00764  *      (1) New box dimensions are cropped at left and top to x >= 0 and y >= 0.
00765  *      (2) For example, to expand in-place by 20 pixels on each side, use
00766  *             boxAdjustSides(box, box, -20, 20, -20, 20);
00767  */
00768 BOX *
00769 boxAdjustSides(BOX     *boxd,
00770                BOX     *boxs,
00771                l_int32  delleft,
00772                l_int32  delright,
00773                l_int32  deltop,
00774                l_int32  delbot)
00775 {
00776 l_int32  x, y, w, h, xl, xr, yt, yb, wnew, hnew;
00777 
00778     PROCNAME("boxAdjustSides");
00779 
00780     if (!boxs)
00781         return (BOX *)ERROR_PTR("boxs not defined", procName, NULL);
00782 
00783     boxGetGeometry(boxs, &x, &y, &w, &h);
00784     xl = L_MAX(0, x + delleft);
00785     yt = L_MAX(0, y + deltop);
00786     xr = x + w + delright;  /* one pixel beyond right edge */
00787     yb = y + h + delbot;    /* one pixel below bottom edge */
00788     wnew = xr - xl;
00789     hnew = yb - yt;
00790     
00791     if (wnew < 1 || hnew < 1)
00792         return (BOX *)ERROR_PTR("boxd has 0 area", procName, NULL);
00793 
00794     if (!boxd)
00795         return boxCreate(xl, yt, wnew, hnew);
00796     else {
00797         boxSetGeometry(boxd, xl, yt, wnew, hnew);
00798         return boxd;
00799     }
00800 }
00801 
00802 
00803 /*!
00804  *  boxEqual()
00805  *
00806  *      Input:  box1
00807  *              box2
00808  *              &same (<return> 1 if equal; 0 otherwise)
00809  *      Return  0 if OK, 1 on error
00810  */
00811 l_int32
00812 boxEqual(BOX      *box1,
00813          BOX      *box2,
00814          l_int32  *psame)
00815 {
00816     PROCNAME("boxEqual");
00817 
00818     if (!psame)
00819         return ERROR_INT("&same not defined", procName, 1);
00820     *psame = 0;
00821     if (!box1 || !box2)
00822         return ERROR_INT("box1 and box2 not both defined", procName, 1);
00823     if (box1->x == box2->x && box1->y == box2->y &&
00824         box1->w == box2->w && box1->h == box2->h)
00825         *psame = 1;
00826     return 0;
00827 }
00828 
00829 
00830 /*!
00831  *  boxaEqual()
00832  *
00833  *      Input:  boxa1
00834  *              boxa2
00835  *              maxdist
00836  *              &naindex (<optional return> index array of correspondences
00837  *              &same (<return> 1 if equal; 0 otherwise)
00838  *      Return  0 if OK, 1 on error
00839  *
00840  *  Notes:
00841  *      (1) The two boxa are the "same" if they contain the same
00842  *          boxes and each box is within @maxdist of its counterpart
00843  *          in their positions within the boxa.  This allows for
00844  *          small rearrangements.  Use 0 for maxdist if the boxa
00845  *          must be identical.
00846  *      (2) This applies only to geometry and ordering; refcounts
00847  *          are not considered.
00848  *      (3) @maxdist allows some latitude in the ordering of the boxes.
00849  *          For the boxa to be the "same", corresponding boxes must
00850  *          be within @maxdist of each other.  Note that for large
00851  *          @maxdist, we should use a hash function for efficiency.
00852  *      (4) naindex[i] gives the position of the box in boxa2 that
00853  *          corresponds to box i in boxa1.  It is only returned if the
00854  *          boxa are equal.
00855  */
00856 l_int32
00857 boxaEqual(BOXA     *boxa1,
00858           BOXA     *boxa2,
00859           l_int32   maxdist,
00860           NUMA    **pnaindex,
00861           l_int32  *psame)
00862 {
00863 l_int32   i, j, n, jstart, jend, found, samebox;
00864 l_int32  *countarray;
00865 BOX      *box1, *box2;
00866 NUMA     *na;
00867 
00868     PROCNAME("boxaEqual");
00869 
00870     if (pnaindex) *pnaindex = NULL;
00871     if (!psame)
00872         return ERROR_INT("&same not defined", procName, 1);
00873     *psame = 0;
00874     if (!boxa1 || !boxa2)
00875         return ERROR_INT("boxa1 and boxa2 not both defined", procName, 1);
00876     n = boxaGetCount(boxa1);
00877     if (n != boxaGetCount(boxa2))
00878         return 0;
00879 
00880     countarray = (l_int32 *)CALLOC(n, sizeof(l_int32));
00881     na = numaMakeConstant(0.0, n);
00882 
00883     for (i = 0; i < n; i++) {
00884         box1 = boxaGetBox(boxa1, i, L_CLONE);
00885         jstart = L_MAX(0, i - maxdist);
00886         jend = L_MIN(n-1, i + maxdist);
00887         found = FALSE;
00888         for (j = jstart; j <= jend; j++) {
00889             box2 = boxaGetBox(boxa2, j, L_CLONE);
00890             boxEqual(box1, box2, &samebox);
00891             if (samebox && countarray[j] == 0) {
00892                 countarray[j] = 1;
00893                 numaReplaceNumber(na, i, j);
00894                 found = TRUE;
00895                 boxDestroy(&box2);
00896                 break;
00897             }
00898             boxDestroy(&box2);
00899         }
00900         boxDestroy(&box1);
00901         if (!found) {
00902             numaDestroy(&na);
00903             FREE(countarray);
00904             return 0;
00905         }
00906     }
00907 
00908     *psame = 1;
00909     if (pnaindex)
00910         *pnaindex = na;
00911     else
00912         numaDestroy(&na);
00913     FREE(countarray);
00914     return 0;
00915 }
00916 
00917 
00918 /*----------------------------------------------------------------------*
00919  *                          Boxa Combination                            *
00920  *----------------------------------------------------------------------*/
00921 /*!
00922  *  boxaJoin()
00923  *
00924  *      Input:  boxad  (dest boxa; add to this one)
00925  *              boxas  (source boxa; add from this one)
00926  *              istart  (starting index in nas)
00927  *              iend  (ending index in nas; use 0 to cat all)
00928  *      Return: 0 if OK, 1 on error
00929  *
00930  *  Notes:
00931  *      (1) This appends a clone of each indicated box in boxas to boxad
00932  *      (2) istart < 0 is taken to mean 'read from the start' (istart = 0)
00933  *      (3) iend <= 0 means 'read to the end'
00934  */
00935 l_int32
00936 boxaJoin(BOXA    *boxad,
00937          BOXA    *boxas,
00938          l_int32  istart,
00939          l_int32  iend)
00940 {
00941 l_int32  ns, i;
00942 BOX     *box;
00943 
00944     PROCNAME("boxaJoin");
00945 
00946     if (!boxad)
00947         return ERROR_INT("boxad not defined", procName, 1);
00948     if (!boxas)
00949         return ERROR_INT("boxas not defined", procName, 1);
00950     if ((ns = boxaGetCount(boxas)) == 0) {
00951         L_INFO("empty boxas", procName);
00952         return 0;
00953     }
00954     if (istart < 0)
00955         istart = 0;
00956     if (istart >= ns)
00957         return ERROR_INT("istart out of bounds", procName, 1);
00958     if (iend <= 0)
00959         iend = ns - 1;
00960     if (iend >= ns)
00961         return ERROR_INT("iend out of bounds", procName, 1);
00962     if (istart > iend)
00963         return ERROR_INT("istart > iend; nothing to add", procName, 1);
00964 
00965     for (i = istart; i <= iend; i++) {
00966         box = boxaGetBox(boxas, i, L_CLONE);
00967         boxaAddBox(boxad, box, L_INSERT);
00968     }
00969 
00970     return 0;
00971 }
00972 
00973 
00974 /*---------------------------------------------------------------------*
00975  *                        Other Boxa functions                         *
00976  *---------------------------------------------------------------------*/
00977 /*!
00978  *  boxaGetExtent()
00979  *
00980  *      Input:  boxa
00981  *              &w  (<optional return> width)
00982  *              &h  (<optional return> height)
00983  *              &box (<optional return>, minimum box containing all boxes
00984  *                    in boxa)
00985  *      Return: 0 if OK, 1 on error
00986  *
00987  *  Notes:
00988  *      (1) The returned w and h are the minimum size image
00989  *          that would contain all boxes untranslated.
00990  *      (2) If there are no boxes, returned w and h are 0 and
00991  *          all parameters in the returned box are 0.
00992  */
00993 l_int32
00994 boxaGetExtent(BOXA     *boxa,
00995               l_int32  *pw,
00996               l_int32  *ph,
00997               BOX     **pbox)
00998 {
00999 l_int32  i, n, x, y, w, h, xmax, ymax, xmin, ymin;
01000 
01001     PROCNAME("boxaGetExtent");
01002 
01003     if (!pw && !ph && !pbox)
01004         return ERROR_INT("no ptrs defined", procName, 1);
01005     if (pbox) *pbox = NULL;
01006     if (pw) *pw = 0;
01007     if (ph) *ph = 0;
01008     if (!boxa)
01009         return ERROR_INT("boxa not defined", procName, 1);
01010 
01011     n = boxaGetCount(boxa);
01012     xmax = ymax = 0;
01013     xmin = ymin = 100000000;
01014     for (i = 0; i < n; i++) {
01015         boxaGetBoxGeometry(boxa, i, &x, &y, &w, &h);
01016         xmin = L_MIN(xmin, x);
01017         ymin = L_MIN(ymin, y);
01018         xmax = L_MAX(xmax, x + w);
01019         ymax = L_MAX(ymax, y + h);
01020     }
01021     if (n == 0)
01022         xmin = ymin = 0;
01023     if (pw) *pw = xmax;
01024     if (ph) *ph = ymax;
01025     if (pbox)
01026       *pbox = boxCreate(xmin, ymin, xmax - xmin, ymax - ymin);
01027 
01028     return 0;
01029 }
01030 
01031 
01032 /*!
01033  *  boxaGetCoverage()
01034  *
01035  *      Input:  boxa
01036  *              wc, hc (dimensions of overall clipping rectangle with UL
01037  *                      corner at (0, 0) that is covered by the boxes.
01038  *              exactflag (1 for guaranteeing an exact result; 0 for getting
01039  *                         an exact result only if the boxes do not overlap)
01040  *              &fract (<return> sum of box area as fraction of w * h)
01041  *      Return: 0 if OK, 1 on error
01042  *
01043  *  Notes:
01044  *      (1) The boxes in boxa are clipped to the input rectangle.
01045  *      (2) * When @exactflag == 1, we generate a 1 bpp pix of size
01046  *            wc x hc, paint all the boxes black, and count the fg pixels.
01047  *            This can take 1 msec on a large page with many boxes.
01048  *          * When @exactflag == 0, we clip each box to the wc x hc region
01049  *            and sum the resulting areas.  This is faster.
01050  *          * The results are the same when none of the boxes overlap
01051  *            within the wc x hc region.
01052  */
01053 l_int32
01054 boxaGetCoverage(BOXA       *boxa,
01055                 l_int32     wc,
01056                 l_int32     hc,
01057                 l_int32     exactflag,
01058                 l_float32  *pfract)
01059 {
01060 l_int32  i, n, x, y, w, h, sum;
01061 BOX     *box, *boxc;
01062 PIX     *pixt;
01063 
01064     PROCNAME("boxaGetCoverage");
01065 
01066     if (!pfract)
01067         return ERROR_INT("&fract not defined", procName, 1);
01068     *pfract = 0.0;
01069     if (!boxa)
01070         return ERROR_INT("boxa not defined", procName, 1);
01071 
01072     n = boxaGetCount(boxa);
01073     if (n == 0)
01074         return ERROR_INT("no boxes in boxa", procName, 1);
01075 
01076     if (exactflag == 0) {  /* quick and dirty */
01077         sum = 0;
01078         for (i = 0; i < n; i++) {
01079             box = boxaGetBox(boxa, i, L_CLONE);
01080             if ((boxc = boxClipToRectangle(box, wc, hc)) != NULL) {
01081                 boxGetGeometry(boxc, NULL, NULL, &w, &h);
01082                 sum += w * h;
01083                 boxDestroy(&boxc);
01084             }
01085             boxDestroy(&box);
01086         }
01087     }
01088     else {  /* slower and exact */
01089         pixt = pixCreate(wc, hc, 1);
01090         for (i = 0; i < n; i++) {
01091             box = boxaGetBox(boxa, i, L_CLONE);
01092             boxGetGeometry(box, &x, &y, &w, &h);
01093             pixRasterop(pixt, x, y, w, h, PIX_SET, NULL, 0, 0);
01094             boxDestroy(&box);
01095         }
01096         pixCountPixels(pixt, &sum, NULL);
01097         pixDestroy(&pixt);
01098     }
01099 
01100     *pfract = (l_float32)sum / (l_float32)(wc * hc);
01101     return 0;
01102 }
01103 
01104 
01105 /*!
01106  *  boxaSizeRange()
01107  *
01108  *      Input:  boxa
01109  *              &minw, &minh, &maxw, &maxh (<optional return> range of
01110  *                                          dimensions of box in the array)
01111  *      Return: 0 if OK, 1 on error
01112  */
01113 l_int32  
01114 boxaSizeRange(BOXA     *boxa,
01115               l_int32  *pminw,
01116               l_int32  *pminh,
01117               l_int32  *pmaxw,
01118               l_int32  *pmaxh)
01119 {
01120 l_int32  minw, minh, maxw, maxh, i, n, w, h;
01121 
01122     PROCNAME("boxaSizeRange");
01123 
01124     if (!boxa)
01125         return ERROR_INT("boxa not defined", procName, 1);
01126     if (!pminw && !pmaxw && !pminh && !pmaxh)
01127         return ERROR_INT("no data can be returned", procName, 1);
01128     
01129     minw = minh = 100000000;
01130     maxw = maxh = 0;
01131     n = boxaGetCount(boxa);
01132     for (i = 0; i < n; i++) {
01133         boxaGetBoxGeometry(boxa, i, NULL, NULL, &w, &h);
01134         if (w < minw)
01135             minw = w;
01136         if (h < minh)
01137             minh = h;
01138         if (w > maxw)
01139             maxw = w;
01140         if (h > maxh)
01141             maxh = h;
01142     }
01143 
01144     if (pminw) *pminw = minw;
01145     if (pminh) *pminh = minh;
01146     if (pmaxw) *pmaxw = maxw;
01147     if (pmaxh) *pmaxh = maxh;
01148 
01149     return 0;
01150 }
01151 
01152 
01153 /*!
01154  *  boxaLocationRange()
01155  *
01156  *      Input:  boxa
01157  *              &minx, &miny, &maxx, &maxy (<optional return> range of
01158  *                                          UL corner positions)
01159  *      Return: 0 if OK, 1 on error
01160  */
01161 l_int32  
01162 boxaLocationRange(BOXA     *boxa,
01163                   l_int32  *pminx,
01164                   l_int32  *pminy,
01165                   l_int32  *pmaxx,
01166                   l_int32  *pmaxy)
01167 {
01168 l_int32  minx, miny, maxx, maxy, i, n, x, y;
01169 
01170     PROCNAME("boxaLocationRange");
01171 
01172     if (!boxa)
01173         return ERROR_INT("boxa not defined", procName, 1);
01174     if (!pminx && !pminy && !pmaxx && !pmaxy)
01175         return ERROR_INT("no data can be returned", procName, 1);
01176     
01177     minx = miny = 100000000;
01178     maxx = maxy = 0;
01179     n = boxaGetCount(boxa);
01180     for (i = 0; i < n; i++) {
01181         boxaGetBoxGeometry(boxa, i, &x, &y, NULL, NULL);
01182         if (x < minx)
01183             minx = x;
01184         if (y < miny)
01185             miny = y;
01186         if (x > maxx)
01187             maxx = x;
01188         if (y > maxy)
01189             maxy = y;
01190     }
01191 
01192     if (pminx) *pminx = minx;
01193     if (pminy) *pminy = miny;
01194     if (pmaxx) *pmaxx = maxx;
01195     if (pmaxy) *pmaxy = maxy;
01196 
01197     return 0;
01198 }
01199 
01200 
01201 /*!
01202  *  boxaSelectBySize()
01203  *
01204  *      Input:  boxas
01205  *              width, height (threshold dimensions)
01206  *              type (L_SELECT_WIDTH, L_SELECT_HEIGHT,
01207  *                    L_SELECT_IF_EITHER, L_SELECT_IF_BOTH)
01208  *              relation (L_SELECT_IF_LT, L_SELECT_IF_GT,
01209  *                        L_SELECT_IF_LTE, L_SELECT_IF_GTE)
01210  *              &changed (<optional return> 1 if changed; 0 if clone returned)
01211  *      Return: boxad (filtered set), or null on error
01212  *
01213  *  Notes:
01214  *      (1) The args specify constraints on the size of the
01215  *          components that are kept.
01216  *      (2) Uses box clones in the new boxa.
01217  *      (3) If the selection type is L_SELECT_WIDTH, the input
01218  *          height is ignored, and v.v.
01219  *      (4) To keep small components, use relation = L_SELECT_IF_LT or
01220  *          L_SELECT_IF_LTE.
01221  *          To keep large components, use relation = L_SELECT_IF_GT or
01222  *          L_SELECT_IF_GTE.
01223  */
01224 BOXA *
01225 boxaSelectBySize(BOXA     *boxas,
01226                  l_int32   width,
01227                  l_int32   height,
01228                  l_int32   type,
01229                  l_int32   relation,
01230                  l_int32  *pchanged)
01231 {
01232 BOXA  *boxad;
01233 NUMA  *na;
01234 
01235     PROCNAME("boxaSelectBySize");
01236 
01237     if (!boxas)
01238         return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
01239     if (type != L_SELECT_WIDTH && type != L_SELECT_HEIGHT &&
01240         type != L_SELECT_IF_EITHER && type != L_SELECT_IF_BOTH)
01241         return (BOXA *)ERROR_PTR("invalid type", procName, NULL);
01242     if (relation != L_SELECT_IF_LT && relation != L_SELECT_IF_GT && 
01243         relation != L_SELECT_IF_LTE && relation != L_SELECT_IF_GTE)
01244         return (BOXA *)ERROR_PTR("invalid relation", procName, NULL);
01245     if (pchanged) *pchanged = FALSE;
01246     
01247         /* Compute the indicator array for saving components */
01248     na = boxaMakeSizeIndicator(boxas, width, height, type, relation);
01249 
01250         /* Filter to get output */
01251     boxad = boxaSelectWithIndicator(boxas, na, pchanged);
01252 
01253     numaDestroy(&na);
01254     return boxad;
01255 }
01256 
01257 
01258 /*!
01259  *  boxaMakeSizeIndicator()
01260  *
01261  *      Input:  boxa
01262  *              width, height (threshold dimensions)
01263  *              type (L_SELECT_WIDTH, L_SELECT_HEIGHT,
01264  *                    L_SELECT_IF_EITHER, L_SELECT_IF_BOTH)
01265  *              relation (L_SELECT_IF_LT, L_SELECT_IF_GT,
01266  *                        L_SELECT_IF_LTE, L_SELECT_IF_GTE)
01267  *      Return: na (indicator array), or null on error
01268  *
01269  *  Notes:
01270  *      (1) The args specify constraints on the size of the
01271  *          components that are kept.
01272  *      (2) If the selection type is L_SELECT_WIDTH, the input
01273  *          height is ignored, and v.v.
01274  *      (3) To keep small components, use relation = L_SELECT_IF_LT or
01275  *          L_SELECT_IF_LTE.
01276  *          To keep large components, use relation = L_SELECT_IF_GT or
01277  *          L_SELECT_IF_GTE.
01278  */
01279 NUMA *
01280 boxaMakeSizeIndicator(BOXA     *boxa,
01281                       l_int32   width,
01282                       l_int32   height,
01283                       l_int32   type,
01284                       l_int32   relation)
01285 {
01286 l_int32  i, n, w, h, ival;
01287 NUMA    *na;
01288 
01289     PROCNAME("boxaMakeSizeIndicator");
01290 
01291     if (!boxa)
01292         return (NUMA *)ERROR_PTR("boxa not defined", procName, NULL);
01293     if (type != L_SELECT_WIDTH && type != L_SELECT_HEIGHT &&
01294         type != L_SELECT_IF_EITHER && type != L_SELECT_IF_BOTH)
01295         return (NUMA *)ERROR_PTR("invalid type", procName, NULL);
01296     if (relation != L_SELECT_IF_LT && relation != L_SELECT_IF_GT && 
01297         relation != L_SELECT_IF_LTE && relation != L_SELECT_IF_GTE)
01298         return (NUMA *)ERROR_PTR("invalid relation", procName, NULL);
01299 
01300     n = boxaGetCount(boxa);
01301     na = numaCreate(n);
01302     for (i = 0; i < n; i++) {
01303         ival = 0;
01304         boxaGetBoxGeometry(boxa, i, NULL, NULL, &w, &h);
01305         switch (type)
01306         {
01307         case L_SELECT_WIDTH:
01308             if ((relation == L_SELECT_IF_LT && w < width) ||
01309                 (relation == L_SELECT_IF_GT && w > width) ||
01310                 (relation == L_SELECT_IF_LTE && w <= width) ||
01311                 (relation == L_SELECT_IF_GTE && w >= width))
01312                 ival = 1;
01313             break;
01314         case L_SELECT_HEIGHT:
01315             if ((relation == L_SELECT_IF_LT && h < height) ||
01316                 (relation == L_SELECT_IF_GT && h > height) ||
01317                 (relation == L_SELECT_IF_LTE && h <= height) ||
01318                 (relation == L_SELECT_IF_GTE && h >= height))
01319                 ival = 1;
01320             break;
01321         case L_SELECT_IF_EITHER:
01322             if (((relation == L_SELECT_IF_LT) && (w < width || h < height)) ||
01323                 ((relation == L_SELECT_IF_GT) && (w > width || h > height)) ||
01324                ((relation == L_SELECT_IF_LTE) && (w <= width || h <= height)) ||
01325                 ((relation == L_SELECT_IF_GTE) && (w >= width || h >= height)))
01326                     ival = 1;
01327             break;
01328         case L_SELECT_IF_BOTH:
01329             if (((relation == L_SELECT_IF_LT) && (w < width && h < height)) ||
01330                 ((relation == L_SELECT_IF_GT) && (w > width && h > height)) ||
01331                ((relation == L_SELECT_IF_LTE) && (w <= width && h <= height)) ||
01332                 ((relation == L_SELECT_IF_GTE) && (w >= width && h >= height)))
01333                     ival = 1;
01334             break;
01335         default:
01336             L_WARNING("can't get here!", procName);
01337         }
01338         numaAddNumber(na, ival);
01339     }
01340 
01341     return na;
01342 }
01343 
01344 
01345 /*!
01346  *  boxaSelectWithIndicator()
01347  *
01348  *      Input:  boxas
01349  *              na (indicator numa)
01350  *              &changed (<optional return> 1 if changed; 0 if clone returned)
01351  *      Return: boxad, or null on error
01352  *
01353  *  Notes:
01354  *      (1) Returns a boxa clone if no components are removed.
01355  *      (2) Uses box clones in the new boxa.
01356  *      (3) The indicator numa has values 0 (ignore) and 1 (accept).
01357  */
01358 BOXA *
01359 boxaSelectWithIndicator(BOXA     *boxas,
01360                         NUMA     *na,
01361                         l_int32  *pchanged)
01362 {
01363 l_int32  i, n, ival, nsave;
01364 BOX     *box;
01365 BOXA    *boxad;
01366 
01367     PROCNAME("boxaSelectWithIndicator");
01368 
01369     if (!boxas)
01370         return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
01371     if (!na)
01372         return (BOXA *)ERROR_PTR("na not defined", procName, NULL);
01373 
01374     nsave = 0;
01375     n = numaGetCount(na);
01376     for (i = 0; i < n; i++) {
01377         numaGetIValue(na, i, &ival);
01378         if (ival == 1) nsave++;
01379     }
01380 
01381     if (nsave == n) {
01382         if (pchanged) *pchanged = FALSE;
01383         return boxaCopy(boxas, L_CLONE);
01384     }
01385     if (pchanged) *pchanged = TRUE;
01386     boxad = boxaCreate(nsave);
01387     for (i = 0; i < n; i++) {
01388         numaGetIValue(na, i, &ival);
01389         if (ival == 0) continue;
01390         box = boxaGetBox(boxas, i, L_CLONE);
01391         boxaAddBox(boxad, box, L_INSERT);
01392     }
01393 
01394     return boxad;
01395 }
01396 
01397 
01398 /*!
01399  *  boxaPermutePseudorandom()
01400  *
01401  *      Input:  boxas (input boxa)
01402  *      Return: boxad (with boxes permuted), or null on error
01403  *
01404  *  Notes:
01405  *      (1) This does a pseudorandom in-place permutation of the boxes.
01406  *      (2) The result is guaranteed not to have any boxes in their
01407  *          original position, but it is not very random.  If you
01408  *          need randomness, use boxaPermuteRandom().
01409  */
01410 BOXA *
01411 boxaPermutePseudorandom(BOXA  *boxas)
01412 {
01413 l_int32  n;
01414 NUMA    *na;
01415 BOXA    *boxad;
01416 
01417     PROCNAME("boxaPermutePseudorandom");
01418 
01419     if (!boxas)
01420         return (BOXA *)ERROR_PTR("boxa not defined", procName, NULL);
01421 
01422     n = boxaGetCount(boxas);
01423     na = numaPseudorandomSequence(n, 0);
01424     boxad = boxaSortByIndex(boxas, na);
01425     numaDestroy(&na);
01426     return boxad;
01427 }
01428 
01429 
01430 /*!
01431  *  boxaPermuteRandom()
01432  *
01433  *      Input:  boxad (<optional> can be null or equal to boxas)
01434  *              boxas (input boxa)
01435  *      Return: boxad (with boxes permuted), or null on error
01436  *
01437  *  Notes:
01438  *      (1) If boxad is null, make a copy of boxas and permute the copy.
01439  *          Otherwise, boxad must be equal to boxas, and the operation
01440  *          is done in-place.
01441  *      (2) This does a random in-place permutation of the boxes,
01442  *          by swapping each box in turn with a random box.  The
01443  *          result is almost guaranteed not to have any boxes in their
01444  *          original position.
01445  *      (3) MSVC rand() has MAX_RAND = 2^15 - 1, so it will not do
01446  *          a proper permutation is the number of boxes exceeds this.
01447  */
01448 BOXA *
01449 boxaPermuteRandom(BOXA  *boxad,
01450                   BOXA  *boxas)
01451 {
01452 l_int32  i, n, index;
01453 
01454     PROCNAME("boxaPermuteRandom");
01455 
01456     if (!boxas)
01457         return (BOXA *)ERROR_PTR("boxa not defined", procName, NULL);
01458     if (boxad && (boxad != boxas))
01459         return (BOXA *)ERROR_PTR("boxad defined but in-place", procName, NULL);
01460 
01461     if (!boxad)
01462         boxad = boxaCopy(boxas, L_COPY);
01463     n = boxaGetCount(boxad);
01464     index = (l_uint32)rand() % n;
01465     index = L_MAX(1, index);
01466     boxaSwapBoxes(boxad, 0, index);
01467     for (i = 1; i < n; i++) {
01468         index = (l_uint32)rand() % n;
01469         if (index == i) index--;
01470         boxaSwapBoxes(boxad, i, index);
01471     }
01472 
01473     return boxad;
01474 }
01475 
01476 
01477 /*!
01478  *  boxaSwapBoxes()
01479  *
01480  *      Input:  boxa
01481  *              i, j (two indices of boxes, that are to be swapped)
01482  *      Return: 0 if OK, 1 on error
01483  */
01484 l_int32
01485 boxaSwapBoxes(BOXA    *boxa,
01486               l_int32  i,
01487               l_int32  j)
01488 {
01489 l_int32  n;
01490 BOX     *box;
01491 
01492     PROCNAME("boxaSwapBoxes");
01493 
01494     if (!boxa)
01495         return ERROR_INT("boxa not defined", procName, 1);
01496     n = boxaGetCount(boxa);
01497     if (i < 0 || i >= n)
01498         return ERROR_INT("i invalid", procName, 1);
01499     if (j < 0 || j >= n)
01500         return ERROR_INT("j invalid", procName, 1);
01501     if (i == j)
01502         return ERROR_INT("i == j", procName, 1);
01503 
01504     box = boxa->box[i];
01505     boxa->box[i] = boxa->box[j];
01506     boxa->box[j] = box;
01507     return 0;
01508 }
01509 
01510 
01511 /*!
01512  *  boxaConvertToPta()
01513  *
01514  *      Input:  boxa 
01515  *              ncorners (2 or 4 for the representation of each box)
01516  *      Return: pta (with @ncorners points for each box in the boxa),
01517  *                   or null on error
01518  *
01519  *  Notes:
01520  *      (1) If ncorners == 2, we select the UL and LR corners.
01521  *          Otherwise we save all 4 corners in this order: UL, UR, LL, LR.
01522  */
01523 PTA *
01524 boxaConvertToPta(BOXA    *boxa,
01525                  l_int32  ncorners)
01526 {
01527 l_int32  i, n, x, y, w, h;
01528 PTA     *pta;
01529 
01530     PROCNAME("boxaConvertToPta");
01531 
01532     if (!boxa)
01533         return (PTA *)ERROR_PTR("boxa not defined", procName, NULL);
01534     if (ncorners != 2 && ncorners != 4)
01535         return (PTA *)ERROR_PTR("ncorners not 2 or 4", procName, NULL);
01536 
01537     n = boxaGetCount(boxa);
01538     if ((pta = ptaCreate(n)) == NULL)
01539         return (PTA *)ERROR_PTR("pta not made", procName, NULL);
01540     for (i = 0; i < n; i++) {
01541         boxaGetBoxGeometry(boxa, i, &x, &y, &w, &h);
01542         ptaAddPt(pta, x, y);
01543         if (ncorners == 2) 
01544             ptaAddPt(pta, x + w - 1, y + h - 1);
01545         else {
01546             ptaAddPt(pta, x + w - 1, y);
01547             ptaAddPt(pta, x, y + h - 1);
01548             ptaAddPt(pta, x + w - 1, y + h - 1);
01549         }
01550     }
01551 
01552     return pta;
01553 }
01554 
01555 
01556 /*!
01557  *  ptaConvertToBoxa()
01558  *
01559  *      Input:  pta
01560  *              ncorners (2 or 4 for the representation of each box)
01561  *      Return: boxa (with one box for each 2 or 4 points in the pta),
01562  *                    or null on error
01563  *
01564  *  Notes:
01565  *      (1) For 2 corners, the order of the 2 points is UL, LR.
01566  *          For 4 corners, the order of points is UL, UR, LL, LR.
01567  *      (2) Each derived box is the minimum szie containing all corners.
01568  */
01569 BOXA *
01570 ptaConvertToBoxa(PTA     *pta,
01571                  l_int32  ncorners)
01572 {
01573 l_int32  i, n, nbox, x1, y1, x2, y2, x3, y3, x4, y4, x, y, xmax, ymax;
01574 BOX     *box;
01575 BOXA    *boxa;
01576 
01577     PROCNAME("ptaConvertToBoxa");
01578 
01579     if (!pta)
01580         return (BOXA *)ERROR_PTR("pta not defined", procName, NULL);
01581     if (ncorners != 2 && ncorners != 4)
01582         return (BOXA *)ERROR_PTR("ncorners not 2 or 4", procName, NULL);
01583     n = ptaGetCount(pta);
01584     if (n % ncorners != 0)
01585         return (BOXA *)ERROR_PTR("size % ncorners != 0", procName, NULL);
01586     nbox = n / ncorners;
01587     if ((boxa = boxaCreate(nbox)) == NULL)
01588         return (BOXA *)ERROR_PTR("boxa not made", procName, NULL);
01589     for (i = 0; i < n; i += ncorners) {
01590         ptaGetIPt(pta, i, &x1, &y1);
01591         ptaGetIPt(pta, i + 1, &x2, &y2);
01592         if (ncorners == 2) {
01593             box = boxCreate(x1, y1, x2 - x1 + 1, y2 - y1 + 1);
01594             boxaAddBox(boxa, box, L_INSERT);
01595             continue;
01596         }
01597         ptaGetIPt(pta, i + 2, &x3, &y3);
01598         ptaGetIPt(pta, i + 3, &x4, &y4);
01599         x = L_MIN(x1, x3);
01600         y = L_MIN(y1, y2);
01601         xmax = L_MAX(x2, x4);
01602         ymax = L_MAX(y3, y4);
01603         box = boxCreate(x, y, xmax - x + 1, ymax - y + 1);
01604         boxaAddBox(boxa, box, L_INSERT);
01605     }
01606 
01607     return boxa;
01608 }
01609 
01610 
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines