Leptonica  1.82.0
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 
74  /* For more than this number of c.c. in a binarized image of
75  * semi-perimeter (w + h) about 5000 or less, the O(n) binsort
76  * is faster than the O(nlogn) shellsort. */
77 static const l_int32 MinCompsForBinSort = 200;
78 
79 /*---------------------------------------------------------------------*
80  * Boxa/Box transform (shift, scale) and orthogonal rotation *
81  *---------------------------------------------------------------------*/
101 BOXA *
103  l_int32 shiftx,
104  l_int32 shifty,
105  l_float32 scalex,
106  l_float32 scaley)
107 {
108 l_int32 i, n;
109 BOX *boxs, *boxd;
110 BOXA *boxad;
111 
112  PROCNAME("boxaTransform");
113 
114  if (!boxas)
115  return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
116  n = boxaGetCount(boxas);
117  if ((boxad = boxaCreate(n)) == NULL)
118  return (BOXA *)ERROR_PTR("boxad not made", procName, NULL);
119  for (i = 0; i < n; i++) {
120  if ((boxs = boxaGetBox(boxas, i, L_CLONE)) == NULL) {
121  boxaDestroy(&boxad);
122  return (BOXA *)ERROR_PTR("boxs not found", procName, NULL);
123  }
124  boxd = boxTransform(boxs, shiftx, shifty, scalex, scaley);
125  boxDestroy(&boxs);
126  boxaAddBox(boxad, boxd, L_INSERT);
127  }
128 
129  return boxad;
130 }
131 
132 
151 BOX *
153  l_int32 shiftx,
154  l_int32 shifty,
155  l_float32 scalex,
156  l_float32 scaley)
157 {
158  PROCNAME("boxTransform");
159 
160  if (!box)
161  return (BOX *)ERROR_PTR("box not defined", procName, NULL);
162  if (box->w <= 0 || box->h <= 0)
163  return boxCreate(0, 0, 0, 0);
164  else
165  return boxCreate((l_int32)(L_MAX(0, scalex * (box->x + shiftx) + 0.5)),
166  (l_int32)(L_MAX(0, scaley * (box->y + shifty) + 0.5)),
167  (l_int32)(L_MAX(1.0, scalex * box->w + 0.5)),
168  (l_int32)(L_MAX(1.0, scaley * box->h + 0.5)));
169 }
170 
171 
205 BOXA *
207  l_int32 shiftx,
208  l_int32 shifty,
209  l_float32 scalex,
210  l_float32 scaley,
211  l_int32 xcen,
212  l_int32 ycen,
213  l_float32 angle,
214  l_int32 order)
215 {
216 l_int32 i, n;
217 BOX *boxs, *boxd;
218 BOXA *boxad;
219 
220  PROCNAME("boxaTransformOrdered");
221 
222  if (!boxas)
223  return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
224  n = boxaGetCount(boxas);
225  if ((boxad = boxaCreate(n)) == NULL)
226  return (BOXA *)ERROR_PTR("boxad not made", procName, NULL);
227  for (i = 0; i < n; i++) {
228  if ((boxs = boxaGetBox(boxas, i, L_CLONE)) == NULL) {
229  boxaDestroy(&boxad);
230  return (BOXA *)ERROR_PTR("boxs not found", procName, NULL);
231  }
232  boxd = boxTransformOrdered(boxs, shiftx, shifty, scalex, scaley,
233  xcen, ycen, angle, order);
234  boxDestroy(&boxs);
235  boxaAddBox(boxad, boxd, L_INSERT);
236  }
237 
238  return boxad;
239 }
240 
241 
295 BOX *
297  l_int32 shiftx,
298  l_int32 shifty,
299  l_float32 scalex,
300  l_float32 scaley,
301  l_int32 xcen,
302  l_int32 ycen,
303  l_float32 angle,
304  l_int32 order)
305 {
306 l_int32 bx, by, bw, bh, tx, ty, tw, th;
307 l_int32 xcent, ycent; /* transformed center of rotation due to scaling */
308 l_float32 sina, cosa, xdif, ydif, rx, ry, rw, rh;
309 BOX *boxd;
310 
311  PROCNAME("boxTransformOrdered");
312 
313  if (!boxs)
314  return (BOX *)ERROR_PTR("boxs not defined", procName, NULL);
315  if (order != L_TR_SC_RO && order != L_SC_RO_TR && order != L_RO_TR_SC &&
316  order != L_TR_RO_SC && order != L_RO_SC_TR && order != L_SC_TR_RO)
317  return (BOX *)ERROR_PTR("order invalid", procName, NULL);
318 
319  boxGetGeometry(boxs, &bx, &by, &bw, &bh);
320  if (bw <= 0 || bh <= 0) /* invalid */
321  return boxCreate(0, 0, 0, 0);
322  if (angle != 0.0) {
323  sina = sin(angle);
324  cosa = cos(angle);
325  }
326 
327  if (order == L_TR_SC_RO) {
328  tx = (l_int32)(scalex * (bx + shiftx) + 0.5);
329  ty = (l_int32)(scaley * (by + shifty) + 0.5);
330  tw = (l_int32)(L_MAX(1.0, scalex * bw + 0.5));
331  th = (l_int32)(L_MAX(1.0, scaley * bh + 0.5));
332  xcent = (l_int32)(scalex * xcen + 0.5);
333  ycent = (l_int32)(scaley * ycen + 0.5);
334  if (angle == 0.0) {
335  boxd = boxCreate(tx, ty, tw, th);
336  } else {
337  xdif = tx + 0.5 * tw - xcent;
338  ydif = ty + 0.5 * th - ycent;
339  rw = L_ABS(tw * cosa) + L_ABS(th * sina);
340  rh = L_ABS(th * cosa) + L_ABS(tw * sina);
341  rx = xcent + xdif * cosa - ydif * sina - 0.5 * rw;
342  ry = ycent + ydif * cosa + xdif * sina - 0.5 * rh;
343  boxd = boxCreate((l_int32)rx, (l_int32)ry, (l_int32)rw,
344  (l_int32)rh);
345  }
346  } else if (order == L_SC_TR_RO) {
347  tx = (l_int32)(scalex * bx + shiftx + 0.5);
348  ty = (l_int32)(scaley * by + shifty + 0.5);
349  tw = (l_int32)(L_MAX(1.0, scalex * bw + 0.5));
350  th = (l_int32)(L_MAX(1.0, scaley * bh + 0.5));
351  xcent = (l_int32)(scalex * xcen + 0.5);
352  ycent = (l_int32)(scaley * ycen + 0.5);
353  if (angle == 0.0) {
354  boxd = boxCreate(tx, ty, tw, th);
355  } else {
356  xdif = tx + 0.5 * tw - xcent;
357  ydif = ty + 0.5 * th - ycent;
358  rw = L_ABS(tw * cosa) + L_ABS(th * sina);
359  rh = L_ABS(th * cosa) + L_ABS(tw * sina);
360  rx = xcent + xdif * cosa - ydif * sina - 0.5 * rw;
361  ry = ycent + ydif * cosa + xdif * sina - 0.5 * rh;
362  boxd = boxCreate((l_int32)rx, (l_int32)ry, (l_int32)rw,
363  (l_int32)rh);
364  }
365  } else if (order == L_RO_TR_SC) {
366  if (angle == 0.0) {
367  rx = bx;
368  ry = by;
369  rw = bw;
370  rh = bh;
371  } else {
372  xdif = bx + 0.5 * bw - xcen;
373  ydif = by + 0.5 * bh - ycen;
374  rw = L_ABS(bw * cosa) + L_ABS(bh * sina);
375  rh = L_ABS(bh * cosa) + L_ABS(bw * sina);
376  rx = xcen + xdif * cosa - ydif * sina - 0.5 * rw;
377  ry = ycen + ydif * cosa + xdif * sina - 0.5 * rh;
378  }
379  tx = (l_int32)(scalex * (rx + shiftx) + 0.5);
380  ty = (l_int32)(scaley * (ry + shifty) + 0.5);
381  tw = (l_int32)(L_MAX(1.0, scalex * rw + 0.5));
382  th = (l_int32)(L_MAX(1.0, scaley * rh + 0.5));
383  boxd = boxCreate(tx, ty, tw, th);
384  } else if (order == L_RO_SC_TR) {
385  if (angle == 0.0) {
386  rx = bx;
387  ry = by;
388  rw = bw;
389  rh = bh;
390  } else {
391  xdif = bx + 0.5 * bw - xcen;
392  ydif = by + 0.5 * bh - ycen;
393  rw = L_ABS(bw * cosa) + L_ABS(bh * sina);
394  rh = L_ABS(bh * cosa) + L_ABS(bw * sina);
395  rx = xcen + xdif * cosa - ydif * sina - 0.5 * rw;
396  ry = ycen + ydif * cosa + xdif * sina - 0.5 * rh;
397  }
398  tx = (l_int32)(scalex * rx + shiftx + 0.5);
399  ty = (l_int32)(scaley * ry + shifty + 0.5);
400  tw = (l_int32)(L_MAX(1.0, scalex * rw + 0.5));
401  th = (l_int32)(L_MAX(1.0, scaley * rh + 0.5));
402  boxd = boxCreate(tx, ty, tw, th);
403  } else if (order == L_TR_RO_SC) {
404  tx = bx + shiftx;
405  ty = by + shifty;
406  if (angle == 0.0) {
407  rx = tx;
408  ry = ty;
409  rw = bw;
410  rh = bh;
411  } else {
412  xdif = tx + 0.5 * bw - xcen;
413  ydif = ty + 0.5 * bh - ycen;
414  rw = L_ABS(bw * cosa) + L_ABS(bh * sina);
415  rh = L_ABS(bh * cosa) + L_ABS(bw * sina);
416  rx = xcen + xdif * cosa - ydif * sina - 0.5 * rw;
417  ry = ycen + ydif * cosa + xdif * sina - 0.5 * rh;
418  }
419  tx = (l_int32)(scalex * rx + 0.5);
420  ty = (l_int32)(scaley * ry + 0.5);
421  tw = (l_int32)(L_MAX(1.0, scalex * rw + 0.5));
422  th = (l_int32)(L_MAX(1.0, scaley * rh + 0.5));
423  boxd = boxCreate(tx, ty, tw, th);
424  } else { /* order == L_SC_RO_TR) */
425  tx = (l_int32)(scalex * bx + 0.5);
426  ty = (l_int32)(scaley * by + 0.5);
427  tw = (l_int32)(L_MAX(1.0, scalex * bw + 0.5));
428  th = (l_int32)(L_MAX(1.0, scaley * bh + 0.5));
429  xcent = (l_int32)(scalex * xcen + 0.5);
430  ycent = (l_int32)(scaley * ycen + 0.5);
431  if (angle == 0.0) {
432  rx = tx;
433  ry = ty;
434  rw = tw;
435  rh = th;
436  } else {
437  xdif = tx + 0.5 * tw - xcent;
438  ydif = ty + 0.5 * th - ycent;
439  rw = L_ABS(tw * cosa) + L_ABS(th * sina);
440  rh = L_ABS(th * cosa) + L_ABS(tw * sina);
441  rx = xcent + xdif * cosa - ydif * sina - 0.5 * rw;
442  ry = ycent + ydif * cosa + xdif * sina - 0.5 * rh;
443  }
444  tx = (l_int32)(rx + shiftx + 0.5);
445  ty = (l_int32)(ry + shifty + 0.5);
446  tw = (l_int32)(rw + 0.5);
447  th = (l_int32)(rh + 0.5);
448  boxd = boxCreate(tx, ty, tw, th);
449  }
450 
451  return boxd;
452 }
453 
454 
469 BOXA *
471  l_int32 w,
472  l_int32 h,
473  l_int32 rotation)
474 {
475 l_int32 i, n;
476 BOX *boxs, *boxd;
477 BOXA *boxad;
478 
479  PROCNAME("boxaRotateOrth");
480 
481  if (!boxas)
482  return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
483  if (rotation < 0 || rotation > 3)
484  return (BOXA *)ERROR_PTR("rotation not in {0,1,2,3}", procName, NULL);
485  if (rotation == 0)
486  return boxaCopy(boxas, L_COPY);
487 
488  n = boxaGetCount(boxas);
489  if ((boxad = boxaCreate(n)) == NULL)
490  return (BOXA *)ERROR_PTR("boxad not made", procName, NULL);
491  for (i = 0; i < n; i++) {
492  if ((boxs = boxaGetBox(boxas, i, L_CLONE)) == NULL) {
493  boxaDestroy(&boxad);
494  return (BOXA *)ERROR_PTR("boxs not found", procName, NULL);
495  }
496  boxd = boxRotateOrth(boxs, w, h, rotation);
497  boxDestroy(&boxs);
498  boxaAddBox(boxad, boxd, L_INSERT);
499  }
500 
501  return boxad;
502 }
503 
504 
521 BOX *
523  l_int32 w,
524  l_int32 h,
525  l_int32 rotation)
526 {
527 l_int32 bx, by, bw, bh, xdist, ydist;
528 
529  PROCNAME("boxRotateOrth");
530 
531  if (!box)
532  return (BOX *)ERROR_PTR("box not defined", procName, NULL);
533  if (rotation < 0 || rotation > 3)
534  return (BOX *)ERROR_PTR("rotation not in {0,1,2,3}", procName, NULL);
535  if (rotation == 0)
536  return boxCopy(box);
537 
538  boxGetGeometry(box, &bx, &by, &bw, &bh);
539  if (bw <= 0 || bh <= 0) /* invalid */
540  return boxCreate(0, 0, 0, 0);
541  ydist = h - by - bh; /* below box */
542  xdist = w - bx - bw; /* to right of box */
543  if (rotation == 1) /* 90 deg cw */
544  return boxCreate(ydist, bx, bh, bw);
545  else if (rotation == 2) /* 180 deg cw */
546  return boxCreate(xdist, ydist, bw, bh);
547  else /* rotation == 3, 270 deg cw */
548  return boxCreate(by, xdist, bh, bw);
549 }
550 
551 
576 BOXA *
578  PTA *pta,
579  l_int32 dir)
580 {
581 l_int32 i, n, x, y, full;
582 BOX *box1, *box2;
583 BOXA *boxad;
584 
585  PROCNAME("boxaShiftWithPta");
586 
587  if (!boxas)
588  return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
589  boxaIsFull(boxas, &full);
590  if (!full)
591  return (BOXA *)ERROR_PTR("boxas not full", procName, NULL);
592  if (!pta)
593  return (BOXA *)ERROR_PTR("pta not defined", procName, NULL);
594  if (dir != 1 && dir != -1)
595  return (BOXA *)ERROR_PTR("invalid dir", procName, NULL);
596  n = boxaGetCount(boxas);
597  if (n != ptaGetCount(pta))
598  return (BOXA *)ERROR_PTR("boxas and pta not same size", procName, NULL);
599 
600  if ((boxad = boxaCreate(n)) == NULL)
601  return (BOXA *)ERROR_PTR("boxad not made", procName, NULL);
602  for (i = 0; i < n; i++) {
603  box1 = boxaGetBox(boxas, i, L_COPY);
604  ptaGetIPt(pta, i, &x, &y);
605  box2 = boxTransform(box1, dir * x, dir * y, 1.0, 1.0);
606  boxaAddBox(boxad, box2, L_INSERT);
607  boxDestroy(&box1);
608  }
609  return boxad;
610 }
611 
612 
613 /*---------------------------------------------------------------------*
614  * Boxa sort *
615  *---------------------------------------------------------------------*/
636 BOXA *
637 boxaSort(BOXA *boxas,
638  l_int32 sorttype,
639  l_int32 sortorder,
640  NUMA **pnaindex)
641 {
642 l_int32 i, n, x, y, w, h, size;
643 BOXA *boxad;
644 NUMA *na, *naindex;
645 
646  PROCNAME("boxaSort");
647 
648  if (pnaindex) *pnaindex = NULL;
649  if (!boxas)
650  return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
651  if ((n = boxaGetCount(boxas)) == 0) {
652  L_WARNING("boxas is empty\n", procName);
653  return boxaCopy(boxas, L_COPY);
654  }
655  if (sorttype != L_SORT_BY_X && sorttype != L_SORT_BY_Y &&
656  sorttype != L_SORT_BY_RIGHT && sorttype != L_SORT_BY_BOT &&
657  sorttype != L_SORT_BY_WIDTH && sorttype != L_SORT_BY_HEIGHT &&
658  sorttype != L_SORT_BY_MIN_DIMENSION &&
659  sorttype != L_SORT_BY_MAX_DIMENSION &&
660  sorttype != L_SORT_BY_PERIMETER &&
661  sorttype != L_SORT_BY_AREA &&
662  sorttype != L_SORT_BY_ASPECT_RATIO)
663  return (BOXA *)ERROR_PTR("invalid sort type", procName, NULL);
664  if (sortorder != L_SORT_INCREASING && sortorder != L_SORT_DECREASING)
665  return (BOXA *)ERROR_PTR("invalid sort order", procName, NULL);
666 
667  /* Use O(n) binsort if possible */
668  if (n > MinCompsForBinSort &&
669  ((sorttype == L_SORT_BY_X) || (sorttype == L_SORT_BY_Y) ||
670  (sorttype == L_SORT_BY_WIDTH) || (sorttype == L_SORT_BY_HEIGHT) ||
671  (sorttype == L_SORT_BY_PERIMETER)))
672  return boxaBinSort(boxas, sorttype, sortorder, pnaindex);
673 
674  /* Build up numa of specific data */
675  if ((na = numaCreate(n)) == NULL)
676  return (BOXA *)ERROR_PTR("na not made", procName, NULL);
677  for (i = 0; i < n; i++) {
678  boxaGetBoxGeometry(boxas, i, &x, &y, &w, &h);
679  switch (sorttype)
680  {
681  case L_SORT_BY_X:
682  numaAddNumber(na, x);
683  break;
684  case L_SORT_BY_Y:
685  numaAddNumber(na, y);
686  break;
687  case L_SORT_BY_RIGHT:
688  numaAddNumber(na, x + w - 1);
689  break;
690  case L_SORT_BY_BOT:
691  numaAddNumber(na, y + h - 1);
692  break;
693  case L_SORT_BY_WIDTH:
694  numaAddNumber(na, w);
695  break;
696  case L_SORT_BY_HEIGHT:
697  numaAddNumber(na, h);
698  break;
700  size = L_MIN(w, h);
701  numaAddNumber(na, size);
702  break;
704  size = L_MAX(w, h);
705  numaAddNumber(na, size);
706  break;
707  case L_SORT_BY_PERIMETER:
708  size = w + h;
709  numaAddNumber(na, size);
710  break;
711  case L_SORT_BY_AREA:
712  size = w * h;
713  numaAddNumber(na, size);
714  break;
716  numaAddNumber(na, (l_float32)w / (l_float32)h);
717  break;
718  default:
719  L_WARNING("invalid sort type\n", procName);
720  }
721  }
722 
723  /* Get the sort index for data array */
724  naindex = numaGetSortIndex(na, sortorder);
725  numaDestroy(&na);
726  if (!naindex)
727  return (BOXA *)ERROR_PTR("naindex not made", procName, NULL);
728 
729  /* Build up sorted boxa using sort index */
730  boxad = boxaSortByIndex(boxas, naindex);
731 
732  if (pnaindex)
733  *pnaindex = naindex;
734  else
735  numaDestroy(&naindex);
736  return boxad;
737 }
738 
739 
760 BOXA *
762  l_int32 sorttype,
763  l_int32 sortorder,
764  NUMA **pnaindex)
765 {
766 l_int32 i, n, x, y, w, h;
767 BOXA *boxad;
768 NUMA *na, *naindex;
769 
770  PROCNAME("boxaBinSort");
771 
772  if (pnaindex) *pnaindex = NULL;
773  if (!boxas)
774  return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
775  if ((n = boxaGetCount(boxas)) == 0) {
776  L_WARNING("boxas is empty\n", procName);
777  return boxaCopy(boxas, L_COPY);
778  }
779  if (sorttype != L_SORT_BY_X && sorttype != L_SORT_BY_Y &&
780  sorttype != L_SORT_BY_WIDTH && sorttype != L_SORT_BY_HEIGHT &&
781  sorttype != L_SORT_BY_PERIMETER)
782  return (BOXA *)ERROR_PTR("invalid sort type", procName, NULL);
783  if (sortorder != L_SORT_INCREASING && sortorder != L_SORT_DECREASING)
784  return (BOXA *)ERROR_PTR("invalid sort order", procName, NULL);
785 
786  /* Generate Numa of appropriate box dimensions */
787  if ((na = numaCreate(n)) == NULL)
788  return (BOXA *)ERROR_PTR("na not made", procName, NULL);
789  for (i = 0; i < n; i++) {
790  boxaGetBoxGeometry(boxas, i, &x, &y, &w, &h);
791  switch (sorttype)
792  {
793  case L_SORT_BY_X:
794  numaAddNumber(na, x);
795  break;
796  case L_SORT_BY_Y:
797  numaAddNumber(na, y);
798  break;
799  case L_SORT_BY_WIDTH:
800  numaAddNumber(na, w);
801  break;
802  case L_SORT_BY_HEIGHT:
803  numaAddNumber(na, h);
804  break;
805  case L_SORT_BY_PERIMETER:
806  numaAddNumber(na, w + h);
807  break;
808  default:
809  L_WARNING("invalid sort type\n", procName);
810  }
811  }
812 
813  /* Get the sort index for data array */
814  naindex = numaGetBinSortIndex(na, sortorder);
815  numaDestroy(&na);
816  if (!naindex)
817  return (BOXA *)ERROR_PTR("naindex not made", procName, NULL);
818 
819  /* Build up sorted boxa using the sort index */
820  boxad = boxaSortByIndex(boxas, naindex);
821 
822  if (pnaindex)
823  *pnaindex = naindex;
824  else
825  numaDestroy(&naindex);
826  return boxad;
827 }
828 
829 
837 BOXA *
839  NUMA *naindex)
840 {
841 l_int32 i, n, index;
842 BOX *box;
843 BOXA *boxad;
844 
845  PROCNAME("boxaSortByIndex");
846 
847  if (!boxas)
848  return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
849  if ((n = boxaGetCount(boxas)) == 0) {
850  L_WARNING("boxas is empty\n", procName);
851  return boxaCopy(boxas, L_COPY);
852  }
853  if (!naindex)
854  return (BOXA *)ERROR_PTR("naindex not defined", procName, NULL);
855 
856  boxad = boxaCreate(n);
857  for (i = 0; i < n; i++) {
858  numaGetIValue(naindex, i, &index);
859  box = boxaGetBox(boxas, index, L_COPY);
860  boxaAddBox(boxad, box, L_INSERT);
861  }
862 
863  return boxad;
864 }
865 
866 
914 BOXAA *
916  NUMAA **pnaad,
917  l_int32 delta1,
918  l_int32 delta2,
919  l_int32 minh1)
920 {
921 l_int32 i, index, h, nt, ne, n, m, ival;
922 BOX *box;
923 BOXA *boxa, *boxae, *boxan, *boxa1, *boxa2, *boxa3, *boxav, *boxavs;
924 BOXAA *baa, *baa1, *baad;
925 NUMA *naindex, *nae, *nan, *nah, *nav, *na1, *na2, *nad, *namap;
926 NUMAA *naa, *naa1, *naad;
927 
928  PROCNAME("boxaSort2d");
929 
930  if (pnaad) *pnaad = NULL;
931  if (!boxas)
932  return (BOXAA *)ERROR_PTR("boxas not defined", procName, NULL);
933  if (boxaGetCount(boxas) == 0)
934  return (BOXAA *)ERROR_PTR("boxas is empty", procName, NULL);
935 
936  /* Sort from left to right */
937  if ((boxa = boxaSort(boxas, L_SORT_BY_X, L_SORT_INCREASING, &naindex))
938  == NULL)
939  return (BOXAA *)ERROR_PTR("boxa not made", procName, NULL);
940 
941  /* First pass: assign taller boxes to boxa by row */
942  nt = boxaGetCount(boxa);
943  baa = boxaaCreate(0);
944  naa = numaaCreate(0);
945  boxae = boxaCreate(0); /* save small height boxes here */
946  nae = numaCreate(0); /* keep track of small height boxes */
947  for (i = 0; i < nt; i++) {
948  box = boxaGetBox(boxa, i, L_CLONE);
949  boxGetGeometry(box, NULL, NULL, NULL, &h);
950  if (h < minh1) { /* save for 2nd pass */
951  boxaAddBox(boxae, box, L_INSERT);
952  numaAddNumber(nae, i);
953  } else {
954  n = boxaaGetCount(baa);
955  boxaaAlignBox(baa, box, delta1, &index);
956  if (index < n) { /* append to an existing boxa */
957  boxaaAddBox(baa, index, box, L_INSERT);
958  } else { /* doesn't align, need new boxa */
959  boxan = boxaCreate(0);
960  boxaAddBox(boxan, box, L_INSERT);
961  boxaaAddBoxa(baa, boxan, L_INSERT);
962  nan = numaCreate(0);
963  numaaAddNuma(naa, nan, L_INSERT);
964  }
965  numaGetIValue(naindex, i, &ival);
966  numaaAddNumber(naa, index, ival);
967  }
968  }
969  boxaDestroy(&boxa);
970  numaDestroy(&naindex);
971 
972  /* Second pass: feed in small height boxes */
973  ne = boxaGetCount(boxae);
974  for (i = 0; i < ne; i++) {
975  box = boxaGetBox(boxae, i, L_CLONE);
976  n = boxaaGetCount(baa);
977  boxaaAlignBox(baa, box, delta2, &index);
978  if (index < n) { /* append to an existing boxa */
979  boxaaAddBox(baa, index, box, L_INSERT);
980  } else { /* doesn't align, need new boxa */
981  boxan = boxaCreate(0);
982  boxaAddBox(boxan, box, L_INSERT);
983  boxaaAddBoxa(baa, boxan, L_INSERT);
984  nan = numaCreate(0);
985  numaaAddNuma(naa, nan, L_INSERT);
986  }
987  numaGetIValue(nae, i, &ival); /* location in original boxas */
988  numaaAddNumber(naa, index, ival);
989  }
990 
991  /* Third pass: merge some boxa whose extent is overlapping.
992  * Think of these boxa as text lines, where the bounding boxes
993  * of the text lines can overlap, but likely won't have
994  * a huge overlap.
995  * First do a greedy find of pairs of overlapping boxa, where
996  * the two boxa overlap by at least 50% of the smaller, and
997  * the smaller is not more than half the area of the larger.
998  * For such pairs, call the larger one the primary boxa. The
999  * boxes in the smaller one are appended to those in the primary
1000  * in pass 3a, and the primaries are extracted in pass 3b.
1001  * In this way, all boxes in the original baa are saved. */
1002  n = boxaaGetCount(baa);
1003  boxaaGetExtent(baa, NULL, NULL, NULL, &boxa3);
1004  boxa1 = boxaHandleOverlaps(boxa3, L_REMOVE_SMALL, 1000, 0.5, 0.5, &namap);
1005  boxaDestroy(&boxa1);
1006  boxaDestroy(&boxa3);
1007  for (i = 0; i < n; i++) { /* Pass 3a: join selected copies of boxa */
1008  numaGetIValue(namap, i, &ival);
1009  if (ival >= 0) { /* join current to primary boxa[ival] */
1010  boxa1 = boxaaGetBoxa(baa, i, L_COPY);
1011  boxa2 = boxaaGetBoxa(baa, ival, L_CLONE);
1012  boxaJoin(boxa2, boxa1, 0, -1);
1013  boxaDestroy(&boxa2);
1014  boxaDestroy(&boxa1);
1015  na1 = numaaGetNuma(naa, i, L_COPY);
1016  na2 = numaaGetNuma(naa, ival, L_CLONE);
1017  numaJoin(na2, na1, 0, -1);
1018  numaDestroy(&na1);
1019  numaDestroy(&na2);
1020  }
1021  }
1022  baa1 = boxaaCreate(n);
1023  naa1 = numaaCreate(n);
1024  for (i = 0; i < n; i++) { /* Pass 3b: save primary boxa */
1025  numaGetIValue(namap, i, &ival);
1026  if (ival == -1) {
1027  boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
1028  boxaaAddBoxa(baa1, boxa1, L_INSERT);
1029  na1 = numaaGetNuma(naa, i, L_CLONE);
1030  numaaAddNuma(naa1, na1, L_INSERT);
1031  }
1032  }
1033  numaDestroy(&namap);
1034  boxaaDestroy(&baa);
1035  baa = baa1;
1036  numaaDestroy(&naa);
1037  naa = naa1;
1038 
1039  /* Sort the boxes in each boxa horizontally */
1040  m = boxaaGetCount(baa);
1041  for (i = 0; i < m; i++) {
1042  boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
1043  boxa2 = boxaSort(boxa1, L_SORT_BY_X, L_SORT_INCREASING, &nah);
1044  boxaaReplaceBoxa(baa, i, boxa2);
1045  na1 = numaaGetNuma(naa, i, L_CLONE);
1046  na2 = numaSortByIndex(na1, nah);
1047  numaaReplaceNuma(naa, i, na2);
1048  boxaDestroy(&boxa1);
1049  numaDestroy(&na1);
1050  numaDestroy(&nah);
1051  }
1052 
1053  /* Sort the boxa vertically within boxaa, using the first box
1054  * in each boxa. */
1055  m = boxaaGetCount(baa);
1056  boxav = boxaCreate(m); /* holds first box in each boxa in baa */
1057  naad = numaaCreate(m);
1058  if (pnaad)
1059  *pnaad = naad;
1060  baad = boxaaCreate(m);
1061  for (i = 0; i < m; i++) {
1062  boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
1063  box = boxaGetBox(boxa1, 0, L_CLONE);
1064  boxaAddBox(boxav, box, L_INSERT);
1065  boxaDestroy(&boxa1);
1066  }
1067  boxavs = boxaSort(boxav, L_SORT_BY_Y, L_SORT_INCREASING, &nav);
1068  for (i = 0; i < m; i++) {
1069  numaGetIValue(nav, i, &index);
1070  boxa = boxaaGetBoxa(baa, index, L_CLONE);
1071  boxaaAddBoxa(baad, boxa, L_INSERT);
1072  nad = numaaGetNuma(naa, index, L_CLONE);
1073  numaaAddNuma(naad, nad, L_INSERT);
1074  }
1075 
1076 
1077 /* lept_stderr("box count = %d, numaa count = %d\n", nt,
1078  numaaGetNumberCount(naad)); */
1079 
1080  boxaaDestroy(&baa);
1081  boxaDestroy(&boxav);
1082  boxaDestroy(&boxavs);
1083  boxaDestroy(&boxae);
1084  numaDestroy(&nav);
1085  numaDestroy(&nae);
1086  numaaDestroy(&naa);
1087  if (!pnaad)
1088  numaaDestroy(&naad);
1089 
1090  return baad;
1091 }
1092 
1093 
1101 BOXAA *
1103  NUMAA *naa)
1104 {
1105 l_int32 ntot, boxtot, i, j, n, nn, index;
1106 BOX *box;
1107 BOXA *boxa;
1108 BOXAA *baa;
1109 NUMA *na;
1110 
1111  PROCNAME("boxaSort2dByIndex");
1112 
1113  if (!boxas)
1114  return (BOXAA *)ERROR_PTR("boxas not defined", procName, NULL);
1115  if ((boxtot = boxaGetCount(boxas)) == 0)
1116  return (BOXAA *)ERROR_PTR("boxas is empty", procName, NULL);
1117  if (!naa)
1118  return (BOXAA *)ERROR_PTR("naindex not defined", procName, NULL);
1119 
1120  /* Check counts */
1121  ntot = numaaGetNumberCount(naa);
1122  if (ntot != boxtot)
1123  return (BOXAA *)ERROR_PTR("element count mismatch", procName, NULL);
1124 
1125  n = numaaGetCount(naa);
1126  baa = boxaaCreate(n);
1127  for (i = 0; i < n; i++) {
1128  na = numaaGetNuma(naa, i, L_CLONE);
1129  nn = numaGetCount(na);
1130  boxa = boxaCreate(nn);
1131  for (j = 0; j < nn; j++) {
1132  numaGetIValue(na, i, &index);
1133  box = boxaGetBox(boxas, index, L_COPY);
1134  boxaAddBox(boxa, box, L_INSERT);
1135  }
1136  boxaaAddBoxa(baa, boxa, L_INSERT);
1137  numaDestroy(&na);
1138  }
1139 
1140  return baa;
1141 }
1142 
1143 
1144 /*---------------------------------------------------------------------*
1145  * Boxa array extraction *
1146  *---------------------------------------------------------------------*/
1170 l_ok
1172  NUMA **pnal,
1173  NUMA **pnat,
1174  NUMA **pnar,
1175  NUMA **pnab,
1176  NUMA **pnaw,
1177  NUMA **pnah,
1178  l_int32 keepinvalid)
1179 {
1180 l_int32 i, n, left, top, right, bot, w, h;
1181 
1182  PROCNAME("boxaExtractAsNuma");
1183 
1184  if (!pnal && !pnat && !pnar && !pnab && !pnaw && !pnah)
1185  return ERROR_INT("no output requested", procName, 1);
1186  if (pnal) *pnal = NULL;
1187  if (pnat) *pnat = NULL;
1188  if (pnar) *pnar = NULL;
1189  if (pnab) *pnab = NULL;
1190  if (pnaw) *pnaw = NULL;
1191  if (pnah) *pnah = NULL;
1192  if (!boxa)
1193  return ERROR_INT("boxa not defined", procName, 1);
1194  if (!keepinvalid && boxaGetValidCount(boxa) == 0)
1195  return ERROR_INT("no valid boxes", procName, 1);
1196 
1197  n = boxaGetCount(boxa);
1198  if (pnal) *pnal = numaCreate(n);
1199  if (pnat) *pnat = numaCreate(n);
1200  if (pnar) *pnar = numaCreate(n);
1201  if (pnab) *pnab = numaCreate(n);
1202  if (pnaw) *pnaw = numaCreate(n);
1203  if (pnah) *pnah = numaCreate(n);
1204  for (i = 0; i < n; i++) {
1205  boxaGetBoxGeometry(boxa, i, &left, &top, &w, &h);
1206  if (!keepinvalid && (w <= 0 || h <= 0))
1207  continue;
1208  right = left + w - 1;
1209  bot = top + h - 1;
1210  if (pnal) numaAddNumber(*pnal, left);
1211  if (pnat) numaAddNumber(*pnat, top);
1212  if (pnar) numaAddNumber(*pnar, right);
1213  if (pnab) numaAddNumber(*pnab, bot);
1214  if (pnaw) numaAddNumber(*pnaw, w);
1215  if (pnah) numaAddNumber(*pnah, h);
1216  }
1217 
1218  return 0;
1219 }
1220 
1221 
1251 l_ok
1253  PTA **pptal,
1254  PTA **pptat,
1255  PTA **pptar,
1256  PTA **pptab,
1257  PTA **pptaw,
1258  PTA **pptah,
1259  l_int32 keepinvalid)
1260 {
1261 l_int32 i, n, left, top, right, bot, w, h;
1262 
1263  PROCNAME("boxaExtractAsPta");
1264 
1265  if (!pptal && !pptar && !pptat && !pptab && !pptaw && !pptah)
1266  return ERROR_INT("no output requested", procName, 1);
1267  if (pptal) *pptal = NULL;
1268  if (pptat) *pptat = NULL;
1269  if (pptar) *pptar = NULL;
1270  if (pptab) *pptab = NULL;
1271  if (pptaw) *pptaw = NULL;
1272  if (pptah) *pptah = NULL;
1273  if (!boxa)
1274  return ERROR_INT("boxa not defined", procName, 1);
1275  if (!keepinvalid && boxaGetValidCount(boxa) == 0)
1276  return ERROR_INT("no valid boxes", procName, 1);
1277 
1278  n = boxaGetCount(boxa);
1279  if (pptal) *pptal = ptaCreate(n);
1280  if (pptat) *pptat = ptaCreate(n);
1281  if (pptar) *pptar = ptaCreate(n);
1282  if (pptab) *pptab = ptaCreate(n);
1283  if (pptaw) *pptaw = ptaCreate(n);
1284  if (pptah) *pptah = ptaCreate(n);
1285  for (i = 0; i < n; i++) {
1286  boxaGetBoxGeometry(boxa, i, &left, &top, &w, &h);
1287  if (!keepinvalid && (w <= 0 || h <= 0))
1288  continue;
1289  right = left + w - 1;
1290  bot = top + h - 1;
1291  if (pptal) ptaAddPt(*pptal, i, left);
1292  if (pptat) ptaAddPt(*pptat, i, top);
1293  if (pptar) ptaAddPt(*pptar, i, right);
1294  if (pptab) ptaAddPt(*pptab, i, bot);
1295  if (pptaw) ptaAddPt(*pptaw, i, w);
1296  if (pptah) ptaAddPt(*pptah, i, h);
1297  }
1298 
1299  return 0;
1300 }
1301 
1302 
1321 PTA *
1323  l_int32 loc)
1324 {
1325 l_int32 i, n, left, top, right, bot, w, h;
1326 PTA *pta;
1327 
1328  PROCNAME("boxaExtractCorners");
1329 
1330  if (!boxa)
1331  return (PTA *)ERROR_PTR("boxa not defined", procName, NULL);
1332  if (loc != L_UPPER_LEFT && loc != L_UPPER_RIGHT && loc != L_LOWER_LEFT &&
1333  loc != L_LOWER_RIGHT && loc != L_BOX_CENTER)
1334  return (PTA *)ERROR_PTR("invalid location", procName, NULL);
1335 
1336  n = boxaGetCount(boxa);
1337  if ((pta = ptaCreate(n)) == NULL)
1338  return (PTA *)ERROR_PTR("pta not made", procName, NULL);
1339 
1340  for (i = 0; i < n; i++) {
1341  boxaGetBoxGeometry(boxa, i, &left, &top, &w, &h);
1342  right = left + w - 1;
1343  bot = top + h - 1;
1344  if (w == 0 || h == 0) { /* invalid */
1345  left = 0;
1346  top = 0;
1347  right = 0;
1348  bot = 0;
1349  }
1350  if (loc == L_UPPER_LEFT)
1351  ptaAddPt(pta, left, top);
1352  else if (loc == L_UPPER_RIGHT)
1353  ptaAddPt(pta, right, top);
1354  else if (loc == L_LOWER_LEFT)
1355  ptaAddPt(pta, left, bot);
1356  else if (loc == L_LOWER_RIGHT)
1357  ptaAddPt(pta, right, bot);
1358  else if (loc == L_BOX_CENTER)
1359  ptaAddPt(pta, (left + right) / 2, (top + bot) / 2);
1360  }
1361 
1362  return pta;
1363 }
1364 
1365 
1366 /*---------------------------------------------------------------------*
1367  * Boxa statistics *
1368  *---------------------------------------------------------------------*/
1400 l_ok
1402  l_float32 fract,
1403  l_int32 *px,
1404  l_int32 *py,
1405  l_int32 *pr,
1406  l_int32 *pb,
1407  l_int32 *pw,
1408  l_int32 *ph)
1409 {
1410 l_float32 xval, yval, rval, bval, wval, hval;
1411 NUMA *nax, *nay, *nar, *nab, *naw, *nah;
1412 
1413  PROCNAME("boxaGetRankVals");
1414 
1415  if (px) *px = 0;
1416  if (py) *py = 0;
1417  if (pr) *pr = 0;
1418  if (pb) *pb = 0;
1419  if (pw) *pw = 0;
1420  if (ph) *ph = 0;
1421  if (!boxa)
1422  return ERROR_INT("boxa not defined", procName, 1);
1423  if (fract < 0.0 || fract > 1.0)
1424  return ERROR_INT("fract not in [0.0 ... 1.0]", procName, 1);
1425  if (boxaGetValidCount(boxa) == 0)
1426  return ERROR_INT("no valid boxes in boxa", procName, 1);
1427 
1428  /* Use only the valid boxes */
1429  boxaExtractAsNuma(boxa, &nax, &nay, &nar, &nab, &naw, &nah, 0);
1430 
1431  if (px) {
1432  numaGetRankValue(nax, 1.0 - fract, NULL, 1, &xval);
1433  *px = (l_int32)xval;
1434  }
1435  if (py) {
1436  numaGetRankValue(nay, 1.0 - fract, NULL, 1, &yval);
1437  *py = (l_int32)yval;
1438  }
1439  if (pr) {
1440  numaGetRankValue(nar, fract, NULL, 1, &rval);
1441  *pr = (l_int32)rval;
1442  }
1443  if (pb) {
1444  numaGetRankValue(nab, fract, NULL, 1, &bval);
1445  *pb = (l_int32)bval;
1446  }
1447  if (pw) {
1448  numaGetRankValue(naw, fract, NULL, 1, &wval);
1449  *pw = (l_int32)wval;
1450  }
1451  if (ph) {
1452  numaGetRankValue(nah, fract, NULL, 1, &hval);
1453  *ph = (l_int32)hval;
1454  }
1455  numaDestroy(&nax);
1456  numaDestroy(&nay);
1457  numaDestroy(&nar);
1458  numaDestroy(&nab);
1459  numaDestroy(&naw);
1460  numaDestroy(&nah);
1461  return 0;
1462 }
1463 
1464 
1482 l_ok
1484  l_int32 *px,
1485  l_int32 *py,
1486  l_int32 *pr,
1487  l_int32 *pb,
1488  l_int32 *pw,
1489  l_int32 *ph)
1490 {
1491  PROCNAME("boxaGetMedianVals");
1492 
1493  if (!boxa)
1494  return ERROR_INT("boxa not defined", procName, 1);
1495  if (boxaGetValidCount(boxa) == 0)
1496  return ERROR_INT("no valid boxes in boxa", procName, 1);
1497 
1498  return boxaGetRankVals(boxa, 0.5, px, py, pr, pb, pw, ph);
1499 }
1500 
1501 
1510 l_ok
1512  l_float32 *pw,
1513  l_float32 *ph)
1514 {
1515 l_int32 i, n, bw, bh;
1516 l_float32 sumw, sumh;
1517 
1518  PROCNAME("boxaGetAverageSize");
1519 
1520  if (pw) *pw = 0.0;
1521  if (ph) *ph = 0.0;
1522  if (!boxa)
1523  return ERROR_INT("boxa not defined", procName, 1);
1524  if ((n = boxaGetCount(boxa)) == 0)
1525  return ERROR_INT("boxa is empty", procName, 1);
1526 
1527  sumw = sumh = 0.0;
1528  for (i = 0; i < n; i++) {
1529  boxaGetBoxGeometry(boxa, i, NULL, NULL, &bw, &bh);
1530  sumw += bw;
1531  sumh += bh;
1532  }
1533 
1534  if (pw) *pw = sumw / n;
1535  if (ph) *ph = sumh / n;
1536  return 0;
1537 }
1538 
1539 
1540 /*---------------------------------------------------------------------*
1541  * Other Boxaa functions *
1542  *---------------------------------------------------------------------*/
1565 l_ok
1567  l_int32 *pw,
1568  l_int32 *ph,
1569  BOX **pbox,
1570  BOXA **pboxa)
1571 {
1572 l_int32 i, n, x, y, w, h, xmax, ymax, xmin, ymin, found;
1573 BOX *box1;
1574 BOXA *boxa, *boxa1;
1575 
1576  PROCNAME("boxaaGetExtent");
1577 
1578  if (!pw && !ph && !pbox && !pboxa)
1579  return ERROR_INT("no ptrs defined", procName, 1);
1580  if (pw) *pw = 0;
1581  if (ph) *ph = 0;
1582  if (pbox) *pbox = NULL;
1583  if (pboxa) *pboxa = NULL;
1584  if (!baa)
1585  return ERROR_INT("baa not defined", procName, 1);
1586 
1587  n = boxaaGetCount(baa);
1588  if (n == 0)
1589  return ERROR_INT("no boxa in baa", procName, 1);
1590 
1591  boxa = boxaCreate(n);
1592  xmax = ymax = 0;
1593  xmin = ymin = 100000000;
1594  found = FALSE;
1595  for (i = 0; i < n; i++) {
1596  boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
1597  boxaGetExtent(boxa1, NULL, NULL, &box1);
1598  boxaDestroy(&boxa1);
1599  boxGetGeometry(box1, &x, &y, &w, &h);
1600  if (w > 0 && h > 0) { /* a valid extent box */
1601  found = TRUE; /* found at least one valid extent box */
1602  xmin = L_MIN(xmin, x);
1603  ymin = L_MIN(ymin, y);
1604  xmax = L_MAX(xmax, x + w);
1605  ymax = L_MAX(ymax, y + h);
1606  }
1607  boxaAddBox(boxa, box1, L_INSERT);
1608  }
1609  if (found == FALSE) /* no valid extent boxes */
1610  xmin = ymin = 0;
1611 
1612  if (pw) *pw = xmax;
1613  if (ph) *ph = ymax;
1614  if (pbox)
1615  *pbox = boxCreate(xmin, ymin, xmax - xmin, ymax - ymin);
1616  if (pboxa)
1617  *pboxa = boxa;
1618  else
1619  boxaDestroy(&boxa);
1620  return 0;
1621 }
1622 
1623 
1645 BOXA *
1647  NUMA **pnaindex,
1648  l_int32 copyflag)
1649 {
1650 l_int32 i, j, m, n;
1651 BOXA *boxa, *boxat;
1652 BOX *box;
1653 NUMA *naindex;
1654 
1655  PROCNAME("boxaaFlattenToBoxa");
1656 
1657  if (pnaindex) *pnaindex = NULL;
1658  if (!baa)
1659  return (BOXA *)ERROR_PTR("baa not defined", procName, NULL);
1660  if (copyflag != L_COPY && copyflag != L_CLONE)
1661  return (BOXA *)ERROR_PTR("invalid copyflag", procName, NULL);
1662  if (pnaindex) {
1663  naindex = numaCreate(0);
1664  *pnaindex = naindex;
1665  }
1666 
1667  n = boxaaGetCount(baa);
1668  boxa = boxaCreate(n);
1669  for (i = 0; i < n; i++) {
1670  boxat = boxaaGetBoxa(baa, i, L_CLONE);
1671  m = boxaGetCount(boxat);
1672  if (m == 0) { /* placeholder box */
1673  box = boxCreate(0, 0, 0, 0);
1674  boxaAddBox(boxa, box, L_INSERT);
1675  if (pnaindex)
1676  numaAddNumber(naindex, i); /* save 'row' number */
1677  } else {
1678  for (j = 0; j < m; j++) {
1679  box = boxaGetBox(boxat, j, copyflag);
1680  boxaAddBox(boxa, box, L_INSERT);
1681  if (pnaindex)
1682  numaAddNumber(naindex, i); /* save 'row' number */
1683  }
1684  }
1685  boxaDestroy(&boxat);
1686  }
1687 
1688  return boxa;
1689 }
1690 
1691 
1711 BOXA *
1713  l_int32 num,
1714  BOX *fillerbox,
1715  l_int32 copyflag)
1716 {
1717 l_int32 i, j, m, n, mval, nshort;
1718 BOXA *boxat, *boxad;
1719 BOX *box;
1720 
1721  PROCNAME("boxaaFlattenAligned");
1722 
1723  if (!baa)
1724  return (BOXA *)ERROR_PTR("baa not defined", procName, NULL);
1725  if (copyflag != L_COPY && copyflag != L_CLONE)
1726  return (BOXA *)ERROR_PTR("invalid copyflag", procName, NULL);
1727 
1728  n = boxaaGetCount(baa);
1729  boxad = boxaCreate(n);
1730  for (i = 0; i < n; i++) {
1731  boxat = boxaaGetBoxa(baa, i, L_CLONE);
1732  m = boxaGetCount(boxat);
1733  mval = L_MIN(m, num);
1734  nshort = num - mval;
1735  for (j = 0; j < mval; j++) { /* take the first %num if possible */
1736  box = boxaGetBox(boxat, j, copyflag);
1737  boxaAddBox(boxad, box, L_INSERT);
1738  }
1739  for (j = 0; j < nshort; j++) { /* add fillers if necessary */
1740  if (fillerbox) {
1741  boxaAddBox(boxad, fillerbox, L_COPY);
1742  } else {
1743  box = boxCreate(0, 0, 0, 0); /* invalid placeholder box */
1744  boxaAddBox(boxad, box, L_INSERT);
1745  }
1746  }
1747  boxaDestroy(&boxat);
1748  }
1749 
1750  return boxad;
1751 }
1752 
1753 
1769 BOXAA *
1771  l_int32 num,
1772  l_int32 copyflag)
1773 {
1774 l_int32 i, j, n, nbaa, index;
1775 BOX *box;
1776 BOXA *boxat;
1777 BOXAA *baa;
1778 
1779  PROCNAME("boxaEncapsulateAligned");
1780 
1781  if (!boxa)
1782  return (BOXAA *)ERROR_PTR("boxa not defined", procName, NULL);
1783  if (copyflag != L_COPY && copyflag != L_CLONE)
1784  return (BOXAA *)ERROR_PTR("invalid copyflag", procName, NULL);
1785 
1786  n = boxaGetCount(boxa);
1787  nbaa = n / num;
1788  if (num * nbaa != n)
1789  L_ERROR("inconsistent alignment: num doesn't divide n\n", procName);
1790  baa = boxaaCreate(nbaa);
1791  for (i = 0, index = 0; i < nbaa; i++) {
1792  boxat = boxaCreate(num);
1793  for (j = 0; j < num; j++, index++) {
1794  box = boxaGetBox(boxa, index, copyflag);
1795  boxaAddBox(boxat, box, L_INSERT);
1796  }
1797  boxaaAddBoxa(baa, boxat, L_INSERT);
1798  }
1799 
1800  return baa;
1801 }
1802 
1803 
1823 BOXAA *
1825 {
1826 l_int32 i, j, ny, nb, nbox;
1827 BOX *box;
1828 BOXA *boxa;
1829 BOXAA *baad;
1830 
1831  PROCNAME("boxaaTranspose");
1832 
1833  if (!baas)
1834  return (BOXAA *)ERROR_PTR("baas not defined", procName, NULL);
1835  if ((ny = boxaaGetCount(baas)) == 0)
1836  return (BOXAA *)ERROR_PTR("baas empty", procName, NULL);
1837 
1838  /* Make sure that each boxa in baas has the same number of boxes */
1839  for (i = 0; i < ny; i++) {
1840  if ((boxa = boxaaGetBoxa(baas, i, L_CLONE)) == NULL)
1841  return (BOXAA *)ERROR_PTR("baas is missing a boxa", procName, NULL);
1842  nb = boxaGetCount(boxa);
1843  boxaDestroy(&boxa);
1844  if (i == 0)
1845  nbox = nb;
1846  else if (nb != nbox)
1847  return (BOXAA *)ERROR_PTR("boxa are not all the same size",
1848  procName, NULL);
1849  }
1850 
1851  /* baad[i][j] = baas[j][i] */
1852  baad = boxaaCreate(nbox);
1853  for (i = 0; i < nbox; i++) {
1854  boxa = boxaCreate(ny);
1855  for (j = 0; j < ny; j++) {
1856  box = boxaaGetBox(baas, j, i, L_COPY);
1857  boxaAddBox(boxa, box, L_INSERT);
1858  }
1859  boxaaAddBoxa(baad, boxa, L_INSERT);
1860  }
1861  return baad;
1862 }
1863 
1864 
1882 l_ok
1884  BOX *box,
1885  l_int32 delta,
1886  l_int32 *pindex)
1887 {
1888 l_int32 i, n, m, y, yt, h, ht, ovlp, maxovlp, maxindex;
1889 BOX *boxt;
1890 BOXA *boxa;
1891 
1892  PROCNAME("boxaaAlignBox");
1893 
1894  if (pindex) *pindex = 0;
1895  if (!baa)
1896  return ERROR_INT("baa not defined", procName, 1);
1897  if (!box)
1898  return ERROR_INT("box not defined", procName, 1);
1899  if (!pindex)
1900  return ERROR_INT("&index not defined", procName, 1);
1901 
1902  n = boxaaGetCount(baa);
1903  boxGetGeometry(box, NULL, &y, NULL, &h);
1904  maxovlp = -10000000;
1905  for (i = 0; i < n; i++) {
1906  boxa = boxaaGetBoxa(baa, i, L_CLONE);
1907  if ((m = boxaGetCount(boxa)) == 0) {
1908  boxaDestroy(&boxa);
1909  L_WARNING("no boxes in boxa\n", procName);
1910  continue;
1911  }
1912  boxaGetExtent(boxa, NULL, NULL, &boxt);
1913  boxGetGeometry(boxt, NULL, &yt, NULL, &ht);
1914  boxDestroy(&boxt);
1915  boxaDestroy(&boxa);
1916 
1917  /* Overlap < 0 means the components do not overlap vertically */
1918  if (yt >= y)
1919  ovlp = y + h - 1 - yt;
1920  else
1921  ovlp = yt + ht - 1 - y;
1922  if (ovlp > maxovlp) {
1923  maxovlp = ovlp;
1924  maxindex = i;
1925  }
1926  }
1927 
1928  if (maxovlp + delta >= 0)
1929  *pindex = maxindex;
1930  else
1931  *pindex = n;
1932  return 0;
1933 }
BOXAA * boxaSort2dByIndex(BOXA *boxas, NUMAA *naa)
boxaSort2dByIndex()
Definition: boxfunc2.c:1102
BOX * boxRotateOrth(BOX *box, l_int32 w, l_int32 h, l_int32 rotation)
boxRotateOrth()
Definition: boxfunc2.c:522
l_ok boxaJoin(BOXA *boxad, BOXA *boxas, l_int32 istart, l_int32 iend)
boxaJoin()
Definition: boxfunc1.c:2537
l_ok boxaExtractAsNuma(BOXA *boxa, NUMA **pnal, NUMA **pnat, NUMA **pnar, NUMA **pnab, NUMA **pnaw, NUMA **pnah, l_int32 keepinvalid)
boxaExtractAsNuma()
Definition: boxfunc2.c:1171
NUMA * numaGetSortIndex(NUMA *na, l_int32 sortorder)
numaGetSortIndex()
Definition: numafunc1.c:2751
BOXA * boxaSort(BOXA *boxas, l_int32 sorttype, l_int32 sortorder, NUMA **pnaindex)
boxaSort()
Definition: boxfunc2.c:637
l_ok boxaaReplaceBoxa(BOXAA *baa, l_int32 index, BOXA *boxa)
boxaaReplaceBoxa()
Definition: boxbasic.c:1665
NUMA * numaSortByIndex(NUMA *nas, NUMA *naindex)
numaSortByIndex()
Definition: numafunc1.c:2916
l_ok ptaAddPt(PTA *pta, l_float32 x, l_float32 y)
ptaAddPt()
Definition: ptabasic.c:343
Definition: pix.h:713
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:478
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:1483
l_int32 numaaGetNumberCount(NUMAA *naa)
numaaGetNumberCount()
Definition: numabasic.c:1670
l_ok boxaaGetExtent(BOXAA *baa, l_int32 *pw, l_int32 *ph, BOX **pbox, BOXA **pboxa)
boxaaGetExtent()
Definition: boxfunc2.c:1566
l_int32 boxaaGetCount(BOXAA *baa)
boxaaGetCount()
Definition: boxbasic.c:1454
NUMA * numaGetBinSortIndex(NUMA *nas, l_int32 sortorder)
numaGetBinSortIndex()
Definition: numafunc1.c:2833
Definition: pix.h:712
PTA * ptaCreate(l_int32 n)
ptaCreate()
Definition: ptabasic.c:120
l_int32 y
Definition: pix.h:483
BOXA * boxaShiftWithPta(BOXA *boxas, PTA *pta, l_int32 dir)
boxaShiftWithPta()
Definition: boxfunc2.c:577
BOXA * boxaCopy(BOXA *boxa, l_int32 copyflag)
boxaCopy()
Definition: boxbasic.c:537
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:194
l_int32 ptaGetCount(PTA *pta)
ptaGetCount()
Definition: ptabasic.c:527
void boxaDestroy(BOXA **pboxa)
boxaDestroy()
Definition: boxbasic.c:583
BOX * boxTransform(BOX *box, l_int32 shiftx, l_int32 shifty, l_float32 scalex, l_float32 scaley)
boxTransform()
Definition: boxfunc2.c:152
BOXA * boxaHandleOverlaps(BOXA *boxas, l_int32 op, l_int32 range, l_float32 min_overlap, l_float32 max_ratio, NUMA **pnamap)
boxaHandleOverlaps()
Definition: boxfunc1.c:914
NUMAA * numaaCreate(l_int32 n)
numaaCreate()
Definition: numabasic.c:1407
Definition: pix.h:491
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:296
void numaaDestroy(NUMAA **pnaa)
numaaDestroy()
Definition: numabasic.c:1510
Definition: pix.h:501
l_ok boxaExtractAsPta(BOXA *boxa, PTA **pptal, PTA **pptat, PTA **pptar, PTA **pptab, PTA **pptaw, PTA **pptah, l_int32 keepinvalid)
boxaExtractAsPta()
Definition: boxfunc2.c:1252
l_ok boxaaAddBoxa(BOXAA *baa, BOXA *ba, l_int32 copyflag)
boxaaAddBoxa()
Definition: boxbasic.c:1346
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:1401
NUMA * numaaGetNuma(NUMAA *naa, l_int32 index, l_int32 accessflag)
numaaGetNuma()
Definition: numabasic.c:1740
l_ok numaGetIValue(NUMA *na, l_int32 index, l_int32 *pival)
numaGetIValue()
Definition: numabasic.c:754
Definition: array.h:70
void boxaaDestroy(BOXAA **pbaa)
boxaaDestroy()
Definition: boxbasic.c:1310
l_ok boxaGetAverageSize(BOXA *boxa, l_float32 *pw, l_float32 *ph)
boxaGetAverageSize()
Definition: boxfunc2.c:1511
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:206
BOXA * boxaTransform(BOXA *boxas, l_int32 shiftx, l_int32 shifty, l_float32 scalex, l_float32 scaley)
boxaTransform()
Definition: boxfunc2.c:102
l_int32 numaGetCount(NUMA *na)
numaGetCount()
Definition: numabasic.c:658
l_int32 w
Definition: pix.h:484
l_ok boxaGetBoxGeometry(BOXA *boxa, l_int32 index, l_int32 *px, l_int32 *py, l_int32 *pw, l_int32 *ph)
boxaGetBoxGeometry()
Definition: boxbasic.c:879
l_ok boxaAddBox(BOXA *boxa, BOX *box, l_int32 copyflag)
boxaAddBox()
Definition: boxbasic.c:620
l_ok boxaaAddBox(BOXAA *baa, l_int32 index, BOX *box, l_int32 accessflag)
boxaaAddBox()
Definition: boxbasic.c:1796
l_ok boxaaAlignBox(BOXAA *baa, BOX *box, l_int32 delta, l_int32 *pindex)
boxaaAlignBox()
Definition: boxfunc2.c:1883
Definition: array.h:82
BOX * boxaGetBox(BOXA *boxa, l_int32 index, l_int32 accessflag)
boxaGetBox()
Definition: boxbasic.c:779
Definition: pix.h:711
BOXA * boxaaFlattenAligned(BOXAA *baa, l_int32 num, BOX *fillerbox, l_int32 copyflag)
boxaaFlattenAligned()
Definition: boxfunc2.c:1712
l_ok numaaReplaceNuma(NUMAA *naa, l_int32 index, NUMA *na)
numaaReplaceNuma()
Definition: numabasic.c:1776
l_ok numaaAddNumber(NUMAA *naa, l_int32 index, l_float32 val)
numaaAddNumber()
Definition: numabasic.c:1852
l_int32 x
Definition: pix.h:482
l_ok boxaGetExtent(BOXA *boxa, l_int32 *pw, l_int32 *ph, BOX **pbox)
boxaGetExtent()
Definition: boxfunc4.c:953
void numaDestroy(NUMA **pna)
numaDestroy()
Definition: numabasic.c:366
BOXAA * boxaaTranspose(BOXAA *baas)
boxaaTranspose()
Definition: boxfunc2.c:1824
BOXA * boxaBinSort(BOXA *boxas, l_int32 sorttype, l_int32 sortorder, NUMA **pnaindex)
boxaBinSort()
Definition: boxfunc2.c:761
BOXAA * boxaaCreate(l_int32 n)
boxaaCreate()
Definition: boxbasic.c:1244
PTA * boxaExtractCorners(BOXA *boxa, l_int32 loc)
boxaExtractCorners()
Definition: boxfunc2.c:1322
BOXA * boxaRotateOrth(BOXA *boxas, l_int32 w, l_int32 h, l_int32 rotation)
boxaRotateOrth()
Definition: boxfunc2.c:470
l_int32 boxaGetValidCount(BOXA *boxa)
boxaGetValidCount()
Definition: boxbasic.c:751
l_ok boxaIsFull(BOXA *boxa, l_int32 *pfull)
boxaIsFull()
Definition: boxbasic.c:915
l_ok numaJoin(NUMA *nad, NUMA *nas, l_int32 istart, l_int32 iend)
numaJoin()
Definition: numafunc1.c:3640
l_int32 numaaGetCount(NUMAA *naa)
numaaGetCount()
Definition: numabasic.c:1631
l_int32 h
Definition: pix.h:485
BOX * boxCopy(BOX *box)
boxCopy()
Definition: boxbasic.c:235
BOX * boxaaGetBox(BOXAA *baa, l_int32 iboxa, l_int32 ibox, l_int32 accessflag)
boxaaGetBox()
Definition: boxbasic.c:1531
BOXA * boxaCreate(l_int32 n)
boxaCreate()
Definition: boxbasic.c:502
void boxDestroy(BOX **pbox)
boxDestroy()
Definition: boxbasic.c:282
BOXAA * boxaSort2d(BOXA *boxas, NUMAA **pnaad, l_int32 delta1, l_int32 delta2, l_int32 minh1)
boxaSort2d()
Definition: boxfunc2.c:915
l_int32 boxaGetCount(BOXA *boxa)
boxaGetCount()
Definition: boxbasic.c:734
l_ok ptaGetIPt(PTA *pta, l_int32 index, l_int32 *px, l_int32 *py)
ptaGetIPt()
Definition: ptabasic.c:578
BOXAA * boxaEncapsulateAligned(BOXA *boxa, l_int32 num, l_int32 copyflag)
boxaEncapsulateAligned()
Definition: boxfunc2.c:1770
BOXA * boxaaFlattenToBoxa(BOXAA *baa, NUMA **pnaindex, l_int32 copyflag)
boxaaFlattenToBoxa()
Definition: boxfunc2.c:1646
l_ok boxGetGeometry(BOX *box, l_int32 *px, l_int32 *py, l_int32 *pw, l_int32 *ph)
boxGetGeometry()
Definition: boxbasic.c:313
Definition: pix.h:480
BOX * boxCreate(l_int32 x, l_int32 y, l_int32 w, l_int32 h)
boxCreate()
Definition: boxbasic.c:172
l_ok numaGetRankValue(NUMA *na, l_float32 fract, NUMA *nasort, l_int32 usebins, l_float32 *pval)
numaGetRankValue()
Definition: numafunc1.c:3352
l_ok numaaAddNuma(NUMAA *naa, NUMA *na, l_int32 copyflag)
numaaAddNuma()
Definition: numabasic.c:1546
Definition: pix.h:516
BOXA * boxaaGetBoxa(BOXAA *baa, l_int32 index, l_int32 accessflag)
boxaaGetBoxa()
Definition: boxbasic.c:1501
BOXA * boxaSortByIndex(BOXA *boxas, NUMA *naindex)
boxaSortByIndex()
Definition: boxfunc2.c:838