Coverage Report

Created: 2025-06-13 07:02

/src/leptonica/src/ccbord.c
Line
Count
Source (jump to first uncovered line)
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
27
28
/*!
29
 * \file ccbord.c
30
 * <pre>
31
 *
32
 *     CCBORDA and CCBORD creation and destruction
33
 *         static CCBORDA  *ccbaCreate()
34
 *         void            *ccbaDestroy()
35
 *         static CCBORD   *ccbCreate()
36
 *         static void      ccbDestroy()
37
 *
38
 *     CCBORDA addition
39
 *         static l_int32   ccbaAddCcb()
40
 *         static l_int32   ccbaExtendArray()
41
 *
42
 *     CCBORDA accessors
43
 *         static l_int32   ccbaGetCount()
44
 *         static l_int32   ccbaGetCcb()
45
 *
46
 *     Top-level border-finding routines
47
 *         CCBORDA         *pixGetAllCCBorders()
48
 *         static CCBORD   *pixGetCCBorders()
49
 *         PTAA            *pixGetOuterBordersPtaa()
50
 *         static PTA      *pixGetOuterBorderPta()
51
 *
52
 *     Lower-level border location routines
53
 *         PTAA            *pixGetOuterBorder()
54
 *         static l_int32   pixGetHoleBorder()
55
 *         static l_int32   findNextBorderPixel()
56
 *         static void      locateOutsideSeedPixel()
57
 *
58
 *     Border conversions
59
 *         l_int32          ccbaGenerateGlobalLocs()
60
 *         l_int32          ccbaGenerateStepChains()
61
 *         l_int32          ccbaStepChainsToPixCoords()
62
 *         l_int32          ccbaGenerateSPGlobalLocs()
63
 *
64
 *     Conversion to single path
65
 *         l_int32          ccbaGenerateSinglePath()
66
 *         static PTA      *getCutPathForHole()
67
 *
68
 *     Border and full image rendering
69
 *         PIX             *ccbaDisplayBorder()
70
 *         PIX             *ccbaDisplaySPBorder()
71
 *         PIX             *ccbaDisplayImage1()
72
 *         PIX             *ccbaDisplayImage2()
73
 *
74
 *     Serialize for I/O
75
 *         l_int32          ccbaWrite()
76
 *         l_int32          ccbaWriteStream()
77
 *         l_int32          ccbaRead()
78
 *         l_int32          ccbaReadStream()
79
 *
80
 *     SVG output
81
 *         l_int32          ccbaWriteSVG()
82
 *         char            *ccbaWriteSVGString()
83
 *
84
 *
85
 *     Border finding is tricky because components can have
86
 *     holes, which also need to be traced out.  The outer
87
 *     border can be connected with all the hole borders,
88
 *     so that there is a single border for each component.
89
 *     [Alternatively, the connecting paths can be eliminated if
90
 *     you're willing to have a set of borders for each
91
 *     component (an exterior border and some number of
92
 *     interior ones), with "line to" operations tracing
93
 *     out each border and "move to" operations going from
94
 *     one border to the next.]
95
 *
96
 *     Here's the plan.  We get the pix for each connected
97
 *     component, and trace its exterior border.  We then
98
 *     find the holes (if any) in the pix, and separately
99
 *     trace out their borders, all using the same
100
 *     border-following rule that has ON pixels on the right
101
 *     side of the path.
102
 *
103
 *     [For svg, we may want to turn each set of borders for a c.c.
104
 *     into a closed path.  This can be done by tunnelling
105
 *     through the component from the outer border to each of the
106
 *     holes, going in and coming out along the same path so
107
 *     the connection will be invisible in any rendering
108
 *     (display or print) from the outline.  The result is a
109
 *     closed path, where the outside border is traversed
110
 *     cw and each hole is traversed ccw.  The svg renderer
111
 *     is assumed to handle these closed borders properly.]
112
 *
113
 *     Each border is a closed path that is traversed in such
114
 *     a way that the stuff inside the c.c. is on the right
115
 *     side of the traveller.  The border of a singly-connected
116
 *     component is thus traversed cw, and the border of the
117
 *     holes inside a c.c. are traversed ccw.  Suppose we have
118
 *     a list of all the borders of each c.c., both the cw and ccw
119
 *     traversals.  How do we reconstruct the image?
120
 *
121
 *   Reconstruction:
122
 *
123
 *     Method 1.  Topological method using connected components.
124
 *     We have closed borders composed of cw border pixels for the
125
 *     exterior of c.c. and ccw border pixels for the interior (holes)
126
 *     in the c.c.
127
 *         (a) Initialize the destination to be OFF.  Then,
128
 *             in any order:
129
 *         (b) Fill the components within and including the cw borders,
130
 *             and sequentially XOR them onto the destination.
131
 *         (c) Fill the components within but not including the ccw
132
 *             borders and sequentially XOR them onto the destination.
133
 *     The components that are XOR'd together can be generated as follows:
134
 *         (a) For each closed cw path, use pixFillClosedBorders():
135
 *               (1) Turn on the path pixels in a subimage that
136
 *                   minimally supports the border.
137
 *               (2) Do a 4-connected fill from a seed of 1 pixel width
138
 *                   on the border, using the inverted image in (1) as
139
 *                   a filling mask.
140
 *               (3) Invert the fill result: this gives the component
141
 *                   including the exterior cw path, with all holes
142
 *                   filled.
143
 *         (b) For each closed ccw path (hole):
144
 *               (1) Turn on the path pixels in a subimage that minimally
145
 *                   supports the path.
146
 *               (2) Find a seed pixel on the inside of this path.
147
 *               (3) Do a 4-connected fill from this seed pixel, using
148
 *                   the inverted image of the path in (1) as a filling
149
 *                   mask.
150
 *
151
 *     ------------------------------------------------------
152
 *
153
 *     Method 2.  A variant of Method 1.  Topological.
154
 *     In Method 1, we treat the exterior border differently from
155
 *     the interior (hole) borders.  Here, all borders in a c.c.
156
 *     are treated equally:
157
 *         (1) Start with a pix with a 1 pixel OFF boundary
158
 *             enclosing all the border pixels of the c.c.
159
 *             This is the filling mask.
160
 *         (2) Make a seed image of the same size as follows:  for
161
 *             each border, put one seed pixel OUTSIDE the border
162
 *             (where OUTSIDE is determined by the inside/outside
163
 *             convention for borders).
164
 *         (3) Seedfill into the seed image, filling in the regions
165
 *             determined by the filling mask.  The fills are clipped
166
 *             by the border pixels.
167
 *         (4) Inverting this, we get the c.c. properly filled,
168
 *             with the holes empty!
169
 *         (5) Rasterop using XOR the filled c.c. (but not the 1
170
 *             pixel boundary) into the full dest image.
171
 *
172
 *     Method 2 is about 1.2x faster than Method 1 on text images,
173
 *     and about 2x faster on complex images (e.g., with halftones).
174
 *
175
 *     ------------------------------------------------------
176
 *
177
 *     Method 3.  The traditional way to fill components delineated
178
 *     by boundaries is through scan line conversion.  It's a bit
179
 *     tricky, and I have not yet tried to implement it.
180
 *
181
 *     ------------------------------------------------------
182
 *
183
 *     Method 4.  [Nota Bene: this method probably doesn't work, and
184
 *     won't be implemented.  If I get a more traditional scan line
185
 *     conversion algorithm working, I'll erase these notes.]
186
 *     Render all border pixels on a destination image,
187
 *     which will be the final result after scan conversion.  Assign
188
 *     a value 1 to pixels on cw paths, 2 to pixels on ccw paths,
189
 *     and 3 to pixels that are on both paths.  Each of the paths
190
 *     is an 8-connected component.  Now scan across each raster
191
 *     line.  The attempt is to make rules for each scan line
192
 *     that are independent of neighboring scanlines.  Here are
193
 *     a set of rules for writing ON pixels on a destination raster image:
194
 *
195
 *         (a) The rasterizer will be in one of two states: ON and OFF.
196
 *         (b) Start each line in the OFF state.  In the OFF state,
197
 *             skip pixels until you hit a path of any type.  Turn
198
 *             the path pixel ON.
199
 *         (c) If the state is ON, each pixel you encounter will
200
 *             be turned on, until and including hitting a path pixel.
201
 *         (d) When you hit a path pixel, if the path does NOT cut
202
 *             through the line, so that there is not an 8-cc path
203
 *             pixel (of any type) both above and below, the state
204
 *             is unchanged (it stays either ON or OFF).
205
 *         (e) If the path does cut through, but with a possible change
206
 *             of pixel type, then we decide whether or
207
 *             not to toggle the state based on the values of the
208
 *             path pixel and the path pixels above and below:
209
 *               (1) if a 1 path cuts through, toggle;
210
 *               (1) if a 2 path cuts through, toggle;
211
 *               (3) if a 3 path cuts through, do not toggle;
212
 *               (4) if on one side a 3 touches both a 1 and a 2, use the 2
213
 *               (5) if a 3 has any 1 neighbors, toggle; else if it has
214
 *                   no 1 neighbors, do not toggle;
215
 *               (6) if a 2 has any neighbors that are 1 or 3,
216
 *                   do not toggle
217
 *               (7) if a 1 has neighbors 1 and x (x = 2 or 3),
218
 *                   toggle
219
 *
220
 *
221
 *     To visualize how these rules work, consider the following
222
 *     component with border pixels labeled according to the scheme
223
 *     above.  We also show the values of the interior pixels
224
 *     (w=OFF, b=ON), but these of course must be inferred properly
225
 *     from the rules above:
226
 *
227
 *                     3
228
 *                  3  w  3             1  1  1
229
 *                  1  2  1          1  b  2  b  1
230
 *                  1  b  1             3  w  2  1
231
 *                  3  b  1          1  b  2  b  1
232
 *               3  w  3                1  1  1
233
 *               3  w  3
234
 *            1  b  2  b  1
235
 *            1  2  w  2  1
236
 *         1  b  2  w  2  b  1
237
 *            1  2  w  2  1
238
 *               1  2  b  1
239
 *               1  b  1
240
 *                  1
241
 *
242
 *
243
 *     Even if this works, which is unlikely, it will certainly be
244
 *     slow because decisions have to be made on a pixel-by-pixel
245
 *     basis when encountering borders.
246
 *
247
 * </pre>
248
 */
249
250
#ifdef HAVE_CONFIG_H
251
#include <config_auto.h>
252
#endif  /* HAVE_CONFIG_H */
253
254
#include <string.h>
255
#include "allheaders.h"
256
#include "pix_internal.h"
257
#include "ccbord_internal.h"
258
259
static const l_int32  INITIAL_PTR_ARRAYSIZE = 20;    /* n'import quoi */
260
261
    /* In ccbaGenerateSinglePath(): don't save holes
262
     * in c.c. with ridiculously many small holes   */
263
static const l_int32  NMAX_HOLES = 150;
264
265
    /*  Tables used to trace the border.
266
     *   - The 8 pixel positions of neighbors Q are labeled clockwise
267
     *     starting from the west:
268
     *                  1   2   3
269
     *                  0   P   4
270
     *                  7   6   5
271
     *     where the labels are the index offset [0, ... 7] of Q relative to P.
272
     *   - xpostab[] and ypostab[] give the actual x and y pixel offsets
273
     *     of Q relative to P, indexed by the index offset.
274
     *   - qpostab[pos] gives the new index offset of Q relative to P, at
275
     *     the time that a new P has been chosen to be in index offset
276
     *     position 'pos' relative to the previous P.   The relation
277
     *     between P and Q is always 4-connected.  */
278
static const l_int32   xpostab[] = {-1, -1, 0, 1, 1, 1, 0, -1};
279
static const l_int32   ypostab[] = {0, -1, -1, -1, 0, 1, 1, 1};
280
static const l_int32   qpostab[] = {6, 6, 0, 0, 2, 2, 4, 4};
281
282
    /* Static functions */
283
static CCBORDA *ccbaCreate(PIX *pixs, l_int32 n);
284
static CCBORD *ccbCreate(PIX *pixs);
285
static void ccbDestroy(CCBORD **pccb);
286
static l_ok ccbaAddCcb(CCBORDA *ccba, CCBORD  *ccb);
287
static l_int32 ccbaExtendArray(CCBORDA *ccba);
288
static l_int32 ccbaGetCount(CCBORDA *ccba);
289
static CCBORD *ccbaGetCcb(CCBORDA *ccba, l_int32 index);
290
static CCBORD *pixGetCCBorders(PIX *pixs, BOX *box);
291
static PTA *pixGetOuterBorderPta(PIX *pixs, BOX *box);
292
static l_ok pixGetHoleBorder(CCBORD *ccb, PIX *pixs, BOX *box,
293
                             l_int32 xs, l_int32 ys);
294
static l_int32 findNextBorderPixel(l_int32 w, l_int32 h, l_uint32 *data,
295
                                   l_int32 wpl, l_int32 px, l_int32 py,
296
                                   l_int32 *pqpos, l_int32 *pnpx,
297
                                   l_int32 *pnpy);
298
static void locateOutsideSeedPixel(l_int32 fpx, l_int32 fpy, l_int32 spx,
299
                                   l_int32 spy, l_int32 *pxs, l_int32 *pys);
300
static PTA *getCutPathForHole(PIX *pix, PTA *pta, BOX *boxinner, l_int32 *pdir,
301
                              l_int32 *plen);
302
303
#ifndef  NO_CONSOLE_IO
304
#define  DEBUG_PRINT   0
305
#endif   /* NO CONSOLE_IO */
306
307
308
/*---------------------------------------------------------------------*
309
 *                   ccba and ccb creation and destruction             *
310
 *---------------------------------------------------------------------*/
311
/*!
312
 * \brief    ccbaCreate()
313
 *
314
 * \param[in]    pixs    1 bpp; can be null
315
 * \param[in]    n       initial number of ptrs
316
 * \return  ccba, or NULL on error
317
 */
318
static CCBORDA *
319
ccbaCreate(PIX     *pixs,
320
           l_int32  n)
