Leptonica  1.83.1
Image processing and image analysis suite
boxfunc2.c
Go to the documentation of this file.
1 /*====================================================================*
2  - Copyright (C) 2001 Leptonica. All rights reserved.
3  -
4  - Redistribution and use in source and binary forms, with or without
5  - modification, are permitted provided that the following conditions
6  - are met:
7  - 1. Redistributions of source code must retain the above copyright
8  - notice, this list of conditions and the following disclaimer.
9  - 2. Redistributions in binary form must reproduce the above
10  - copyright notice, this list of conditions and the following
11  - disclaimer in the documentation and/or other materials
12  - provided with the distribution.
13  -
14  - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15  - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16  - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17  - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18  - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23  - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24  - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  *====================================================================*/
26 
67 #ifdef HAVE_CONFIG_H
68 #include <config_auto.h>
69 #endif /* HAVE_CONFIG_H */
70 
71 #include <math.h>
72 #include "allheaders.h"
73 #include "pix_internal.h"
74 
75  /* For more than this number of c.c. in a binarized image of
76  * semi-perimeter (w + h) about 5000 or less, the O(n) binsort
77  * is faster than the O(nlogn) shellsort. */
78 static const l_int32 MinCompsForBinSort = 200;
79 
80 /*---------------------------------------------------------------------*
81  * Boxa/Box transform (shift, scale) and orthogonal rotation *
82  *---------------------------------------------------------------------*/
102 BOXA *
104  l_int32 shiftx,
105  l_int32 shifty,
106  l_float32 scalex,
107  l_float32 scaley)
108 {
109 l_int32 i, n;
110 BOX *boxs, *boxd;
111 BOXA *boxad;
112 
113  if (!boxas)
114  return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
115  n = boxaGetCount(boxas);
116  if ((boxad = boxaCreate(n)) == NULL)
117  return (BOXA *)ERROR_PTR("boxad not made", __func__, NULL);
118  for (i = 0; i < n; i++) {
119  if ((boxs = boxaGetBox(boxas, i, L_CLONE)) == NULL) {
120  boxaDestroy(&boxad);
121  return (BOXA *)ERROR_PTR("boxs not found", __func__, NULL);
122  }
123  boxd = boxTransform(boxs, shiftx, shifty, scalex, scaley);
124  boxDestroy(&boxs);
125  boxaAddBox(boxad, boxd, L_INSERT);
126  }
127 
128  return boxad;
129 }
130 
131 
150 BOX *
152  l_int32 shiftx,
153  l_int32 shifty,
154  l_float32 scalex,
155  l_float32 scaley)
156 {
157  if (!box)
158  return (BOX *)ERROR_PTR("box not defined", __func__, NULL);
159  if (box->w <= 0 || box->h <= 0)
160  return boxCreate(0, 0, 0, 0);
161  else
162  return boxCreate((l_int32)(L_MAX(0, scalex * (box->x + shiftx) + 0.5)),
163  (l_int32)(L_MAX(0, scaley * (box->y + shifty) + 0.5)),
164  (l_int32)(L_MAX(1.0, scalex * box->w + 0.5)),
165  (l_int32)(L_MAX(1.0, scaley * box->h + 0.5)));
166 }
167 
168 
202 BOXA *
204  l_int32 shiftx,
205  l_int32 shifty,
206  l_float32 scalex,
207  l_float32 scaley,
208  l_int32 xcen,
209  l_int32 ycen,
210  l_float32 angle,
211  l_int32 order)
212 {
213 l_int32 i, n;
214 BOX *boxs, *boxd;
215 BOXA *boxad;
216 
217  if (!boxas)
218  return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
219  n = boxaGetCount(boxas);
220  if ((boxad = boxaCreate(n)) == NULL)
221  return (BOXA *)ERROR_PTR("boxad not made", __func__, NULL);
222  for (i = 0; i < n; i++) {
223  if ((boxs = boxaGetBox(boxas, i, L_CLONE)) == NULL) {
224  boxaDestroy(&boxad);
225  return (BOXA *)ERROR_PTR("boxs not found", __func__, NULL);
226  }
227  boxd = boxTransformOrdered(boxs, shiftx, shifty, scalex, scaley,
228  xcen, ycen, angle, order);
229  boxDestroy(&boxs);
230  boxaAddBox(boxad, boxd, L_INSERT);
231  }
232 
233  return boxad;
234 }
235 
236 
290 BOX *
292  l_int32 shiftx,
293  l_int32 shifty,
294  l_float32 scalex,
295  l_float32 scaley,
296  l_int32 xcen,
297  l_int32 ycen,
298  l_float32 angle,
299  l_int32 order)
300 {
301 l_int32 bx, by, bw, bh, tx, ty, tw, th;
302 l_int32 xcent, ycent; /* transformed center of rotation due to scaling */
303 l_float32 sina, cosa, xdif, ydif, rx, ry, rw, rh;
304 BOX *boxd;
305 
306  if (!boxs)
307  return (BOX *)ERROR_PTR("boxs not defined", __func__, NULL);
308  if (order != L_TR_SC_RO && order != L_SC_RO_TR && order != L_RO_TR_SC &&
309  order != L_TR_RO_SC && order != L_RO_SC_TR && order != L_SC_TR_RO)
310  return (BOX *)ERROR_PTR("order invalid", __func__, NULL);
311 
312  boxGetGeometry(boxs, &bx, &by, &bw, &bh);
313  if (bw <= 0 || bh <= 0) /* invalid */
314  return boxCreate(0, 0, 0, 0);
315  if (angle != 0.0) {
316  sina = sin(angle);
317  cosa = cos(angle);
318  }
319 
320  if (order == L_TR_SC_RO) {
321  tx = (l_int32)(scalex * (bx + shiftx) + 0.5);
322  ty = (l_int32)(scaley * (by + shifty) + 0.5);
323  tw = (l_int32)(L_MAX(1.0, scalex * bw + 0.5));
324  th = (l_int32)(L_MAX(1.0, scaley * bh + 0.5));
325  xcent = (l_int32)(scalex * xcen + 0.5);
326  ycent = (l_int32)(scaley * ycen + 0.5);
327  if (angle == 0.0) {
328  boxd = boxCreate(tx, ty, tw, th);
329  } else {
330  xdif = tx + 0.5 * tw - xcent;
331  ydif = ty + 0.5 * th - ycent;
332  rw = L_ABS(tw * cosa) + L_ABS(th * sina);
333  rh = L_ABS(th * cosa) + L_ABS(tw * sina);
334  rx = xcent + xdif * cosa - ydif * sina - 0.5 * rw;
335  ry = ycent + ydif * cosa + xdif * sina - 0.5 * rh;
336  boxd = boxCreate((l_int32)rx, (l_int32)ry, (l_int32)rw,
337  (l_int32)rh);
338  }
339  } else if (order == L_SC_TR_RO) {
340  tx = (l_int32)(scalex * bx + shiftx + 0.5);
341  ty = (l_int32)(scaley * by + shifty + 0.5);
342  tw = (l_int32)(L_MAX(1.0, scalex * bw + 0.5));
343  th = (l_int32)(L_MAX(1.0, scaley * bh + 0.5));
344  xcent = (l_int32)(scalex * xcen + 0.5);
345  ycent = (l_int32)(scaley * ycen + 0.5);
346  if (angle == 0.0) {
347  boxd = boxCreate(tx, ty, tw, th);
348  } else {
349  xdif = tx + 0.5 * tw - xcent;
350  ydif = ty + 0.5 * th - ycent;
351  rw = L_ABS(tw * cosa) + L_ABS(th * sina);
352  rh = L_ABS(th * cosa) + L_ABS(tw * sina);
353  rx = xcent + xdif * cosa - ydif * sina - 0.5 * rw;
354  ry = ycent + ydif * cosa + xdif * sina - 0.5 * rh;
355  boxd = boxCreate((l_int32)rx, (l_int32)ry, (l_int32)rw,
356  (l_int32)rh);
357  }
358  } else if (order == L_RO_TR_SC) {
359  if (angle == 0.0) {
360  rx = bx;
361  ry = by;
362  rw = bw;
363  rh = bh;
364  } else {
365  xdif = bx + 0.5 * bw - xcen;
366  ydif = by + 0.5 * bh - ycen;
367  rw = L_ABS(bw * cosa) + L_ABS(bh * sina);
368  rh = L_ABS(bh * cosa) + L_ABS(bw * sina);
369  rx = xcen + xdif * cosa - ydif * sina - 0.5 * rw;
370  ry = ycen + ydif * cosa + xdif * sina - 0.5 * rh;
371  }
372  tx = (l_int32)(scalex * (rx + shiftx) + 0.5);
373  ty = (l_int32)(scaley * (ry + shifty) + 0.5);
374  tw = (l_int32)(L_MAX(1.0, scalex * rw + 0.5));
375  th = (l_int32)(L_MAX(1.0, scaley * rh + 0.5));
376  boxd = boxCreate(tx, ty, tw, th);
377  } else if (order == L_RO_SC_TR) {
378  if (angle == 0.0) {
379  rx = bx;
380  ry = by;
381  rw = bw;
382  rh = bh;
383  } else {
384  xdif = bx + 0.5 * bw - xcen;
385  ydif = by + 0.5 * bh - ycen;
386  rw = L_ABS(bw * cosa) + L_ABS(bh * sina);
387  rh = L_ABS(bh * cosa) + L_ABS(bw * sina);
388  rx = xcen + xdif * cosa - ydif * sina - 0.5 * rw;
389  ry = ycen + ydif * cosa + xdif * sina - 0.5 * rh;
390  }
391  tx = (l_int32)(scalex * rx + shiftx + 0.5);
392  ty = (l_int32)(scaley * ry + shifty + 0.5);
393  tw = (l_int32)(L_MAX(1.0, scalex * rw + 0.5));
394  th = (l_int32)(L_MAX(1.0, scaley * rh + 0.5));
395  boxd = boxCreate(tx, ty, tw, th);
396  } else if (order == L_TR_RO_SC) {
397  tx = bx + shiftx;
398  ty = by + shifty;
399  if (angle == 0.0) {
400  rx = tx;
401  ry = ty;
402  rw = bw;
403  rh = bh;
404  } else {
405  xdif = tx + 0.5 * bw - xcen;
406  ydif = ty + 0.5 * bh - ycen;
407  rw = L_ABS(bw * cosa) + L_ABS(bh * sina);
408  rh = L_ABS(bh * cosa) + L_ABS(bw * sina);
409  rx = xcen + xdif * cosa - ydif * sina - 0.5 * rw;
410  ry = ycen + ydif * cosa + xdif * sina - 0.5 * rh;
411  }
412  tx = (l_int32)(scalex * rx + 0.5);
413  ty = (l_int32)(scaley * ry + 0.5);
414  tw = (l_int32)(L_MAX(1.0, scalex * rw + 0.5));
415  th = (l_int32)(L_MAX(1.0, scaley * rh + 0.5));
416  boxd = boxCreate(tx, ty, tw, th);
417  } else { /* order == L_SC_RO_TR) */
418  tx = (l_int32)(scalex * bx + 0.5);
419  ty = (l_int32)(scaley * by + 0.5);
420  tw = (l_int32)(L_MAX(1.0, scalex * bw + 0.5));
421  th = (l_int32)(L_MAX(1.0, scaley * bh + 0.5));
422  xcent = (l_int32)(scalex * xcen + 0.5);
423  ycent = (l_int32)(scaley * ycen + 0.5);
424  if (angle == 0.0) {
425  rx = tx;
426  ry = ty;
427  rw = tw;
428  rh = th;
429  } else {
430  xdif = tx + 0.5 * tw - xcent;
431  ydif = ty + 0.5 * th - ycent;
432  rw = L_ABS(tw * cosa) + L_ABS(th * sina);
433  rh = L_ABS(th * cosa) + L_ABS(tw * sina);
434  rx = xcent + xdif * cosa - ydif * sina - 0.5 * rw;
435  ry = ycent + ydif * cosa + xdif * sina - 0.5 * rh;
436  }
437  tx = (l_int32)(rx + shiftx + 0.5);
438  ty = (l_int32)(ry + shifty + 0.5);
439  tw = (l_int32)(rw + 0.5);
440  th = (l_int32)(rh + 0.5);
441  boxd = boxCreate(tx, ty, tw, th);
442  }
443 
444  return boxd;
445 }
446 
447 
462 BOXA *
464  l_int32 w,
465  l_int32 h,
466  l_int32 rotation)
467 {
468 l_int32 i, n;
469 BOX *boxs, *boxd;
470 BOXA *boxad;
471 
472  if (!boxas)
473  return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
474  if (rotation < 0 || rotation > 3)
475  return (BOXA *)ERROR_PTR("rotation not in {0,1,2,3}", __func__, NULL);
476  if (rotation == 0)
477  return boxaCopy(boxas, L_COPY);
478 
479  n = boxaGetCount(boxas);
480  if ((boxad = boxaCreate(n)) == NULL)
481  return (BOXA *)ERROR_PTR("boxad not made", __func__, NULL);
482  for (i = 0; i < n; i++) {
483  if ((boxs = boxaGetBox(boxas, i, L_CLONE)) == NULL) {
484  boxaDestroy(&boxad);
485  return (BOXA *)ERROR_PTR("boxs not found", __func__, NULL);
486  }
487  boxd = boxRotateOrth(boxs, w, h, rotation);
488  boxDestroy(&boxs);
489  boxaAddBox(boxad, boxd, L_INSERT);
490  }
491 
492  return boxad;
493 }
494 
495 
512 BOX *
514  l_int32 w,
515  l_int32 h,
516  l_int32 rotation)
517 {
518 l_int32 bx, by, bw, bh, xdist, ydist;
519 
520  if (!box)
521  return (BOX *)ERROR_PTR("box not defined", __func__, NULL);
522  if (rotation < 0 || rotation > 3)
523  return (BOX *)ERROR_PTR("rotation not in {0,1,2,3}", __func__, NULL);
524  if (rotation == 0)
525  return boxCopy(box);
526 
527  boxGetGeometry(box, &bx, &by, &bw, &bh);
528  if (bw <= 0 || bh <= 0) /* invalid */
529  return boxCreate(0, 0, 0, 0);
530  ydist = h - by - bh; /* below box */
531  xdist = w - bx - bw; /* to right of box */
532  if (rotation == 1) /* 90 deg cw */
533  return boxCreate(ydist, bx, bh, bw);
534  else if (rotation == 2) /* 180 deg cw */
535  return boxCreate(xdist, ydist, bw, bh);
536  else /* rotation == 3, 270 deg cw */
537  return boxCreate(by, xdist, bh, bw);
538 }
539 
540 
565 BOXA *
567  PTA *pta,
568  l_int32 dir)
569 {
570 l_int32 i, n, x, y, full;
571 BOX *box1, *box2;
572 BOXA *boxad;
573 
574  if (!boxas)
575  return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
576  boxaIsFull(boxas, &full);
577  if (!full)
578  return (BOXA *)ERROR_PTR("boxas not full", __func__, NULL);
579  if (!pta)
580  return (BOXA *)ERROR_PTR("pta not defined", __func__, NULL);
581  if (dir != 1 && dir != -1)
582  return (BOXA *)ERROR_PTR("invalid dir", __func__, NULL);
583  n = boxaGetCount(boxas);
584  if (n != ptaGetCount(pta))
585  return (BOXA *)ERROR_PTR("boxas and pta not same size", __func__, NULL);
586 
587  if ((boxad = boxaCreate(n)) == NULL)
588  return (BOXA *)ERROR_PTR("boxad not made", __func__, NULL);
589  for (i = 0; i < n; i++) {
590  box1 = boxaGetBox(boxas, i, L_COPY);
591  ptaGetIPt(pta, i, &x, &y);
592  box2 = boxTransform(box1, dir * x, dir * y, 1.0, 1.0);
593  boxaAddBox(boxad, box2, L_INSERT);
594  boxDestroy(&box1);
595  }
596  return boxad;
597 }
598 
599 
600 /*---------------------------------------------------------------------*
601  * Boxa sort *
602  *---------------------------------------------------------------------*/
623 BOXA *
624 boxaSort(BOXA *boxas,
625  l_int32 sorttype,
626  l_int32 sortorder,
627  NUMA **pnaindex)
628 {
629 l_int32 i, n, x, y, w, h, size;
630 BOXA *boxad;
631 NUMA *na, *naindex;
632 
633  if (pnaindex) *pnaindex = NULL;
634  if (!boxas)
635  return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
636  if ((n = boxaGetCount(boxas)) == 0) {
637  L_WARNING("boxas is empty\n", __func__);
638  return boxaCopy(boxas, L_COPY);
639  }
640  if (sorttype != L_SORT_BY_X && sorttype != L_SORT_BY_Y &&
641  sorttype != L_SORT_BY_RIGHT && sorttype != L_SORT_BY_BOT &&
642  sorttype != L_SORT_BY_WIDTH && sorttype != L_SORT_BY_HEIGHT &&
643  sorttype != L_SORT_BY_MIN_DIMENSION &&
644  sorttype != L_SORT_BY_MAX_DIMENSION &&
645  sorttype != L_SORT_BY_PERIMETER &&
646  sorttype != L_SORT_BY_AREA &&
647  sorttype != L_SORT_BY_ASPECT_RATIO)
648  return (BOXA *)ERROR_PTR("invalid sort type", __func__, NULL);
649  if (sortorder != L_SORT_INCREASING && sortorder != L_SORT_DECREASING)
650  return (BOXA *)ERROR_PTR("invalid sort order", __func__, NULL);
651 
652  /* Use O(n) binsort if possible */
653  if (n > MinCompsForBinSort &&
654  ((sorttype == L_SORT_BY_X) || (sorttype == L_SORT_BY_Y) ||
655  (sorttype == L_SORT_BY_WIDTH) || (sorttype == L_SORT_BY_HEIGHT) ||
656  (sorttype == L_SORT_BY_PERIMETER)))
657  return boxaBinSort(boxas, sorttype, sortorder, pnaindex);
658 
659  /* Build up numa of specific data */
660  if ((na = numaCreate(n)) == NULL)
661  return (BOXA *)ERROR_PTR("na not made", __func__, NULL);
662  for (i = 0; i < n; i++) {
663  boxaGetBoxGeometry(boxas, i, &x, &y, &w, &h);
664  switch (sorttype)
665  {
666  case L_SORT_BY_X:
667  numaAddNumber(na, x);
668  break;
669  case L_SORT_BY_Y:
670  numaAddNumber(na, y);
671  break;
672  case L_SORT_BY_RIGHT:
673  numaAddNumber(na, x + w - 1);
674  break;
675  case L_SORT_BY_BOT:
676  numaAddNumber(na, y + h - 1);
677  break;
678  case L_SORT_BY_WIDTH:
679  numaAddNumber(na, w);
680  break;
681  case L_SORT_BY_HEIGHT:
682  numaAddNumber(na, h);
683  break;
685  size = L_MIN(w, h);
686  numaAddNumber(na, size);
687  break;
689  size = L_MAX(w, h);
690  numaAddNumber(na, size);
691  break;
692  case L_SORT_BY_PERIMETER:
693  size = w + h;
694  numaAddNumber(na, size);
695  break;
696  case L_SORT_BY_AREA:
697  size = w * h;
698  numaAddNumber(na, size);
699  break;
701  numaAddNumber(na, (l_float32)w / (l_float32)h);
702  break;
703  default:
704  L_WARNING("invalid sort type\n", __func__);
705  }
706  }
707 
708  /* Get the sort index for data array */
709  naindex = numaGetSortIndex(na, sortorder);
710  numaDestroy(&na);
711  if (!naindex)
712  return (BOXA *)ERROR_PTR("naindex not made", __func__, NULL);
713 
714  /* Build up sorted boxa using sort index */
715  boxad = boxaSortByIndex(boxas, naindex);
716 
717  if (pnaindex)
718  *pnaindex = naindex;
719  else
720  numaDestroy(&naindex);
721  return boxad;
722 }
723 
724 
745 BOXA *
747  l_int32 sorttype,
748  l_int32 sortorder,
749  NUMA **pnaindex)
750 {
751 l_int32 i, n, x, y, w, h;
752 BOXA *boxad;
753 NUMA *na, *naindex;
754 
755  if (pnaindex) *pnaindex = NULL;
756  if (!boxas)
757  return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
758  if ((n = boxaGetCount(boxas)) == 0) {
759  L_WARNING("boxas is empty\n", __func__);
760  return boxaCopy(boxas, L_COPY);
761  }
762  if (sorttype != L_SORT_BY_X && sorttype != L_SORT_BY_Y &&
763  sorttype != L_SORT_BY_WIDTH && sorttype != L_SORT_BY_HEIGHT &&
764  sorttype != L_SORT_BY_PERIMETER)
765  return (BOXA *)ERROR_PTR("invalid sort type", __func__, NULL);
766  if (sortorder != L_SORT_INCREASING && sortorder != L_SORT_DECREASING)
767  return (BOXA *)ERROR_PTR("invalid sort order", __func__, NULL);
768 
769  /* Generate Numa of appropriate box dimensions */
770  if ((na = numaCreate(n)) == NULL)
771  return (BOXA *)ERROR_PTR("na not made", __func__, NULL);
772  for (i = 0; i < n; i++) {
773  boxaGetBoxGeometry(boxas, i, &x, &y, &w, &h);
774  switch (sorttype)
775  {
776  case L_SORT_BY_X:
777  numaAddNumber(na, x);
778  break;
779  case L_SORT_BY_Y:
780  numaAddNumber(na, y);
781  break;
782  case L_SORT_BY_WIDTH:
783  numaAddNumber(na, w);
784  break;
785  case L_SORT_BY_HEIGHT:
786  numaAddNumber(na, h);
787  break;
788  case L_SORT_BY_PERIMETER:
789  numaAddNumber(na, w + h);
790  break;
791  default:
792  L_WARNING("invalid sort type\n", __func__);
793  }
794  }
795 
796  /* Get the sort index for data array */
797  naindex = numaGetBinSortIndex(na, sortorder);
798  numaDestroy(&na);
799  if (!naindex)
800  return (BOXA *)ERROR_PTR("naindex not made", __func__, NULL);
801 
802  /* Build up sorted boxa using the sort index */
803  boxad = boxaSortByIndex(boxas, naindex);
804 
805  if (pnaindex)
806  *pnaindex = naindex;
807  else
808  numaDestroy(&naindex);
809  return boxad;
810 }
811 
812 
820 BOXA *
822  NUMA *naindex)
823 {
824 l_int32 i, n, index;
825 BOX *box;
826 BOXA *boxad;
827 
828  if (!boxas)
829  return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
830  if ((n = boxaGetCount(boxas)) == 0) {
831  L_WARNING("boxas is empty\n", __func__);
832  return boxaCopy(boxas, L_COPY);
833  }
834  if (!naindex)
835  return (BOXA *)ERROR_PTR("naindex not defined", __func__, NULL);
836 
837  boxad = boxaCreate(n);
838  for (i = 0; i < n; i++) {
839  numaGetIValue(naindex, i, &index);
840  box = boxaGetBox(boxas, index, L_COPY);
841  boxaAddBox(boxad, box, L_INSERT);
842  }
843 
844  return boxad;
845 }
846 
847 
895 BOXAA *
897  NUMAA **pnaad,
898  l_int32 delta1,
899  l_int32 delta2,
900  l_int32 minh1)
901 {
902 l_int32 i, index, h, nt, ne, n, m, ival;
903 BOX *box;
904 BOXA *boxa, *boxae, *boxan, *boxa1, *boxa2, *boxa3, *boxav, *boxavs;
905 BOXAA *baa, *baa1, *baad;
906 NUMA *naindex, *nae, *nan, *nah, *nav, *na1, *na2, *nad, *namap;
907 NUMAA *naa, *naa1, *naad;
908 
909  if (pnaad) *pnaad = NULL;
910  if (!boxas)
911  return (BOXAA *)ERROR_PTR("boxas not defined", __func__, NULL);
912  if (boxaGetCount(boxas) == 0)
913  return (BOXAA *)ERROR_PTR("boxas is empty", __func__, NULL);
914 
915  /* Sort from left to right */
916  if ((boxa = boxaSort(boxas, L_SORT_BY_X, L_SORT_INCREASING, &naindex))
917  == NULL)
918  return (BOXAA *)ERROR_PTR("boxa not made", __func__, NULL);
919 
920  /* First pass: assign taller boxes to boxa by row */
921  nt = boxaGetCount(boxa);
922  baa = boxaaCreate(0);
923  naa = numaaCreate(0);
924  boxae = boxaCreate(0); /* save small height boxes here */
925  nae = numaCreate(0); /* keep track of small height boxes */
926  for (i = 0; i < nt; i++) {
927  box = boxaGetBox(boxa, i, L_CLONE);
928  boxGetGeometry(box, NULL, NULL, NULL, &h);
929  if (h < minh1) { /* save for 2nd pass */
930  boxaAddBox(boxae, box, L_INSERT);
931  numaAddNumber(nae, i);
932  } else {
933  n = boxaaGetCount(baa);
934  boxaaAlignBox(baa, box, delta1, &index);
935  if (index < n) { /* append to an existing boxa */
936  boxaaAddBox(baa, index, box, L_INSERT);
937  } else { /* doesn't align, need new boxa */
938  boxan = boxaCreate(0);
939  boxaAddBox(boxan, box, L_INSERT);
940  boxaaAddBoxa(baa, boxan, L_INSERT);
941  nan = numaCreate(0);
942  numaaAddNuma(naa, nan, L_INSERT);
943  }
944  numaGetIValue(naindex, i, &ival);
945  numaaAddNumber(naa, index, ival);
946  }
947  }
948  boxaDestroy(&boxa);
949  numaDestroy(&naindex);
950 
951  /* Second pass: feed in small height boxes */
952  ne = boxaGetCount(boxae);
953  for (i = 0; i < ne; i++) {
954  box = boxaGetBox(boxae, i, L_CLONE);
955  n = boxaaGetCount(baa);
956  boxaaAlignBox(baa, box, delta2, &index);
957  if (index < n) { /* append to an existing boxa */
958  boxaaAddBox(baa, index, box, L_INSERT);
959  } else { /* doesn't align, need new boxa */
960  boxan = boxaCreate(0);
961  boxaAddBox(boxan, box, L_INSERT);
962  boxaaAddBoxa(baa, boxan, L_INSERT);
963  nan = numaCreate(0);
964  numaaAddNuma(naa, nan, L_INSERT);
965  }
966  numaGetIValue(nae, i, &ival); /* location in original boxas */
967  numaaAddNumber(naa, index, ival);
968  }
969 
970  /* Third pass: merge some boxa whose extent is overlapping.
971  * Think of these boxa as text lines, where the bounding boxes
972  * of the text lines can overlap, but likely won't have
973  * a huge overlap.
974  * First do a greedy find of pairs of overlapping boxa, where
975  * the two boxa overlap by at least 50% of the smaller, and
976  * the smaller is not more than half the area of the larger.
977  * For such pairs, call the larger one the primary boxa. The
978  * boxes in the smaller one are appended to those in the primary
979  * in pass 3a, and the primaries are extracted in pass 3b.
980  * In this way, all boxes in the original baa are saved. */
981  n = boxaaGetCount(baa);
982  boxaaGetExtent(baa, NULL, NULL, NULL, &boxa3);
983  boxa1 = boxaHandleOverlaps(boxa3, L_REMOVE_SMALL, 1000, 0.5, 0.5, &namap);
984  boxaDestroy(&boxa1);
985  boxaDestroy(&boxa3);
986  for (i = 0; i < n; i++) { /* Pass 3a: join selected copies of boxa */
987  numaGetIValue(namap, i, &ival);
988  if (ival >= 0) { /* join current to primary boxa[ival] */
989  boxa1 = boxaaGetBoxa(baa, i, L_COPY);
990  boxa2 = boxaaGetBoxa(baa, ival, L_CLONE);
991  boxaJoin(boxa2, boxa1, 0, -1);
992  boxaDestroy(&boxa2);
993  boxaDestroy(&boxa1);
994  na1 = numaaGetNuma(naa, i, L_COPY);
995  na2 = numaaGetNuma(naa, ival, L_CLONE);
996  numaJoin(na2, na1, 0, -1);
997  numaDestroy(&na1);
998  numaDestroy(&na2);
999  }
1000  }
1001  baa1 = boxaaCreate(n);
1002  naa1 = numaaCreate(n);
1003  for (i = 0; i < n; i++) { /* Pass 3b: save primary boxa */
1004  numaGetIValue(namap, i, &ival);
1005  if (ival == -1) {
1006  boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
1007  boxaaAddBoxa(baa1, boxa1, L_INSERT);
1008  na1 = numaaGetNuma(naa, i, L_CLONE);
1009  numaaAddNuma(naa1, na1, L_INSERT);
1010  }
1011  }
1012  numaDestroy(&namap);
1013  boxaaDestroy(&baa);
1014  baa = baa1;
1015  numaaDestroy(&naa);
1016  naa = naa1;
1017 
1018  /* Sort the boxes in each boxa horizontally */
1019  m = boxaaGetCount(baa);
1020  for (i = 0; i < m; i++) {
1021  boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
1022  boxa2 = boxaSort(boxa1, L_SORT_BY_X, L_SORT_INCREASING, &nah);
1023  boxaaReplaceBoxa(baa, i, boxa2);
1024  na1 = numaaGetNuma(naa, i, L_CLONE);
1025  na2 = numaSortByIndex(na1, nah);
1026  numaaReplaceNuma(naa, i, na2);
1027  boxaDestroy(&boxa1);
1028  numaDestroy(&na1);
1029  numaDestroy(&nah);
1030  }
1031 
1032  /* Sort the boxa vertically within boxaa, using the first box
1033  * in each boxa. */
1034  m = boxaaGetCount(baa);
1035  boxav = boxaCreate(m); /* holds first box in each boxa in baa */
1036  naad = numaaCreate(m);
1037  if (pnaad)
1038  *pnaad = naad;
1039  baad = boxaaCreate(m);
1040  for (i = 0; i < m; i++) {
1041  boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
1042  box = boxaGetBox(boxa1, 0, L_CLONE);
1043  boxaAddBox(boxav, box, L_INSERT);
1044  boxaDestroy(&boxa1);
1045  }
1046  boxavs = boxaSort(boxav, L_SORT_BY_Y, L_SORT_INCREASING, &nav);
1047  for (i = 0; i < m; i++) {
1048  numaGetIValue(nav, i, &index);
1049  boxa = boxaaGetBoxa(baa, index, L_CLONE);
1050  boxaaAddBoxa(baad, boxa, L_INSERT);
1051  nad = numaaGetNuma(naa, index, L_CLONE);
1052  numaaAddNuma(naad, nad, L_INSERT);
1053  }
1054 
1055 
1056 /* lept_stderr("box count = %d, numaa count = %d\n", nt,
1057  numaaGetNumberCount(naad)); */
1058 
1059  boxaaDestroy(&baa);
1060  boxaDestroy(&boxav);
1061  boxaDestroy(&boxavs);
1062  boxaDestroy(&boxae);
1063  numaDestroy(&nav);
1064  numaDestroy(&nae);
1065  numaaDestroy(&naa);
1066  if (!pnaad)
1067  numaaDestroy(&naad);
1068 
1069  return baad;
1070 }
1071 
1072 
1080 BOXAA *
1082  NUMAA *naa)
1083 {
1084 l_int32 ntot, boxtot, i, j, n, nn, index;
1085 BOX *box;
1086 BOXA *boxa;
1087 BOXAA *baa;
1088 NUMA *na;
1089 
1090  if (!boxas)
1091  return (BOXAA *)ERROR_PTR("boxas not defined", __func__, NULL);
1092  if ((boxtot = boxaGetCount(boxas)) == 0)
1093  return (BOXAA *)ERROR_PTR("boxas is empty", __func__, NULL);
1094  if (!naa)
1095  return (BOXAA *)ERROR_PTR("naindex not defined", __func__, NULL);
1096 
1097  /* Check counts */
1098  ntot = numaaGetNumberCount(naa);
1099  if (ntot != boxtot)
1100  return (BOXAA *)ERROR_PTR("element count mismatch", __func__, NULL);
1101 
1102  n = numaaGetCount(naa);
1103  baa = boxaaCreate(n);
1104  for (i = 0; i < n; i++) {
1105  na = numaaGetNuma(naa, i, L_CLONE);
1106  nn = numaGetCount(na);
1107  boxa = boxaCreate(nn);
1108  for (j = 0; j < nn; j++) {
1109  numaGetIValue(na, i, &index);
1110  box = boxaGetBox(boxas, index, L_COPY);
1111  boxaAddBox(boxa, box, L_INSERT);
1112  }
1113  boxaaAddBoxa(baa, boxa, L_INSERT);
1114  numaDestroy(&na);
1115  }
1116 
1117  return baa;
1118 }
1119 
1120 
1121 /*---------------------------------------------------------------------*
1122  * Boxa array extraction *
1123  *---------------------------------------------------------------------*/
1147 l_ok
1149  NUMA **pnal,
1150  NUMA **pnat,
1151  NUMA **pnar,
1152  NUMA **pnab,
1153  NUMA **pnaw,
1154  NUMA **pnah,
1155  l_int32 keepinvalid)
1156 {
1157 l_int32 i, n, left, top, right, bot, w, h;
1158 
1159  if (!pnal && !pnat && !pnar && !pnab && !pnaw && !pnah)
1160  return ERROR_INT("no output requested", __func__, 1);
1161  if (pnal) *pnal = NULL;
1162  if (pnat) *pnat = NULL;
1163  if (pnar) *pnar = NULL;
1164  if (pnab) *pnab = NULL;
1165  if (pnaw) *pnaw = NULL;
1166  if (pnah) *pnah = NULL;
1167  if (!boxa)
1168  return ERROR_INT("boxa not defined", __func__, 1);
1169  if (!keepinvalid && boxaGetValidCount(boxa) == 0)
1170  return ERROR_INT("no valid boxes", __func__, 1);
1171 
1172  n = boxaGetCount(boxa);
1173  if (pnal) *pnal = numaCreate(n);
1174  if (pnat) *pnat = numaCreate(n);
1175  if (pnar) *pnar = numaCreate(n);
1176  if (pnab) *pnab = numaCreate(n);
1177  if (pnaw) *pnaw = numaCreate(n);
1178  if (pnah) *pnah = numaCreate(n);
1179  for (i = 0; i < n; i++) {
1180  boxaGetBoxGeometry(boxa, i, &left, &top, &w, &h);
1181  if (!keepinvalid && (w <= 0 || h <= 0))
1182  continue;
1183  right = left + w - 1;
1184  bot = top + h - 1;
1185  if (pnal) numaAddNumber(*pnal, left);
1186  if (pnat) numaAddNumber(*pnat, top);
1187  if (pnar) numaAddNumber(*pnar, right);
1188  if (pnab) numaAddNumber(*pnab, bot);
1189  if (pnaw) numaAddNumber(*pnaw, w);
1190  if (pnah) numaAddNumber(*pnah, h);
1191  }
1192 
1193  return 0;
1194 }
1195 
1196 
1226 l_ok
1228  PTA **pptal,
1229  PTA **pptat,
1230  PTA **pptar,
1231  PTA **pptab,
1232  PTA **pptaw,
1233  PTA **pptah,
1234  l_int32 keepinvalid)
1235 {
1236 l_int32 i, n, left, top, right, bot, w, h;
1237 
1238  if (!pptal && !pptar && !pptat && !pptab && !pptaw && !pptah)
1239  return ERROR_INT("no output requested", __func__, 1);
1240  if (pptal) *pptal = NULL;
1241  if (pptat) *pptat = NULL;
1242  if (pptar) *pptar = NULL;
1243  if (pptab) *pptab = NULL;
1244  if (pptaw) *pptaw = NULL;
1245  if (pptah) *pptah = NULL;
1246  if (!boxa)
1247  return ERROR_INT("boxa not defined", __func__, 1);
1248  if (!keepinvalid && boxaGetValidCount(boxa) == 0)
1249  return ERROR_INT("no valid boxes", __func__, 1);
1250 
1251  n = boxaGetCount(boxa);
1252  if (pptal) *pptal = ptaCreate(n);
1253  if (pptat) *pptat = ptaCreate(n);
1254  if (pptar) *pptar = ptaCreate(n);
1255  if (pptab) *pptab = ptaCreate(n);
1256  if (pptaw) *pptaw = ptaCreate(n);
1257  if (pptah) *pptah = ptaCreate(n);
1258  for (i = 0; i < n; i++) {
1259  boxaGetBoxGeometry(boxa, i, &left, &top, &w, &h);
1260  if (!keepinvalid && (w <= 0 || h <= 0))
1261  continue;
1262  right = left + w - 1;
1263  bot = top + h - 1;
1264  if (pptal) ptaAddPt(*pptal, i, left);
1265  if (pptat) ptaAddPt(*pptat, i, top);
1266  if (pptar) ptaAddPt(*pptar, i, right);
1267  if (pptab) ptaAddPt(*pptab, i, bot);
1268  if (pptaw) ptaAddPt(*pptaw, i, w);
1269  if (pptah) ptaAddPt(*pptah, i, h);
1270  }
1271 
1272  return 0;
1273 }
1274 
1275 
1294 PTA *
1296  l_int32 loc)
1297 {
1298 l_int32 i, n, left, top, right, bot, w, h;
1299 PTA *pta;
1300 
1301  if (!boxa)
1302  return (PTA *)ERROR_PTR("boxa not defined", __func__, NULL);
1303  if (loc != L_UPPER_LEFT && loc != L_UPPER_RIGHT && loc != L_LOWER_LEFT &&
1304  loc != L_LOWER_RIGHT && loc != L_BOX_CENTER)
1305  return (PTA *)ERROR_PTR("invalid location", __func__, NULL);
1306 
1307  n = boxaGetCount(boxa);
1308  if ((pta = ptaCreate(n)) == NULL)
1309  return (PTA *)ERROR_PTR("pta not made", __func__, NULL);
1310 
1311  for (i = 0; i < n; i++) {
1312  boxaGetBoxGeometry(boxa, i, &left, &top, &w, &h);
1313  right = left + w - 1;
1314  bot = top + h - 1;
1315  if (w == 0 || h == 0) { /* invalid */
1316  left = 0;
1317  top = 0;
1318  right = 0;
1319  bot = 0;
1320  }
1321  if (loc == L_UPPER_LEFT)
1322  ptaAddPt(pta, left, top);
1323  else if (loc == L_UPPER_RIGHT)
1324  ptaAddPt(pta, right, top);
1325  else if (loc == L_LOWER_LEFT)
1326  ptaAddPt(pta, left, bot);
1327  else if (loc == L_LOWER_RIGHT)
1328  ptaAddPt(pta, right, bot);
1329  else if (loc == L_BOX_CENTER)
1330  ptaAddPt(pta, (left + right) / 2, (top + bot) / 2);
1331  }
1332 
1333  return pta;
1334 }
1335 
1336 
1337 /*---------------------------------------------------------------------*
1338  * Boxa statistics *
1339  *---------------------------------------------------------------------*/
1371 l_ok
1373  l_float32 fract,
1374  l_int32 *px,
1375  l_int32 *py,
1376  l_int32 *pr,
1377  l_int32 *pb,
1378  l_int32 *pw,
1379  l_int32 *ph)
1380 {
1381 l_float32 xval, yval, rval, bval, wval, hval;
1382 NUMA *nax, *nay, *nar, *nab, *naw, *nah;
1383 
1384  if (px) *px = 0;
1385  if (py) *py = 0;
1386  if (pr) *pr = 0;
1387  if (pb) *pb = 0;
1388  if (pw) *pw = 0;
1389  if (ph) *ph = 0;
1390  if (!boxa)
1391  return ERROR_INT("boxa not defined", __func__, 1);
1392  if (fract < 0.0 || fract > 1.0)
1393  return ERROR_INT("fract not in [0.0 ... 1.0]", __func__, 1);
1394  if (boxaGetValidCount(boxa) == 0)
1395  return ERROR_INT("no valid boxes in boxa", __func__, 1);
1396 
1397  /* Use only the valid boxes */
1398  boxaExtractAsNuma(boxa, &nax, &nay, &nar, &nab, &naw, &nah, 0);
1399 
1400  if (px) {
1401  numaGetRankValue(nax, 1.0 - fract, NULL, 1, &xval);
1402  *px = (l_int32)xval;
1403  }
1404  if (py) {
1405  numaGetRankValue(nay, 1.0 - fract, NULL, 1, &yval);
1406  *py = (l_int32)yval;
1407  }
1408  if (pr) {
1409  numaGetRankValue(nar, fract, NULL, 1, &rval);
1410  *pr = (l_int32)rval;
1411  }
1412  if (pb) {
1413  numaGetRankValue(nab, fract, NULL, 1, &bval);
1414  *pb = (l_int32)bval;
1415  }
1416  if (pw) {
1417  numaGetRankValue(naw, fract, NULL, 1, &wval);
1418  *pw = (l_int32)wval;
1419  }
1420  if (ph) {
1421  numaGetRankValue(nah, fract, NULL, 1, &hval);
1422  *ph = (l_int32)hval;
1423  }
1424  numaDestroy(&nax);
1425  numaDestroy(&nay);
1426  numaDestroy(&nar);
1427  numaDestroy(&nab);
1428  numaDestroy(&naw);
1429  numaDestroy(&nah);
1430  return 0;
1431 }
1432 
1433 
1451 l_ok
1453  l_int32 *px,
1454  l_int32 *py,
1455  l_int32 *pr,
1456  l_int32 *pb,
1457  l_int32 *pw,
1458  l_int32 *ph)
1459 {
1460  if (!boxa)
1461  return ERROR_INT("boxa not defined", __func__, 1);
1462  if (boxaGetValidCount(boxa) == 0)
1463  return ERROR_INT("no valid boxes in boxa", __func__, 1);
1464 
1465  return boxaGetRankVals(boxa, 0.5, px, py, pr, pb, pw, ph);
1466 }
1467 
1468 
1477 l_ok
1479  l_float32 *pw,
1480  l_float32 *ph)
1481 {
1482 l_int32 i, n, bw, bh;
1483 l_float32 sumw, sumh;
1484 
1485  if (pw) *pw = 0.0;
1486  if (ph) *ph = 0.0;
1487  if (!boxa)
1488  return ERROR_INT("boxa not defined", __func__, 1);
1489  if ((n = boxaGetCount(boxa)) == 0)
1490  return ERROR_INT("boxa is empty", __func__, 1);
1491 
1492  sumw = sumh = 0.0;
1493  for (i = 0; i < n; i++) {
1494  boxaGetBoxGeometry(boxa, i, NULL, NULL, &bw, &bh);
1495  sumw += bw;
1496  sumh += bh;
1497  }
1498 
1499  if (pw) *pw = sumw / n;
1500  if (ph) *ph = sumh / n;
1501  return 0;
1502 }
1503 
1504 
1505 /*---------------------------------------------------------------------*
1506  * Other Boxaa functions *
1507  *---------------------------------------------------------------------*/
1530 l_ok
1532  l_int32 *pw,
1533  l_int32 *ph,
1534  BOX **pbox,
1535  BOXA **pboxa)
1536 {
1537 l_int32 i, n, x, y, w, h, xmax, ymax, xmin, ymin, found;
1538 BOX *box1;
1539 BOXA *boxa, *boxa1;
1540 
1541  if (!pw && !ph && !pbox && !pboxa)
1542  return ERROR_INT("no ptrs defined", __func__, 1);
1543  if (pw) *pw = 0;
1544  if (ph) *ph = 0;
1545  if (pbox) *pbox = NULL;
1546  if (pboxa) *pboxa = NULL;
1547  if (!baa)
1548  return ERROR_INT("baa not defined", __func__, 1);
1549 
1550  n = boxaaGetCount(baa);
1551  if (n == 0)
1552  return ERROR_INT("no boxa in baa", __func__, 1);
1553 
1554  boxa = boxaCreate(n);
1555  xmax = ymax = 0;
1556  xmin = ymin = 100000000;
1557  found = FALSE;
1558  for (i = 0; i < n; i++) {
1559  boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
1560  boxaGetExtent(boxa1, NULL, NULL, &box1);
1561  boxaDestroy(&boxa1);
1562  boxGetGeometry(box1, &x, &y, &w, &h);
1563  if (w > 0 && h > 0) { /* a valid extent box */
1564  found = TRUE; /* found at least one valid extent box */
1565  xmin = L_MIN(xmin, x);
1566  ymin = L_MIN(ymin, y);
1567  xmax = L_MAX(xmax, x + w);
1568  ymax = L_MAX(ymax, y + h);
1569  }
1570  boxaAddBox(boxa, box1, L_INSERT);
1571  }
1572  if (found == FALSE) /* no valid extent boxes */
1573  xmin = ymin = 0;
1574 
1575  if (pw) *pw = xmax;
1576  if (ph) *ph = ymax;
1577  if (pbox)
1578  *pbox = boxCreate(xmin, ymin, xmax - xmin, ymax - ymin);
1579  if (pboxa)
1580  *pboxa = boxa;
1581  else
1582  boxaDestroy(&boxa);
1583  return 0;
1584 }
1585 
1586 
1608 BOXA *
1610  NUMA **pnaindex,
1611  l_int32 copyflag)
1612 {
1613 l_int32 i, j, m, n;
1614 BOXA *boxa, *boxat;
1615 BOX *box;
1616 NUMA *naindex;
1617 
1618  if (pnaindex) *pnaindex = NULL;
1619  if (!baa)
1620  return (BOXA *)ERROR_PTR("baa not defined", __func__, NULL);
1621  if (copyflag != L_COPY && copyflag != L_CLONE)
1622  return (BOXA *)ERROR_PTR("invalid copyflag", __func__, NULL);
1623  if (pnaindex) {
1624  naindex = numaCreate(0);
1625  *pnaindex = naindex;
1626  }
1627 
1628  n = boxaaGetCount(baa);
1629  boxa = boxaCreate(n);
1630  for (i = 0; i < n; i++) {
1631  boxat = boxaaGetBoxa(baa, i, L_CLONE);
1632  m = boxaGetCount(boxat);
1633  if (m == 0) { /* placeholder box */
1634  box = boxCreate(0, 0, 0, 0);
1635  boxaAddBox(boxa, box, L_INSERT);
1636  if (pnaindex)
1637  numaAddNumber(naindex, i); /* save 'row' number */
1638  } else {
1639  for (j = 0; j < m; j++) {
1640  box = boxaGetBox(boxat, j, copyflag);
1641  boxaAddBox(boxa, box, L_INSERT);
1642  if (pnaindex)
1643  numaAddNumber(naindex, i); /* save 'row' number */
1644  }
1645  }
1646  boxaDestroy(&boxat);
1647  }
1648 
1649  return boxa;
1650 }
1651 
1652 
1672 BOXA *
1674  l_int32 num,
1675  BOX *fillerbox,
1676  l_int32 copyflag)
1677 {
1678 l_int32 i, j, m, n, mval, nshort;
1679 BOXA *boxat, *boxad;
1680 BOX *box;
1681 
1682  if (!baa)
1683  return (BOXA *)ERROR_PTR("baa not defined", __func__, NULL);
1684  if (copyflag != L_COPY && copyflag != L_CLONE)
1685  return (BOXA *)ERROR_PTR("invalid copyflag", __func__, NULL);
1686 
1687  n = boxaaGetCount(baa);
1688  boxad = boxaCreate(n);
1689  for (i = 0; i < n; i++) {
1690  boxat = boxaaGetBoxa(baa, i, L_CLONE);
1691  m = boxaGetCount(boxat);
1692  mval = L_MIN(m, num);
1693  nshort = num - mval;
1694  for (j = 0; j < mval; j++) { /* take the first %num if possible */
1695  box = boxaGetBox(boxat, j, copyflag);
1696  boxaAddBox(boxad, box, L_INSERT);
1697  }
1698  for (j = 0; j < nshort; j++) { /* add fillers if necessary */
1699  if (fillerbox) {
1700  boxaAddBox(boxad, fillerbox, L_COPY);
1701  } else {
1702  box = boxCreate(0, 0, 0, 0); /* invalid placeholder box */
1703  boxaAddBox(boxad, box, L_INSERT);
1704  }
1705  }
1706  boxaDestroy(&boxat);
1707  }
1708 
1709  return boxad;
1710 }
1711 
1712 
1728 BOXAA *
1730  l_int32 num,
1731  l_int32 copyflag)
1732 {
1733 l_int32 i, j, n, nbaa, index;
1734 BOX *box;
1735 BOXA *boxat;
1736 BOXAA *baa;
1737 
1738  if (!boxa)
1739  return (BOXAA *)ERROR_PTR("boxa not defined", __func__, NULL);
1740  if (copyflag != L_COPY && copyflag != L_CLONE)
1741  return (BOXAA *)ERROR_PTR("invalid copyflag", __func__, NULL);
1742 
1743  n = boxaGetCount(boxa);
1744  nbaa = n / num;
1745  if (num * nbaa != n)
1746  L_ERROR("inconsistent alignment: num doesn't divide n\n", __func__);
1747  baa = boxaaCreate(nbaa);
1748  for (i = 0, index = 0; i < nbaa; i++) {
1749  boxat = boxaCreate(num);
1750  for (j = 0; j < num; j++, index++) {
1751  box = boxaGetBox(boxa, index, copyflag);
1752  boxaAddBox(boxat, box, L_INSERT);
1753  }
1754  boxaaAddBoxa(baa, boxat, L_INSERT);
1755  }
1756 
1757  return baa;
1758 }
1759 
1760 
1780 BOXAA *
1782 {
1783 l_int32 i, j, ny, nb, nbox;
1784 BOX *box;
1785 BOXA *boxa;
1786 BOXAA *baad;
1787 
1788  if (!baas)
1789  return (BOXAA *)ERROR_PTR("baas not defined", __func__, NULL);
1790  if ((ny = boxaaGetCount(baas)) == 0)
1791  return (BOXAA *)ERROR_PTR("baas empty", __func__, NULL);
1792 
1793  /* Make sure that each boxa in baas has the same number of boxes */
1794  for (i = 0; i < ny; i++) {
1795  if ((boxa = boxaaGetBoxa(baas, i, L_CLONE)) == NULL)
1796  return (BOXAA *)ERROR_PTR("baas is missing a boxa", __func__, NULL);
1797  nb = boxaGetCount(boxa);
1798  boxaDestroy(&boxa);
1799  if (i == 0)
1800  nbox = nb;
1801  else if (nb != nbox)
1802  return (BOXAA *)ERROR_PTR("boxa are not all the same size",
1803  __func__, NULL);
1804  }
1805 
1806  /* baad[i][j] = baas[j][i] */
1807  baad = boxaaCreate(nbox);
1808  for (i = 0; i < nbox; i++) {
1809  boxa = boxaCreate(ny);
1810  for (j = 0; j < ny; j++) {
1811  box = boxaaGetBox(baas, j, i, L_COPY);
1812  boxaAddBox(boxa, box, L_INSERT);
1813  }
1814  boxaaAddBoxa(baad, boxa, L_INSERT);
1815  }
1816  return baad;
1817 }
1818 
1819 
1837 l_ok
1839  BOX *box,
1840  l_int32 delta,
1841  l_int32 *pindex)
1842 {
1843 l_int32 i, n, m, y, yt, h, ht, ovlp, maxovlp, maxindex;
1844 BOX *boxt;
1845 BOXA *boxa;
1846 
1847  if (pindex) *pindex = 0;
1848  if (!baa)
1849  return ERROR_INT("baa not defined", __func__, 1);
1850  if (!box)
1851  return ERROR_INT("box not defined", __func__, 1);
1852  if (!pindex)
1853  return ERROR_INT("&index not defined", __func__, 1);
1854 
1855  n = boxaaGetCount(baa);
1856  boxGetGeometry(box, NULL, &y, NULL, &h);
1857  maxovlp = -10000000;
1858  for (i = 0; i < n; i++) {
1859  boxa = boxaaGetBoxa(baa, i, L_CLONE);
1860  if ((m = boxaGetCount(boxa)) == 0) {
1861  boxaDestroy(&boxa);
1862  L_WARNING("no boxes in boxa\n", __func__);
1863  continue;
1864  }
1865  boxaGetExtent(boxa, NULL, NULL, &boxt);
1866  boxGetGeometry(boxt, NULL, &yt, NULL, &ht);
1867  boxDestroy(&boxt);
1868  boxaDestroy(&boxa);
1869 
1870  /* Overlap < 0 means the components do not overlap vertically */
1871  if (yt >= y)
1872  ovlp = y + h - 1 - yt;
1873  else
1874  ovlp = yt + ht - 1 - y;
1875  if (ovlp > maxovlp) {
1876  maxovlp = ovlp;
1877  maxindex = i;
1878  }
1879  }
1880 
1881  if (maxovlp + delta >= 0)
1882  *pindex = maxindex;
1883  else
1884  *pindex = n;
1885  return 0;
1886 }
l_int32 boxaGetValidCount(BOXA *boxa)
boxaGetValidCount()
Definition: boxbasic.c:676
l_ok boxGetGeometry(const BOX *box, l_int32 *px, l_int32 *py, l_int32 *pw, l_int32 *ph)
boxGetGeometry()
Definition: boxbasic.c:301
l_ok boxaaReplaceBoxa(BOXAA *baa, l_int32 index, BOXA *boxa)
boxaaReplaceBoxa()
Definition: boxbasic.c:1542
l_ok boxaIsFull(BOXA *boxa, l_int32 *pfull)
boxaIsFull()
Definition: boxbasic.c:830
BOXA * boxaCopy(BOXA *boxa, l_int32 copyflag)
boxaCopy()
Definition: boxbasic.c:475
void boxDestroy(BOX **pbox)
boxDestroy()
Definition: boxbasic.c:273
BOX * boxaaGetBox(BOXAA *baa, l_int32 iboxa, l_int32 ibox, l_int32 accessflag)
boxaaGetBox()
Definition: boxbasic.c:1414
BOXAA * boxaaCreate(l_int32 n)
boxaaCreate()
Definition: boxbasic.c:1145
l_int32 boxaaGetCount(BOXAA *baa)
boxaaGetCount()
Definition: boxbasic.c:1343
l_ok boxaGetBoxGeometry(BOXA *boxa, l_int32 index, l_int32 *px, l_int32 *py, l_int32 *pw, l_int32 *ph)
boxaGetBoxGeometry()
Definition: boxbasic.c:796
l_ok boxaaAddBoxa(BOXAA *baa, BOXA *ba, l_int32 copyflag)
boxaaAddBoxa()
Definition: boxbasic.c:1241
l_ok boxaAddBox(BOXA *boxa, BOX *box, l_int32 copyflag)
boxaAddBox()
Definition: boxbasic.c:553
void boxaDestroy(BOXA **pboxa)
boxaDestroy()
Definition: boxbasic.c:519
l_int32 boxaGetCount(const BOXA *boxa)
boxaGetCount()
Definition: boxbasic.c:661
BOXA * boxaaGetBoxa(BOXAA *baa, l_int32 index, l_int32 accessflag)
boxaaGetBoxa()
Definition: boxbasic.c:1386
BOX * boxaGetBox(BOXA *boxa, l_int32 index, l_int32 accessflag)
boxaGetBox()
Definition: boxbasic.c:702
BOX * boxCopy(BOX *box)
boxCopy()
Definition: boxbasic.c:230
void boxaaDestroy(BOXAA **pbaa)
boxaaDestroy()
Definition: boxbasic.c:1207
BOX * boxCreate(l_int32 x, l_int32 y, l_int32 w, l_int32 h)
boxCreate()
Definition: boxbasic.c:171
BOXA * boxaCreate(l_int32 n)
boxaCreate()
Definition: boxbasic.c:442
l_ok boxaaAddBox(BOXAA *baa, l_int32 index, BOX *box, l_int32 accessflag)
boxaaAddBox()
Definition: boxbasic.c:1667
l_ok boxaJoin(BOXA *boxad, BOXA *boxas, l_int32 istart, l_int32 iend)
boxaJoin()
Definition: boxfunc1.c:2460
BOXA * boxaHandleOverlaps(BOXA *boxas, l_int32 op, l_int32 range, l_float32 min_overlap, l_float32 max_ratio, NUMA **pnamap)
boxaHandleOverlaps()
Definition: boxfunc1.c:887
BOXAA * boxaEncapsulateAligned(BOXA *boxa, l_int32 num, l_int32 copyflag)
boxaEncapsulateAligned()
Definition: boxfunc2.c:1729
BOXA * boxaaFlattenAligned(BOXAA *baa, l_int32 num, BOX *fillerbox, l_int32 copyflag)
boxaaFlattenAligned()
Definition: boxfunc2.c:1673
BOXAA * boxaSort2dByIndex(BOXA *boxas, NUMAA *naa)
boxaSort2dByIndex()
Definition: boxfunc2.c:1081
l_ok boxaaAlignBox(BOXAA *baa, BOX *box, l_int32 delta, l_int32 *pindex)
boxaaAlignBox()
Definition: boxfunc2.c:1838
l_ok boxaGetRankVals(BOXA *boxa, l_float32 fract, l_int32 *px, l_int32 *py, l_int32 *pr, l_int32 *pb, l_int32 *pw, l_int32 *ph)
boxaGetRankVals()
Definition: boxfunc2.c:1372
PTA * boxaExtractCorners(BOXA *boxa, l_int32 loc)
boxaExtractCorners()
Definition: boxfunc2.c:1295
l_ok boxaaGetExtent(BOXAA *baa, l_int32 *pw, l_int32 *ph, BOX **pbox, BOXA **pboxa)
boxaaGetExtent()
Definition: boxfunc2.c:1531
BOX * boxRotateOrth(BOX *box, l_int32 w, l_int32 h, l_int32 rotation)
boxRotateOrth()
Definition: boxfunc2.c:513
BOXA * boxaRotateOrth(BOXA *boxas, l_int32 w, l_int32 h, l_int32 rotation)
boxaRotateOrth()
Definition: boxfunc2.c:463
BOX * boxTransformOrdered(BOX *boxs, l_int32 shiftx, l_int32 shifty, l_float32 scalex, l_float32 scaley, l_int32 xcen, l_int32 ycen, l_float32 angle, l_int32 order)
boxTransformOrdered()
Definition: boxfunc2.c:291
BOX * boxTransform(BOX *box, l_int32 shiftx, l_int32 shifty, l_float32 scalex, l_float32 scaley)
boxTransform()
Definition: boxfunc2.c:151
l_ok boxaGetMedianVals(BOXA *boxa, l_int32 *px, l_int32 *py, l_int32 *pr, l_int32 *pb, l_int32 *pw, l_int32 *ph)
boxaGetMedianVals()
Definition: boxfunc2.c:1452
l_ok boxaGetAverageSize(BOXA *boxa, l_float32 *pw, l_float32 *ph)
boxaGetAverageSize()
Definition: boxfunc2.c:1478
BOXA * boxaTransformOrdered(BOXA *boxas, l_int32 shiftx, l_int32 shifty, l_float32 scalex, l_float32 scaley, l_int32 xcen, l_int32 ycen, l_float32 angle, l_int32 order)
boxaTransformOrdered()
Definition: boxfunc2.c:203
BOXA * boxaTransform(BOXA *boxas, l_int32 shiftx, l_int32 shifty, l_float32 scalex, l_float32 scaley)
boxaTransform()
Definition: boxfunc2.c:103
BOXA * boxaaFlattenToBoxa(BOXAA *baa, NUMA **pnaindex, l_int32 copyflag)
boxaaFlattenToBoxa()
Definition: boxfunc2.c:1609
BOXA * boxaSort(BOXA *boxas, l_int32 sorttype, l_int32 sortorder, NUMA **pnaindex)
boxaSort()
Definition: boxfunc2.c:624
BOXA * boxaSortByIndex(BOXA *boxas, NUMA *naindex)
boxaSortByIndex()
Definition: boxfunc2.c:821
BOXA * boxaBinSort(BOXA *boxas, l_int32 sorttype, l_int32 sortorder, NUMA **pnaindex)
boxaBinSort()
Definition: boxfunc2.c:746
BOXA * boxaShiftWithPta(BOXA *boxas, PTA *pta, l_int32 dir)
boxaShiftWithPta()
Definition: boxfunc2.c:566
BOXAA * boxaaTranspose(BOXAA *baas)
boxaaTranspose()
Definition: boxfunc2.c:1781
l_ok boxaExtractAsPta(BOXA *boxa, PTA **pptal, PTA **pptat, PTA **pptar, PTA **pptab, PTA **pptaw, PTA **pptah, l_int32 keepinvalid)
boxaExtractAsPta()
Definition: boxfunc2.c:1227
BOXAA * boxaSort2d(BOXA *boxas, NUMAA **pnaad, l_int32 delta1, l_int32 delta2, l_int32 minh1)
boxaSort2d()
Definition: boxfunc2.c:896
l_ok boxaExtractAsNuma(BOXA *boxa, NUMA **pnal, NUMA **pnat, NUMA **pnar, NUMA **pnab, NUMA **pnaw, NUMA **pnah, l_int32 keepinvalid)
boxaExtractAsNuma()
Definition: boxfunc2.c:1148
l_ok boxaGetExtent(BOXA *boxa, l_int32 *pw, l_int32 *ph, BOX **pbox)
boxaGetExtent()
Definition: boxfunc4.c:922
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:460
l_int32 numaaGetNumberCount(NUMAA *naa)
numaaGetNumberCount()
Definition: numabasic.c:1551
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:193
l_int32 numaaGetCount(NUMAA *naa)
numaaGetCount()
Definition: numabasic.c:1516
l_ok numaaAddNumber(NUMAA *naa, l_int32 index, l_float32 val)
numaaAddNumber()
Definition: numabasic.c:1723
NUMA * numaaGetNuma(NUMAA *naa, l_int32 index, l_int32 accessflag)
numaaGetNuma()
Definition: numabasic.c:1617
void numaDestroy(NUMA **pna)
numaDestroy()
Definition: numabasic.c:357
NUMAA * numaaCreate(l_int32 n)
numaaCreate()
Definition: numabasic.c:1302
l_int32 numaGetCount(NUMA *na)
numaGetCount()
Definition: numabasic.c:630
l_ok numaGetIValue(NUMA *na, l_int32 index, l_int32 *pival)
numaGetIValue()
Definition: numabasic.c:720
l_ok numaaAddNuma(NUMAA *naa, NUMA *na, l_int32 copyflag)
numaaAddNuma()
Definition: numabasic.c:1435
void numaaDestroy(NUMAA **pnaa)
numaaDestroy()
Definition: numabasic.c:1401
l_ok numaaReplaceNuma(NUMAA *naa, l_int32 index, NUMA *na)
numaaReplaceNuma()
Definition: numabasic.c:1651
NUMA * numaGetSortIndex(NUMA *na, l_int32 sortorder)
numaGetSortIndex()
Definition: numafunc1.c:2664
l_ok numaJoin(NUMA *nad, NUMA *nas, l_int32 istart, l_int32 iend)
numaJoin()
Definition: numafunc1.c:3521
l_ok numaGetRankValue(NUMA *na, l_float32 fract, NUMA *nasort, l_int32 usebins, l_float32 *pval)
numaGetRankValue()
Definition: numafunc1.c:3245
NUMA * numaSortByIndex(NUMA *nas, NUMA *naindex)
numaSortByIndex()
Definition: numafunc1.c:2825
NUMA * numaGetBinSortIndex(NUMA *nas, l_int32 sortorder)
numaGetBinSortIndex()
Definition: numafunc1.c:2744
@ L_SORT_BY_AREA
Definition: pix.h:537
@ L_SORT_BY_MIN_DIMENSION
Definition: pix.h:534
@ L_SORT_BY_PERIMETER
Definition: pix.h:536
@ L_SORT_BY_WIDTH
Definition: pix.h:532
@ L_SORT_BY_RIGHT
Definition: pix.h:530
@ L_SORT_BY_BOT
Definition: pix.h:531
@ L_SORT_BY_ASPECT_RATIO
Definition: pix.h:538
@ L_SORT_BY_HEIGHT
Definition: pix.h:533
@ L_SORT_BY_MAX_DIMENSION
Definition: pix.h:535
@ L_SORT_BY_Y
Definition: pix.h:529
@ L_SORT_BY_X
Definition: pix.h:528
@ L_COPY
Definition: pix.h:505
@ L_CLONE
Definition: pix.h:506
@ L_INSERT
Definition: pix.h:504
@ L_UPPER_RIGHT
Definition: pix.h:910
@ L_LOWER_RIGHT
Definition: pix.h:912
@ L_UPPER_LEFT
Definition: pix.h:909
@ L_BOX_CENTER
Definition: pix.h:913
@ L_LOWER_LEFT
Definition: pix.h:911
@ L_REMOVE_SMALL
Definition: pix.h:881
@ L_SORT_DECREASING
Definition: pix.h:523
@ L_SORT_INCREASING
Definition: pix.h:522
@ L_RO_TR_SC
Definition: pix.h:679
@ L_TR_RO_SC
Definition: pix.h:680
@ L_SC_RO_TR
Definition: pix.h:678
@ L_TR_SC_RO
Definition: pix.h:677
@ L_SC_TR_RO
Definition: pix.h:682
@ L_RO_SC_TR
Definition: pix.h:681
l_ok ptaGetIPt(PTA *pta, l_int32 index, l_int32 *px, l_int32 *py)
ptaGetIPt()
Definition: ptabasic.c:527
l_ok ptaAddPt(PTA *pta, l_float32 x, l_float32 y)
ptaAddPt()
Definition: ptabasic.c:328
l_int32 ptaGetCount(PTA *pta)
ptaGetCount()
Definition: ptabasic.c:480
PTA * ptaCreate(l_int32 n)
ptaCreate()
Definition: ptabasic.c:120
l_int32 y
Definition: pix_internal.h:258
l_int32 x
Definition: pix_internal.h:257
l_int32 w
Definition: pix_internal.h:259
l_int32 h
Definition: pix_internal.h:260