1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 - This software is distributed in the hope that it will be
4 - useful, but with NO WARRANTY OF ANY KIND.
5 - No author or distributor accepts responsibility to anyone for the
6 - consequences of using this software, or for whether it serves any
7 - particular purpose or works at all, unless he or she says so in
8 - writing. Everyone is granted permission to copy, modify and
9 - redistribute this source code, for commercial or non-commercial
10 - purposes, with the following restrictions: (1) the origin of this
11 - source code must not be misrepresented; (2) modified versions must
12 - be plainly marked as such; and (3) this notice may not be removed
13 - or altered from any source or modified source distribution.
14 *====================================================================*/
15
16 /*
17 * boxfunc1.c
18 *
19 * Box geometry
20 * l_int32 boxContains()
21 * l_int32 boxIntersects()
22 * BOXA *boxaContainedInBox()
23 * BOXA *boxaIntersectsBox()
24 * BOXA *boxaClipToBox()
25 * BOX *boxOverlapRegion()
26 * BOX *boxBoundingRegion()
27 * l_int32 boxOverlapFraction()
28 * l_int32 boxContainsPt()
29 * BOX *boxaGetNearestToPt()
30 * l_int32 boxIntersectByLine()
31 * l_int32 boxGetCentroid()
32 * BOX *boxClipToRectangle()
33 * BOX *boxRelocateOneSide()
34 * BOX *boxAdjustSides()
35 * l_int32 boxEqual()
36 * l_int32 boxaEqual()
37 *
38 * Boxa combination
39 * l_int32 boxaJoin()
40 *
41 * Other boxa functions
42 * l_int32 boxaGetExtent()
43 * l_int32 boxaGetCoverage()
44 * l_int32 boxaSizeRange()
45 * l_int32 boxaLocationRange()
46 * BOXA *boxaSelectBySize()
47 * NUMA *boxaMakeSizeIndicator()
48 * BOXA *boxaSelectWithIndicator()
49 * BOXA *boxaPermutePseudorandom()
50 * BOXA *boxaPermuteRandom()
51 * l_int32 boxaSwapBoxes()
52 * PTA *boxaConvertToPta()
53 * BOXA *ptaConvertToBoxa()
54 *
55 */
56
57 #include <stdio.h>
58 #include <stdlib.h>
59 #include "allheaders.h"
60
61
62 /*---------------------------------------------------------------------*
63 * Box geometry *
64 *---------------------------------------------------------------------*/
65 /*!
66 * boxContains()
67 *
68 * Input: box1, box2
69 * &result (<return> 1 if box2 is entirely contained within
70 * box1, and 0 otherwise)
71 * Return: 0 if OK, 1 on error
72 */
73 l_int32
boxContains(BOX * box1,BOX * box2,l_int32 * presult)74 boxContains(BOX *box1,
75 BOX *box2,
76 l_int32 *presult)
77 {
78 PROCNAME("boxContains");
79
80 if (!box1 || !box2)
81 return ERROR_INT("box1 and box2 not both defined", procName, 1);
82
83 if ((box1->x <= box2->x) &&
84 (box1->y <= box2->y) &&
85 (box1->x + box1->w >= box2->x + box2->w) &&
86 (box1->y + box1->h >= box2->y + box2->h))
87 *presult = 1;
88 else
89 *presult = 0;
90 return 0;
91 }
92
93
94
95 /*!
96 * boxIntersects()
97 *
98 * Input: box1, box2
99 * &result (<return> 1 if any part of box2 is contained
100 * in box1, and 0 otherwise)
101 * Return: 0 if OK, 1 on error
102 */
103 l_int32
boxIntersects(BOX * box1,BOX * box2,l_int32 * presult)104 boxIntersects(BOX *box1,
105 BOX *box2,
106 l_int32 *presult)
107 {
108 l_int32 left1, left2, top1, top2, right1, right2, bot1, bot2;
109
110 PROCNAME("boxIntersects");
111
112 if (!box1 || !box2)
113 return ERROR_INT("box1 and box2 not both defined", procName, 1);
114
115 left1 = box1->x;
116 left2 = box2->x;
117 top1 = box1->y;
118 top2 = box2->y;
119 right1 = box1->x + box1->w - 1;
120 bot1 = box1->y + box1->h - 1;
121 right2 = box2->x + box2->w - 1;
122 bot2 = box2->y + box2->h - 1;
123 if ((bot2 >= top1) && (bot1 >= top2) &&
124 (right1 >= left2) && (right2 >= left1))
125 *presult = 1;
126 else
127 *presult = 0;
128 return 0;
129 }
130
131
132 /*!
133 * boxaContainedInBox()
134 *
135 * Input: boxas
136 * box (for containment)
137 * Return: boxad (boxa with all boxes in boxas that are
138 * entirely contained in box), or null on error
139 *
140 * Notes:
141 * (1) All boxes in boxa that are entirely outside box are removed.
142 */
143 BOXA *
boxaContainedInBox(BOXA * boxas,BOX * box)144 boxaContainedInBox(BOXA *boxas,
145 BOX *box)
146 {
147 l_int32 i, n, val;
148 BOX *boxt;
149 BOXA *boxad;
150
151 PROCNAME("boxaContainedInBox");
152
153 if (!boxas)
154 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
155 if (!box)
156 return (BOXA *)ERROR_PTR("box not defined", procName, NULL);
157 if ((n = boxaGetCount(boxas)) == 0)
158 return boxaCreate(1); /* empty */
159
160 boxad = boxaCreate(0);
161 for (i = 0; i < n; i++) {
162 boxt = boxaGetBox(boxas, i, L_CLONE);
163 boxContains(box, boxt, &val);
164 if (val == 1)
165 boxaAddBox(boxad, boxt, L_COPY);
166 boxDestroy(&boxt); /* destroy the clone */
167 }
168
169 return boxad;
170 }
171
172
173 /*!
174 * boxaIntersectsBox()
175 *
176 * Input: boxas
177 * box (for intersecting)
178 * Return boxad (boxa with all boxes in boxas that intersect box),
179 * or null on error
180 *
181 * Notes:
182 * (1) All boxes in boxa that intersect with box (i.e., are completely
183 * or partially contained in box) are retained.
184 */
185 BOXA *
boxaIntersectsBox(BOXA * boxas,BOX * box)186 boxaIntersectsBox(BOXA *boxas,
187 BOX *box)
188 {
189 l_int32 i, n, val;
190 BOX *boxt;
191 BOXA *boxad;
192
193 PROCNAME("boxaIntersectsBox");
194
195 if (!boxas)
196 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
197 if (!box)
198 return (BOXA *)ERROR_PTR("box not defined", procName, NULL);
199 if ((n = boxaGetCount(boxas)) == 0)
200 return boxaCreate(1); /* empty */
201
202 boxad = boxaCreate(0);
203 for (i = 0; i < n; i++) {
204 boxt = boxaGetBox(boxas, i, L_CLONE);
205 boxIntersects(box, boxt, &val);
206 if (val == 1)
207 boxaAddBox(boxad, boxt, L_COPY);
208 boxDestroy(&boxt); /* destroy the clone */
209 }
210
211 return boxad;
212 }
213
214
215 /*!
216 * boxaClipToBox()
217 *
218 * Input: boxas
219 * box (for clipping)
220 * Return boxad (boxa with boxes in boxas clipped to box),
221 * or null on error
222 *
223 * Notes:
224 * (1) All boxes in boxa not intersecting with box are removed, and
225 * the remaining boxes are clipped to box.
226 */
227 BOXA *
boxaClipToBox(BOXA * boxas,BOX * box)228 boxaClipToBox(BOXA *boxas,
229 BOX *box)
230 {
231 l_int32 i, n;
232 BOX *boxt, *boxo;
233 BOXA *boxad;
234
235 PROCNAME("boxaClipToBox");
236
237 if (!boxas)
238 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
239 if (!box)
240 return (BOXA *)ERROR_PTR("box not defined", procName, NULL);
241 if ((n = boxaGetCount(boxas)) == 0)
242 return boxaCreate(1); /* empty */
243
244 boxad = boxaCreate(0);
245 for (i = 0; i < n; i++) {
246 boxt = boxaGetBox(boxas, i, L_CLONE);
247 if ((boxo = boxOverlapRegion(box, boxt)) != NULL)
248 boxaAddBox(boxad, boxo, L_INSERT);
249 boxDestroy(&boxt);
250 }
251
252 return boxad;
253 }
254
255
256 /*!
257 * boxOverlapRegion()
258 *
259 * Input: box1, box2 (two boxes)
260 * Return: box (of overlap region between input boxes),
261 * or null if no overlap or on error
262 */
263 BOX *
boxOverlapRegion(BOX * box1,BOX * box2)264 boxOverlapRegion(BOX *box1,
265 BOX *box2)
266 {
267 l_int32 x, y, w, h, left1, left2, top1, top2, right1, right2, bot1, bot2;
268
269 PROCNAME("boxOverlapRegion");
270
271 if (!box1)
272 return (BOX *)ERROR_PTR("box1 not defined", procName, NULL);
273 if (!box2)
274 return (BOX *)ERROR_PTR("box2 not defined", procName, NULL);
275
276 left1 = box1->x;
277 left2 = box2->x;
278 top1 = box1->y;
279 top2 = box2->y;
280 right1 = box1->x + box1->w - 1;
281 bot1 = box1->y + box1->h - 1;
282 right2 = box2->x + box2->w - 1;
283 bot2 = box2->y + box2->h - 1;
284 if ((bot2 < top1) || (bot1 < top2) ||
285 (right1 < left2) || (right2 < left1))
286 return NULL;
287
288 x = (left1 > left2) ? left1 : left2;
289 y = (top1 > top2) ? top1 : top2;
290 w = L_MIN(right1 - x + 1, right2 - x + 1);
291 h = L_MIN(bot1 - y + 1, bot2 - y + 1);
292 return boxCreate(x, y, w, h);
293 }
294
295
296 /*!
297 * boxBoundingRegion()
298 *
299 * Input: box1, box2 (two boxes)
300 * Return: box (of bounding region containing the input boxes),
301 * or null on error
302 */
303 BOX *
boxBoundingRegion(BOX * box1,BOX * box2)304 boxBoundingRegion(BOX *box1,
305 BOX *box2)
306 {
307 l_int32 left, top, right1, right2, right, bot1, bot2, bot;
308
309 PROCNAME("boxBoundingRegion");
310
311 if (!box1)
312 return (BOX *)ERROR_PTR("box1 not defined", procName, NULL);
313 if (!box2)
314 return (BOX *)ERROR_PTR("box2 not defined", procName, NULL);
315
316 left = L_MIN(box1->x, box2->x);
317 top = L_MIN(box1->y, box2->y);
318 right1 = box1->x + box1->w - 1;
319 right2 = box2->x + box2->w - 1;
320 right = L_MAX(right1, right2);
321 bot1 = box1->y + box1->h - 1;
322 bot2 = box2->y + box2->h - 1;
323 bot = L_MAX(bot1, bot2);
324 return boxCreate(left, top, right - left + 1, bot - top + 1);
325 }
326
327
328 /*!
329 * boxOverlapFraction()
330 *
331 * Input: box1, box2 (two boxes)
332 * &fract (<return> the fraction of box2 overlapped by box1)
333 * Return: 0 if OK, 1 on error.
334 *
335 * Notes:
336 * (1) The result depends on the order of the input boxes,
337 * because the overlap is taken as a fraction of box2.
338 */
339 l_int32
boxOverlapFraction(BOX * box1,BOX * box2,l_float32 * pfract)340 boxOverlapFraction(BOX *box1,
341 BOX *box2,
342 l_float32 *pfract)
343 {
344 l_int32 w2, h2, w, h;
345 BOX *boxo;
346
347 PROCNAME("boxOverlapFraction");
348
349 if (!pfract)
350 return ERROR_INT("&fract not defined", procName, 1);
351 *pfract = 0.0;
352 if (!box1)
353 return ERROR_INT("box1 not defined", procName, 1);
354 if (!box2)
355 return ERROR_INT("box2 not defined", procName, 1);
356
357 if ((boxo = boxOverlapRegion(box1, box2)) == NULL) /* no overlap */
358 return 0;
359
360 boxGetGeometry(box2, NULL, NULL, &w2, &h2);
361 boxGetGeometry(boxo, NULL, NULL, &w, &h);
362 *pfract = (l_float32)(w * h) / (l_float32)(w2 * h2);
363 boxDestroy(&boxo);
364 return 0;
365 }
366
367
368 /*!
369 * boxContainsPt()
370 *
371 * Input: box
372 * x, y (a point)
373 * &contains (<return> 1 if box contains point; 0 otherwise)
374 * Return: 0 if OK, 1 on error.
375 */
376 l_int32
boxContainsPt(BOX * box,l_float32 x,l_float32 y,l_int32 * pcontains)377 boxContainsPt(BOX *box,
378 l_float32 x,
379 l_float32 y,
380 l_int32 *pcontains)
381 {
382 l_int32 bx, by, bw, bh;
383
384 PROCNAME("boxContainsPt");
385
386 if (!pcontains)
387 return ERROR_INT("&contains not defined", procName, 1);
388 *pcontains = 0;
389 if (!box)
390 return ERROR_INT("&box not defined", procName, 1);
391 boxGetGeometry(box, &bx, &by, &bw, &bh);
392 if (x >= bx && x < bx + bw && y >= by && y < by + bh)
393 *pcontains = 1;
394 return 0;
395 }
396
397
398 /*!
399 * boxaGetNearestToPt()
400 *
401 * Input: boxa
402 * x, y (point)
403 * Return box (box with centroid closest to the given point [x,y]),
404 * or NULL if no boxes in boxa)
405 *
406 * Notes:
407 * (1) Uses euclidean distance between centroid and point.
408 */
409 BOX *
boxaGetNearestToPt(BOXA * boxa,l_int32 x,l_int32 y)410 boxaGetNearestToPt(BOXA *boxa,
411 l_int32 x,
412 l_int32 y)
413 {
414 l_int32 i, n, cx, cy, minindex;
415 l_float32 delx, dely, dist, mindist;
416 BOX *box;
417
418 PROCNAME("boxaGetNearestToPt");
419
420 if (!boxa)
421 return (BOX *)ERROR_PTR("boxa not defined", procName, NULL);
422 if ((n = boxaGetCount(boxa)) == 0)
423 return (BOX *)ERROR_PTR("n = 0", procName, NULL);
424
425 mindist = 1000000000.;
426 minindex = 0;
427 for (i = 0; i < n; i++) {
428 box = boxaGetBox(boxa, i, L_CLONE);
429 boxGetCentroid(box, &cx, &cy);
430 delx = (l_float32)(cx - x);
431 dely = (l_float32)(cy - y);
432 dist = delx * delx + dely * dely;
433 if (dist < mindist) {
434 minindex = i;
435 mindist = dist;
436 }
437 boxDestroy(&box);
438 }
439
440 return boxaGetBox(boxa, minindex, L_COPY);
441 }
442
443
444 /*!
445 * boxGetCentroid()
446 *
447 * Input: box
448 * &x, &y (<return> location of center of box)
449 * Return 0 if OK, 1 on error
450 */
451 l_int32
boxGetCentroid(BOX * box,l_int32 * px,l_int32 * py)452 boxGetCentroid(BOX *box,
453 l_int32 *px,
454 l_int32 *py)
455 {
456 l_int32 x, y, w, h;
457
458 PROCNAME("boxGetCentroid");
459
460 if (!px || !py)
461 return ERROR_INT("&x, &y not both defined", procName, 1);
462 *px = *py = 0;
463 if (!box)
464 return ERROR_INT("box not defined", procName, 1);
465 boxGetGeometry(box, &x, &y, &w, &h);
466 *px = x + w / 2;
467 *py = y + h / 2;
468
469 return 0;
470 }
471
472
473 /*!
474 * boxIntersectByLine()
475 *
476 * Input: box
477 * x, y (point that line goes through)
478 * slope (of line)
479 * (&x1, &y1) (<return> 1st point of intersection with box)
480 * (&x2, &y2) (<return> 2nd point of intersection with box)
481 * &n (<return> number of points of intersection)
482 * Return: 0 if OK, 1 on error
483 *
484 * Notes:
485 * (1) If the intersection is at only one point (a corner), the
486 * coordinates are returned in (x1, y1).
487 * (2) Represent a vertical line by one with a large but finite slope.
488 */
489 l_int32
boxIntersectByLine(BOX * box,l_int32 x,l_int32 y,l_float32 slope,l_int32 * px1,l_int32 * py1,l_int32 * px2,l_int32 * py2,l_int32 * pn)490 boxIntersectByLine(BOX *box,
491 l_int32 x,
492 l_int32 y,
493 l_float32 slope,
494 l_int32 *px1,
495 l_int32 *py1,
496 l_int32 *px2,
497 l_int32 *py2,
498 l_int32 *pn)
499 {
500 l_int32 bx, by, bw, bh, xp, yp, xt, yt, i, n;
501 l_float32 invslope;
502 PTA *pta;
503
504 PROCNAME("boxIntersectByLine");
505
506 if (!px1 || !py1 || !px2 || !py2)
507 return ERROR_INT("&x1, &y1, &x2, &y2 not all defined", procName, 1);
508 *px1 = *py1 = *px2 = *py2 = 0;
509 if (!pn)
510 return ERROR_INT("&n not defined", procName, 1);
511 *pn = 0;
512 if (!box)
513 return ERROR_INT("box not defined", procName, 1);
514 boxGetGeometry(box, &bx, &by, &bw, &bh);
515
516 if (slope == 0.0) {
517 if (y >= by && y < by + bh) {
518 *py1 = *py2 = y;
519 *px1 = bx;
520 *px2 = bx + bw - 1;
521 }
522 return 0;
523 }
524
525 if (slope > 1000000.0) {
526 if (x >= bx && x < bx + bw) {
527 *px1 = *px2 = x;
528 *py1 = by;
529 *py2 = by + bh - 1;
530 }
531 return 0;
532 }
533
534 /* Intersection with top and bottom lines of box */
535 pta = ptaCreate(2);
536 invslope = 1.0 / slope;
537 xp = (l_int32)(x + invslope * (y - by));
538 if (xp >= bx && xp < bx + bw)
539 ptaAddPt(pta, xp, by);
540 xp = (l_int32)(x + invslope * (y - by - bh + 1));
541 if (xp >= bx && xp < bx + bw)
542 ptaAddPt(pta, xp, by + bh - 1);
543
544 /* Intersection with left and right lines of box */
545 yp = (l_int32)(y + slope * (x - bx));
546 if (yp >= by && yp < by + bh)
547 ptaAddPt(pta, bx, yp);
548 yp = (l_int32)(y + slope * (x - bx - bw + 1));
549 if (yp >= by && yp < by + bh)
550 ptaAddPt(pta, bx + bw - 1, yp);
551
552 /* There is a maximum of 2 unique points; remove duplicates. */
553 n = ptaGetCount(pta);
554 if (n > 0) {
555 ptaGetIPt(pta, 0, px1, py1); /* accept the first one */
556 *pn = 1;
557 }
558 for (i = 1; i < n; i++) {
559 ptaGetIPt(pta, i, &xt, &yt);
560 if ((*px1 != xt) || (*py1 != yt)) {
561 *px2 = xt;
562 *py2 = yt;
563 *pn = 2;
564 break;
565 }
566 }
567
568 ptaDestroy(&pta);
569 return 0;
570 }
571
572
573 /*!
574 * boxClipToRectangle()
575 *
576 * Input: box
577 * wi, hi (rectangle representing image)
578 * Return: part of box within given rectangle, or NULL on error
579 * or if box is entirely outside the rectangle
580 *
581 * Note: the rectangle is assumed to go from (0,0) to (wi - 1, hi - 1)
582 */
583 BOX *
boxClipToRectangle(BOX * box,l_int32 wi,l_int32 hi)584 boxClipToRectangle(BOX *box,
585 l_int32 wi,
586 l_int32 hi)
587 {
588 BOX *boxd;
589
590 PROCNAME("boxClipToRectangle");
591
592 if (!box)
593 return (BOX *)ERROR_PTR("box not defined", procName, NULL);
594 if (box->x >= wi || box->y >= hi ||
595 box->x + box->w <= 0 || box->y + box->h <= 0)
596 return (BOX *)ERROR_PTR("box outside rectangle", procName, NULL);
597
598 boxd = boxCopy(box);
599 if (boxd->x < 0) {
600 boxd->w += boxd->x;
601 boxd->x = 0;
602 }
603 if (boxd->y < 0) {
604 boxd->h += boxd->y;
605 boxd->y = 0;
606 }
607 if (boxd->x + boxd->w > wi)
608 boxd->w = wi - boxd->x;
609 if (boxd->y + boxd->h > hi)
610 boxd->h = hi - boxd->y;
611 return boxd;
612 }
613
614
615 /*!
616 * boxRelocateOneSide()
617 *
618 * Input: boxd (<optional>; this can be null, equal to boxs,
619 * or different from boxs);
620 * boxs (starting box; to have one side relocated)
621 * loc (new location of the side that is changing)
622 * sideflag (L_FROM_LEFT, etc., indicating the side that moves)
623 * Return: boxd, or null on error or if the computed boxd has
624 * width or height <= 0.
625 *
626 * Notes:
627 * (1) Set boxd == NULL to get new box; boxd == boxs for in-place;
628 * or otherwise to resize existing boxd.
629 * (2) For usage, suggest one of these:
630 * boxd = boxRelocateOneSide(NULL, boxs, ...); // new
631 * boxRelocateOneSide(boxs, boxs, ...); // in-place
632 * boxRelocateOneSide(boxd, boxs, ...); // other
633 */
634 BOX *
boxRelocateOneSide(BOX * boxd,BOX * boxs,l_int32 loc,l_int32 sideflag)635 boxRelocateOneSide(BOX *boxd,
636 BOX *boxs,
637 l_int32 loc,
638 l_int32 sideflag)
639 {
640 l_int32 x, y, w, h;
641
642 PROCNAME("boxRelocateOneSide");
643
644 if (!boxs)
645 return (BOX *)ERROR_PTR("boxs not defined", procName, NULL);
646 if (!boxd)
647 boxd = boxCopy(boxs);
648
649 boxGetGeometry(boxs, &x, &y, &w, &h);
650 if (sideflag == L_FROM_LEFT)
651 boxSetGeometry(boxd, loc, -1, w + x - loc, -1);
652 else if (sideflag == L_FROM_RIGHT)
653 boxSetGeometry(boxd, -1, -1, loc - x + 1, -1);
654 else if (sideflag == L_FROM_TOP)
655 boxSetGeometry(boxd, -1, loc, -1, h + y - loc);
656 else if (sideflag == L_FROM_BOTTOM)
657 boxSetGeometry(boxd, -1, -1, -1, loc - y + 1);
658 return boxd;
659 }
660
661
662 /*!
663 * boxAdjustSides()
664 *
665 * Input: boxd (<optional>; this can be null, equal to boxs,
666 * or different from boxs)
667 * boxs (starting box; to have sides adjusted)
668 * delleft, delright, deltop, delbot (changes in location of
669 * each side)
670 * Return: boxd, or null on error or if the computed boxd has
671 * width or height <= 0.
672 *
673 * Notes:
674 * (1) Set boxd == NULL to get new box; boxd == boxs for in-place;
675 * or otherwise to resize existing boxd.
676 * (2) For usage, suggest one of these:
677 * boxd = boxAdjustSides(NULL, boxs, ...); // new
678 * boxAdjustSides(boxs, boxs, ...); // in-place
679 * boxAdjustSides(boxd, boxs, ...); // other
680 * (1) New box dimensions are cropped at left and top to x >= 0 and y >= 0.
681 * (2) For example, to expand in-place by 20 pixels on each side, use
682 * boxAdjustSides(box, box, -20, 20, -20, 20);
683 */
684 BOX *
boxAdjustSides(BOX * boxd,BOX * boxs,l_int32 delleft,l_int32 delright,l_int32 deltop,l_int32 delbot)685 boxAdjustSides(BOX *boxd,
686 BOX *boxs,
687 l_int32 delleft,
688 l_int32 delright,
689 l_int32 deltop,
690 l_int32 delbot)
691 {
692 l_int32 x, y, w, h, xl, xr, yt, yb, wnew, hnew;
693
694 PROCNAME("boxAdjustSides");
695
696 if (!boxs)
697 return (BOX *)ERROR_PTR("boxs not defined", procName, NULL);
698
699 boxGetGeometry(boxs, &x, &y, &w, &h);
700 xl = L_MAX(0, x + delleft);
701 yt = L_MAX(0, y + deltop);
702 xr = x + w + delright; /* one pixel beyond right edge */
703 yb = y + h + delbot; /* one pixel below bottom edge */
704 wnew = xr - xl;
705 hnew = yb - yt;
706
707 if (wnew < 1 || hnew < 1)
708 return (BOX *)ERROR_PTR("boxd has 0 area", procName, NULL);
709
710 if (!boxd)
711 return boxCreate(xl, yt, wnew, hnew);
712 else {
713 boxSetGeometry(boxd, xl, yt, wnew, hnew);
714 return boxd;
715 }
716 }
717
718
719 /*!
720 * boxEqual()
721 *
722 * Input: box1
723 * box2
724 * &same (<return> 1 if equal; 0 otherwise)
725 * Return 0 if OK, 1 on error
726 */
727 l_int32
boxEqual(BOX * box1,BOX * box2,l_int32 * psame)728 boxEqual(BOX *box1,
729 BOX *box2,
730 l_int32 *psame)
731 {
732 PROCNAME("boxEqual");
733
734 if (!psame)
735 return ERROR_INT("&same not defined", procName, 1);
736 *psame = 0;
737 if (!box1 || !box2)
738 return ERROR_INT("box1 and box2 not both defined", procName, 1);
739 if (box1->x == box2->x && box1->y == box2->y &&
740 box1->w == box2->w && box1->h == box2->h)
741 *psame = 1;
742 return 0;
743 }
744
745
746 /*!
747 * boxaEqual()
748 *
749 * Input: boxa1
750 * boxa2
751 * maxdist
752 * &naindex (<optional return> index array of correspondences
753 * &same (<return> 1 if equal; 0 otherwise)
754 * Return 0 if OK, 1 on error
755 *
756 * Notes:
757 * (1) The two boxa are the "same" if they contain the same
758 * boxes and each box is within @maxdist of its counterpart
759 * in their positions within the boxa. This allows for
760 * small rearrangements. Use 0 for maxdist if the boxa
761 * must be identical.
762 * (2) This applies only to geometry and ordering; refcounts
763 * are not considered.
764 * (3) @maxdist allows some latitude in the ordering of the boxes.
765 * For the boxa to be the "same", corresponding boxes must
766 * be within @maxdist of each other. Note that for large
767 * @maxdist, we should use a hash function for efficiency.
768 * (4) naindex[i] gives the position of the box in boxa2 that
769 * corresponds to box i in boxa1. It is only returned if the
770 * boxa are equal.
771 */
772 l_int32
boxaEqual(BOXA * boxa1,BOXA * boxa2,l_int32 maxdist,NUMA ** pnaindex,l_int32 * psame)773 boxaEqual(BOXA *boxa1,
774 BOXA *boxa2,
775 l_int32 maxdist,
776 NUMA **pnaindex,
777 l_int32 *psame)
778 {
779 l_int32 i, j, n, jstart, jend, found, samebox;
780 l_int32 *countarray;
781 BOX *box1, *box2;
782 NUMA *na;
783
784 PROCNAME("boxaEqual");
785
786 if (pnaindex) *pnaindex = NULL;
787 if (!psame)
788 return ERROR_INT("&same not defined", procName, 1);
789 *psame = 0;
790 if (!boxa1 || !boxa2)
791 return ERROR_INT("boxa1 and boxa2 not both defined", procName, 1);
792 n = boxaGetCount(boxa1);
793 if (n != boxaGetCount(boxa2))
794 return 0;
795
796 countarray = (l_int32 *)CALLOC(n, sizeof(l_int32));
797 na = numaMakeConstant(0.0, n);
798
799 for (i = 0; i < n; i++) {
800 box1 = boxaGetBox(boxa1, i, L_CLONE);
801 jstart = L_MAX(0, i - maxdist);
802 jend = L_MIN(n-1, i + maxdist);
803 found = FALSE;
804 for (j = jstart; j <= jend; j++) {
805 box2 = boxaGetBox(boxa2, j, L_CLONE);
806 boxEqual(box1, box2, &samebox);
807 if (samebox && countarray[j] == 0) {
808 countarray[j] = 1;
809 numaReplaceNumber(na, i, j);
810 found = TRUE;
811 boxDestroy(&box2);
812 break;
813 }
814 boxDestroy(&box2);
815 }
816 boxDestroy(&box1);
817 if (!found) {
818 numaDestroy(&na);
819 FREE(countarray);
820 return 0;
821 }
822 }
823
824 *psame = 1;
825 if (pnaindex)
826 *pnaindex = na;
827 else
828 numaDestroy(&na);
829 FREE(countarray);
830 return 0;
831 }
832
833
834 /*----------------------------------------------------------------------*
835 * Boxa Combination *
836 *----------------------------------------------------------------------*/
837 /*!
838 * boxaJoin()
839 *
840 * Input: boxad (dest boxa; add to this one)
841 * boxas (source boxa; add from this one)
842 * istart (starting index in nas)
843 * iend (ending index in nas; use 0 to cat all)
844 * Return: 0 if OK, 1 on error
845 *
846 * Notes:
847 * (1) This appends a clone of each indicated box in boxas to boxad
848 * (2) istart < 0 is taken to mean 'read from the start' (istart = 0)
849 * (3) iend <= 0 means 'read to the end'
850 */
851 l_int32
boxaJoin(BOXA * boxad,BOXA * boxas,l_int32 istart,l_int32 iend)852 boxaJoin(BOXA *boxad,
853 BOXA *boxas,
854 l_int32 istart,
855 l_int32 iend)
856 {
857 l_int32 ns, i;
858 BOX *box;
859
860 PROCNAME("boxaJoin");
861
862 if (!boxad)
863 return ERROR_INT("boxad not defined", procName, 1);
864 if (!boxas)
865 return ERROR_INT("boxas not defined", procName, 1);
866 ns = boxaGetCount(boxas);
867 if (istart < 0)
868 istart = 0;
869 if (istart >= ns)
870 return ERROR_INT("istart out of bounds", procName, 1);
871 if (iend <= 0)
872 iend = ns - 1;
873 if (iend >= ns)
874 return ERROR_INT("iend out of bounds", procName, 1);
875 if (istart > iend)
876 return ERROR_INT("istart > iend; nothing to add", procName, 1);
877
878 for (i = istart; i <= iend; i++) {
879 box = boxaGetBox(boxas, i, L_CLONE);
880 boxaAddBox(boxad, box, L_INSERT);
881 }
882
883 return 0;
884 }
885
886
887 /*---------------------------------------------------------------------*
888 * Other Boxa functions *
889 *---------------------------------------------------------------------*/
890 /*!
891 * boxaGetExtent()
892 *
893 * Input: boxa
894 * &w (<optional return> width)
895 * &h (<optional return> height)
896 * &box (<optional return>, minimum box containing all boxes
897 * in boxa)
898 * Return: 0 if OK, 1 on error
899 *
900 * Notes:
901 * (1) The returned w and h are the minimum size image
902 * that would contain all boxes untranslated.
903 */
904 l_int32
boxaGetExtent(BOXA * boxa,l_int32 * pw,l_int32 * ph,BOX ** pbox)905 boxaGetExtent(BOXA *boxa,
906 l_int32 *pw,
907 l_int32 *ph,
908 BOX **pbox)
909 {
910 l_int32 i, n, x, y, w, h, xmax, ymax, xmin, ymin;
911
912 PROCNAME("boxaGetExtent");
913
914 if (!pw && !ph && !pbox)
915 return ERROR_INT("no ptrs defined", procName, 1);
916 if (pbox) *pbox = NULL;
917 if (pw) *pw = 0;
918 if (ph) *ph = 0;
919 if (!boxa)
920 return ERROR_INT("boxa not defined", procName, 1);
921
922 n = boxaGetCount(boxa);
923 if (n == 0)
924 return ERROR_INT("no boxes in boxa", procName, 1);
925
926 xmax = ymax = 0;
927 xmin = ymin = 100000000;
928 for (i = 0; i < n; i++) {
929 boxaGetBoxGeometry(boxa, i, &x, &y, &w, &h);
930 xmin = L_MIN(xmin, x);
931 ymin = L_MIN(ymin, y);
932 xmax = L_MAX(xmax, x + w);
933 ymax = L_MAX(ymax, y + h);
934 }
935 if (pw) *pw = xmax;
936 if (ph) *ph = ymax;
937 if (pbox)
938 *pbox = boxCreate(xmin, ymin, xmax - xmin, ymax - ymin);
939
940 return 0;
941 }
942
943
944 /*!
945 * boxaGetCoverage()
946 *
947 * Input: boxa
948 * wc, hc (dimensions of overall clipping rectangle with UL
949 * corner at (0, 0) that is covered by the boxes.
950 * exactflag (1 for guaranteeing an exact result; 0 for getting
951 * an exact result only if the boxes do not overlap)
952 * &fract (<return> sum of box area as fraction of w * h)
953 * Return: 0 if OK, 1 on error
954 *
955 * Notes:
956 * (1) The boxes in boxa are clipped to the input rectangle.
957 * (2) * When @exactflag == 1, we generate a 1 bpp pix of size
958 * wc x hc, paint all the boxes black, and count the fg pixels.
959 * This can take 1 msec on a large page with many boxes.
960 * * When @exactflag == 0, we clip each box to the wc x hc region
961 * and sum the resulting areas. This is faster.
962 * * The results are the same when none of the boxes overlap
963 * within the wc x hc region.
964 */
965 l_int32
boxaGetCoverage(BOXA * boxa,l_int32 wc,l_int32 hc,l_int32 exactflag,l_float32 * pfract)966 boxaGetCoverage(BOXA *boxa,
967 l_int32 wc,
968 l_int32 hc,
969 l_int32 exactflag,
970 l_float32 *pfract)
971 {
972 l_int32 i, n, x, y, w, h, sum;
973 BOX *box, *boxc;
974 PIX *pixt;
975
976 PROCNAME("boxaGetCoverage");
977
978 if (!pfract)
979 return ERROR_INT("&fract not defined", procName, 1);
980 *pfract = 0.0;
981 if (!boxa)
982 return ERROR_INT("boxa not defined", procName, 1);
983
984 n = boxaGetCount(boxa);
985 if (n == 0)
986 return ERROR_INT("no boxes in boxa", procName, 1);
987
988 if (exactflag == 0) { /* quick and dirty */
989 sum = 0;
990 for (i = 0; i < n; i++) {
991 box = boxaGetBox(boxa, i, L_CLONE);
992 if ((boxc = boxClipToRectangle(box, wc, hc)) != NULL) {
993 boxGetGeometry(boxc, NULL, NULL, &w, &h);
994 sum += w * h;
995 boxDestroy(&boxc);
996 }
997 boxDestroy(&box);
998 }
999 }
1000 else { /* slower and exact */
1001 pixt = pixCreate(wc, hc, 1);
1002 for (i = 0; i < n; i++) {
1003 box = boxaGetBox(boxa, i, L_CLONE);
1004 boxGetGeometry(box, &x, &y, &w, &h);
1005 pixRasterop(pixt, x, y, w, h, PIX_SET, NULL, 0, 0);
1006 boxDestroy(&box);
1007 }
1008 pixCountPixels(pixt, &sum, NULL);
1009 pixDestroy(&pixt);
1010 }
1011
1012 *pfract = (l_float32)sum / (l_float32)(wc * hc);
1013 return 0;
1014 }
1015
1016
1017 /*!
1018 * boxaSizeRange()
1019 *
1020 * Input: boxa
1021 * &minw, &minh, &maxw, &maxh (<optional return> range of
1022 * dimensions of box in the array)
1023 * Return: 0 if OK, 1 on error
1024 */
1025 l_int32
boxaSizeRange(BOXA * boxa,l_int32 * pminw,l_int32 * pminh,l_int32 * pmaxw,l_int32 * pmaxh)1026 boxaSizeRange(BOXA *boxa,
1027 l_int32 *pminw,
1028 l_int32 *pminh,
1029 l_int32 *pmaxw,
1030 l_int32 *pmaxh)
1031 {
1032 l_int32 minw, minh, maxw, maxh, i, n, w, h;
1033
1034 PROCNAME("boxaSizeRange");
1035
1036 if (!boxa)
1037 return ERROR_INT("boxa not defined", procName, 1);
1038 if (!pminw && !pmaxw && !pminh && !pmaxh)
1039 return ERROR_INT("no data can be returned", procName, 1);
1040
1041 minw = minh = 100000000;
1042 maxw = maxh = 0;
1043 n = boxaGetCount(boxa);
1044 for (i = 0; i < n; i++) {
1045 boxaGetBoxGeometry(boxa, i, NULL, NULL, &w, &h);
1046 if (w < minw)
1047 minw = w;
1048 if (h < minh)
1049 minh = h;
1050 if (w > maxw)
1051 maxw = w;
1052 if (h > maxh)
1053 maxh = h;
1054 }
1055
1056 if (pminw) *pminw = minw;
1057 if (pminh) *pminh = minh;
1058 if (pmaxw) *pmaxw = maxw;
1059 if (pmaxh) *pmaxh = maxh;
1060
1061 return 0;
1062 }
1063
1064
1065 /*!
1066 * boxaLocationRange()
1067 *
1068 * Input: boxa
1069 * &minx, &miny, &maxx, &maxy (<optional return> range of
1070 * UL corner positions)
1071 * Return: 0 if OK, 1 on error
1072 */
1073 l_int32
boxaLocationRange(BOXA * boxa,l_int32 * pminx,l_int32 * pminy,l_int32 * pmaxx,l_int32 * pmaxy)1074 boxaLocationRange(BOXA *boxa,
1075 l_int32 *pminx,
1076 l_int32 *pminy,
1077 l_int32 *pmaxx,
1078 l_int32 *pmaxy)
1079 {
1080 l_int32 minx, miny, maxx, maxy, i, n, x, y;
1081
1082 PROCNAME("boxaLocationRange");
1083
1084 if (!boxa)
1085 return ERROR_INT("boxa not defined", procName, 1);
1086 if (!pminx && !pminy && !pmaxx && !pmaxy)
1087 return ERROR_INT("no data can be returned", procName, 1);
1088
1089 minx = miny = 100000000;
1090 maxx = maxy = 0;
1091 n = boxaGetCount(boxa);
1092 for (i = 0; i < n; i++) {
1093 boxaGetBoxGeometry(boxa, i, &x, &y, NULL, NULL);
1094 if (x < minx)
1095 minx = x;
1096 if (y < miny)
1097 miny = y;
1098 if (x > maxx)
1099 maxx = x;
1100 if (y > maxy)
1101 maxy = y;
1102 }
1103
1104 if (pminx) *pminx = minx;
1105 if (pminy) *pminy = miny;
1106 if (pmaxx) *pmaxx = maxx;
1107 if (pmaxy) *pmaxy = maxy;
1108
1109 return 0;
1110 }
1111
1112
1113 /*!
1114 * boxaSelectBySize()
1115 *
1116 * Input: boxas
1117 * width, height (threshold dimensions)
1118 * type (L_SELECT_WIDTH, L_SELECT_HEIGHT,
1119 * L_SELECT_IF_EITHER, L_SELECT_IF_BOTH)
1120 * relation (L_SELECT_IF_LT, L_SELECT_IF_GT,
1121 * L_SELECT_IF_LTE, L_SELECT_IF_GTE)
1122 * &changed (<optional return> 1 if changed; 0 if clone returned)
1123 * Return: boxad (filtered set), or null on error
1124 *
1125 * Notes:
1126 * (1) The args specify constraints on the size of the
1127 * components that are kept.
1128 * (2) Uses box clones in the new boxa.
1129 * (3) If the selection type is L_SELECT_WIDTH, the input
1130 * height is ignored, and v.v.
1131 * (4) To keep small components, use relation = L_SELECT_IF_LT or
1132 * L_SELECT_IF_LTE.
1133 * To keep large components, use relation = L_SELECT_IF_GT or
1134 * L_SELECT_IF_GTE.
1135 */
1136 BOXA *
boxaSelectBySize(BOXA * boxas,l_int32 width,l_int32 height,l_int32 type,l_int32 relation,l_int32 * pchanged)1137 boxaSelectBySize(BOXA *boxas,
1138 l_int32 width,
1139 l_int32 height,
1140 l_int32 type,
1141 l_int32 relation,
1142 l_int32 *pchanged)
1143 {
1144 BOXA *boxad;
1145 NUMA *na;
1146
1147 PROCNAME("boxaSelectBySize");
1148
1149 if (!boxas)
1150 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
1151 if (type != L_SELECT_WIDTH && type != L_SELECT_HEIGHT &&
1152 type != L_SELECT_IF_EITHER && type != L_SELECT_IF_BOTH)
1153 return (BOXA *)ERROR_PTR("invalid type", procName, NULL);
1154 if (relation != L_SELECT_IF_LT && relation != L_SELECT_IF_GT &&
1155 relation != L_SELECT_IF_LTE && relation != L_SELECT_IF_GTE)
1156 return (BOXA *)ERROR_PTR("invalid relation", procName, NULL);
1157 if (pchanged) *pchanged = FALSE;
1158
1159 /* Compute the indicator array for saving components */
1160 na = boxaMakeSizeIndicator(boxas, width, height, type, relation);
1161
1162 /* Filter to get output */
1163 boxad = boxaSelectWithIndicator(boxas, na, pchanged);
1164
1165 numaDestroy(&na);
1166 return boxad;
1167 }
1168
1169
1170 /*!
1171 * boxaMakeSizeIndicator()
1172 *
1173 * Input: boxa
1174 * width, height (threshold dimensions)
1175 * type (L_SELECT_WIDTH, L_SELECT_HEIGHT,
1176 * L_SELECT_IF_EITHER, L_SELECT_IF_BOTH)
1177 * relation (L_SELECT_IF_LT, L_SELECT_IF_GT,
1178 * L_SELECT_IF_LTE, L_SELECT_IF_GTE)
1179 * Return: na (indicator array), or null on error
1180 *
1181 * Notes:
1182 * (1) The args specify constraints on the size of the
1183 * components that are kept.
1184 * (2) If the selection type is L_SELECT_WIDTH, the input
1185 * height is ignored, and v.v.
1186 * (3) To keep small components, use relation = L_SELECT_IF_LT or
1187 * L_SELECT_IF_LTE.
1188 * To keep large components, use relation = L_SELECT_IF_GT or
1189 * L_SELECT_IF_GTE.
1190 */
1191 NUMA *
boxaMakeSizeIndicator(BOXA * boxa,l_int32 width,l_int32 height,l_int32 type,l_int32 relation)1192 boxaMakeSizeIndicator(BOXA *boxa,
1193 l_int32 width,
1194 l_int32 height,
1195 l_int32 type,
1196 l_int32 relation)
1197 {
1198 l_int32 i, n, w, h, ival;
1199 NUMA *na;
1200
1201 PROCNAME("boxaMakeSizeIndicator");
1202
1203 if (!boxa)
1204 return (NUMA *)ERROR_PTR("boxa not defined", procName, NULL);
1205 if (type != L_SELECT_WIDTH && type != L_SELECT_HEIGHT &&
1206 type != L_SELECT_IF_EITHER && type != L_SELECT_IF_BOTH)
1207 return (NUMA *)ERROR_PTR("invalid type", procName, NULL);
1208 if (relation != L_SELECT_IF_LT && relation != L_SELECT_IF_GT &&
1209 relation != L_SELECT_IF_LTE && relation != L_SELECT_IF_GTE)
1210 return (NUMA *)ERROR_PTR("invalid relation", procName, NULL);
1211
1212 n = boxaGetCount(boxa);
1213 na = numaCreate(n);
1214 for (i = 0; i < n; i++) {
1215 ival = 0;
1216 boxaGetBoxGeometry(boxa, i, NULL, NULL, &w, &h);
1217 switch (type)
1218 {
1219 case L_SELECT_WIDTH:
1220 if ((relation == L_SELECT_IF_LT && w < width) ||
1221 (relation == L_SELECT_IF_GT && w > width) ||
1222 (relation == L_SELECT_IF_LTE && w <= width) ||
1223 (relation == L_SELECT_IF_GTE && w >= width))
1224 ival = 1;
1225 break;
1226 case L_SELECT_HEIGHT:
1227 if ((relation == L_SELECT_IF_LT && h < height) ||
1228 (relation == L_SELECT_IF_GT && h > height) ||
1229 (relation == L_SELECT_IF_LTE && h <= height) ||
1230 (relation == L_SELECT_IF_GTE && h >= height))
1231 ival = 1;
1232 break;
1233 case L_SELECT_IF_EITHER:
1234 if (((relation == L_SELECT_IF_LT) && (w < width || h < height)) ||
1235 ((relation == L_SELECT_IF_GT) && (w > width || h > height)) ||
1236 ((relation == L_SELECT_IF_LTE) && (w <= width || h <= height)) ||
1237 ((relation == L_SELECT_IF_GTE) && (w >= width || h >= height)))
1238 ival = 1;
1239 break;
1240 case L_SELECT_IF_BOTH:
1241 if (((relation == L_SELECT_IF_LT) && (w < width && h < height)) ||
1242 ((relation == L_SELECT_IF_GT) && (w > width && h > height)) ||
1243 ((relation == L_SELECT_IF_LTE) && (w <= width && h <= height)) ||
1244 ((relation == L_SELECT_IF_GTE) && (w >= width && h >= height)))
1245 ival = 1;
1246 break;
1247 default:
1248 L_WARNING("can't get here!", procName);
1249 }
1250 numaAddNumber(na, ival);
1251 }
1252
1253 return na;
1254 }
1255
1256
1257 /*!
1258 * boxaSelectWithIndicator()
1259 *
1260 * Input: boxas
1261 * na (indicator numa)
1262 * &changed (<optional return> 1 if changed; 0 if clone returned)
1263 * Return: boxad, or null on error
1264 *
1265 * Notes:
1266 * (1) Returns a boxa clone if no components are removed.
1267 * (2) Uses box clones in the new boxa.
1268 * (3) The indicator numa has values 0 (ignore) and 1 (accept).
1269 */
1270 BOXA *
boxaSelectWithIndicator(BOXA * boxas,NUMA * na,l_int32 * pchanged)1271 boxaSelectWithIndicator(BOXA *boxas,
1272 NUMA *na,
1273 l_int32 *pchanged)
1274 {
1275 l_int32 i, n, ival, nsave;
1276 BOX *box;
1277 BOXA *boxad;
1278
1279 PROCNAME("boxaSelectWithIndicator");
1280
1281 if (!boxas)
1282 return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
1283 if (!na)
1284 return (BOXA *)ERROR_PTR("na not defined", procName, NULL);
1285
1286 nsave = 0;
1287 n = numaGetCount(na);
1288 for (i = 0; i < n; i++) {
1289 numaGetIValue(na, i, &ival);
1290 if (ival == 1) nsave++;
1291 }
1292
1293 if (nsave == n) {
1294 if (pchanged) *pchanged = FALSE;
1295 return boxaCopy(boxas, L_CLONE);
1296 }
1297 if (pchanged) *pchanged = TRUE;
1298 boxad = boxaCreate(nsave);
1299 for (i = 0; i < n; i++) {
1300 numaGetIValue(na, i, &ival);
1301 if (ival == 0) continue;
1302 box = boxaGetBox(boxas, i, L_CLONE);
1303 boxaAddBox(boxad, box, L_INSERT);
1304 }
1305
1306 return boxad;
1307 }
1308
1309
1310 /*!
1311 * boxaPermutePseudorandom()
1312 *
1313 * Input: boxas (input boxa)
1314 * Return: boxad (with boxes permuted), or null on error
1315 *
1316 * Notes:
1317 * (1) This does a pseudorandom in-place permutation of the boxes.
1318 * (2) The result is guaranteed not to have any boxes in their
1319 * original position, but it is not very random. If you
1320 * need randomness, use boxaPermuteRandom().
1321 */
1322 BOXA *
boxaPermutePseudorandom(BOXA * boxas)1323 boxaPermutePseudorandom(BOXA *boxas)
1324 {
1325 l_int32 n;
1326 NUMA *na;
1327 BOXA *boxad;
1328
1329 PROCNAME("boxaPermutePseudorandom");
1330
1331 if (!boxas)
1332 return (BOXA *)ERROR_PTR("boxa not defined", procName, NULL);
1333
1334 n = boxaGetCount(boxas);
1335 na = numaPseudorandomSequence(n, 0);
1336 boxad = boxaSortByIndex(boxas, na);
1337 numaDestroy(&na);
1338 return boxad;
1339 }
1340
1341
1342 /*!
1343 * boxaPermuteRandom()
1344 *
1345 * Input: boxad (<optional> can be null or equal to boxas)
1346 * boxas (input boxa)
1347 * Return: boxad (with boxes permuted), or null on error
1348 *
1349 * Notes:
1350 * (1) If boxad is null, make a copy of boxas and permute the copy.
1351 * Otherwise, boxad must be equal to boxas, and the operation
1352 * is done in-place.
1353 * (2) This does a random in-place permutation of the boxes,
1354 * by swapping each box in turn with a random box. The
1355 * result is almost guaranteed not to have any boxes in their
1356 * original position.
1357 * (3) MSVC rand() has MAX_RAND = 2^15 - 1, so it will not do
1358 * a proper permutation is the number of boxes exceeds this.
1359 */
1360 BOXA *
boxaPermuteRandom(BOXA * boxad,BOXA * boxas)1361 boxaPermuteRandom(BOXA *boxad,
1362 BOXA *boxas)
1363 {
1364 l_int32 i, n, index;
1365
1366 PROCNAME("boxaPermuteRandom");
1367
1368 if (!boxas)
1369 return (BOXA *)ERROR_PTR("boxa not defined", procName, NULL);
1370 if (boxad && (boxad != boxas))
1371 return (BOXA *)ERROR_PTR("boxad defined but in-place", procName, NULL);
1372
1373 if (!boxad)
1374 boxad = boxaCopy(boxas, L_COPY);
1375 n = boxaGetCount(boxad);
1376 index = (l_uint32)rand() % n;
1377 index = L_MAX(1, index);
1378 boxaSwapBoxes(boxad, 0, index);
1379 for (i = 1; i < n; i++) {
1380 index = (l_uint32)rand() % n;
1381 if (index == i) index--;
1382 boxaSwapBoxes(boxad, i, index);
1383 }
1384
1385 return boxad;
1386 }
1387
1388
1389 /*!
1390 * boxaSwapBoxes()
1391 *
1392 * Input: boxa
1393 * i, j (two indices of boxes, that are to be swapped)
1394 * Return: 0 if OK, 1 on error
1395 */
1396 l_int32
boxaSwapBoxes(BOXA * boxa,l_int32 i,l_int32 j)1397 boxaSwapBoxes(BOXA *boxa,
1398 l_int32 i,
1399 l_int32 j)
1400 {
1401 l_int32 n;
1402 BOX *box;
1403
1404 PROCNAME("boxaSwapBoxes");
1405
1406 if (!boxa)
1407 return ERROR_INT("boxa not defined", procName, 1);
1408 n = boxaGetCount(boxa);
1409 if (i < 0 || i >= n)
1410 return ERROR_INT("i invalid", procName, 1);
1411 if (j < 0 || j >= n)
1412 return ERROR_INT("j invalid", procName, 1);
1413 if (i == j)
1414 return ERROR_INT("i == j", procName, 1);
1415
1416 box = boxa->box[i];
1417 boxa->box[i] = boxa->box[j];
1418 boxa->box[j] = box;
1419 return 0;
1420 }
1421
1422
1423 /*!
1424 * boxaConvertToPta()
1425 *
1426 * Input: boxa
1427 * ncorners (2 or 4 for the representation of each box)
1428 * Return: pta (with @ncorners points for each box in the boxa),
1429 * or null on error
1430 *
1431 * Notes:
1432 * (1) If ncorners == 2, we select the UL and LR corners.
1433 * Otherwise we save all 4 corners in this order: UL, UR, LL, LR.
1434 */
1435 PTA *
boxaConvertToPta(BOXA * boxa,l_int32 ncorners)1436 boxaConvertToPta(BOXA *boxa,
1437 l_int32 ncorners)
1438 {
1439 l_int32 i, n, x, y, w, h;
1440 PTA *pta;
1441
1442 PROCNAME("boxaConvertToPta");
1443
1444 if (!boxa)
1445 return (PTA *)ERROR_PTR("boxa not defined", procName, NULL);
1446 if (ncorners != 2 && ncorners != 4)
1447 return (PTA *)ERROR_PTR("ncorners not 2 or 4", procName, NULL);
1448
1449 n = boxaGetCount(boxa);
1450 if ((pta = ptaCreate(n)) == NULL)
1451 return (PTA *)ERROR_PTR("pta not made", procName, NULL);
1452 for (i = 0; i < n; i++) {
1453 boxaGetBoxGeometry(boxa, i, &x, &y, &w, &h);
1454 ptaAddPt(pta, x, y);
1455 if (ncorners == 2)
1456 ptaAddPt(pta, x + w - 1, y + h - 1);
1457 else {
1458 ptaAddPt(pta, x + w - 1, y);
1459 ptaAddPt(pta, x, y + h - 1);
1460 ptaAddPt(pta, x + w - 1, y + h - 1);
1461 }
1462 }
1463
1464 return pta;
1465 }
1466
1467
1468 /*!
1469 * ptaConvertToBoxa()
1470 *
1471 * Input: pta
1472 * ncorners (2 or 4 for the representation of each box)
1473 * Return: boxa (with one box for each 2 or 4 points in the pta),
1474 * or null on error
1475 *
1476 * Notes:
1477 * (1) For 2 corners, the order of the 2 points is UL, LR.
1478 * For 4 corners, the order of points is UL, UR, LL, LR.
1479 * (2) Each derived box is the minimum szie containing all corners.
1480 */
1481 BOXA *
ptaConvertToBoxa(PTA * pta,l_int32 ncorners)1482 ptaConvertToBoxa(PTA *pta,
1483 l_int32 ncorners)
1484 {
1485 l_int32 i, n, nbox, x1, y1, x2, y2, x3, y3, x4, y4, x, y, xmax, ymax;
1486 BOX *box;
1487 BOXA *boxa;
1488
1489 PROCNAME("ptaConvertToBoxa");
1490
1491 if (!pta)
1492 return (BOXA *)ERROR_PTR("pta not defined", procName, NULL);
1493 if (ncorners != 2 && ncorners != 4)
1494 return (BOXA *)ERROR_PTR("ncorners not 2 or 4", procName, NULL);
1495 n = ptaGetCount(pta);
1496 if (n % ncorners != 0)
1497 return (BOXA *)ERROR_PTR("size % ncorners != 0", procName, NULL);
1498 nbox = n / ncorners;
1499 if ((boxa = boxaCreate(nbox)) == NULL)
1500 return (BOXA *)ERROR_PTR("boxa not made", procName, NULL);
1501 for (i = 0; i < n; i += ncorners) {
1502 ptaGetIPt(pta, i, &x1, &y1);
1503 ptaGetIPt(pta, i + 1, &x2, &y2);
1504 if (ncorners == 2) {
1505 box = boxCreate(x1, y1, x2 - x1 + 1, y2 - y1 + 1);
1506 boxaAddBox(boxa, box, L_INSERT);
1507 continue;
1508 }
1509 ptaGetIPt(pta, i + 2, &x3, &y3);
1510 ptaGetIPt(pta, i + 3, &x4, &y4);
1511 x = L_MIN(x1, x3);
1512 y = L_MIN(y1, y2);
1513 xmax = L_MAX(x2, x4);
1514 ymax = L_MAX(y3, y4);
1515 box = boxCreate(x, y, xmax - x + 1, ymax - y + 1);
1516 boxaAddBox(boxa, box, L_INSERT);
1517 }
1518
1519 return boxa;
1520 }
1521
1522
1523