321
0
{
322
0
CCBORDA  *ccba;
323
324
0
    if (n <= 0)
325
0
        n = INITIAL_PTR_ARRAYSIZE;
326
327
0
    ccba = (CCBORDA *)LEPT_CALLOC(1, sizeof(CCBORDA));
328
0
    if (pixs) {
329
0
        ccba->pix = pixClone(pixs);
330
0
        ccba->w = pixGetWidth(pixs);
331
0
        ccba->h = pixGetHeight(pixs);
332
0
    }
333
0
    ccba->n = 0;
334
0
    ccba->nalloc = n;
335
0
    if ((ccba->ccb = (CCBORD **)LEPT_CALLOC(n, sizeof(CCBORD *))) == NULL) {
336
0
        ccbaDestroy(&ccba);
337
0
        return (CCBORDA *)ERROR_PTR("ccba ptrs not made", __func__, NULL);
338
0
    }
339
0
    return ccba;
340
0
}
341
342
343
/*!
344
 * \brief   ccbaDestroy()
345
 *
346
 * \param[in,out]   pccba     will be set to null befoe returning
347
 * \return  void
348
 */
349
void
350
ccbaDestroy(CCBORDA  **pccba)
351
0
{
352
0
l_int32   i;
353
0
CCBORDA  *ccba;
354
355
0
    if (pccba == NULL) {
356
0
        L_WARNING("ptr address is NULL!\n", __func__);
357
0
        return;
358
0
    }
359
360
0
    if ((ccba = *pccba) == NULL)
361
0
        return;
362
363
0
    pixDestroy(&ccba->pix);
364
0
    for (i = 0; i < ccba->n; i++)
365
0
        ccbDestroy(&ccba->ccb[i]);
366
0
    LEPT_FREE(ccba->ccb);
367
0
    LEPT_FREE(ccba);
368
0
    *pccba = NULL;
369
0
}
370
371
372
/*!
373
 * \brief   ccbCreate()
374
 *
375
 * \param[in]    pixs    [optional]; can be null
376
 * \return  ccb or NULL on error
377
 */
378
static CCBORD *
379
ccbCreate(PIX  *pixs)
380
0
{
381
0
BOXA    *boxa;
382
0
CCBORD  *ccb;
383
0
PTA     *start;
384
0
PTAA    *local;
385
386
0
    if (pixs && pixGetDepth(pixs) != 1)  /* pixs can be null */
387
0
        return (CCBORD *)ERROR_PTR("pixs defined and not 1bpp", __func__, NULL);
388
389
0
    ccb = (CCBORD *)LEPT_CALLOC(1, sizeof(CCBORD));
390
0
    ccb->refcount = 1;
391
0
    if (pixs)
392
0
        ccb->pix = pixClone(pixs);
393
0
    boxa = boxaCreate(1);
394
0
    ccb->boxa = boxa;
395
0
    start = ptaCreate(1);
396
0
    ccb->start = start;
397
0
    local = ptaaCreate(1);
398
0
    ccb->local = local;
399
0
    return ccb;
400
0
}
401
402
403
/*!
404
 * \brief   ccbDestroy()
405
 *
406
 * \param[in,out]   pccb    will be set to null before returning
407
 * \return  void
408
 */
409
static void
410
ccbDestroy(CCBORD  **pccb)
411
0
{
412
0
CCBORD  *ccb;
413
414
0
    if (pccb == NULL) {
415
0
        L_WARNING("ptr address is NULL!\n", __func__);
416
0
        return;
417
0
    }
418
419
0
    if ((ccb = *pccb) == NULL)
420
0
        return;
421
422
0
    if (--ccb->refcount == 0) {
423
0
        if (ccb->pix)
424
0
            pixDestroy(&ccb->pix);
425
0
        if (ccb->boxa)
426
0
            boxaDestroy(&ccb->boxa);
427
0
        if (ccb->start)
428
0
            ptaDestroy(&ccb->start);
429
0
        if (ccb->local)
430
0
            ptaaDestroy(&ccb->local);
431
0
        if (ccb->global)
432
0
            ptaaDestroy(&ccb->global);
433
0
        if (ccb->step)
434
0
            numaaDestroy(&ccb->step);
435
0
        if (ccb->splocal)
436
0
            ptaDestroy(&ccb->splocal);
437
0
        if (ccb->spglobal)
438
0
            ptaDestroy(&ccb->spglobal);
439
0
        LEPT_FREE(ccb);
440
0
        *pccb = NULL;
441
0
    }
442
0
}
443
444
445
/*---------------------------------------------------------------------*
446
 *                            ccba addition                            *
447
 *---------------------------------------------------------------------*/
448
/*!
449
 * \brief   ccbaAddCcb()
450
 *
451
 * \param[in]    ccba
452
 * \param[in]    ccb     to be added by insertion
453
 * \return  0 if OK; 1 on error
454
 */
455
static l_ok
456
ccbaAddCcb(CCBORDA  *ccba,
457
           CCBORD   *ccb)
458
0
{
459
0
l_int32  n;
460
461
0
    if (!ccba)
462
0
        return ERROR_INT("ccba not defined", __func__, 1);
463
0
    if (!ccb)
464
0
        return ERROR_INT("ccb not defined", __func__, 1);
465
466
0
    n = ccbaGetCount(ccba);
467
0
    if (n >= ccba->nalloc) {
468
0
        if (ccbaExtendArray(ccba))
469
0
            return ERROR_INT("extension failed", __func__, 1);
470
0
    }
471
0
    ccba->ccb[n] = ccb;
472
0
    ccba->n++;
473
0
    return 0;
474
0
}
475
476
477
/*!
478
 * \brief   ccbaExtendArray()
479
 *
480
 * \param[in]    ccba
481
 * \return  0 if OK; 1 on error
482
 */
483
static l_int32
484
ccbaExtendArray(CCBORDA  *ccba)
485
0
{
486
0
    if (!ccba)
487
0
        return ERROR_INT("ccba not defined", __func__, 1);
488
489
0
    if ((ccba->ccb = (CCBORD **)reallocNew((void **)&ccba->ccb,
490
0
                                sizeof(CCBORD *) * ccba->nalloc,
491
0
                                2 * sizeof(CCBORD *) * ccba->nalloc)) == NULL)
492
0
        return ERROR_INT("new ptr array not returned", __func__, 1);
493
494
0
    ccba->nalloc = 2 * ccba->nalloc;
495
0
    return 0;
496
0
}
497
498
499
500
/*---------------------------------------------------------------------*
501
 *                            ccba accessors                           *
502
 *---------------------------------------------------------------------*/
503
/*!
504
 * \brief   ccbaGetCount()
505
 *
506
 * \param[in]    ccba
507
 * \return  count, with 0 on error
508
 */
509
static l_int32
510
ccbaGetCount(CCBORDA  *ccba)
511
0
{
512
513
0
    if (!ccba)
514
0
        return ERROR_INT("ccba not defined", __func__, 0);
515
516
0
    return ccba->n;
517
0
}
518
519
520
/*!
521
 * \brief   ccbaGetCcb()
522
 *
523
 * \param[in]    ccba
524
 * \param[in]    index
525
 * \return  ccb, or NULL on error
526
 *
527
 * <pre>
528
 * Notes:
529
 *      (1) This returns a clone of the ccb; it must be destroyed
530
 * </pre>
531
 */
532
static CCBORD *
533
ccbaGetCcb(CCBORDA  *ccba,
534
           l_int32   index)
535
0
{
536
0
CCBORD  *ccb;
537
538
0
    if (!ccba)
539
0
        return (CCBORD *)ERROR_PTR("ccba not defined", __func__, NULL);
540
0
    if (index < 0 || index >= ccba->n)
541
0
        return (CCBORD *)ERROR_PTR("index out of bounds", __func__, NULL);
542
543
0
    ccb = ccba->ccb[index];
544
0
    ccb->refcount++;
545
0
    return ccb;
546
0
}
547
548
549
550
/*---------------------------------------------------------------------*
551
 *                   Top-level border-finding routines                 *
552
 *---------------------------------------------------------------------*/
553
/*!
554
 * \brief   pixGetAllCCBorders()
555
 *
556
 * \param[in]    pixs    1 bpp
557
 * \return  ccborda, or NULL on error
558
 */
559
CCBORDA *
560
pixGetAllCCBorders(PIX  *pixs)
561
0
{
562
0
l_int32   n, i;
563
0
BOX      *box;
564
0
BOXA     *boxa;
565
0
CCBORDA  *ccba;
566
0
CCBORD   *ccb;
567
0
PIX      *pix;
568
0
PIXA     *pixa;
569
570
0
    if (!pixs)
571
0
        return (CCBORDA *)ERROR_PTR("pixs not defined", __func__, NULL);
572
0
    if (pixGetDepth(pixs) != 1)
573
0
        return (CCBORDA *)ERROR_PTR("pixs not binary", __func__, NULL);
574
575
0
    if ((boxa = pixConnComp(pixs, &pixa, 8)) == NULL)
576
0
        return (CCBORDA *)ERROR_PTR("boxa not made", __func__, NULL);
577
0
    n = boxaGetCount(boxa);
578
579
0
    if ((ccba = ccbaCreate(pixs, n)) == NULL) {
580
0
        boxaDestroy(&boxa);
581
0
        pixaDestroy(&pixa);
582
0
        return (CCBORDA *)ERROR_PTR("ccba not made", __func__, NULL);
583
0
    }
584
0
    for (i = 0; i < n; i++) {
585
0
        if ((pix = pixaGetPix(pixa, i, L_CLONE)) == NULL) {
586
0
            ccbaDestroy(&ccba);
587
0
            pixaDestroy(&pixa);
588
0
            boxaDestroy(&boxa);
589
0
            return (CCBORDA *)ERROR_PTR("pix not found", __func__, NULL);
590
0
        }
591
0
        if ((box = pixaGetBox(pixa, i, L_CLONE)) == NULL) {
592
0
            ccbaDestroy(&ccba);
593
0
            pixaDestroy(&pixa);
594
0
            boxaDestroy(&boxa);
595
0
            pixDestroy(&pix);
596
0
            return (CCBORDA *)ERROR_PTR("box not found", __func__, NULL);
597
0
        }
598
0
        ccb = pixGetCCBorders(pix, box);
599
0
        pixDestroy(&pix);
600
0
        boxDestroy(&box);
601
0
        if (!ccb) {
602
0
            ccbaDestroy(&ccba);
603
0
            pixaDestroy(&pixa);
604
0
            boxaDestroy(&boxa);
605
0
            return (CCBORDA *)ERROR_PTR("ccb not made", __func__, NULL);
606
0
        }
607
/*        ptaWriteStream(stderr, ccb->local, 1); */
608
0
        ccbaAddCcb(ccba, ccb);
609
0
    }
610
611
0
    boxaDestroy(&boxa);
612
0
    pixaDestroy(&pixa);
613
0
    return ccba;
614
0
}
615
616
617
/*!
618
 * \brief   pixGetCCBorders()
619
 *
620
 * \param[in]    pixs     1 bpp, one 8-connected component
621
 * \param[in]    box      of %pixs, in global coords
622
 * \return  ccbord, or NULL on error
623
 *
624
 * <pre>
625
 * Notes:
626
 *      (1) We are finding the exterior and interior borders
627
 *          of an 8-connected component.   This should be used
628
 *          on a pix that has exactly one 8-connected component.
629
 *      (2) Typically, pixs is a c.c. in some larger pix.  The
630
 *          input box gives its location in global coordinates.
631
 *          This box is saved, as well as the boxes for the
632
 *          borders of any holes within the c.c., but the latter
633
 *          are given in relative coords within the c.c.
634
 *      (3) The calculations for the exterior border are done
635
 *          on a pix with a 1-pixel
636
 *          added border, but the saved pixel coordinates
637
 *          are the correct (relative) ones for the input pix
638
 *          (without a 1-pixel border)
639
 *      (4) For the definition of the three tables -- xpostab[], ypostab[]
640
 *          and qpostab[] -- see above where they are defined.
641
 * </pre>
642
 */
643
static CCBORD *
644
pixGetCCBorders(PIX      *pixs,
645
                BOX      *box)
646
0
{
647
0
l_int32   allzero, i, x, xh, w, nh;
648
0
l_int32   xs, ys;   /* starting hole border pixel, relative in pixs */
649
0
l_uint32  val;
650
0
BOX      *boxt, *boxe;
651
0
BOXA     *boxa;
652
0
CCBORD   *ccb;
653
0
PIX      *pixh;  /* for hole components */
654
0
PIX      *pixt;
655
0
PIXA     *pixa;
656
657
0
    if (!pixs)
658
0
        return (CCBORD *)ERROR_PTR("pixs not defined", __func__, NULL);
659
0
    if (!box)
660
0
        return (CCBORD *)ERROR_PTR("box not defined", __func__, NULL);
661
0
    if (pixGetDepth(pixs) != 1)
662
0
        return (CCBORD *)ERROR_PTR("pixs not binary", __func__, NULL);
663
664
0
    pixZero(pixs, &allzero);
665
0
    if (allzero)
666
0
        return (CCBORD *)ERROR_PTR("pixs all 0", __func__, NULL);
667
668
0
    if ((ccb = ccbCreate(pixs)) == NULL)
669
0
        return (CCBORD *)ERROR_PTR("ccb not made", __func__, NULL);
670
671
        /* Get the exterior border */
672
0
    pixGetOuterBorder(ccb, pixs, box);
673
674
        /* Find the holes, if any */
675
0
    if ((pixh = pixHolesByFilling(pixs, 4)) == NULL) {
676
0
        ccbDestroy(&ccb);
677
0
        return (CCBORD *)ERROR_PTR("pixh not made", __func__, NULL);
678
0
    }
679
0
    pixZero(pixh, &allzero);
680
0
    if (allzero) {  /* no holes */
681
0
        pixDestroy(&pixh);
682
0
        return ccb;
683
0
    }
684
685
        /* Get c.c. and locations of the holes */
686
0
    if ((boxa = pixConnComp(pixh, &pixa, 4)) == NULL) {
687
0
        ccbDestroy(&ccb);
688
0
        pixDestroy(&pixh);
689
0
        return (CCBORD *)ERROR_PTR("boxa not made", __func__, NULL);
690
0
    }
691
0
    nh = boxaGetCount(boxa);
692
/*    lept_stderr("%d holes\n", nh); */
693
694
        /* For each hole, find an interior pixel within the hole,
695
         * then march to the right and stop at the first border
696
         * pixel.  Save the bounding box of the border, which
697
         * is 1 pixel bigger on each side than the bounding box
698
         * of the hole itself.  Note that we use a pix of the
699
         * c.c. of the hole itself to be sure that we start
700
         * with a pixel in the hole of the proper component.
701
         * If we did everything from the parent component, it is
702
         * possible to start in a different hole that is within
703
         * the b.b. of a larger hole.  */
704
0
    w = pixGetWidth(pixs);
705
0
    for (i = 0; i < nh; i++) {
706
0
        boxt = boxaGetBox(boxa, i, L_CLONE);
707
0
        pixt = pixaGetPix(pixa, i, L_CLONE);
708
0
        ys = boxt->y;   /* there must be a hole pixel on this raster line */
709
0
        for (x = 0; x < boxt->w; x++) {  /* look for (fg) hole pixel */
710
0
            pixGetPixel(pixt, x, 0, &val);
711
0
            if (val == 1) {
712
0
                xh = x;
713
0
                break;
714
0
            }
715
0
        }
716
0
        if (x == boxt->w) {
717
0
            L_WARNING("no hole pixel found!\n", __func__);
718
0
            continue;
719
0
        }
720
0
        for (x = xh + boxt->x; x < w; x++) {  /* look for (fg) border pixel */
721
0
            pixGetPixel(pixs, x, ys, &val);
722
0
            if (val == 1) {
723
0
                xs = x;
724
0
                break;
725
0
            }
726
0
        }
727
0
        boxe = boxCreate(boxt->x - 1, boxt->y - 1, boxt->w + 2, boxt->h + 2);
728
#if  DEBUG_PRINT
729
        boxPrintStreamInfo(stderr, box);
730
        boxPrintStreamInfo(stderr, boxe);
731
        lept_stderr("xs = %d, ys = %d\n", xs, ys);
732
#endif   /* DEBUG_PRINT */
733
0
        pixGetHoleBorder(ccb, pixs, boxe, xs, ys);
734
0
        boxDestroy(&boxt);
735
0
        boxDestroy(&boxe);
736
0
        pixDestroy(&pixt);
737
0
    }
738
739
0
    boxaDestroy(&boxa);
740
0
    pixaDestroy(&pixa);
741
0
    pixDestroy(&pixh);
742
0
    return ccb;
743
0
}
744
745
746
/*!
747
 * \brief   pixGetOuterBordersPtaa()
748
 *
749
 * \param[in]    pixs     1 bpp
750
 * \return  ptaa of outer borders, in global coords, or NULL on error
751
 */
752
PTAA *
753
pixGetOuterBordersPtaa(PIX  *pixs)
754
0
{
755
0
l_int32  i, n;
756
0
BOX     *box;
757
0
BOXA    *boxa;
758
0
PIX     *pix;
759
0
PIXA    *pixa;
760
0
PTA     *pta;
761
0
PTAA    *ptaa;
762
763
0
    if (!pixs)
764
0
        return (PTAA *)ERROR_PTR("pixs not defined", __func__, NULL);
765
0
    if (pixGetDepth(pixs) != 1)
766
0
        return (PTAA *)ERROR_PTR("pixs not binary", __func__, NULL);
767
768
0
    boxa = pixConnComp(pixs, &pixa, 8);
769
0
    n = boxaGetCount(boxa);
770
0
    if (n == 0) {
771
0
        boxaDestroy(&boxa);
772
0
        pixaDestroy(&pixa);
773
0
        return (PTAA *)ERROR_PTR("pixs empty", __func__, NULL);
774
0
    }
775
776
0
    ptaa = ptaaCreate(n);
777
0
    for (i = 0; i < n; i++) {
778
0
        box = boxaGetBox(boxa, i, L_CLONE);
779
0
        pix = pixaGetPix(pixa, i, L_CLONE);
780
0
        pta = pixGetOuterBorderPta(pix, box);
781
0
        if (pta)
782
0
            ptaaAddPta(ptaa, pta, L_INSERT);
783
0
        boxDestroy(&box);
784
0
        pixDestroy(&pix);
785
0
    }
786
787
0
    pixaDestroy(&pixa);
788
0
    boxaDestroy(&boxa);
789
0
    return ptaa;
790
0
}
791
792
793
/*!
794
 * \brief   pixGetOuterBorderPta()
795
 *
796
 * \param[in]    pixs    1 bpp, one 8-connected component
797
 * \param[in]    box     [optional] of %pixs, in global coordinates
798
 * \return  pta of outer border, in global coords, or NULL on error
799
 *
800
 * <pre>
801
 * Notes:
802
 *      (1) We are finding the exterior border of a single 8-connected
803
 *          component.
804
 *      (2) If box is NULL, the outline returned is in the local coords
805
 *          of the input pix.  Otherwise, box is assumed to give the
806
 *          location of the pix in global coordinates, and the returned
807
 *          pta will be in those global coordinates.
808
 * </pre>
809
 */
810
static PTA *
811
pixGetOuterBorderPta(PIX  *pixs,
812
                     BOX  *box)
813
0
{
814
0
l_int32  allzero, x, y;
815
0
BOX     *boxt;
816
0
CCBORD  *ccb;
817
0
PTA     *ptaloc, *ptad;
818
819
0
    if (!pixs)
820
0
        return (PTA *)ERROR_PTR("pixs not defined", __func__, NULL);
821
0
    if (pixGetDepth(pixs) != 1)
822
0
        return (PTA *)ERROR_PTR("pixs not binary", __func__, NULL);
823
824
0
    pixZero(pixs, &allzero);
825
0
    if (allzero)
826
0
        return (PTA *)ERROR_PTR("pixs all 0", __func__, NULL);
827
828
0
    if ((ccb = ccbCreate(pixs)) == NULL)
829
0
        return (PTA *)ERROR_PTR("ccb not made", __func__, NULL);
830
0
    if (!box)
831
0
        boxt = boxCreate(0, 0, pixGetWidth(pixs), pixGetHeight(pixs));
832
0
    else
833
0
        boxt = boxClone(box);
834
835
        /* Get the exterior border in local coords */
836
0
    pixGetOuterBorder(ccb, pixs, boxt);
837
0
    if ((ptaloc = ptaaGetPta(ccb->local, 0, L_CLONE)) == NULL) {
838
0
        ccbDestroy(&ccb);
839
0
        boxDestroy(&boxt);
840
0
        return (PTA *)ERROR_PTR("ptaloc not made", __func__, NULL);
841
0
    }
842
843
        /* Transform to global coordinates, if they are given */
844
0
    if (box) {
845
0
        boxGetGeometry(box, &x, &y, NULL, NULL);
846
0
        ptad = ptaTransform(ptaloc, x, y, 1.0, 1.0);
847
0
    } else {
848
0
        ptad = ptaClone(ptaloc);
849
0
    }
850
851
0
    ptaDestroy(&ptaloc);
852
0
    boxDestroy(&boxt);
853
0
    ccbDestroy(&ccb);
854
0
    return ptad;
855
0
}
856
857
858
/*---------------------------------------------------------------------*
859
 *                   Lower-level border-finding routines               *
860
 *---------------------------------------------------------------------*/
861
/*!
862
 * \brief   pixGetOuterBorder()
863
 *
864
 * \param[in]    ccb     unfilled
865
 * \param[in]    pixs    for the component at hand
866
 * \param[in]    box     for the component, in global coords
867
 * \return  0 if OK, 1 on error
868
 *
869
 * <pre>
870
 * Notes:
871
 *      (1) the border is saved in relative coordinates within
872
 *          the c.c. (pixs).  Because the calculation is done
873
 *          in pixb with added 1 pixel border, we must subtract
874
 *          1 from each pixel value before storing it.
875
 *      (2) the stopping condition is that after the first pixel is
876
 *          returned to, the next pixel is the second pixel.  Having
877
 *          these 2 pixels recur in sequence proves the path is closed,
878
 *          and we do not store the second pixel again.
879
 * </pre>
880
 */
881
l_ok
882
pixGetOuterBorder(CCBORD   *ccb,
883
                  PIX      *pixs,
884
                  BOX      *box)
885
0
{
886
0
l_int32    fpx, fpy, spx, spy, qpos;
887
0
l_int32    px, py, npx, npy;
888
0
l_int32    w, h, wpl;
889
0
l_uint32  *data;
890
0
PTA       *pta;
891
0
PIX       *pixb;  /* with 1 pixel border */
892
893
0
    if (!ccb)
894
0
        return ERROR_INT("ccb not defined", __func__, 1);
895
0
    if (!pixs)
896
0
        return ERROR_INT("pixs not defined", __func__, 1);
897
0
    if (!box)
898
0
        return ERROR_INT("box not defined", __func__, 1);
899
900
        /* Add 1-pixel border all around, and find start pixel */
901
0
    if ((pixb = pixAddBorder(pixs, 1, 0)) == NULL)
902
0
        return ERROR_INT("pixs not made", __func__, 1);
903
0
    if (!nextOnPixelInRaster(pixb, 1, 1, &px, &py)) {
904
0
        pixDestroy(&pixb);
905
0
        return ERROR_INT("no start pixel found", __func__, 1);
906
0
    }
907
0
    qpos = 0;   /* relative to p */
908
0
    fpx = px;  /* save location of first pixel on border */
909
0
    fpy = py;
910
911
        /* Save box and start pixel in relative coords */
912
0
    boxaAddBox(ccb->boxa, box, L_COPY);
913
0
    ptaAddPt(ccb->start, px - 1, py - 1);
914
915
0
    pta = ptaCreate(0);
916
0
    ptaaAddPta(ccb->local, pta, L_INSERT);
917
0
    ptaAddPt(pta, px - 1, py - 1);   /* initial point */
918
0
    pixGetDimensions(pixb, &w, &h, NULL);
919
0
    data = pixGetData(pixb);
920
0
    wpl = pixGetWpl(pixb);
921
922
        /* Get the second point; if there is none, return */
923
0
    if (findNextBorderPixel(w, h, data, wpl, px, py, &qpos, &npx, &npy)) {
924
0
        pixDestroy(&pixb);
925
0
        return 0;
926
0
    }
927
928
0
    spx = npx;  /* save location of second pixel on border */
929
0
    spy = npy;
930
0
    ptaAddPt(pta, npx - 1, npy - 1);   /* second point */
931
0
    px = npx;
932
0
    py = npy;
933
934
0
    while (1) {
935
0
        findNextBorderPixel(w, h, data, wpl, px, py, &qpos, &npx, &npy);
936
0
        if (px == fpx && py == fpy && npx == spx && npy == spy)
937
0
            break;
938
0
        ptaAddPt(pta, npx - 1, npy - 1);
939
0
        px = npx;
940
0
        py = npy;
941
0
    }
942
943
0
    pixDestroy(&pixb);
944
0
    return 0;
945
0
}
946
947
948
/*!
949
 * \brief   pixGetHoleBorder()
950
 *
951
 * \param[in]    ccb      the exterior border is already made
952
 * \param[in]    pixs     for the connected component at hand
953
 * \param[in]    box      for the specific hole border, in relative
954
 *                        coordinates to the c.c.
955
 * \param[in]    xs, ys   first pixel on hole border, relative to c.c.
956
 * \return  0 if OK, 1 on error
957
 *
958
 * <pre>
959
 * Notes:
960
 *      (1) we trace out hole border on pixs without addition
961
 *          of single pixel added border to pixs
962
 *      (2) therefore all coordinates are relative within the c.c. (pixs)
963
 *      (3) same position tables and stopping condition as for
964
 *          exterior borders
965
 * </pre>
966
 */
967
static l_ok
968
pixGetHoleBorder(CCBORD   *ccb,
969
                 PIX      *pixs,
970
                 BOX      *box,
971
                 l_int32   xs,
972
                 l_int32   ys)
973
0
{
974
0
l_int32    fpx, fpy, spx, spy, qpos;
975
0
l_int32    px, py, npx, npy;
976
0
l_int32    w, h, wpl;
977
0
l_uint32  *data;
978
0
PTA       *pta;
979
980
0
    if (!ccb)
981
0
        return ERROR_INT("ccb not defined", __func__, 1);
982
0
    if (!pixs)
983
0
        return ERROR_INT("pixs not defined", __func__, 1);
984
0
    if (!box)
985
0
        return ERROR_INT("box not defined", __func__, 1);
986
987
        /* Add border and find start pixel */
988
0
    qpos = 0;   /* orientation of Q relative to P */
989
0
    fpx = xs;  /* save location of first pixel on border */
990
0
    fpy = ys;
991
992
        /* Save box and start pixel */
993
0
    boxaAddBox(ccb->boxa, box, L_COPY);
994
0
    ptaAddPt(ccb->start, xs, ys);
995
996
0
    pta = ptaCreate(0);
997
0
    ptaaAddPta(ccb->local, pta, L_INSERT);
998
0
    ptaAddPt(pta, xs, ys);   /* initial pixel */
999
1000
0
    w = pixGetWidth(pixs);
1001
0
    h = pixGetHeight(pixs);
1002
0
    data = pixGetData(pixs);
1003
0
    wpl = pixGetWpl(pixs);
1004
1005
        /* Get the second point; there should always be at least 4 pts
1006
         * in a minimal hole border!  */
1007
0
    if (findNextBorderPixel(w, h, data, wpl, xs, ys, &qpos, &npx, &npy))
1008
0
        return ERROR_INT("isolated hole border point!", __func__, 1);
1009
1010
0
    spx = npx;  /* save location of second pixel on border */
1011
0
    spy = npy;
1012
0
    ptaAddPt(pta, npx, npy);   /* second pixel */
1013
0
    px = npx;
1014
0
    py = npy;
1015
1016
0
    while (1) {
1017
0
        findNextBorderPixel(w, h, data, wpl, px, py, &qpos, &npx, &npy);
1018
0
        if (px == fpx && py == fpy && npx == spx && npy == spy)
1019
0
            break;
1020
0
        ptaAddPt(pta, npx, npy);
1021
0
        px = npx;
1022
0
        py = npy;
1023
0
    }
1024
1025
0
    return 0;
1026
0
}
1027
1028
1029
/*!
1030
 * \brief   findNextBorderPixel()
1031
 *
1032
 * \param[in]       w, h
1033
 * \param[in]       data, wpl
1034
 * \param[in]       px, py       current P
1035
 * \param[in,out]   pqpos        input current Q; new Q
1036
 * \param[out]      pnpx, pnpy   new P
1037
 * \return  0 if next pixel found; 1 otherwise
1038
 *
1039
 * <pre>
1040
 * Notes:
1041
 *      (1) qpos increases clockwise from 0 to 7, with 0 at
1042
 *          location with Q to left of P:   Q P
1043
 *      (2) this is a low-level function that does not check input
1044
 *          parameters.  All calling functions should check them.
1045
 * </pre>
1046
 */
1047
static l_int32
1048
findNextBorderPixel(l_int32    w,
1049
                    l_int32    h,
1050
                    l_uint32  *data,
1051
                    l_int32    wpl,
1052
                    l_int32    px,
1053
                    l_int32    py,
1054
                    l_int32   *pqpos,
1055
                    l_int32   *pnpx,
1056
                    l_int32   *pnpy)
1057
0
{
1058
0
l_int32    qpos, i, pos, npx, npy, val;
1059
0
l_uint32  *line;
1060
1061
0
    qpos = *pqpos;
1062
0
    for (i = 1; i < 8; i++) {
1063
0
        pos = (qpos + i) % 8;
1064
0
        npx = px + xpostab[pos];
1065
0
        npy = py + ypostab[pos];
1066
0
        if (npx < 0 || npx >= w || npy < 0 || npy >= h)
1067
0
            continue;
1068
0
        line = data + npy * wpl;
1069
0
        val = GET_DATA_BIT(line, npx);
1070
0
        if (val) {
1071
0
            *pnpx = npx;
1072
0
            *pnpy = npy;
1073
0
            *pqpos = qpostab[pos];
1074
0
            return 0;
1075
0
        }
1076
0
    }
1077
1078
0
    return 1;
1079
0
}
1080
1081
1082
/*!
1083
 * \brief   locateOutsideSeedPixel()
1084
 *
1085
 * \param[in]   fpx, fpy    location of first pixel
1086
 * \param[in]   spx, spy    location of second pixel
1087
 * \param[out]  pxs, pys    seed pixel to be returned
1088
 *
1089
 * <pre>
1090
 * Notes:
1091
 *      (1) The first and second pixels must be 8-adjacent,
1092
 *          so |dx| <= 1 and |dy| <= 1 and both dx and dy
1093
 *          cannot be 0.  There are 8 possible cases.
1094
 *      (2) The seed pixel is OUTSIDE the foreground of the c.c.
1095
 *      (3) These rules are for the situation where the INSIDE
1096
 *          of the c.c. is on the right as you follow the border:
1097
 *          cw for an exterior border and ccw for a hole border.
1098
 * </pre>
1099
 */
1100
static void
1101
locateOutsideSeedPixel(l_int32   fpx,
1102
                       l_int32   fpy,
1103
                       l_int32   spx,
1104
                       l_int32   spy,
1105
                       l_int32  *pxs,
1106
                       l_int32  *pys)
1107
0
{
1108
0
l_int32  dx, dy;
1109
1110
0
    dx = spx - fpx;
1111
0
    dy = spy - fpy;
1112
1113
0
    if (dx * dy == 1) {
1114
0
        *pxs = fpx + dx;
1115
0
        *pys = fpy;
1116
0
    } else if (dx * dy == -1) {
1117
0
        *pxs = fpx;
1118
0
        *pys = fpy + dy;
1119
0
    } else if (dx == 0) {
1120
0
        *pxs = fpx + dy;
1121
0
        *pys = fpy + dy;
1122
0
    } else  /* dy == 0 */ {
1123
0
        *pxs = fpx + dx;
1124
0
        *pys = fpy - dx;
1125
0
    }
1126
1127
0
    return;
1128
0
}
1129
1130
1131
1132
/*---------------------------------------------------------------------*
1133
 *                            Border conversions                       *
1134
 *---------------------------------------------------------------------*/
1135
/*!
1136
 * \brief   ccbaGenerateGlobalLocs()
1137
 *
1138
 * \param[in]    ccba     with local chain ptaa of borders computed
1139
 * \return  0 if OK, 1 on error
1140
 *
1141
 * <pre>
1142
 * Notes:
1143
 *      (1) This uses the pixel locs in the local ptaa, which are all
1144
 *          relative to each c.c., to find the global pixel locations,
1145
 *          and stores them in the global ptaa.
1146
 * </pre>
1147
 */
1148
l_ok
1149
ccbaGenerateGlobalLocs(CCBORDA  *ccba)
1150
0
{
1151
0
l_int32  ncc, nb, n, i, j, k, xul, yul, x, y;
1152
0
CCBORD  *ccb;
1153
0
PTAA    *ptaal, *ptaag;
1154
0
PTA     *ptal, *ptag;
1155
1156
0
    if (!ccba)
1157
0
        return ERROR_INT("ccba not defined", __func__, 1);
1158
1159
0
    ncc = ccbaGetCount(ccba);  /* number of c.c. */
1160
0
    for (i = 0; i < ncc; i++) {
1161
0
        ccb = ccbaGetCcb(ccba, i);
1162
1163
            /* Get the UL corner in global coords, (xul, yul), of the c.c. */
1164
0
        boxaGetBoxGeometry(ccb->boxa, 0, &xul, &yul, NULL, NULL);
1165
1166
            /* Make a new global ptaa, removing any old one */
1167
0
        ptaal = ccb->local;
1168
0
        nb = ptaaGetCount(ptaal);   /* number of borders */
1169
0
        if (ccb->global)   /* remove old one */
1170
0
            ptaaDestroy(&ccb->global);
1171
0
        if ((ptaag = ptaaCreate(nb)) == NULL) {
1172
0
            ccbDestroy(&ccb);
1173
0
            return ERROR_INT("ptaag not made", __func__, 1);
1174
0
        }
1175
0
        ccb->global = ptaag;  /* save new one */
1176
1177
            /* Iterate through the borders for this c.c. */
1178
0
        for (j = 0; j < nb; j++) {
1179
0
            ptal = ptaaGetPta(ptaal, j, L_CLONE);
1180
0
            n = ptaGetCount(ptal);   /* number of pixels in border */
1181
0
            ptag = ptaCreate(n);
1182
0
            ptaaAddPta(ptaag, ptag, L_INSERT);
1183
0
            for (k = 0; k < n; k++) {
1184
0
                ptaGetIPt(ptal, k, &x, &y);
1185
0
                ptaAddPt(ptag, x  + xul, y + yul);
1186
0
            }
1187
0
            ptaDestroy(&ptal);
1188
0
        }
1189
0
        ccbDestroy(&ccb);
1190
0
    }
1191
1192
0
    return 0;
1193
0
}
1194
1195
1196
/*!
1197
 * \brief   ccbaGenerateStepChains()
1198
 *
1199
 * \param[in]    ccba     with local chain ptaa of borders computed
1200
 * \return  0 if OK, 1 on error
1201
 *
1202
 * <pre>
1203
 * Notes:
1204
 *      (1) This uses the pixel locs in the local ptaa,
1205
 *          which are all relative to each c.c., to find
1206
 *          the step directions for successive pixels in
1207
 *          the chain, and stores them in the step numaa.
1208
 *      (2) To get the step direction, use
1209
 *              1   2   3
1210
 *              0   P   4
1211
 *              7   6   5
1212
 *          where P is the previous pixel at (px, py).  The step direction
1213
 *          is the number (from 0 through 7) for each relative location
1214
 *          of the current pixel at (cx, cy).  It is easily found by
1215
 *          indexing into a 2-d 3x3 array (dirtab).
1216
 * </pre>
1217
 */
1218
l_ok
1219
ccbaGenerateStepChains(CCBORDA  *ccba)
1220
0
{
1221
0
l_int32  ncc, nb, n, i, j, k;
1222
0
l_int32  px, py, cx, cy, stepdir;
1223
0
l_int32  dirtab[][3] = {{1, 2, 3}, {0, -1, 4}, {7, 6, 5}};
1224
0
CCBORD  *ccb;
1225
0
NUMA    *na;
1226
0
NUMAA   *naa;   /* step chain code; to be made */
1227
0
PTA     *ptal;
1228
0
PTAA    *ptaal;  /* local chain code */
1229
1230
0
    if (!ccba)
1231
0
        return ERROR_INT("ccba not defined", __func__, 1);
1232
1233
0
    ncc = ccbaGetCount(ccba);  /* number of c.c. */
1234
0
    for (i = 0; i < ncc; i++) {
1235
0
        ccb = ccbaGetCcb(ccba, i);
1236
1237
            /* Make a new step numaa, removing any old one */
1238
0
        ptaal = ccb->local;
1239
0
        nb = ptaaGetCount(ptaal);  /* number of borders */
1240
0
        if (ccb->step)  /* remove old one */
1241
0
            numaaDestroy(&ccb->step);
1242
0
        if ((naa = numaaCreate(nb)) == NULL) {
1243
0
            ccbDestroy(&ccb);
1244
0
            return ERROR_INT("naa not made", __func__, 1);
1245
0
        }
1246
0
        ccb->step = naa;  /* save new one */
1247
1248
            /* Iterate through the borders for this c.c. */
1249
0
        for (j = 0; j < nb; j++) {
1250
0
            ptal = ptaaGetPta(ptaal, j, L_CLONE);
1251
0
            n = ptaGetCount(ptal);   /* number of pixels in border */
1252
0
            if (n == 1) {  /* isolated pixel */
1253
0
                na = numaCreate(1);   /* but leave it empty */
1254
0
            } else {   /* trace out the boundary */
1255
0
                na = numaCreate(n);
1256
0
                ptaGetIPt(ptal, 0, &px, &py);
1257
0
                for (k = 1; k < n; k++) {
1258
0
                    ptaGetIPt(ptal, k, &cx, &cy);
1259
0
                    stepdir = dirtab[1 + cy - py][1 + cx - px];
1260
0
                    numaAddNumber(na, stepdir);
1261
0
                    px = cx;
1262
0
                    py = cy;
1263
0
                }
1264
0
            }
1265
0
            numaaAddNuma(naa, na, L_INSERT);
1266
0
            ptaDestroy(&ptal);
1267
0
        }
1268
0
        ccbDestroy(&ccb);  /* just decrement refcount */
1269
0
    }
1270
1271
0
    return 0;
1272
0
}
1273
1274
1275
/*!
1276
 * \brief   ccbaStepChainsToPixCoords()
1277
 *
1278
 * \param[in]    ccba        with step chains numaa of borders
1279
 * \param[in]    coordtype   CCB_GLOBAL_COORDS or CCB_LOCAL_COORDS
1280
 * \return  0 if OK, 1 on error
1281
 *
1282
 * <pre>
1283
 * Notes:
1284
 *      (1) This uses the step chain data in each ccb to determine
1285
 *          the pixel locations, either global or local,
1286
 *          and stores them in the appropriate ptaa,
1287
 *          either global or local.  For the latter, the
1288
 *          pixel locations are relative to the c.c.
1289
 * </pre>
1290
 */
1291
l_ok
1292
ccbaStepChainsToPixCoords(CCBORDA  *ccba,
1293
                          l_int32   coordtype)
1294
0
{
1295
0
l_int32  ncc, nb, n, i, j, k;
1296
0
l_int32  xul, yul, xstart, ystart, x, y, stepdir;
1297
0
BOXA    *boxa;
1298
0
CCBORD  *ccb;
1299
0
NUMA    *na;
1300
0
NUMAA   *naa;
1301
0
PTAA    *ptaan;  /* new pix coord ptaa */
1302
0
PTA     *ptas, *ptan;
1303
1304
0
    if (!ccba)
1305
0
        return ERROR_INT("ccba not defined", __func__, 1);
1306
0
    if (coordtype != CCB_GLOBAL_COORDS && coordtype != CCB_LOCAL_COORDS)
1307
0
        return ERROR_INT("coordtype not valid", __func__, 1);
1308
1309
0
    ncc = ccbaGetCount(ccba);  /* number of c.c. */
1310
0
    for (i = 0; i < ncc; i++) {
1311
0
        ccb = ccbaGetCcb(ccba, i);
1312
0
        if ((naa = ccb->step) == NULL) {
1313
0
            ccbDestroy(&ccb);
1314
0
            return ERROR_INT("step numaa not found", __func__, 1);
1315
0
        } if ((boxa = ccb->boxa) == NULL) {
1316
0
            ccbDestroy(&ccb);
1317
0
            return ERROR_INT("boxa not found", __func__, 1);
1318
0
        } if ((ptas = ccb->start) == NULL) {
1319
0
            ccbDestroy(&ccb);
1320
0
            return ERROR_INT("start pta not found", __func__, 1);
1321
0
        }
1322
1323
            /* For global coords, get the (xul, yul) of the c.c.;
1324
             * otherwise, use relative coords. */
1325
0
        if (coordtype == CCB_LOCAL_COORDS) {
1326
0
            xul = 0;
1327
0
            yul = 0;
1328
0
        } else {  /* coordtype == CCB_GLOBAL_COORDS */
1329
                /* Get UL corner in global coords */
1330
0
            if (boxaGetBoxGeometry(boxa, 0, &xul, &yul, NULL, NULL)) {
1331
0
                ccbDestroy(&ccb);
1332
0
                return ERROR_INT("bounding rectangle not found", __func__, 1);
1333
0
            }
1334
0
        }
1335
1336
            /* Make a new ptaa, removing any old one */
1337
0
        nb = numaaGetCount(naa);   /* number of borders */
1338
0
        if ((ptaan = ptaaCreate(nb)) == NULL) {
1339
0
            ccbDestroy(&ccb);
1340
0
            return ERROR_INT("ptaan not made", __func__, 1);
1341
0
        }
1342
0
        if (coordtype == CCB_LOCAL_COORDS) {
1343
0
            if (ccb->local)   /* remove old one */
1344
0
                ptaaDestroy(&ccb->local);
1345
0
            ccb->local = ptaan;  /* save new local chain */
1346
0
        } else {   /* coordtype == CCB_GLOBAL_COORDS */
1347
0
            if (ccb->global)   /* remove old one */
1348
0
                ptaaDestroy(&ccb->global);
1349
0
            ccb->global = ptaan;  /* save new global chain */
1350
0
        }
1351
1352
            /* Iterate through the borders for this c.c. */
1353
0
        for (j = 0; j < nb; j++) {
1354
0
            na = numaaGetNuma(naa, j, L_CLONE);
1355
0
            n = numaGetCount(na);   /* number of steps in border */
1356
0
            if ((ptan = ptaCreate(n + 1)) == NULL) {
1357
0
                ccbDestroy(&ccb);
1358
0
                numaDestroy(&na);
1359
0
                return ERROR_INT("ptan not made", __func__, 1);
1360
0
            }
1361
0
            ptaaAddPta(ptaan, ptan, L_INSERT);
1362
0
            ptaGetIPt(ptas, j, &xstart, &ystart);
1363
0
            x = xul + xstart;
1364
0
            y = yul + ystart;
1365
0
            ptaAddPt(ptan, x, y);
1366
0
            for (k = 0; k < n; k++) {
1367
0
                numaGetIValue(na, k, &stepdir);
1368
0
                x += xpostab[stepdir];
1369
0
                y += ypostab[stepdir];
1370
0
                ptaAddPt(ptan, x, y);
1371
0
            }
1372
0
            numaDestroy(&na);
1373
0
        }
1374
0
        ccbDestroy(&ccb);
1375
0
    }
1376
1377
0
    return 0;
1378
0
}
1379
1380
1381
/*!
1382
 * \brief   ccbaGenerateSPGlobalLocs()
1383
 *
1384
 * \param[in]    ccba
1385
 * \param[in]    ptsflag      CCB_SAVE_ALL_PTS or CCB_SAVE_TURNING_PTS
1386
 * \return  0 if OK, 1 on error
1387
 *
1388
 * <pre>
1389
 * Notes:
1390
 *      (1) This calculates the splocal rep if not yet made.
1391
 *      (2) It uses the local pixel values in splocal, the single
1392
 *          path pta, which are all relative to each c.c., to find
1393
 *          the corresponding global pixel locations, and stores
1394
 *          them in the spglobal pta.
1395
 *      (3) This lists only the turning points: it both makes a
1396
 *          valid svg file and is typically about half the size
1397
 *          when all border points are listed.
1398
 * </pre>
1399
 */
1400
l_ok
1401
ccbaGenerateSPGlobalLocs(CCBORDA  *ccba,
1402
                         l_int32   ptsflag)
1403
0
{
1404
0
l_int32  ncc, npt, i, j, xul, yul, x, y, delx, dely;
1405
0
l_int32  xp, yp, delxp, delyp;   /* prev point and increments */
1406
0
CCBORD  *ccb;
1407
0
PTA     *ptal, *ptag;
1408
1409
0
    if (!ccba)
1410
0
        return ERROR_INT("ccba not defined", __func__, 1);
1411
1412
        /* Make sure we have a local single path representation */
1413
0
    if ((ccb = ccbaGetCcb(ccba, 0)) == NULL)
1414
0
        return ERROR_INT("no ccb", __func__, 1);
1415
0
    if (!ccb->splocal)
1416
0
        ccbaGenerateSinglePath(ccba);
1417
0
    ccbDestroy(&ccb);  /* clone ref */
1418
1419
0
    ncc = ccbaGetCount(ccba);  /* number of c.c. */
1420
0
    for (i = 0; i < ncc; i++) {
1421
0
        ccb = ccbaGetCcb(ccba, i);
1422
1423
            /* Get the UL corner in global coords, (xul, yul), of the c.c. */
1424
0
        if (boxaGetBoxGeometry(ccb->boxa, 0, &xul, &yul, NULL, NULL)) {
1425
0
            ccbDestroy(&ccb);
1426
0
            return ERROR_INT("bounding rectangle not found", __func__, 1);
1427
0
        }
1428
1429
            /* Make a new spglobal pta, removing any old one */
1430
0
        ptal = ccb->splocal;
1431
0
        npt = ptaGetCount(ptal);   /* number of points */
1432
0
        if (ccb->spglobal)   /* remove old one */
1433
0
            ptaDestroy(&ccb->spglobal);
1434
0
        if ((ptag = ptaCreate(npt)) == NULL) {
1435
0
            ccbDestroy(&ccb);
1436
0
            return ERROR_INT("ptag not made", __func__, 1);
1437
0
        }
1438
0
        ccb->spglobal = ptag;  /* save new one */
1439
1440
            /* Convert local to global */
1441
0
        if (ptsflag == CCB_SAVE_ALL_PTS) {
1442
0
            for (j = 0; j < npt; j++) {
1443
0
                ptaGetIPt(ptal, j, &x, &y);
1444
0
                ptaAddPt(ptag, x  + xul, y + yul);
1445
0
            }
1446
0
        } else {   /* ptsflag = CCB_SAVE_TURNING_PTS */
1447
0
            ptaGetIPt(ptal, 0, &xp, &yp);   /* get the 1st pt */
1448
0
            ptaAddPt(ptag, xp  + xul, yp + yul);   /* save the 1st pt */
1449
0
            if (npt == 2) {  /* get and save the 2nd pt  */
1450
0
                ptaGetIPt(ptal, 1, &x, &y);
1451
0
                ptaAddPt(ptag, x  + xul, y + yul);
1452
0
            } else if (npt > 2)  {
1453
0
                ptaGetIPt(ptal, 1, &x, &y);
1454
0
                delxp = x - xp;
1455
0
                delyp = y - yp;
1456
0
                xp = x;
1457
0
                yp = y;
1458
0
                for (j = 2; j < npt; j++) {
1459
0
                    ptaGetIPt(ptal, j, &x, &y);
1460
0
                    delx = x - xp;
1461
0
                    dely = y - yp;
1462
0
                    if (delx != delxp || dely != delyp)
1463
0
                        ptaAddPt(ptag, xp  + xul, yp + yul);
1464
0
                    xp = x;
1465
0
                    yp = y;
1466
0
                    delxp = delx;
1467
0
                    delyp = dely;
1468
0
                }
1469
0
                ptaAddPt(ptag, xp  + xul, yp + yul);
1470
0
            }
1471
0
        }
1472
1473
0
        ccbDestroy(&ccb);  /* clone ref */
1474
0
    }
1475
1476
0
    return 0;
1477
0
}
1478
1479
1480
1481
/*---------------------------------------------------------------------*
1482
 *                       Conversion to single path                     *
1483
 *---------------------------------------------------------------------*/
1484
/*!
1485
 * \brief   ccbaGenerateSinglePath()
1486
 *
1487
 * \param[in]    ccba
1488
 * \return  0 if OK, 1 on error
1489
 *
1490
 * <pre>
1491
 * Notes:
1492
 *      (1) Generates a single border in local pixel coordinates.
1493
 *          For each c.c., if there is just an outer border, copy it.
1494
 *          If there are also hole borders, for each hole border,
1495
 *          determine the smallest horizontal or vertical
1496
 *          distance from the border to the outside of the c.c.,
1497
 *          and find a path through the c.c. for this cut.
1498
 *          We do this in a way that guarantees a pixel from the
1499
 *          hole border is the starting point of the path, and
1500
 *          we must verify that the path intersects the outer
1501
 *          border (if it intersects it, then it ends on it).
1502
 *          One can imagine pathological cases, but they may not
1503
 *          occur in images of text characters and un-textured
1504
 *          line graphics.
1505
 *      (2) Once it is verified that the path through the c.c.
1506
 *          intersects both the hole and outer borders, we
1507
 *          generate the full single path for all borders in the
1508
 *          c.c.  Starting at the start point on the outer
1509
 *          border, when we hit a line on a cut, we take
1510
 *          the cut, do the hole border, and return on the cut
1511
 *          to the outer border.  We compose a pta of the
1512
 *          outer border pts that are on cut paths, and for
1513
 *          every point on the outer border (as we go around),
1514
 *          we check against this pta.  When we find a matching
1515
 *          point in the pta, we do its cut path and hole border.
1516
 *          The single path is saved in the ccb.
1517
 * </pre>
1518
 */
1519
l_ok
1520
ccbaGenerateSinglePath(CCBORDA  *ccba)
1521
0
{
1522
0
l_int32   i, j, k, ncc, nb, ncut, npt, dir, len, state, lostholes;
1523
0
l_int32   x, y, xl, yl, xf, yf;
1524
0
BOX      *boxinner;
1525
0
BOXA     *boxa;
1526
0
CCBORD   *ccb;
1527
0
PTA      *pta, *ptac, *ptah;
1528
0
PTA      *ptahc;  /* cyclic permutation of hole border, with end pts at cut */
1529
0
PTA      *ptas;  /* output result: new single path for c.c. */
1530
0
PTA      *ptaf;  /* points on the hole borders that intersect with cuts */
1531
0
PTA      *ptal;  /* points on outer border that intersect with cuts */
1532
0
PTA      *ptap, *ptarp;   /* path and reverse path between borders */
1533
0
PTAA     *ptaa;
1534
0
PTAA     *ptaap;  /* ptaa for all paths between borders */
1535
1536
0
    if (!ccba)
1537
0
        return ERROR_INT("ccba not defined", __func__, 1);
1538
1539
0
    ncc = ccbaGetCount(ccba);   /* number of c.c. */
1540
0
    lostholes = 0;
1541
0
    for (i = 0; i < ncc; i++) {
1542
0
        ccb = ccbaGetCcb(ccba, i);
1543
0
        if ((ptaa = ccb->local) == NULL) {
1544
0
            L_WARNING("local pixel loc array not found\n", __func__);
1545
0
            continue;
1546
0
        }
1547
0
        nb = ptaaGetCount(ptaa);   /* number of borders in the c.c.  */
1548
1549
            /* Prepare the output pta */
1550
0
        if (ccb->splocal)
1551
0
            ptaDestroy(&ccb->splocal);
1552
0
        ptas = ptaCreate(0);
1553
0
        ccb->splocal = ptas;
1554
1555
            /* If no holes, just concat the outer border */
1556
0
        pta = ptaaGetPta(ptaa, 0, L_CLONE);
1557
0
        if (nb == 1 || nb > NMAX_HOLES + 1) {
1558
0
            ptaJoin(ptas, pta, 0, -1);
1559
0
            ptaDestroy(&pta);  /* remove clone */
1560
0
            ccbDestroy(&ccb);  /* remove clone */
1561
0
            continue;
1562
0
        }
1563
1564
            /* Find the (nb - 1) cut paths that connect holes
1565
             * with outer border */
1566
0
        boxa = ccb->boxa;
1567
0
        ptaap = ptaaCreate(nb - 1);
1568
0
        ptaf = ptaCreate(nb - 1);
1569
0
        ptal = ptaCreate(nb - 1);
1570
0
        for (j = 1; j < nb; j++) {
1571
0
            boxinner = boxaGetBox(boxa, j, L_CLONE);
1572
1573
                /* Find a short path and store it */
1574
0
            ptac = getCutPathForHole(ccb->pix, pta, boxinner, &dir, &len);
1575
0
            if (len == 0) {  /* lost the hole */
1576
0
                lostholes++;
1577
/*                boxPrintStreamInfo(stderr, boxa->box[0]); */
1578
0
            }
1579
0
            ptaaAddPta(ptaap, ptac, L_INSERT);
1580
/*            lept_stderr("dir = %d, length = %d\n", dir, len); */
1581
/*            ptaWriteStream(stderr, ptac, 1); */
1582
1583
                /* Store the first and last points in the cut path,
1584
                 * which must be on a hole border and the outer
1585
                 * border, respectively */
1586
0
            ncut = ptaGetCount(ptac);
1587
0
            if (ncut == 0) {   /* missed hole; neg coords won't match */
1588
0
                ptaAddPt(ptaf, -1, -1);
1589
0
                ptaAddPt(ptal, -1, -1);
1590
0
            } else {
1591
0
                ptaGetIPt(ptac, 0, &x, &y);
1592
0
                ptaAddPt(ptaf, x, y);
1593
0
                ptaGetIPt(ptac, ncut - 1, &x, &y);
1594
0
                ptaAddPt(ptal, x, y);
1595
0
            }
1596
0
            boxDestroy(&boxinner);
1597
0
        }
1598
1599
            /* Make a single path for the c.c. using these connections */
1600
0
        npt = ptaGetCount(pta);  /* outer border pts */
1601
0
        for (k = 0; k < npt; k++) {
1602
0
            ptaGetIPt(pta, k, &x, &y);
1603
0
            if (k == 0) {   /* if there is a cut at the first point,
1604
                             * we can wait until the end to take it */
1605
0
                ptaAddPt(ptas, x, y);
1606
0
                continue;
1607
0
            }
1608
0
            state = L_NOT_FOUND;
1609
0
            for (j = 0; j < nb - 1; j++) {  /* iterate over cut end pts */
1610
0
                ptaGetIPt(ptal, j, &xl, &yl);  /* cut point on outer border */
1611
0
                if (x == xl && y == yl) {  /* take this cut to the hole */
1612
0
                    state = L_FOUND;
1613
0
                    ptap = ptaaGetPta(ptaap, j, L_CLONE);
1614
0
                    ptarp = ptaReverse(ptap, 1);
1615
                        /* Cut point on hole border: */
1616
0
                    ptaGetIPt(ptaf, j, &xf, &yf);
1617
                        /* Hole border: */
1618
0
                    ptah = ptaaGetPta(ptaa, j + 1, L_CLONE);
1619
0
                    ptahc = ptaCyclicPerm(ptah, xf, yf);
1620
/*                    ptaWriteStream(stderr, ptahc, 1); */
1621
0
                    ptaJoin(ptas, ptarp, 0, -1);
1622
0
                    ptaJoin(ptas, ptahc, 0, -1);
1623
0
                    ptaJoin(ptas, ptap, 0, -1);
1624
0
                    ptaDestroy(&ptap);
1625
0
                    ptaDestroy(&ptarp);
1626
0
                    ptaDestroy(&ptah);
1627
0
                    ptaDestroy(&ptahc);
1628
0
                    break;
1629
0
                }
1630
0
            }
1631
0
            if (state == L_NOT_FOUND)
1632
0
                ptaAddPt(ptas, x, y);
1633
0
        }
1634
1635
/*        ptaWriteStream(stderr, ptas, 1); */
1636
0
        ptaaDestroy(&ptaap);
1637
0
        ptaDestroy(&ptaf);
1638
0
        ptaDestroy(&ptal);
1639
0
        ptaDestroy(&pta);  /* remove clone */
1640
0
        ccbDestroy(&ccb);  /* remove clone */
1641
0
    }
1642
1643
0
    if (lostholes > 0)
1644
0
        L_INFO("***** %d lost holes *****\n", __func__, lostholes);
1645
0
    return 0;
1646
0
}
1647
1648
1649
/*!
1650
 * \brief   getCutPathForHole()
1651
 *
1652
 * \param[in]    pix        1 bpp, of c.c.
1653
 * \param[in]    pta        of outer border
1654
 * \param[in]    boxinner   bounding box of hole path
1655
 * \param[out]   pdir       direction (0-3), returned; only needed for debug
1656
 * \param[out]   plen       length of path, returned
1657
 * \return  pta of pts on cut path from the hole border
1658
 *              to the outer border, including end points on
1659
 *              both borders; or NULL on error
1660
 *
1661
 * <pre>
1662
 * Notes:
1663
 *      (1) If we don't find a path, we return a pta with no pts
1664
 *          in it and len = 0.
1665
 *      (2) The goal is to get a reasonably short path between the
1666
 *          inner and outer borders, that goes entirely within the fg of
1667
 *          the pix.  This function is cheap-and-dirty, may fail for some
1668
 *          holes in complex topologies such as those you might find in a
1669
 *          moderately dark scanned halftone.  If it fails to find a
1670
 *          path to any particular hole, the hole will not be rendered.
1671
 *          Nevertheless, the image can be perfectly reconstructed
1672
 *          from the boundary representation.
1673
 * </pre>
1674
 */
1675
static PTA *
1676
getCutPathForHole(PIX      *pix,
1677
                  PTA      *pta,
1678
                  BOX      *boxinner,
1679
                  l_int32  *pdir,
1680
                  l_int32  *plen)
1681
0
{
1682
0
l_int32   w, h, nc, x, y, xl, yl, xmid, ymid;
1683
0
l_uint32  val;
1684
0
PTA      *ptac;
1685
1686
0
    if (!pix)
1687
0
        return (PTA *)ERROR_PTR("pix not defined", __func__, NULL);
1688
0
    if (!pta)
1689
0
        return (PTA *)ERROR_PTR("pta not defined", __func__, NULL);
1690
0
    if (!boxinner)
1691
0
        return (PTA *)ERROR_PTR("boxinner not defined", __func__, NULL);
1692
1693
0
    pixGetDimensions(pix, &w, &h, NULL);
1694
0
    ptac = ptaCreate(4);
1695
0
    xmid = boxinner->x + boxinner->w / 2;
1696
0
    ymid = boxinner->y + boxinner->h / 2;
1697
1698
        /* try top first */
1699
0
    for (y = ymid; y >= 0; y--) {
1700
0
        pixGetPixel(pix, xmid, y, &val);
1701
0
        if (val == 1) {
1702
0
            ptaAddPt(ptac, xmid, y);
1703
0
            break;
1704
0
        }
1705
0
    }
1706
0
    for (y = y - 1; y >= 0; y--) {
1707
0
        pixGetPixel(pix, xmid, y, &val);
1708
0
        if (val == 1)
1709
0
            ptaAddPt(ptac, xmid, y);
1710
0
        else
1711
0
            break;
1712
0
    }
1713
0
    nc = ptaGetCount(ptac);
1714
0
    ptaGetIPt(ptac, nc - 1, &xl, &yl);
1715
0
    if (ptaContainsPt(pta, xl, yl)) {
1716
0
        *pdir = 1;
1717
0
        *plen = nc;
1718
0
        return ptac;
1719
0
    }
1720
1721
        /* Next try bottom */
1722
0
    ptaEmpty(ptac);
1723
0
    for (y = ymid; y < h; y++) {
1724
0
        pixGetPixel(pix, xmid, y, &val);
1725
0
        if (val == 1) {
1726
0
            ptaAddPt(ptac, xmid, y);
1727
0
            break;
1728
0
        }
1729
0
    }
1730
0
    for (y = y + 1; y < h; y++) {
1731
0
        pixGetPixel(pix, xmid, y, &val);
1732
0
        if (val == 1)
1733
0
            ptaAddPt(ptac, xmid, y);
1734
0
        else
1735
0
            break;
1736
0
    }
1737
0
    nc = ptaGetCount(ptac);
1738
0
    ptaGetIPt(ptac, nc - 1, &xl, &yl);
1739
0
    if (ptaContainsPt(pta, xl, yl)) {
1740
0
        *pdir = 3;
1741
0
        *plen = nc;
1742
0
        return ptac;
1743
0
    }
1744
1745
        /* Next try left */
1746
0
    ptaEmpty(ptac);
1747
0
    for (x = xmid; x >= 0; x--) {
1748
0
        pixGetPixel(pix, x, ymid, &val);
1749
0
        if (val == 1) {
1750
0
            ptaAddPt(ptac, x, ymid);
1751
0
            break;
1752
0
        }
1753
0
    }
1754
0
    for (x = x - 1; x >= 0; x--) {
1755
0
        pixGetPixel(pix, x, ymid, &val);
1756
0
        if (val == 1)
1757
0
            ptaAddPt(ptac, x, ymid);
1758
0
        else
1759
0
            break;
1760
0
    }
1761
0
    nc = ptaGetCount(ptac);
1762
0
    ptaGetIPt(ptac, nc - 1, &xl, &yl);
1763
0
    if (ptaContainsPt(pta, xl, yl)) {
1764
0
        *pdir = 0;
1765
0
        *plen = nc;
1766
0
        return ptac;
1767
0
    }
1768
1769
        /* Finally try right */
1770
0
    ptaEmpty(ptac);
1771
0
    for (x = xmid; x < w; x++) {
1772
0
        pixGetPixel(pix, x, ymid, &val);
1773
0
        if (val == 1) {
1774
0
            ptaAddPt(ptac, x, ymid);
1775
0
            break;
1776
0
        }
1777
0
    }
1778
0
    for (x = x + 1; x < w; x++) {
1779
0
        pixGetPixel(pix, x, ymid, &val);
1780
0
        if (val == 1)
1781
0
            ptaAddPt(ptac, x, ymid);
1782
0
        else
1783
0
            break;
1784
0
    }
1785
0
    nc = ptaGetCount(ptac);
1786
0
    ptaGetIPt(ptac, nc - 1, &xl, &yl);
1787
0
    if (ptaContainsPt(pta, xl, yl)) {
1788
0
        *pdir = 2;
1789
0
        *plen = nc;
1790
0
        return ptac;
1791
0
    }
1792
1793
        /* Sometimes, there is nothing. */
1794
0
    ptaEmpty(ptac);
1795
0
    *plen = 0;
1796
0
    return ptac;
1797
0
}
1798
1799
1800
1801
/*---------------------------------------------------------------------*
1802
 *                            Border rendering                         *
1803
 *---------------------------------------------------------------------*/
1804
/*!
1805
 * \brief   ccbaDisplayBorder()
1806
 *
1807
 * \param[in]    ccba
1808
 * \return  pix of border pixels, or NULL on error
1809
 *
1810
 * <pre>
1811
 * Notes:
1812
 *      (1) Uses global ptaa, which gives each border pixel in
1813
 *          global coordinates, and must be computed in advance
1814
 *          by calling ccbaGenerateGlobalLocs().
1815
 * </pre>
1816
 */
1817
PIX *
1818
ccbaDisplayBorder(CCBORDA  *ccba)
1819
0
{
1820
0
l_int32  ncc, nb, n, i, j, k, x, y;
1821
0
CCBORD  *ccb;
1822
0
PIX     *pixd;
1823
0
PTAA    *ptaa;
1824
0
PTA     *pta;
1825
1826
0
    if (!ccba)
1827
0
        return (PIX *)ERROR_PTR("ccba not defined", __func__, NULL);
1828
1829
0
    if ((pixd = pixCreate(ccba->w, ccba->h, 1)) == NULL)
1830
0
        return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
1831
0
    ncc = ccbaGetCount(ccba);   /* number of c.c. */
1832
0
    for (i = 0; i < ncc; i++) {
1833
0
        ccb = ccbaGetCcb(ccba, i);
1834
0
        if ((ptaa = ccb->global) == NULL) {
1835
0
            L_WARNING("global pixel loc array not found", __func__);
1836
0
            ccbDestroy(&ccb);
1837
0
            continue;
1838
0
        }
1839
0
        nb = ptaaGetCount(ptaa);   /* number of borders in the c.c.  */
1840
0
        for (j = 0; j < nb; j++) {
1841
0
            pta = ptaaGetPta(ptaa, j, L_CLONE);
1842
0
            n = ptaGetCount(pta);   /* number of pixels in the border */
1843
0
            for (k = 0; k < n; k++) {
1844
0
                ptaGetIPt(pta, k, &x, &y);
1845
0
                pixSetPixel(pixd, x, y, 1);
1846
0
            }
1847
0
            ptaDestroy(&pta);
1848
0
        }
1849
0
        ccbDestroy(&ccb);
1850
0
    }
1851
1852
0
    return pixd;
1853
0
}
1854
1855
1856
/*!
1857
 * \brief   ccbaDisplaySPBorder()
1858
 *
1859
 * \param[in]    ccba
1860
 * \return  pix of border pixels, or NULL on error
1861
 *
1862
 * <pre>
1863
 * Notes:
1864
 *      (1) Uses spglobal pta, which gives each border pixel in
1865
 *          global coordinates, one path per c.c., and must
1866
 *          be computed in advance by calling ccbaGenerateSPGlobalLocs().
1867
 * </pre>
1868
 */
1869
PIX *
1870
ccbaDisplaySPBorder(CCBORDA  *ccba)
1871
0
{
1872
0
l_int32  ncc, npt, i, j, x, y;
1873
0
CCBORD  *ccb;
1874
0
PIX     *pixd;
1875
0
PTA     *ptag;
1876
1877
0
    if (!ccba)
1878
0
        return (PIX *)ERROR_PTR("ccba not defined", __func__, NULL);
1879
1880
0
    if ((pixd = pixCreate(ccba->w, ccba->h, 1)) == NULL)
1881
0
        return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
1882
0
    ncc = ccbaGetCount(ccba);   /* number of c.c. */
1883
0
    for (i = 0; i < ncc; i++) {
1884
0
        ccb = ccbaGetCcb(ccba, i);
1885
0
        if ((ptag = ccb->spglobal) == NULL) {
1886
0
            L_WARNING("spglobal pixel loc array not found\n", __func__);
1887
0
            ccbDestroy(&ccb);
1888
0
            continue;
1889
0
        }
1890
0
        npt = ptaGetCount(ptag);   /* number of pixels on path */
1891
0
        for (j = 0; j < npt; j++) {
1892
0
            ptaGetIPt(ptag, j, &x, &y);
1893
0
            pixSetPixel(pixd, x, y, 1);
1894
0
        }
1895
0
        ccbDestroy(&ccb);  /* clone ref */
1896
0
    }
1897
1898
0
    return pixd;
1899
0
}
1900
1901
1902
/*!
1903
 * \brief   ccbaDisplayImage1()
1904
 *
1905
 * \param[in]    ccba
1906
 * \return  pix of image, or NULL on error
1907
 *
1908
 * <pre>
1909
 * Notes:
1910
 *      (1) Uses local ptaa, which gives each border pixel in
1911
 *          local coordinates, so the actual pixel positions must
1912
 *          be computed using all offsets.
1913
 *      (2) For the holes, use coordinates relative to the c.c.
1914
 *      (3) This is slower than Method 2.
1915
 *      (4) This uses topological properties (Method 1) to do scan
1916
 *          conversion to raster
1917
 *
1918
 *  This algorithm deserves some commentary.
1919
 *
1920
 *  I first tried the following:
1921
 *    ~ outer borders: 4-fill from outside, stopping at the
1922
 *         border, using pixFillClosedBorders()
1923
 *    ~ inner borders: 4-fill from outside, stopping again
1924
 *         at the border, XOR with the border, and invert
1925
 *         to get the hole.  This did not work, because if
1926
 *         you have a hole border that looks like:
1927
 *
1928
 *                x x x x x x
1929
 *                x          x
1930
 *                x   x x x   x
1931
 *                  x x o x   x
1932
 *                      x     x
1933
 *                      x     x
1934
 *                        x x x
1935
 *
1936
 *         if you 4-fill from the outside, the pixel 'o' will
1937
 *         not be filled!  XORing with the border leaves it OFF.
1938
 *         Inverting then gives a single bad ON pixel that is not
1939
 *         actually part of the hole.
1940
 *
1941
 *  So what you must do instead is 4-fill the holes from inside.
1942
 *  You can do this from a seedfill, using a pix with the hole
1943
 *  border as the filling mask.  But you need to start with a
1944
 *  pixel inside the hole.  How is this determined?  The best
1945
 *  way is from the contour.  We have a right-hand shoulder
1946
 *  rule for inside (i.e., the filled region).   Take the
1947
 *  first 2 pixels of the hole border, and compute dx and dy
1948
 *  (second coord minus first coord:  dx = sx - fx, dy = sy - fy).
1949
 *  There are 8 possibilities, depending on the values of dx and
1950
 *  dy (which can each be -1, 0, and +1, but not both 0).
1951
 *  These 8 cases can be broken into 4; see the simple algorithm below.
1952
 *  Once you have an interior seed pixel, you fill from the seed,
1953
 *  clipping with the hole border pix by filling into its invert.
1954
 *
1955
 *  You then successively XOR these interior filled components, in any order.
1956
 * </pre>
1957
 */
1958
PIX *
1959
ccbaDisplayImage1(CCBORDA  *ccba)
1960
0
{
1961
0
l_int32  ncc, i, nb, n, j, k, x, y, xul, yul, xoff, yoff, w, h;
1962
0
l_int32  fpx, fpy, spx, spy, xs, ys;
1963
0
BOX     *box;
1964
0
BOXA    *boxa;
1965
0
CCBORD  *ccb;
1966
0
PIX     *pixd, *pixt, *pixh;
1967
0
PTAA    *ptaa;
1968
0
PTA     *pta;
1969
1970
0
    if (!ccba)
1971
0
        return (PIX *)ERROR_PTR("ccba not defined", __func__, NULL);
1972
1973
0
    if ((pixd = pixCreate(ccba->w, ccba->h, 1)) == NULL)
1974
0
        return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
1975
0
    ncc = ccbaGetCount(ccba);
1976
0
    for (i = 0; i < ncc; i++) {
1977
0
        ccb = ccbaGetCcb(ccba, i);
1978
0
        if ((boxa = ccb->boxa) == NULL) {
1979
0
            pixDestroy(&pixd);
1980
0
            ccbDestroy(&ccb);
1981
0
            return (PIX *)ERROR_PTR("boxa not found", __func__, NULL);
1982
0
        }
1983
1984
            /* Render border in pixt */
1985
0
        if ((ptaa = ccb->local) == NULL) {
1986
0
            L_WARNING("local chain array not found\n", __func__);
1987
0
            ccbDestroy(&ccb);
1988
0
            continue;
1989
0
        }
1990
1991
0
        nb = ptaaGetCount(ptaa);   /* number of borders in the c.c.  */
1992
0
        for (j = 0; j < nb; j++) {
1993
0
            if ((box = boxaGetBox(boxa, j, L_CLONE)) == NULL) {
1994
0
                pixDestroy(&pixd);
1995
0
                ccbDestroy(&ccb);
1996
0
                return (PIX *)ERROR_PTR("b. box not found", __func__, NULL);
1997
0
            }
1998
0
            if (j == 0) {
1999
0
                boxGetGeometry(box, &xul, &yul, &w, &h);
2000
0
                xoff = yoff = 0;
2001
0
            } else {
2002
0
                boxGetGeometry(box, &xoff, &yoff, &w, &h);
2003
0
            }
2004
0
            boxDestroy(&box);
2005
2006
                /* Render the border in a minimum-sized pix;
2007
                 * subtract xoff and yoff because the pixel
2008
                 * location is stored relative to the c.c., but
2009
                 * we need it relative to just the hole border. */
2010
0
            if ((pixt = pixCreate(w, h, 1)) == NULL) {
2011
0
                pixDestroy(&pixd);
2012
0
                ccbDestroy(&ccb);
2013
0
                return (PIX *)ERROR_PTR("pixt not made", __func__, NULL);
2014
0
            }
2015
0
            pta = ptaaGetPta(ptaa, j, L_CLONE);
2016
0
            n = ptaGetCount(pta);   /* number of pixels in the border */
2017
0
            for (k = 0; k < n; k++) {
2018
0
                ptaGetIPt(pta, k, &x, &y);
2019
0
                pixSetPixel(pixt, x - xoff, y - yoff, 1);
2020
0
                if (j > 0) {   /* need this for finding hole border pixel */
2021
0
                    if (k == 0) {
2022
0
                        fpx = x - xoff;
2023
0
                        fpy = y - yoff;
2024
0
                    }
2025
0
                    if (k == 1) {
2026
0
                        spx = x - xoff;
2027
0
                        spy = y - yoff;
2028
0
                    }
2029
0
                }
2030
0
            }
2031
0
            ptaDestroy(&pta);
2032
2033
                /* Get the filled component */
2034
0
            if (j == 0) {  /* if outer border, fill from outer boundary */
2035
0
                if ((pixh = pixFillClosedBorders(pixt, 4)) == NULL) {
2036
0
                    pixDestroy(&pixd);
2037
0
                    pixDestroy(&pixt);
2038
0
                    ccbDestroy(&ccb);
2039
0
                    return (PIX *)ERROR_PTR("pixh not made", __func__, NULL);
2040
0
                }
2041
0
            } else {   /* fill the hole from inside */
2042
                    /* get the location of a seed pixel in the hole */
2043
0
                locateOutsideSeedPixel(fpx, fpy, spx, spy, &xs, &ys);
2044
2045
                    /* Put seed in hole and fill interior of hole,
2046
                     * using pixt as clipping mask */
2047
0
                pixh = pixCreateTemplate(pixt);
2048
0
                pixSetPixel(pixh, xs, ys, 1);  /* put seed pixel in hole */
2049
0
                pixInvert(pixt, pixt);  /* to make filling mask */
2050
0
                pixSeedfillBinary(pixh, pixh, pixt, 4);  /* 4-fill hole */
2051
0
            }
2052
2053
                /* XOR into the dest */
2054
0
            pixRasterop(pixd, xul + xoff, yul + yoff, w, h, PIX_XOR,
2055
0
                        pixh, 0, 0);
2056
0
            pixDestroy(&pixt);
2057
0
            pixDestroy(&pixh);
2058
0
        }
2059
0
        ccbDestroy(&ccb);
2060
0
    }
2061
0
    return pixd;
2062
0
}
2063
2064
2065
2066
/*!
2067
 * \brief   ccbaDisplayImage2()
2068
 *
2069
 * \param[in]   ccba
2070
 * \return  pix of image, or NULL on error
2071
 *
2072
 * <pre>
2073
 * Notes:
2074
 *      (1) Uses local chain ptaa, which gives each border pixel in
2075
 *          local coordinates, so the actual pixel positions must
2076
 *          be computed using all offsets.
2077
 *      (2) Treats exterior and hole borders on equivalent
2078
 *          footing, and does all calculations on a pix
2079
 *          that spans the c.c. with a 1 pixel added boundary.
2080
 *      (3) This uses topological properties (Method 2) to do scan
2081
 *          conversion to raster
2082
 *      (4) The algorithm is described at the top of this file (Method 2).
2083
 *          It is preferred to Method 1 because it is between 1.2x and 2x
2084
 *          faster than Method 1.
2085
 * </pre>
2086
 */
2087
PIX *
2088
ccbaDisplayImage2(CCBORDA  *ccba)
2089
0
{
2090
0
l_int32  ncc, nb, n, i, j, k, x, y, xul, yul, w, h;
2091
0
l_int32  fpx, fpy, spx, spy, xs, ys;
2092
0
BOXA    *boxa;
2093
0
CCBORD  *ccb;
2094
0
PIX     *pixd, *pixc, *pixs;
2095
0
PTAA    *ptaa;
2096
0
PTA     *pta;
2097
2098
0
    if (!ccba)
2099
0
        return (PIX *)ERROR_PTR("ccba not defined", __func__, NULL);
2100
2101
0
    if ((pixd = pixCreate(ccba->w, ccba->h, 1)) == NULL)
2102
0
        return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
2103
0
    ncc = ccbaGetCount(ccba);
2104
0
    for (i = 0; i < ncc; i++) {
2105
            /* Generate clipping mask from border pixels and seed image
2106
             * from one seed for each closed border. */
2107
0
        ccb = ccbaGetCcb(ccba, i);
2108
0
        if ((boxa = ccb->boxa) == NULL) {
2109
0
            pixDestroy(&pixd);
2110
0
            ccbDestroy(&ccb);
2111
0
            return (PIX *)ERROR_PTR("boxa not found", __func__, NULL);
2112
0
        }
2113
0
        if (boxaGetBoxGeometry(boxa, 0, &xul, &yul, &w, &h)) {
2114
0
            pixDestroy(&pixd);
2115
0
            ccbDestroy(&ccb);
2116
0
            return (PIX *)ERROR_PTR("b. box not found", __func__, NULL);
2117
0
        }
2118
0
        pixc = pixCreate(w + 2, h + 2, 1);
2119
0
        pixs = pixCreateTemplate(pixc);
2120
2121
0
        if ((ptaa = ccb->local) == NULL) {
2122
0
            pixDestroy(&pixc);
2123
0
            pixDestroy(&pixs);
2124
0
            ccbDestroy(&ccb);
2125
0
            L_WARNING("local chain array not found\n", __func__);
2126
0
            continue;
2127
0
        }
2128
0
        nb = ptaaGetCount(ptaa);   /* number of borders in the c.c.  */
2129
0
        for (j = 0; j < nb; j++) {
2130
0
            pta = ptaaGetPta(ptaa, j, L_CLONE);
2131
0
            n = ptaGetCount(pta);   /* number of pixels in the border */
2132
2133
                /* Render border pixels in pixc */
2134
0
            for (k = 0; k < n; k++) {
2135
0
                ptaGetIPt(pta, k, &x, &y);
2136
0
                pixSetPixel(pixc, x + 1, y + 1, 1);
2137
0
                if (k == 0) {
2138
0
                    fpx = x + 1;
2139
0
                    fpy = y + 1;
2140
0
                } else if (k == 1) {
2141
0
                    spx = x + 1;
2142
0
                    spy = y + 1;
2143
0
                }
2144
0
            }
2145
2146
                /* Get and set seed pixel for this border in pixs */
2147
0
            if (n > 1)
2148
0
                locateOutsideSeedPixel(fpx, fpy, spx, spy, &xs, &ys);
2149
0
            else  /* isolated c.c. */
2150
0
                xs = ys = 0;
2151
0
            pixSetPixel(pixs, xs, ys, 1);
2152
0
            ptaDestroy(&pta);
2153
0
        }
2154
2155
            /* Fill from seeds in pixs, using pixc as the clipping mask,
2156
             * to reconstruct the c.c. */
2157
0
        pixInvert(pixc, pixc);  /* to convert clipping -> filling mask */
2158
0
        pixSeedfillBinary(pixs, pixs, pixc, 4);  /* 4-fill */
2159
0
        pixInvert(pixs, pixs);  /* to make the c.c. */
2160
2161
            /* XOR into the dest */
2162
0
        pixRasterop(pixd, xul, yul, w, h, PIX_XOR, pixs, 1, 1);
2163
2164
0
        pixDestroy(&pixc);
2165
0
        pixDestroy(&pixs);
2166
0
        ccbDestroy(&ccb);  /* ref-counted */
2167
0
    }
2168
0
    return pixd;
2169
0
}
2170
2171
2172
/*---------------------------------------------------------------------*
2173
 *                            Serialize for I/O                        *
2174
 *---------------------------------------------------------------------*/
2175
/*!
2176
 * \brief   ccbaWrite()
2177
 *
2178
 * \param[in]    filename
2179
 * \param[in]    ccba
2180
 * \return  0 if OK, 1 on error
2181
 */
2182
l_ok
2183
ccbaWrite(const char  *filename,
2184
          CCBORDA     *ccba)
2185
0
{
2186
0
FILE  *fp;
2187
2188
0
    if (!filename)
2189
0
        return ERROR_INT("filename not defined", __func__, 1);
2190
0
    if (!ccba)
2191
0
        return ERROR_INT("ccba not defined", __func__, 1);
2192
2193
0
    if ((fp = fopenWriteStream(filename, "wb+")) == NULL)
2194
0
        return ERROR_INT_1("stream not opened", filename, __func__, 1);
2195
0
    if (ccbaWriteStream(fp, ccba)) {
2196
0
        fclose(fp);
2197
0
        return ERROR_INT_1("ccba not written to stream", filename, __func__, 1);
2198
0
    }
2199
2200
0
    fclose(fp);
2201
0
    return 0;
2202
0
}
2203
2204
2205
2206
/*!
2207
 * \brief   ccbaWriteStream()
2208
 *
2209
 * \param[in]    fp       file stream
2210
 * \param[in]    ccba
2211
 * \return  0 if OK; 1 on error
2212
 *
2213
 *  Format:
2214
 * \code
2215
 *           ccba: %7d cc\n num. c.c.) (ascii)   (18B
2216
 *           pix width 4B
2217
 *           pix height 4B
2218
 *           [for i = 1, ncc]
2219
 *               ulx  4B
2220
 *               uly  4B
2221
 *               w    4B       -- not req'd for reconstruction
2222
 *               h    4B       -- not req'd for reconstruction
2223
 *               number of borders 4B
2224
 *               [for j = 1, nb]
2225
 *                   startx  4B
2226
 *                   starty  4B
2227
 *                   [for k = 1, nb]
2228
 *                        2 steps 1B
2229
 *                   end in z8 or 88  1B
2230
 * \endcode
2231
 */
2232
l_ok
2233
ccbaWriteStream(FILE     *fp,
2234
                CCBORDA  *ccba)
2235
0
{
2236
0
char        strbuf[256];
2237
0
l_uint8     bval;
2238
0
l_uint8    *datain, *dataout;
2239
0
l_int32     i, j, k, bx, by, bw, bh, val, startx, starty;
2240
0
l_int32     ncc, nb, n;
2241
0
l_uint32    w, h;
2242
0
size_t      inbytes, outbytes;
2243
0
L_BBUFFER  *bbuf;
2244
0
CCBORD     *ccb;
2245
0
NUMA       *na;
2246
0
NUMAA      *naa;
2247
0
PTA        *pta;
2248
2249
#if  !HAVE_LIBZ  /* defined in environ.h */
2250
    return ERROR_INT("no libz: can't write data", __func__, 1);
2251
#else
2252
2253
0
    if (!fp)
2254
0
        return ERROR_INT("stream not open", __func__, 1);
2255
0
    if (!ccba)
2256
0
        return ERROR_INT("ccba not defined", __func__, 1);
2257
2258
0
    if ((bbuf = bbufferCreate(NULL, 1000)) == NULL)
2259
0
        return ERROR_INT("bbuf not made", __func__, 1);
2260
2261
0
    ncc = ccbaGetCount(ccba);
2262
0
    snprintf(strbuf, sizeof(strbuf), "ccba: %7d cc\n", ncc);
2263
0
    bbufferRead(bbuf, (l_uint8 *)strbuf, 18);
2264
0
    w = pixGetWidth(ccba->pix);
2265
0
    h = pixGetHeight(ccba->pix);
2266
0
    bbufferRead(bbuf, (l_uint8 *)&w, 4);  /* width */
2267
0
    bbufferRead(bbuf, (l_uint8 *)&h, 4);  /* height */
2268
0
    for (i = 0; i < ncc; i++) {
2269
0
        ccb = ccbaGetCcb(ccba, i);
2270
0
        if (boxaGetBoxGeometry(ccb->boxa, 0, &bx, &by, &bw, &bh)) {
2271
0
            bbufferDestroy(&bbuf);
2272
0
            ccbDestroy(&ccb);
2273
0
            return ERROR_INT("bounding box not found", __func__, 1);
2274
0
        }
2275
0
        bbufferRead(bbuf, (l_uint8 *)&bx, 4);  /* ulx of c.c. */
2276
0
        bbufferRead(bbuf, (l_uint8 *)&by, 4);  /* uly of c.c. */
2277
0
        bbufferRead(bbuf, (l_uint8 *)&bw, 4);  /* w of c.c. */
2278
0
        bbufferRead(bbuf, (l_uint8 *)&bh, 4);  /* h of c.c. */
2279
0
        if ((naa = ccb->step) == NULL) {
2280
0
            ccbaGenerateStepChains(ccba);
2281
0
            naa = ccb->step;
2282
0
        }
2283
0
        nb = numaaGetCount(naa);
2284
0
        bbufferRead(bbuf, (l_uint8 *)&nb, 4);  /* number of borders in c.c. */
2285
0
        pta = ccb->start;
2286
0
        for (j = 0; j < nb; j++) {
2287
0
            ptaGetIPt(pta, j, &startx, &starty);
2288
0
            bbufferRead(bbuf, (l_uint8 *)&startx, 4); /* starting x in border */
2289
0
            bbufferRead(bbuf, (l_uint8 *)&starty, 4); /* starting y in border */
2290
0
            na = numaaGetNuma(naa, j, L_CLONE);
2291
0
            n = numaGetCount(na);
2292
0
            for (k = 0; k < n; k++) {
2293
0
                numaGetIValue(na, k, &val);
2294
0
                if (k % 2 == 0)
2295
0
                    bval = (l_uint8)val << 4;
2296
0
                else
2297
0
                    bval |= (l_uint8)val;
2298
0
                if (k % 2 == 1)
2299
0
                    bbufferRead(bbuf, (l_uint8 *)&bval, 1); /* 2 border steps */
2300
0
            }
2301
0
            if (n % 2 == 1) {
2302
0
                bval |= 0x8;
2303
0
                bbufferRead(bbuf, (l_uint8 *)&bval, 1); /* end with 0xz8,   */
2304
                                             /* where z = {0..7} */
2305
0
            } else {  /* n % 2 == 0 */
2306
0
                bval = 0x88;
2307
0
                bbufferRead(bbuf, (l_uint8 *)&bval, 1);   /* end with 0x88 */
2308
0
            }
2309
0
            numaDestroy(&na);
2310
0
        }
2311
0
        ccbDestroy(&ccb);
2312
0
    }
2313
2314
0
    datain = bbufferDestroyAndSaveData(&bbuf, &inbytes);
2315
0
    dataout = zlibCompress(datain, inbytes, &outbytes);
2316
0
    fwrite(dataout, 1, outbytes, fp);
2317
2318
0
    LEPT_FREE(datain);
2319
0
    LEPT_FREE(dataout);
2320
0
    return 0;
2321
2322
0
#endif  /* !HAVE_LIBZ */
2323
0
}
2324
2325
2326
/*!
2327
 * \brief   ccbaRead()
2328
 *
2329
 * \param[in]    filename
2330
 * \return  ccba, or NULL on error
2331
 */
2332
CCBORDA *
2333
ccbaRead(const char  *filename)
2334
0
{
2335
0
FILE     *fp;
2336
0
CCBORDA  *ccba;
2337
2338
0
    if (!filename)
2339
0
        return (CCBORDA *)ERROR_PTR("filename not defined", __func__, NULL);
2340
2341
0
    if ((fp = fopenReadStream(filename)) == NULL)
2342
0
        return (CCBORDA *)ERROR_PTR_1("stream not opened",
2343
0
                                      filename, __func__, NULL);
2344
0
    ccba = ccbaReadStream(fp);
2345
0
    fclose(fp);
2346
2347
0
    if (!ccba)
2348
0
        return (CCBORDA *)ERROR_PTR_1("ccba not returned",
2349
0
                                      filename, __func__, NULL);
2350
0
    return ccba;
2351
0
}
2352
2353
2354
/*!
2355
 * \brief   ccbaReadStream()
2356
 *
2357
 * \param[in]     fp     file stream
2358
 * \return   ccba, or NULL on error
2359
 *
2360
 * \code
2361
 *  Format:  ccba: %7d cc\n num. c.c.) (ascii)   (17B
2362
 *           pix width 4B
2363
 *           pix height 4B
2364
 *           [for i = 1, ncc]
2365
 *               ulx  4B
2366
 *               uly  4B
2367
 *               w    4B       -- not req'd for reconstruction
2368
 *               h    4B       -- not req'd for reconstruction
2369
 *               number of borders 4B
2370
 *               [for j = 1, nb]
2371
 *                   startx  4B
2372
 *                   starty  4B
2373
 *                   [for k = 1, nb]
2374
 *                        2 steps 1B
2375
 *                   end in z8 or 88  1B
2376
 * \endcode
2377
 */
2378
CCBORDA *
2379
ccbaReadStream(FILE  *fp)
2380
0
{
2381
0
char      strbuf[256];
2382
0
l_uint8   bval;
2383
0
l_uint8  *datain, *dataout;
2384
0
l_int32   i, j, startx, starty;
2385
0
l_int32   offset, nib1, nib2;
2386
0
l_int32   ncc, nb;
2387
0
l_uint32  width, height, w, h, xoff, yoff;
2388
0
size_t    inbytes, outbytes;
2389
0
BOX      *box;
2390
0
CCBORD   *ccb;
2391
0
CCBORDA  *ccba;
2392
0
NUMA     *na;
2393
0
NUMAA    *step;
2394
2395
#if  !HAVE_LIBZ  /* defined in environ.h */
2396
    return (CCBORDA *)ERROR_PTR("no libz: can't read data", __func__, NULL);
2397
#else
2398
2399
0
    if (!fp)
2400
0
        return (CCBORDA *)ERROR_PTR("stream not open", __func__, NULL);
2401
2402
0
    if ((datain = l_binaryReadStream(fp, &inbytes)) == NULL)
2403
0
        return (CCBORDA *)ERROR_PTR("data not read from file", __func__, NULL);
2404
0
    dataout = zlibUncompress(datain, inbytes, &outbytes);
2405
0
    LEPT_FREE(datain);
2406
0
    if (!dataout)
2407
0
        return (CCBORDA *)ERROR_PTR("dataout not made", __func__, NULL);
2408
2409
0
    offset = 18;
2410
0
    memcpy(strbuf, dataout, offset);
2411
0
    strbuf[17] = '\0';
2412
0
    if (memcmp(strbuf, "ccba:", 5) != 0) {
2413
0
        LEPT_FREE(dataout);
2414
0
        return (CCBORDA *)ERROR_PTR("file not type ccba", __func__, NULL);
2415
0
    }
2416
0
    sscanf(strbuf, "ccba: %7d cc\n", &ncc);
2417
/*    lept_stderr("ncc = %d\n", ncc); */
2418
0
    if ((ccba = ccbaCreate(NULL, ncc)) == NULL) {
2419
0
        LEPT_FREE(dataout);
2420
0
        return (CCBORDA *)ERROR_PTR("ccba not made", __func__, NULL);
2421
0
    }
2422
2423
0
    memcpy(&width, dataout + offset, 4);
2424
0
    offset += 4;
2425
0
    memcpy(&height, dataout + offset, 4);
2426
0
    offset += 4;
2427
0
    ccba->w = width;
2428
0
    ccba->h = height;
2429
/*    lept_stderr("width = %d, height = %d\n", width, height); */
2430
2431
0
    for (i = 0; i < ncc; i++) {  /* should be ncc */
2432
0
        ccb = ccbCreate(NULL);
2433
0
        ccbaAddCcb(ccba, ccb);
2434
2435
0
        memcpy(&xoff, dataout + offset, 4);
2436
0
        offset += 4;
2437
0
        memcpy(&yoff, dataout + offset, 4);
2438
0
        offset += 4;
2439
0
        memcpy(&w, dataout + offset, 4);
2440
0
        offset += 4;
2441
0
        memcpy(&h, dataout + offset, 4);
2442
0
        offset += 4;
2443
0
        box = boxCreate(xoff, yoff, w, h);
2444
0
        boxaAddBox(ccb->boxa, box, L_INSERT);
2445
/*        lept_stderr("xoff = %d, yoff = %d, w = %d, h = %d\n",
2446
                xoff, yoff, w, h); */
2447
2448
0
        memcpy(&nb, dataout + offset, 4);
2449
0
        offset += 4;
2450
/*        lept_stderr("num borders = %d\n", nb); */
2451
0
        step = numaaCreate(nb);
2452
0
        ccb->step = step;
2453
2454
0
        for (j = 0; j < nb; j++) {  /* should be nb */
2455
0
            memcpy(&startx, dataout + offset, 4);
2456
0
            offset += 4;
2457
0
            memcpy(&starty, dataout + offset, 4);
2458
0
            offset += 4;
2459
0
            ptaAddPt(ccb->start, startx, starty);
2460
/*            lept_stderr("startx = %d, starty = %d\n", startx, starty); */
2461
0
            na = numaCreate(0);
2462
0
            numaaAddNuma(step, na, L_INSERT);
2463
2464
0
            while(1) {
2465
0
                bval = *(dataout + offset);
2466
0
                offset++;
2467
0
                nib1 = (bval >> 4);
2468
0
                nib2 = bval & 0xf;
2469
0
                if (nib1 != 8)
2470
0
                    numaAddNumber(na, nib1);
2471
0
                else
2472
0
                    break;
2473
0
                if (nib2 != 8)
2474
0
                    numaAddNumber(na, nib2);
2475
0
                else
2476
0
                    break;
2477
0
            }
2478
0
        }
2479
0
    }
2480
0
    LEPT_FREE(dataout);
2481
0
    return ccba;
2482
2483
0
#endif  /* !HAVE_LIBZ */
2484
0
}
2485
2486
2487
/*---------------------------------------------------------------------*
2488
 *                                SVG Output                           *
2489
 *---------------------------------------------------------------------*/
2490
/*!
2491
 * \brief   ccbaWriteSVG()
2492
 *
2493
 * \param[in]    filename
2494
 * \param[in]    ccba
2495
 * \return  0 if OK, 1 on error
2496
 */
2497
l_ok
2498
ccbaWriteSVG(const char  *filename,
2499
             CCBORDA     *ccba)
2500
0
{
2501
0
char  *svgstr;
2502
2503
0
    if (!filename)
2504
0
        return ERROR_INT("filename not defined", __func__, 1);
2505
0
    if (!ccba)
2506
0
        return ERROR_INT("ccba not defined", __func__, 1);
2507
2508
0
    if ((svgstr = ccbaWriteSVGString(ccba)) == NULL)
2509
0
        return ERROR_INT("svgstr not made", __func__, 1);
2510
2511
0
    l_binaryWrite(filename, "w", svgstr, strlen(svgstr));
2512
0
    LEPT_FREE(svgstr);
2513
2514
0
    return 0;
2515
0
}
2516
2517
2518
/*!
2519
 * \brief   ccbaWriteSVGString()
2520
 *
2521
 * \param[in]    ccba
2522
 * \return  string in svg-formatted, that can be written to file,
2523
 *              or NULL on error.
2524
 */
2525
char  *
2526
ccbaWriteSVGString(CCBORDA *ccba)
2527
0
{
2528
0
char    *svgstr;
2529
0
char     smallbuf[256];
2530
0
char     line0[] = "<?xml version=\"1.0\" encoding=\"iso-8859-1\"?>";
2531
0
char     line1[] = "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 20000303 Stylable//EN\" \"http://www.w3.org/TR/2000/03/WD-SVG-20000303/DTD/svg-20000303-stylable.dtd\">";
2532
0
char     line2[] = "<svg>";
2533
0
char     line3[] = "<polygon style=\"stroke-width:1;stroke:black;\" points=\"";
2534
0
char     line4[] = "\" />";
2535
0
char     line5[] = "</svg>";
2536
0
char     space[] = " ";
2537
0
l_int32  i, j, ncc, npt, x, y;
2538
0
CCBORD  *ccb;
2539
0
PTA     *pta;
2540
0
SARRAY  *sa;
2541
2542
0
    if (!ccba)
2543
0
        return (char *)ERROR_PTR("ccba not defined", __func__, NULL);
2544
2545
0
    sa = sarrayCreate(0);
2546
0
    sarrayAddString(sa, line0, L_COPY);
2547
0
    sarrayAddString(sa, line1, L_COPY);
2548
0
    sarrayAddString(sa, line2, L_COPY);
2549
0
    ncc = ccbaGetCount(ccba);
2550
0
    for (i = 0; i < ncc; i++) {
2551
0
        if ((ccb = ccbaGetCcb(ccba, i)) == NULL) {
2552
0
            sarrayDestroy(&sa);
2553
0
            return (char *)ERROR_PTR("ccb not found", __func__, NULL);
2554
0
        }
2555
0
        if ((pta = ccb->spglobal) == NULL) {
2556
0
            sarrayDestroy(&sa);
2557
0
            ccbDestroy(&ccb);
2558
0
            return (char *)ERROR_PTR("spglobal not made", __func__, NULL);
2559
0
        }
2560
0
        sarrayAddString(sa, line3, L_COPY);
2561
0
        npt = ptaGetCount(pta);
2562
0
        for (j = 0; j < npt; j++) {
2563
0
            ptaGetIPt(pta, j, &x, &y);
2564
0
            snprintf(smallbuf, sizeof(smallbuf), "%0d,%0d", x, y);
2565
0
            sarrayAddString(sa, smallbuf, L_COPY);
2566
0
        }
2567
0
        sarrayAddString(sa, line4, L_COPY);
2568
0
        ccbDestroy(&ccb);
2569
0
    }
2570
0
    sarrayAddString(sa, line5, L_COPY);
2571
0
    sarrayAddString(sa, space, L_COPY);
2572
2573
0
    svgstr = sarrayToString(sa, 1);
2574
/*    lept_stderr("%s", svgstr); */
2575
2576
0
    sarrayDestroy(&sa);
2577
0
    return svgstr;
2578
0
}