Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/ccbord.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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 {
322 CCBORDA *ccba;
323
324 if (n <= 0)
325 n = INITIAL_PTR_ARRAYSIZE;
326
327 ccba = (CCBORDA *)LEPT_CALLOC(1, sizeof(CCBORDA));
328 if (pixs) {
329 ccba->pix = pixClone(pixs);
330 ccba->w = pixGetWidth(pixs);
331 ccba->h = pixGetHeight(pixs);
332 }
333 ccba->n = 0;
334 ccba->nalloc = n;
335 if ((ccba->ccb = (CCBORD **)LEPT_CALLOC(n, sizeof(CCBORD *))) == NULL) {
336 ccbaDestroy(&ccba);
337 return (CCBORDA *)ERROR_PTR("ccba ptrs not made", __func__, NULL);
338 }
339 return ccba;
340 }
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 {
352 l_int32 i;
353 CCBORDA *ccba;
354
355 if (pccba == NULL) {
356 L_WARNING("ptr address is NULL!\n", __func__);
357 return;
358 }
359
360 if ((ccba = *pccba) == NULL)
361 return;
362
363 pixDestroy(&ccba->pix);
364 for (i = 0; i < ccba->n; i++)
365 ccbDestroy(&ccba->ccb[i]);
366 LEPT_FREE(ccba->ccb);
367 LEPT_FREE(ccba);
368 *pccba = NULL;
369 }
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 {
381 BOXA *boxa;
382 CCBORD *ccb;
383 PTA *start;
384 PTAA *local;
385
386 if (pixs && pixGetDepth(pixs) != 1) /* pixs can be null */
387 return (CCBORD *)ERROR_PTR("pixs defined and not 1bpp", __func__, NULL);
388
389 ccb = (CCBORD *)LEPT_CALLOC(1, sizeof(CCBORD));
390 ccb->refcount = 1;
391 if (pixs)
392 ccb->pix = pixClone(pixs);
393 boxa = boxaCreate(1);
394 ccb->boxa = boxa;
395 start = ptaCreate(1);
396 ccb->start = start;
397 local = ptaaCreate(1);
398 ccb->local = local;
399 return ccb;
400 }
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 {
412 CCBORD *ccb;
413
414 if (pccb == NULL) {
415 L_WARNING("ptr address is NULL!\n", __func__);
416 return;
417 }
418
419 if ((ccb = *pccb) == NULL)
420 return;
421
422 if (--ccb->refcount == 0) {
423 if (ccb->pix)
424 pixDestroy(&ccb->pix);
425 if (ccb->boxa)
426 boxaDestroy(&ccb->boxa);
427 if (ccb->start)
428 ptaDestroy(&ccb->start);
429 if (ccb->local)
430 ptaaDestroy(&ccb->local);
431 if (ccb->global)
432 ptaaDestroy(&ccb->global);
433 if (ccb->step)
434 numaaDestroy(&ccb->step);
435 if (ccb->splocal)
436 ptaDestroy(&ccb->splocal);
437 if (ccb->spglobal)
438 ptaDestroy(&ccb->spglobal);
439 LEPT_FREE(ccb);
440 *pccb = NULL;
441 }
442 }
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 {
459 l_int32 n;
460
461 if (!ccba)
462 return ERROR_INT("ccba not defined", __func__, 1);
463 if (!ccb)
464 return ERROR_INT("ccb not defined", __func__, 1);
465
466 n = ccbaGetCount(ccba);
467 if (n >= ccba->nalloc) {
468 if (ccbaExtendArray(ccba))
469 return ERROR_INT("extension failed", __func__, 1);
470 }
471 ccba->ccb[n] = ccb;
472 ccba->n++;
473 return 0;
474 }
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 {
486 if (!ccba)
487 return ERROR_INT("ccba not defined", __func__, 1);
488
489 if ((ccba->ccb = (CCBORD **)reallocNew((void **)&ccba->ccb,
490 sizeof(CCBORD *) * ccba->nalloc,
491 2 * sizeof(CCBORD *) * ccba->nalloc)) == NULL)
492 return ERROR_INT("new ptr array not returned", __func__, 1);
493
494 ccba->nalloc = 2 * ccba->nalloc;
495 return 0;
496 }
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 {
512
513 if (!ccba)
514 return ERROR_INT("ccba not defined", __func__, 0);
515
516 return ccba->n;
517 }
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 {
536 CCBORD *ccb;
537
538 if (!ccba)
539 return (CCBORD *)ERROR_PTR("ccba not defined", __func__, NULL);
540 if (index < 0 || index >= ccba->n)
541 return (CCBORD *)ERROR_PTR("index out of bounds", __func__, NULL);
542
543 ccb = ccba->ccb[index];
544 ccb->refcount++;
545 return ccb;
546 }
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 {
562 l_int32 n, i;
563 BOX *box;
564 BOXA *boxa;
565 CCBORDA *ccba;
566 CCBORD *ccb;
567 PIX *pix;
568 PIXA *pixa;
569
570 if (!pixs)
571 return (CCBORDA *)ERROR_PTR("pixs not defined", __func__, NULL);
572 if (pixGetDepth(pixs) != 1)
573 return (CCBORDA *)ERROR_PTR("pixs not binary", __func__, NULL);
574
575 if ((boxa = pixConnComp(pixs, &pixa, 8)) == NULL)
576 return (CCBORDA *)ERROR_PTR("boxa not made", __func__, NULL);
577 n = boxaGetCount(boxa);
578
579 if ((ccba = ccbaCreate(pixs, n)) == NULL) {
580 boxaDestroy(&boxa);
581 pixaDestroy(&pixa);
582 return (CCBORDA *)ERROR_PTR("ccba not made", __func__, NULL);
583 }
584 for (i = 0; i < n; i++) {
585 if ((pix = pixaGetPix(pixa, i, L_CLONE)) == NULL) {
586 ccbaDestroy(&ccba);
587 pixaDestroy(&pixa);
588 boxaDestroy(&boxa);
589 return (CCBORDA *)ERROR_PTR("pix not found", __func__, NULL);
590 }
591 if ((box = pixaGetBox(pixa, i, L_CLONE)) == NULL) {
592 ccbaDestroy(&ccba);
593 pixaDestroy(&pixa);
594 boxaDestroy(&boxa);
595 pixDestroy(&pix);
596 return (CCBORDA *)ERROR_PTR("box not found", __func__, NULL);
597 }
598 ccb = pixGetCCBorders(pix, box);
599 pixDestroy(&pix);
600 boxDestroy(&box);
601 if (!ccb) {
602 ccbaDestroy(&ccba);
603 pixaDestroy(&pixa);
604 boxaDestroy(&boxa);
605 return (CCBORDA *)ERROR_PTR("ccb not made", __func__, NULL);
606 }
607 /* ptaWriteStream(stderr, ccb->local, 1); */
608 ccbaAddCcb(ccba, ccb);
609 }
610
611 boxaDestroy(&boxa);
612 pixaDestroy(&pixa);
613 return ccba;
614 }
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 {
647 l_int32 allzero, i, x, xh, w, nh;
648 l_int32 xs, ys; /* starting hole border pixel, relative in pixs */
649 l_uint32 val;
650 BOX *boxt, *boxe;
651 BOXA *boxa;
652 CCBORD *ccb;
653 PIX *pixh; /* for hole components */
654 PIX *pixt;
655 PIXA *pixa;
656
657 if (!pixs)
658 return (CCBORD *)ERROR_PTR("pixs not defined", __func__, NULL);
659 if (!box)
660 return (CCBORD *)ERROR_PTR("box not defined", __func__, NULL);
661 if (pixGetDepth(pixs) != 1)
662 return (CCBORD *)ERROR_PTR("pixs not binary", __func__, NULL);
663
664 pixZero(pixs, &allzero);
665 if (allzero)
666 return (CCBORD *)ERROR_PTR("pixs all 0", __func__, NULL);
667
668 if ((ccb = ccbCreate(pixs)) == NULL)
669 return (CCBORD *)ERROR_PTR("ccb not made", __func__, NULL);
670
671 /* Get the exterior border */
672 pixGetOuterBorder(ccb, pixs, box);
673
674 /* Find the holes, if any */
675 if ((pixh = pixHolesByFilling(pixs, 4)) == NULL) {
676 ccbDestroy(&ccb);
677 return (CCBORD *)ERROR_PTR("pixh not made", __func__, NULL);
678 }
679 pixZero(pixh, &allzero);
680 if (allzero) { /* no holes */
681 pixDestroy(&pixh);
682 return ccb;
683 }
684
685 /* Get c.c. and locations of the holes */
686 if ((boxa = pixConnComp(pixh, &pixa, 4)) == NULL) {
687 ccbDestroy(&ccb);
688 pixDestroy(&pixh);
689 return (CCBORD *)ERROR_PTR("boxa not made", __func__, NULL);
690 }
691 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 w = pixGetWidth(pixs);
705 for (i = 0; i < nh; i++) {
706 boxt = boxaGetBox(boxa, i, L_CLONE);
707 pixt = pixaGetPix(pixa, i, L_CLONE);
708 ys = boxt->y; /* there must be a hole pixel on this raster line */
709 for (x = 0; x < boxt->w; x++) { /* look for (fg) hole pixel */
710 pixGetPixel(pixt, x, 0, &val);
711 if (val == 1) {
712 xh = x;
713 break;
714 }
715 }
716 if (x == boxt->w) {
717 L_WARNING("no hole pixel found!\n", __func__);
718 continue;
719 }
720 for (x = xh + boxt->x; x < w; x++) { /* look for (fg) border pixel */
721 pixGetPixel(pixs, x, ys, &val);
722 if (val == 1) {
723 xs = x;
724 break;
725 }
726 }
727 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 pixGetHoleBorder(ccb, pixs, boxe, xs, ys);
734 boxDestroy(&boxt);
735 boxDestroy(&boxe);
736 pixDestroy(&pixt);
737 }
738
739 boxaDestroy(&boxa);
740 pixaDestroy(&pixa);
741 pixDestroy(&pixh);
742 return ccb;
743 }
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 {
755 l_int32 i, n;
756 BOX *box;
757 BOXA *boxa;
758 PIX *pix;
759 PIXA *pixa;
760 PTA *pta;
761 PTAA *ptaa;
762
763 if (!pixs)
764 return (PTAA *)ERROR_PTR("pixs not defined", __func__, NULL);
765 if (pixGetDepth(pixs) != 1)
766 return (PTAA *)ERROR_PTR("pixs not binary", __func__, NULL);
767
768 boxa = pixConnComp(pixs, &pixa, 8);
769 n = boxaGetCount(boxa);
770 if (n == 0) {
771 boxaDestroy(&boxa);
772 pixaDestroy(&pixa);
773 return (PTAA *)ERROR_PTR("pixs empty", __func__, NULL);
774 }
775
776 ptaa = ptaaCreate(n);
777 for (i = 0; i < n; i++) {
778 box = boxaGetBox(boxa, i, L_CLONE);
779 pix = pixaGetPix(pixa, i, L_CLONE);
780 pta = pixGetOuterBorderPta(pix, box);
781 if (pta)
782 ptaaAddPta(ptaa, pta, L_INSERT);
783 boxDestroy(&box);
784 pixDestroy(&pix);
785 }
786
787 pixaDestroy(&pixa);
788 boxaDestroy(&boxa);
789 return ptaa;
790 }
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 {
814 l_int32 allzero, x, y;
815 BOX *boxt;
816 CCBORD *ccb;
817 PTA *ptaloc, *ptad;
818
819 if (!pixs)
820 return (PTA *)ERROR_PTR("pixs not defined", __func__, NULL);
821 if (pixGetDepth(pixs) != 1)
822 return (PTA *)ERROR_PTR("pixs not binary", __func__, NULL);
823
824 pixZero(pixs, &allzero);
825 if (allzero)
826 return (PTA *)ERROR_PTR("pixs all 0", __func__, NULL);
827
828 if ((ccb = ccbCreate(pixs)) == NULL)
829 return (PTA *)ERROR_PTR("ccb not made", __func__, NULL);
830 if (!box)
831 boxt = boxCreate(0, 0, pixGetWidth(pixs), pixGetHeight(pixs));
832 else
833 boxt = boxClone(box);
834
835 /* Get the exterior border in local coords */
836 pixGetOuterBorder(ccb, pixs, boxt);
837 if ((ptaloc = ptaaGetPta(ccb->local, 0, L_CLONE)) == NULL) {
838 ccbDestroy(&ccb);
839 boxDestroy(&boxt);
840 return (PTA *)ERROR_PTR("ptaloc not made", __func__, NULL);
841 }
842
843 /* Transform to global coordinates, if they are given */
844 if (box) {
845 boxGetGeometry(box, &x, &y, NULL, NULL);
846 ptad = ptaTransform(ptaloc, x, y, 1.0, 1.0);
847 } else {
848 ptad = ptaClone(ptaloc);
849 }
850
851 ptaDestroy(&ptaloc);
852 boxDestroy(&boxt);
853 ccbDestroy(&ccb);
854 return ptad;
855 }
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 {
886 l_int32 fpx, fpy, spx, spy, qpos;
887 l_int32 px, py, npx, npy;
888 l_int32 w, h, wpl;
889 l_uint32 *data;
890 PTA *pta;
891 PIX *pixb; /* with 1 pixel border */
892
893 if (!ccb)
894 return ERROR_INT("ccb not defined", __func__, 1);
895 if (!pixs)
896 return ERROR_INT("pixs not defined", __func__, 1);
897 if (!box)
898 return ERROR_INT("box not defined", __func__, 1);
899
900 /* Add 1-pixel border all around, and find start pixel */
901 if ((pixb = pixAddBorder(pixs, 1, 0)) == NULL)
902 return ERROR_INT("pixs not made", __func__, 1);
903 if (!nextOnPixelInRaster(pixb, 1, 1, &px, &py)) {
904 pixDestroy(&pixb);
905 return ERROR_INT("no start pixel found", __func__, 1);
906 }
907 qpos = 0; /* relative to p */
908 fpx = px; /* save location of first pixel on border */
909 fpy = py;
910
911 /* Save box and start pixel in relative coords */
912 boxaAddBox(ccb->boxa, box, L_COPY);
913 ptaAddPt(ccb->start, px - 1, py - 1);
914
915 pta = ptaCreate(0);
916 ptaaAddPta(ccb->local, pta, L_INSERT);
917 ptaAddPt(pta, px - 1, py - 1); /* initial point */
918 pixGetDimensions(pixb, &w, &h, NULL);
919 data = pixGetData(pixb);
920 wpl = pixGetWpl(pixb);
921
922 /* Get the second point; if there is none, return */
923 if (findNextBorderPixel(w, h, data, wpl, px, py, &qpos, &npx, &npy)) {
924 pixDestroy(&pixb);
925 return 0;
926 }
927
928 spx = npx; /* save location of second pixel on border */
929 spy = npy;
930 ptaAddPt(pta, npx - 1, npy - 1); /* second point */
931 px = npx;
932 py = npy;
933
934 while (1) {
935 findNextBorderPixel(w, h, data, wpl, px, py, &qpos, &npx, &npy);
936 if (px == fpx && py == fpy && npx == spx && npy == spy)
937 break;
938 ptaAddPt(pta, npx - 1, npy - 1);
939 px = npx;
940 py = npy;
941 }
942
943 pixDestroy(&pixb);
944 return 0;
945 }
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 {
974 l_int32 fpx, fpy, spx, spy, qpos;
975 l_int32 px, py, npx, npy;
976 l_int32 w, h, wpl;
977 l_uint32 *data;
978 PTA *pta;
979
980 if (!ccb)
981 return ERROR_INT("ccb not defined", __func__, 1);
982 if (!pixs)
983 return ERROR_INT("pixs not defined", __func__, 1);
984 if (!box)
985 return ERROR_INT("box not defined", __func__, 1);
986
987 /* Add border and find start pixel */
988 qpos = 0; /* orientation of Q relative to P */
989 fpx = xs; /* save location of first pixel on border */
990 fpy = ys;
991
992 /* Save box and start pixel */
993 boxaAddBox(ccb->boxa, box, L_COPY);
994 ptaAddPt(ccb->start, xs, ys);
995
996 pta = ptaCreate(0);
997 ptaaAddPta(ccb->local, pta, L_INSERT);
998 ptaAddPt(pta, xs, ys); /* initial pixel */
999
1000 w = pixGetWidth(pixs);
1001 h = pixGetHeight(pixs);
1002 data = pixGetData(pixs);
1003 wpl = pixGetWpl(pixs);
1004
1005 /* Get the second point; there should always be at least 4 pts
1006 * in a minimal hole border! */
1007 if (findNextBorderPixel(w, h, data, wpl, xs, ys, &qpos, &npx, &npy))
1008 return ERROR_INT("isolated hole border point!", __func__, 1);
1009
1010 spx = npx; /* save location of second pixel on border */
1011 spy = npy;
1012 ptaAddPt(pta, npx, npy); /* second pixel */
1013 px = npx;
1014 py = npy;
1015
1016 while (1) {
1017 findNextBorderPixel(w, h, data, wpl, px, py, &qpos, &npx, &npy);
1018 if (px == fpx && py == fpy && npx == spx && npy == spy)
1019 break;
1020 ptaAddPt(pta, npx, npy);
1021 px = npx;
1022 py = npy;
1023 }
1024
1025 return 0;
1026 }
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 {
1058 l_int32 qpos, i, pos, npx, npy, val;
1059 l_uint32 *line;
1060
1061 qpos = *pqpos;
1062 for (i = 1; i < 8; i++) {
1063 pos = (qpos + i) % 8;
1064 npx = px + xpostab[pos];
1065 npy = py + ypostab[pos];
1066 if (npx < 0 || npx >= w || npy < 0 || npy >= h)
1067 continue;
1068 line = data + npy * wpl;
1069 val = GET_DATA_BIT(line, npx);
1070 if (val) {
1071 *pnpx = npx;
1072 *pnpy = npy;
1073 *pqpos = qpostab[pos];
1074 return 0;
1075 }
1076 }
1077
1078 return 1;
1079 }
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 {
1108 l_int32 dx, dy;
1109
1110 dx = spx - fpx;
1111 dy = spy - fpy;
1112
1113 if (dx * dy == 1) {
1114 *pxs = fpx + dx;
1115 *pys = fpy;
1116 } else if (dx * dy == -1) {
1117 *pxs = fpx;
1118 *pys = fpy + dy;
1119 } else if (dx == 0) {
1120 *pxs = fpx + dy;
1121 *pys = fpy + dy;
1122 } else /* dy == 0 */ {
1123 *pxs = fpx + dx;
1124 *pys = fpy - dx;
1125 }
1126
1127 return;
1128 }
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 {
1151 l_int32 ncc, nb, n, i, j, k, xul, yul, x, y;
1152 CCBORD *ccb;
1153 PTAA *ptaal, *ptaag;
1154 PTA *ptal, *ptag;
1155
1156 if (!ccba)
1157 return ERROR_INT("ccba not defined", __func__, 1);
1158
1159 ncc = ccbaGetCount(ccba); /* number of c.c. */
1160 for (i = 0; i < ncc; i++) {
1161 ccb = ccbaGetCcb(ccba, i);
1162
1163 /* Get the UL corner in global coords, (xul, yul), of the c.c. */
1164 boxaGetBoxGeometry(ccb->boxa, 0, &xul, &yul, NULL, NULL);
1165
1166 /* Make a new global ptaa, removing any old one */
1167 ptaal = ccb->local;
1168 nb = ptaaGetCount(ptaal); /* number of borders */
1169 if (ccb->global) /* remove old one */
1170 ptaaDestroy(&ccb->global);
1171 if ((ptaag = ptaaCreate(nb)) == NULL) {
1172 ccbDestroy(&ccb);
1173 return ERROR_INT("ptaag not made", __func__, 1);
1174 }
1175 ccb->global = ptaag; /* save new one */
1176
1177 /* Iterate through the borders for this c.c. */
1178 for (j = 0; j < nb; j++) {
1179 ptal = ptaaGetPta(ptaal, j, L_CLONE);
1180 n = ptaGetCount(ptal); /* number of pixels in border */
1181 ptag = ptaCreate(n);
1182 ptaaAddPta(ptaag, ptag, L_INSERT);
1183 for (k = 0; k < n; k++) {
1184 ptaGetIPt(ptal, k, &x, &y);
1185 ptaAddPt(ptag, x + xul, y + yul);
1186 }
1187 ptaDestroy(&ptal);
1188 }
1189 ccbDestroy(&ccb);
1190 }
1191
1192 return 0;
1193 }
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 {
1221 l_int32 ncc, nb, n, i, j, k;
1222 l_int32 px, py, cx, cy, stepdir;
1223 l_int32 dirtab[][3] = {{1, 2, 3}, {0, -1, 4}, {7, 6, 5}};
1224 CCBORD *ccb;
1225 NUMA *na;
1226 NUMAA *naa; /* step chain code; to be made */
1227 PTA *ptal;
1228 PTAA *ptaal; /* local chain code */
1229
1230 if (!ccba)
1231 return ERROR_INT("ccba not defined", __func__, 1);
1232
1233 ncc = ccbaGetCount(ccba); /* number of c.c. */
1234 for (i = 0; i < ncc; i++) {
1235 ccb = ccbaGetCcb(ccba, i);
1236
1237 /* Make a new step numaa, removing any old one */
1238 ptaal = ccb->local;
1239 nb = ptaaGetCount(ptaal); /* number of borders */
1240 if (ccb->step) /* remove old one */
1241 numaaDestroy(&ccb->step);
1242 if ((naa = numaaCreate(nb)) == NULL) {
1243 ccbDestroy(&ccb);
1244 return ERROR_INT("naa not made", __func__, 1);
1245 }
1246 ccb->step = naa; /* save new one */
1247
1248 /* Iterate through the borders for this c.c. */
1249 for (j = 0; j < nb; j++) {
1250 ptal = ptaaGetPta(ptaal, j, L_CLONE);
1251 n = ptaGetCount(ptal); /* number of pixels in border */
1252 if (n == 1) { /* isolated pixel */
1253 na = numaCreate(1); /* but leave it empty */
1254 } else { /* trace out the boundary */
1255 na = numaCreate(n);
1256 ptaGetIPt(ptal, 0, &px, &py);
1257 for (k = 1; k < n; k++) {
1258 ptaGetIPt(ptal, k, &cx, &cy);
1259 stepdir = dirtab[1 + cy - py][1 + cx - px];
1260 numaAddNumber(na, stepdir);
1261 px = cx;
1262 py = cy;
1263 }
1264 }
1265 numaaAddNuma(naa, na, L_INSERT);
1266 ptaDestroy(&ptal);
1267 }
1268 ccbDestroy(&ccb); /* just decrement refcount */
1269 }
1270
1271 return 0;
1272 }
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 {
1295 l_int32 ncc, nb, n, i, j, k;
1296 l_int32 xul, yul, xstart, ystart, x, y, stepdir;
1297 BOXA *boxa;
1298 CCBORD *ccb;
1299 NUMA *na;
1300 NUMAA *naa;
1301 PTAA *ptaan; /* new pix coord ptaa */
1302 PTA *ptas, *ptan;
1303
1304 if (!ccba)
1305 return ERROR_INT("ccba not defined", __func__, 1);
1306 if (coordtype != CCB_GLOBAL_COORDS && coordtype != CCB_LOCAL_COORDS)
1307 return ERROR_INT("coordtype not valid", __func__, 1);
1308
1309 ncc = ccbaGetCount(ccba); /* number of c.c. */
1310 for (i = 0; i < ncc; i++) {
1311 ccb = ccbaGetCcb(ccba, i);
1312 if ((naa = ccb->step) == NULL) {
1313 ccbDestroy(&ccb);
1314 return ERROR_INT("step numaa not found", __func__, 1);
1315 } if ((boxa = ccb->boxa) == NULL) {
1316 ccbDestroy(&ccb);
1317 return ERROR_INT("boxa not found", __func__, 1);
1318 } if ((ptas = ccb->start) == NULL) {
1319 ccbDestroy(&ccb);
1320 return ERROR_INT("start pta not found", __func__, 1);
1321 }
1322
1323 /* For global coords, get the (xul, yul) of the c.c.;
1324 * otherwise, use relative coords. */
1325 if (coordtype == CCB_LOCAL_COORDS) {
1326 xul = 0;
1327 yul = 0;
1328 } else { /* coordtype == CCB_GLOBAL_COORDS */
1329 /* Get UL corner in global coords */
1330 if (boxaGetBoxGeometry(boxa, 0, &xul, &yul, NULL, NULL)) {
1331 ccbDestroy(&ccb);
1332 return ERROR_INT("bounding rectangle not found", __func__, 1);
1333 }
1334 }
1335
1336 /* Make a new ptaa, removing any old one */
1337 nb = numaaGetCount(naa); /* number of borders */
1338 if ((ptaan = ptaaCreate(nb)) == NULL) {
1339 ccbDestroy(&ccb);
1340 return ERROR_INT("ptaan not made", __func__, 1);
1341 }
1342 if (coordtype == CCB_LOCAL_COORDS) {
1343 if (ccb->local) /* remove old one */
1344 ptaaDestroy(&ccb->local);
1345 ccb->local = ptaan; /* save new local chain */
1346 } else { /* coordtype == CCB_GLOBAL_COORDS */
1347 if (ccb->global) /* remove old one */
1348 ptaaDestroy(&ccb->global);
1349 ccb->global = ptaan; /* save new global chain */
1350 }
1351
1352 /* Iterate through the borders for this c.c. */
1353 for (j = 0; j < nb; j++) {
1354 na = numaaGetNuma(naa, j, L_CLONE);
1355 n = numaGetCount(na); /* number of steps in border */
1356 if ((ptan = ptaCreate(n + 1)) == NULL) {
1357 ccbDestroy(&ccb);
1358 numaDestroy(&na);
1359 return ERROR_INT("ptan not made", __func__, 1);
1360 }
1361 ptaaAddPta(ptaan, ptan, L_INSERT);
1362 ptaGetIPt(ptas, j, &xstart, &ystart);
1363 x = xul + xstart;
1364 y = yul + ystart;
1365 ptaAddPt(ptan, x, y);
1366 for (k = 0; k < n; k++) {
1367 numaGetIValue(na, k, &stepdir);
1368 x += xpostab[stepdir];
1369 y += ypostab[stepdir];
1370 ptaAddPt(ptan, x, y);
1371 }
1372 numaDestroy(&na);
1373 }
1374 ccbDestroy(&ccb);
1375 }
1376
1377 return 0;
1378 }
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 {
1404 l_int32 ncc, npt, i, j, xul, yul, x, y, delx, dely;
1405 l_int32 xp, yp, delxp, delyp; /* prev point and increments */
1406 CCBORD *ccb;
1407 PTA *ptal, *ptag;
1408
1409 if (!ccba)
1410 return ERROR_INT("ccba not defined", __func__, 1);
1411
1412 /* Make sure we have a local single path representation */
1413 if ((ccb = ccbaGetCcb(ccba, 0)) == NULL)
1414 return ERROR_INT("no ccb", __func__, 1);
1415 if (!ccb->splocal)
1416 ccbaGenerateSinglePath(ccba);
1417 ccbDestroy(&ccb); /* clone ref */
1418
1419 ncc = ccbaGetCount(ccba); /* number of c.c. */
1420 for (i = 0; i < ncc; i++) {
1421 ccb = ccbaGetCcb(ccba, i);
1422
1423 /* Get the UL corner in global coords, (xul, yul), of the c.c. */
1424 if (boxaGetBoxGeometry(ccb->boxa, 0, &xul, &yul, NULL, NULL)) {
1425 ccbDestroy(&ccb);
1426 return ERROR_INT("bounding rectangle not found", __func__, 1);
1427 }
1428
1429 /* Make a new spglobal pta, removing any old one */
1430 ptal = ccb->splocal;
1431 npt = ptaGetCount(ptal); /* number of points */
1432 if (ccb->spglobal) /* remove old one */
1433 ptaDestroy(&ccb->spglobal);
1434 if ((ptag = ptaCreate(npt)) == NULL) {
1435 ccbDestroy(&ccb);
1436 return ERROR_INT("ptag not made", __func__, 1);
1437 }
1438 ccb->spglobal = ptag; /* save new one */
1439
1440 /* Convert local to global */
1441 if (ptsflag == CCB_SAVE_ALL_PTS) {
1442 for (j = 0; j < npt; j++) {
1443 ptaGetIPt(ptal, j, &x, &y);
1444 ptaAddPt(ptag, x + xul, y + yul);
1445 }
1446 } else { /* ptsflag = CCB_SAVE_TURNING_PTS */
1447 ptaGetIPt(ptal, 0, &xp, &yp); /* get the 1st pt */
1448 ptaAddPt(ptag, xp + xul, yp + yul); /* save the 1st pt */
1449 if (npt == 2) { /* get and save the 2nd pt */
1450 ptaGetIPt(ptal, 1, &x, &y);
1451 ptaAddPt(ptag, x + xul, y + yul);
1452 } else if (npt > 2) {
1453 ptaGetIPt(ptal, 1, &x, &y);
1454 delxp = x - xp;
1455 delyp = y - yp;
1456 xp = x;
1457 yp = y;
1458 for (j = 2; j < npt; j++) {
1459 ptaGetIPt(ptal, j, &x, &y);
1460 delx = x - xp;
1461 dely = y - yp;
1462 if (delx != delxp || dely != delyp)
1463 ptaAddPt(ptag, xp + xul, yp + yul);
1464 xp = x;
1465 yp = y;
1466 delxp = delx;
1467 delyp = dely;
1468 }
1469 ptaAddPt(ptag, xp + xul, yp + yul);
1470 }
1471 }
1472
1473 ccbDestroy(&ccb); /* clone ref */
1474 }
1475
1476 return 0;
1477 }
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 {
1522 l_int32 i, j, k, ncc, nb, ncut, npt, dir, len, state, lostholes;
1523 l_int32 x, y, xl, yl, xf, yf;
1524 BOX *boxinner;
1525 BOXA *boxa;
1526 CCBORD *ccb;
1527 PTA *pta, *ptac, *ptah;
1528 PTA *ptahc; /* cyclic permutation of hole border, with end pts at cut */
1529 PTA *ptas; /* output result: new single path for c.c. */
1530 PTA *ptaf; /* points on the hole borders that intersect with cuts */
1531 PTA *ptal; /* points on outer border that intersect with cuts */
1532 PTA *ptap, *ptarp; /* path and reverse path between borders */
1533 PTAA *ptaa;
1534 PTAA *ptaap; /* ptaa for all paths between borders */
1535
1536 if (!ccba)
1537 return ERROR_INT("ccba not defined", __func__, 1);
1538
1539 ncc = ccbaGetCount(ccba); /* number of c.c. */
1540 lostholes = 0;
1541 for (i = 0; i < ncc; i++) {
1542 ccb = ccbaGetCcb(ccba, i);
1543 if ((ptaa = ccb->local) == NULL) {
1544 L_WARNING("local pixel loc array not found\n", __func__);
1545 continue;
1546 }
1547 nb = ptaaGetCount(ptaa); /* number of borders in the c.c. */
1548
1549 /* Prepare the output pta */
1550 if (ccb->splocal)
1551 ptaDestroy(&ccb->splocal);
1552 ptas = ptaCreate(0);
1553 ccb->splocal = ptas;
1554
1555 /* If no holes, just concat the outer border */
1556 pta = ptaaGetPta(ptaa, 0, L_CLONE);
1557 if (nb == 1 || nb > NMAX_HOLES + 1) {
1558 ptaJoin(ptas, pta, 0, -1);
1559 ptaDestroy(&pta); /* remove clone */
1560 ccbDestroy(&ccb); /* remove clone */
1561 continue;
1562 }
1563
1564 /* Find the (nb - 1) cut paths that connect holes
1565 * with outer border */
1566 boxa = ccb->boxa;
1567 ptaap = ptaaCreate(nb - 1);
1568 ptaf = ptaCreate(nb - 1);
1569 ptal = ptaCreate(nb - 1);
1570 for (j = 1; j < nb; j++) {
1571 boxinner = boxaGetBox(boxa, j, L_CLONE);
1572
1573 /* Find a short path and store it */
1574 ptac = getCutPathForHole(ccb->pix, pta, boxinner, &dir, &len);
1575 if (len == 0) { /* lost the hole */
1576 lostholes++;
1577 /* boxPrintStreamInfo(stderr, boxa->box[0]); */
1578 }
1579 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 ncut = ptaGetCount(ptac);
1587 if (ncut == 0) { /* missed hole; neg coords won't match */
1588 ptaAddPt(ptaf, -1, -1);
1589 ptaAddPt(ptal, -1, -1);
1590 } else {
1591 ptaGetIPt(ptac, 0, &x, &y);
1592 ptaAddPt(ptaf, x, y);
1593 ptaGetIPt(ptac, ncut - 1, &x, &y);
1594 ptaAddPt(ptal, x, y);
1595 }
1596 boxDestroy(&boxinner);
1597 }
1598
1599 /* Make a single path for the c.c. using these connections */
1600 npt = ptaGetCount(pta); /* outer border pts */
1601 for (k = 0; k < npt; k++) {
1602 ptaGetIPt(pta, k, &x, &y);
1603 if (k == 0) { /* if there is a cut at the first point,
1604 * we can wait until the end to take it */
1605 ptaAddPt(ptas, x, y);
1606 continue;
1607 }
1608 state = L_NOT_FOUND;
1609 for (j = 0; j < nb - 1; j++) { /* iterate over cut end pts */
1610 ptaGetIPt(ptal, j, &xl, &yl); /* cut point on outer border */
1611 if (x == xl && y == yl) { /* take this cut to the hole */
1612 state = L_FOUND;
1613 ptap = ptaaGetPta(ptaap, j, L_CLONE);
1614 ptarp = ptaReverse(ptap, 1);
1615 /* Cut point on hole border: */
1616 ptaGetIPt(ptaf, j, &xf, &yf);
1617 /* Hole border: */
1618 ptah = ptaaGetPta(ptaa, j + 1, L_CLONE);
1619 ptahc = ptaCyclicPerm(ptah, xf, yf);
1620 /* ptaWriteStream(stderr, ptahc, 1); */
1621 ptaJoin(ptas, ptarp, 0, -1);
1622 ptaJoin(ptas, ptahc, 0, -1);
1623 ptaJoin(ptas, ptap, 0, -1);
1624 ptaDestroy(&ptap);
1625 ptaDestroy(&ptarp);
1626 ptaDestroy(&ptah);
1627 ptaDestroy(&ptahc);
1628 break;
1629 }
1630 }
1631 if (state == L_NOT_FOUND)
1632 ptaAddPt(ptas, x, y);
1633 }
1634
1635 /* ptaWriteStream(stderr, ptas, 1); */
1636 ptaaDestroy(&ptaap);
1637 ptaDestroy(&ptaf);
1638 ptaDestroy(&ptal);
1639 ptaDestroy(&pta); /* remove clone */
1640 ccbDestroy(&ccb); /* remove clone */
1641 }
1642
1643 if (lostholes > 0)
1644 L_INFO("***** %d lost holes *****\n", __func__, lostholes);
1645 return 0;
1646 }
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 {
1682 l_int32 w, h, nc, x, y, xl, yl, xmid, ymid;
1683 l_uint32 val;
1684 PTA *ptac;
1685
1686 if (!pix)
1687 return (PTA *)ERROR_PTR("pix not defined", __func__, NULL);
1688 if (!pta)
1689 return (PTA *)ERROR_PTR("pta not defined", __func__, NULL);
1690 if (!boxinner)
1691 return (PTA *)ERROR_PTR("boxinner not defined", __func__, NULL);
1692
1693 pixGetDimensions(pix, &w, &h, NULL);
1694 ptac = ptaCreate(4);
1695 xmid = boxinner->x + boxinner->w / 2;
1696 ymid = boxinner->y + boxinner->h / 2;
1697
1698 /* try top first */
1699 for (y = ymid; y >= 0; y--) {
1700 pixGetPixel(pix, xmid, y, &val);
1701 if (val == 1) {
1702 ptaAddPt(ptac, xmid, y);
1703 break;
1704 }
1705 }
1706 for (y = y - 1; y >= 0; y--) {
1707 pixGetPixel(pix, xmid, y, &val);
1708 if (val == 1)
1709 ptaAddPt(ptac, xmid, y);
1710 else
1711 break;
1712 }
1713 nc = ptaGetCount(ptac);
1714 ptaGetIPt(ptac, nc - 1, &xl, &yl);
1715 if (ptaContainsPt(pta, xl, yl)) {
1716 *pdir = 1;
1717 *plen = nc;
1718 return ptac;
1719 }
1720
1721 /* Next try bottom */
1722 ptaEmpty(ptac);
1723 for (y = ymid; y < h; y++) {
1724 pixGetPixel(pix, xmid, y, &val);
1725 if (val == 1) {
1726 ptaAddPt(ptac, xmid, y);
1727 break;
1728 }
1729 }
1730 for (y = y + 1; y < h; y++) {
1731 pixGetPixel(pix, xmid, y, &val);
1732 if (val == 1)
1733 ptaAddPt(ptac, xmid, y);
1734 else
1735 break;
1736 }
1737 nc = ptaGetCount(ptac);
1738 ptaGetIPt(ptac, nc - 1, &xl, &yl);
1739 if (ptaContainsPt(pta, xl, yl)) {
1740 *pdir = 3;
1741 *plen = nc;
1742 return ptac;
1743 }
1744
1745 /* Next try left */
1746 ptaEmpty(ptac);
1747 for (x = xmid; x >= 0; x--) {
1748 pixGetPixel(pix, x, ymid, &val);
1749 if (val == 1) {
1750 ptaAddPt(ptac, x, ymid);
1751 break;
1752 }
1753 }
1754 for (x = x - 1; x >= 0; x--) {
1755 pixGetPixel(pix, x, ymid, &val);
1756 if (val == 1)
1757 ptaAddPt(ptac, x, ymid);
1758 else
1759 break;
1760 }
1761 nc = ptaGetCount(ptac);
1762 ptaGetIPt(ptac, nc - 1, &xl, &yl);
1763 if (ptaContainsPt(pta, xl, yl)) {
1764 *pdir = 0;
1765 *plen = nc;
1766 return ptac;
1767 }
1768
1769 /* Finally try right */
1770 ptaEmpty(ptac);
1771 for (x = xmid; x < w; x++) {
1772 pixGetPixel(pix, x, ymid, &val);
1773 if (val == 1) {
1774 ptaAddPt(ptac, x, ymid);
1775 break;
1776 }
1777 }
1778 for (x = x + 1; x < w; x++) {
1779 pixGetPixel(pix, x, ymid, &val);
1780 if (val == 1)
1781 ptaAddPt(ptac, x, ymid);
1782 else
1783 break;
1784 }
1785 nc = ptaGetCount(ptac);
1786 ptaGetIPt(ptac, nc - 1, &xl, &yl);
1787 if (ptaContainsPt(pta, xl, yl)) {
1788 *pdir = 2;
1789 *plen = nc;
1790 return ptac;
1791 }
1792
1793 /* Sometimes, there is nothing. */
1794 ptaEmpty(ptac);
1795 *plen = 0;
1796 return ptac;
1797 }
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 {
1820 l_int32 ncc, nb, n, i, j, k, x, y;
1821 CCBORD *ccb;
1822 PIX *pixd;
1823 PTAA *ptaa;
1824 PTA *pta;
1825
1826 if (!ccba)
1827 return (PIX *)ERROR_PTR("ccba not defined", __func__, NULL);
1828
1829 if ((pixd = pixCreate(ccba->w, ccba->h, 1)) == NULL)
1830 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
1831 ncc = ccbaGetCount(ccba); /* number of c.c. */
1832 for (i = 0; i < ncc; i++) {
1833 ccb = ccbaGetCcb(ccba, i);
1834 if ((ptaa = ccb->global) == NULL) {
1835 L_WARNING("global pixel loc array not found", __func__);
1836 ccbDestroy(&ccb);
1837 continue;
1838 }
1839 nb = ptaaGetCount(ptaa); /* number of borders in the c.c. */
1840 for (j = 0; j < nb; j++) {
1841 pta = ptaaGetPta(ptaa, j, L_CLONE);
1842 n = ptaGetCount(pta); /* number of pixels in the border */
1843 for (k = 0; k < n; k++) {
1844 ptaGetIPt(pta, k, &x, &y);
1845 pixSetPixel(pixd, x, y, 1);
1846 }
1847 ptaDestroy(&pta);
1848 }
1849 ccbDestroy(&ccb);
1850 }
1851
1852 return pixd;
1853 }
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 {
1872 l_int32 ncc, npt, i, j, x, y;
1873 CCBORD *ccb;
1874 PIX *pixd;
1875 PTA *ptag;
1876
1877 if (!ccba)
1878 return (PIX *)ERROR_PTR("ccba not defined", __func__, NULL);
1879
1880 if ((pixd = pixCreate(ccba->w, ccba->h, 1)) == NULL)
1881 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
1882 ncc = ccbaGetCount(ccba); /* number of c.c. */
1883 for (i = 0; i < ncc; i++) {
1884 ccb = ccbaGetCcb(ccba, i);
1885 if ((ptag = ccb->spglobal) == NULL) {
1886 L_WARNING("spglobal pixel loc array not found\n", __func__);
1887 ccbDestroy(&ccb);
1888 continue;
1889 }
1890 npt = ptaGetCount(ptag); /* number of pixels on path */
1891 for (j = 0; j < npt; j++) {
1892 ptaGetIPt(ptag, j, &x, &y);
1893 pixSetPixel(pixd, x, y, 1);
1894 }
1895 ccbDestroy(&ccb); /* clone ref */
1896 }
1897
1898 return pixd;
1899 }
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 {
1961 l_int32 ncc, i, nb, n, j, k, x, y, xul, yul, xoff, yoff, w, h;
1962 l_int32 fpx, fpy, spx, spy, xs, ys;
1963 BOX *box;
1964 BOXA *boxa;
1965 CCBORD *ccb;
1966 PIX *pixd, *pixt, *pixh;
1967 PTAA *ptaa;
1968 PTA *pta;
1969
1970 if (!ccba)
1971 return (PIX *)ERROR_PTR("ccba not defined", __func__, NULL);
1972
1973 if ((pixd = pixCreate(ccba->w, ccba->h, 1)) == NULL)
1974 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
1975 ncc = ccbaGetCount(ccba);
1976 for (i = 0; i < ncc; i++) {
1977 ccb = ccbaGetCcb(ccba, i);
1978 if ((boxa = ccb->boxa) == NULL) {
1979 pixDestroy(&pixd);
1980 ccbDestroy(&ccb);
1981 return (PIX *)ERROR_PTR("boxa not found", __func__, NULL);
1982 }
1983
1984 /* Render border in pixt */
1985 if ((ptaa = ccb->local) == NULL) {
1986 L_WARNING("local chain array not found\n", __func__);
1987 ccbDestroy(&ccb);
1988 continue;
1989 }
1990
1991 nb = ptaaGetCount(ptaa); /* number of borders in the c.c. */
1992 for (j = 0; j < nb; j++) {
1993 if ((box = boxaGetBox(boxa, j, L_CLONE)) == NULL) {
1994 pixDestroy(&pixd);
1995 ccbDestroy(&ccb);
1996 return (PIX *)ERROR_PTR("b. box not found", __func__, NULL);
1997 }
1998 if (j == 0) {
1999 boxGetGeometry(box, &xul, &yul, &w, &h);
2000 xoff = yoff = 0;
2001 } else {
2002 boxGetGeometry(box, &xoff, &yoff, &w, &h);
2003 }
2004 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 if ((pixt = pixCreate(w, h, 1)) == NULL) {
2011 pixDestroy(&pixd);
2012 ccbDestroy(&ccb);
2013 return (PIX *)ERROR_PTR("pixt not made", __func__, NULL);
2014 }
2015 pta = ptaaGetPta(ptaa, j, L_CLONE);
2016 n = ptaGetCount(pta); /* number of pixels in the border */
2017 for (k = 0; k < n; k++) {
2018 ptaGetIPt(pta, k, &x, &y);
2019 pixSetPixel(pixt, x - xoff, y - yoff, 1);
2020 if (j > 0) { /* need this for finding hole border pixel */
2021 if (k == 0) {
2022 fpx = x - xoff;
2023 fpy = y - yoff;
2024 }
2025 if (k == 1) {
2026 spx = x - xoff;
2027 spy = y - yoff;
2028 }
2029 }
2030 }
2031 ptaDestroy(&pta);
2032
2033 /* Get the filled component */
2034 if (j == 0) { /* if outer border, fill from outer boundary */
2035 if ((pixh = pixFillClosedBorders(pixt, 4)) == NULL) {
2036 pixDestroy(&pixd);
2037 pixDestroy(&pixt);
2038 ccbDestroy(&ccb);
2039 return (PIX *)ERROR_PTR("pixh not made", __func__, NULL);
2040 }
2041 } else { /* fill the hole from inside */
2042 /* get the location of a seed pixel in the hole */
2043 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 pixh = pixCreateTemplate(pixt);
2048 pixSetPixel(pixh, xs, ys, 1); /* put seed pixel in hole */
2049 pixInvert(pixt, pixt); /* to make filling mask */
2050 pixSeedfillBinary(pixh, pixh, pixt, 4); /* 4-fill hole */
2051 }
2052
2053 /* XOR into the dest */
2054 pixRasterop(pixd, xul + xoff, yul + yoff, w, h, PIX_XOR,
2055 pixh, 0, 0);
2056 pixDestroy(&pixt);
2057 pixDestroy(&pixh);
2058 }
2059 ccbDestroy(&ccb);
2060 }
2061 return pixd;
2062 }
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 {
2090 l_int32 ncc, nb, n, i, j, k, x, y, xul, yul, w, h;
2091 l_int32 fpx, fpy, spx, spy, xs, ys;
2092 BOXA *boxa;
2093 CCBORD *ccb;
2094 PIX *pixd, *pixc, *pixs;
2095 PTAA *ptaa;
2096 PTA *pta;
2097
2098 if (!ccba)
2099 return (PIX *)ERROR_PTR("ccba not defined", __func__, NULL);
2100
2101 if ((pixd = pixCreate(ccba->w, ccba->h, 1)) == NULL)
2102 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
2103 ncc = ccbaGetCount(ccba);
2104 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 ccb = ccbaGetCcb(ccba, i);
2108 if ((boxa = ccb->boxa) == NULL) {
2109 pixDestroy(&pixd);
2110 ccbDestroy(&ccb);
2111 return (PIX *)ERROR_PTR("boxa not found", __func__, NULL);
2112 }
2113 if (boxaGetBoxGeometry(boxa, 0, &xul, &yul, &w, &h)) {
2114 pixDestroy(&pixd);
2115 ccbDestroy(&ccb);
2116 return (PIX *)ERROR_PTR("b. box not found", __func__, NULL);
2117 }
2118 pixc = pixCreate(w + 2, h + 2, 1);
2119 pixs = pixCreateTemplate(pixc);
2120
2121 if ((ptaa = ccb->local) == NULL) {
2122 pixDestroy(&pixc);
2123 pixDestroy(&pixs);
2124 ccbDestroy(&ccb);
2125 L_WARNING("local chain array not found\n", __func__);
2126 continue;
2127 }
2128 nb = ptaaGetCount(ptaa); /* number of borders in the c.c. */
2129 for (j = 0; j < nb; j++) {
2130 pta = ptaaGetPta(ptaa, j, L_CLONE);
2131 n = ptaGetCount(pta); /* number of pixels in the border */
2132
2133 /* Render border pixels in pixc */
2134 for (k = 0; k < n; k++) {
2135 ptaGetIPt(pta, k, &x, &y);
2136 pixSetPixel(pixc, x + 1, y + 1, 1);
2137 if (k == 0) {
2138 fpx = x + 1;
2139 fpy = y + 1;
2140 } else if (k == 1) {
2141 spx = x + 1;
2142 spy = y + 1;
2143 }
2144 }
2145
2146 /* Get and set seed pixel for this border in pixs */
2147 if (n > 1)
2148 locateOutsideSeedPixel(fpx, fpy, spx, spy, &xs, &ys);
2149 else /* isolated c.c. */
2150 xs = ys = 0;
2151 pixSetPixel(pixs, xs, ys, 1);
2152 ptaDestroy(&pta);
2153 }
2154
2155 /* Fill from seeds in pixs, using pixc as the clipping mask,
2156 * to reconstruct the c.c. */
2157 pixInvert(pixc, pixc); /* to convert clipping -> filling mask */
2158 pixSeedfillBinary(pixs, pixs, pixc, 4); /* 4-fill */
2159 pixInvert(pixs, pixs); /* to make the c.c. */
2160
2161 /* XOR into the dest */
2162 pixRasterop(pixd, xul, yul, w, h, PIX_XOR, pixs, 1, 1);
2163
2164 pixDestroy(&pixc);
2165 pixDestroy(&pixs);
2166 ccbDestroy(&ccb); /* ref-counted */
2167 }
2168 return pixd;
2169 }
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 {
2186 FILE *fp;
2187
2188 if (!filename)
2189 return ERROR_INT("filename not defined", __func__, 1);
2190 if (!ccba)
2191 return ERROR_INT("ccba not defined", __func__, 1);
2192
2193 if ((fp = fopenWriteStream(filename, "wb+")) == NULL)
2194 return ERROR_INT_1("stream not opened", filename, __func__, 1);
2195 if (ccbaWriteStream(fp, ccba)) {
2196 fclose(fp);
2197 return ERROR_INT_1("ccba not written to stream", filename, __func__, 1);
2198 }
2199
2200 fclose(fp);
2201 return 0;
2202 }
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 {
2236 #if HAVE_LIBZ /* defined in environ.h */
2237 char strbuf[256];
2238 l_uint8 bval;
2239 l_uint8 *datain, *dataout;
2240 l_int32 i, j, k, bx, by, bw, bh, val, startx, starty;
2241 l_int32 ncc, nb, n;
2242 l_uint32 w, h;
2243 size_t inbytes, outbytes;
2244 L_BBUFFER *bbuf;
2245 CCBORD *ccb;
2246 NUMA *na;
2247 NUMAA *naa;
2248 PTA *pta;
2249 #endif
2250
2251 #if !HAVE_LIBZ /* defined in environ.h */
2252 return ERROR_INT("no libz: can't write data", __func__, 1);
2253 #else
2254
2255 if (!fp)
2256 return ERROR_INT("stream not open", __func__, 1);
2257 if (!ccba)
2258 return ERROR_INT("ccba not defined", __func__, 1);
2259
2260 if ((bbuf = bbufferCreate(NULL, 1000)) == NULL)
2261 return ERROR_INT("bbuf not made", __func__, 1);
2262
2263 ncc = ccbaGetCount(ccba);
2264 snprintf(strbuf, sizeof(strbuf), "ccba: %7d cc\n", ncc);
2265 bbufferRead(bbuf, (l_uint8 *)strbuf, 18);
2266 w = pixGetWidth(ccba->pix);
2267 h = pixGetHeight(ccba->pix);
2268 bbufferRead(bbuf, (l_uint8 *)&w, 4); /* width */
2269 bbufferRead(bbuf, (l_uint8 *)&h, 4); /* height */
2270 for (i = 0; i < ncc; i++) {
2271 ccb = ccbaGetCcb(ccba, i);
2272 if (boxaGetBoxGeometry(ccb->boxa, 0, &bx, &by, &bw, &bh)) {
2273 bbufferDestroy(&bbuf);
2274 ccbDestroy(&ccb);
2275 return ERROR_INT("bounding box not found", __func__, 1);
2276 }
2277 bbufferRead(bbuf, (l_uint8 *)&bx, 4); /* ulx of c.c. */
2278 bbufferRead(bbuf, (l_uint8 *)&by, 4); /* uly of c.c. */
2279 bbufferRead(bbuf, (l_uint8 *)&bw, 4); /* w of c.c. */
2280 bbufferRead(bbuf, (l_uint8 *)&bh, 4); /* h of c.c. */
2281 if ((naa = ccb->step) == NULL) {
2282 ccbaGenerateStepChains(ccba);
2283 naa = ccb->step;
2284 }
2285 nb = numaaGetCount(naa);
2286 bbufferRead(bbuf, (l_uint8 *)&nb, 4); /* number of borders in c.c. */
2287 pta = ccb->start;
2288 for (j = 0; j < nb; j++) {
2289 ptaGetIPt(pta, j, &startx, &starty);
2290 bbufferRead(bbuf, (l_uint8 *)&startx, 4); /* starting x in border */
2291 bbufferRead(bbuf, (l_uint8 *)&starty, 4); /* starting y in border */
2292 na = numaaGetNuma(naa, j, L_CLONE);
2293 n = numaGetCount(na);
2294 for (k = 0; k < n; k++) {
2295 numaGetIValue(na, k, &val);
2296 if (k % 2 == 0)
2297 bval = (l_uint8)val << 4;
2298 else
2299 bval |= (l_uint8)val;
2300 if (k % 2 == 1)
2301 bbufferRead(bbuf, (l_uint8 *)&bval, 1); /* 2 border steps */
2302 }
2303 if (n % 2 == 1) {
2304 bval |= 0x8;
2305 bbufferRead(bbuf, (l_uint8 *)&bval, 1); /* end with 0xz8, */
2306 /* where z = {0..7} */
2307 } else { /* n % 2 == 0 */
2308 bval = 0x88;
2309 bbufferRead(bbuf, (l_uint8 *)&bval, 1); /* end with 0x88 */
2310 }
2311 numaDestroy(&na);
2312 }
2313 ccbDestroy(&ccb);
2314 }
2315
2316 datain = bbufferDestroyAndSaveData(&bbuf, &inbytes);
2317 dataout = zlibCompress(datain, inbytes, &outbytes);
2318 fwrite(dataout, 1, outbytes, fp);
2319
2320 LEPT_FREE(datain);
2321 LEPT_FREE(dataout);
2322 return 0;
2323
2324 #endif /* !HAVE_LIBZ */
2325 }
2326
2327
2328 /*!
2329 * \brief ccbaRead()
2330 *
2331 * \param[in] filename
2332 * \return ccba, or NULL on error
2333 */
2334 CCBORDA *
2335 ccbaRead(const char *filename)
2336 {
2337 FILE *fp;
2338 CCBORDA *ccba;
2339
2340 if (!filename)
2341 return (CCBORDA *)ERROR_PTR("filename not defined", __func__, NULL);
2342
2343 if ((fp = fopenReadStream(filename)) == NULL)
2344 return (CCBORDA *)ERROR_PTR_1("stream not opened",
2345 filename, __func__, NULL);
2346 ccba = ccbaReadStream(fp);
2347 fclose(fp);
2348
2349 if (!ccba)
2350 return (CCBORDA *)ERROR_PTR_1("ccba not returned",
2351 filename, __func__, NULL);
2352 return ccba;
2353 }
2354
2355
2356 /*!
2357 * \brief ccbaReadStream()
2358 *
2359 * \param[in] fp file stream
2360 * \return ccba, or NULL on error
2361 *
2362 * \code
2363 * Format: ccba: %7d cc\n num. c.c.) (ascii) (17B
2364 * pix width 4B
2365 * pix height 4B
2366 * [for i = 1, ncc]
2367 * ulx 4B
2368 * uly 4B
2369 * w 4B -- not req'd for reconstruction
2370 * h 4B -- not req'd for reconstruction
2371 * number of borders 4B
2372 * [for j = 1, nb]
2373 * startx 4B
2374 * starty 4B
2375 * [for k = 1, nb]
2376 * 2 steps 1B
2377 * end in z8 or 88 1B
2378 * \endcode
2379 */
2380 CCBORDA *
2381 ccbaReadStream(FILE *fp)
2382 {
2383 #if HAVE_LIBZ /* defined in environ.h */
2384 char strbuf[256];
2385 l_uint8 bval;
2386 l_uint8 *datain, *dataout;
2387 l_int32 i, j, startx, starty;
2388 l_int32 offset, nib1, nib2;
2389 l_int32 ncc, nb;
2390 l_uint32 width, height, w, h, xoff, yoff;
2391 size_t inbytes, outbytes;
2392 BOX *box;
2393 CCBORD *ccb;
2394 CCBORDA *ccba;
2395 NUMA *na;
2396 NUMAA *step;
2397 #endif
2398
2399 #if !HAVE_LIBZ /* defined in environ.h */
2400 return (CCBORDA *)ERROR_PTR("no libz: can't read data", __func__, NULL);
2401 #else
2402
2403 if (!fp)
2404 return (CCBORDA *)ERROR_PTR("stream not open", __func__, NULL);
2405
2406 if ((datain = l_binaryReadStream(fp, &inbytes)) == NULL)
2407 return (CCBORDA *)ERROR_PTR("data not read from file", __func__, NULL);
2408 dataout = zlibUncompress(datain, inbytes, &outbytes);
2409 LEPT_FREE(datain);
2410 if (!dataout)
2411 return (CCBORDA *)ERROR_PTR("dataout not made", __func__, NULL);
2412
2413 offset = 18;
2414 memcpy(strbuf, dataout, offset);
2415 strbuf[17] = '\0';
2416 if (memcmp(strbuf, "ccba:", 5) != 0) {
2417 LEPT_FREE(dataout);
2418 return (CCBORDA *)ERROR_PTR("file not type ccba", __func__, NULL);
2419 }
2420 sscanf(strbuf, "ccba: %7d cc\n", &ncc);
2421 /* lept_stderr("ncc = %d\n", ncc); */
2422 if ((ccba = ccbaCreate(NULL, ncc)) == NULL) {
2423 LEPT_FREE(dataout);
2424 return (CCBORDA *)ERROR_PTR("ccba not made", __func__, NULL);
2425 }
2426
2427 memcpy(&width, dataout + offset, 4);
2428 offset += 4;
2429 memcpy(&height, dataout + offset, 4);
2430 offset += 4;
2431 ccba->w = width;
2432 ccba->h = height;
2433 /* lept_stderr("width = %d, height = %d\n", width, height); */
2434
2435 for (i = 0; i < ncc; i++) { /* should be ncc */
2436 ccb = ccbCreate(NULL);
2437 ccbaAddCcb(ccba, ccb);
2438
2439 memcpy(&xoff, dataout + offset, 4);
2440 offset += 4;
2441 memcpy(&yoff, dataout + offset, 4);
2442 offset += 4;
2443 memcpy(&w, dataout + offset, 4);
2444 offset += 4;
2445 memcpy(&h, dataout + offset, 4);
2446 offset += 4;
2447 box = boxCreate(xoff, yoff, w, h);
2448 boxaAddBox(ccb->boxa, box, L_INSERT);
2449 /* lept_stderr("xoff = %d, yoff = %d, w = %d, h = %d\n",
2450 xoff, yoff, w, h); */
2451
2452 memcpy(&nb, dataout + offset, 4);
2453 offset += 4;
2454 /* lept_stderr("num borders = %d\n", nb); */
2455 step = numaaCreate(nb);
2456 ccb->step = step;
2457
2458 for (j = 0; j < nb; j++) { /* should be nb */
2459 memcpy(&startx, dataout + offset, 4);
2460 offset += 4;
2461 memcpy(&starty, dataout + offset, 4);
2462 offset += 4;
2463 ptaAddPt(ccb->start, startx, starty);
2464 /* lept_stderr("startx = %d, starty = %d\n", startx, starty); */
2465 na = numaCreate(0);
2466 numaaAddNuma(step, na, L_INSERT);
2467
2468 while(1) {
2469 bval = *(dataout + offset);
2470 offset++;
2471 nib1 = (bval >> 4);
2472 nib2 = bval & 0xf;
2473 if (nib1 != 8)
2474 numaAddNumber(na, nib1);
2475 else
2476 break;
2477 if (nib2 != 8)
2478 numaAddNumber(na, nib2);
2479 else
2480 break;
2481 }
2482 }
2483 }
2484 LEPT_FREE(dataout);
2485 return ccba;
2486
2487 #endif /* !HAVE_LIBZ */
2488 }
2489
2490
2491 /*---------------------------------------------------------------------*
2492 * SVG Output *
2493 *---------------------------------------------------------------------*/
2494 /*!
2495 * \brief ccbaWriteSVG()
2496 *
2497 * \param[in] filename
2498 * \param[in] ccba
2499 * \return 0 if OK, 1 on error
2500 */
2501 l_ok
2502 ccbaWriteSVG(const char *filename,
2503 CCBORDA *ccba)
2504 {
2505 char *svgstr;
2506
2507 if (!filename)
2508 return ERROR_INT("filename not defined", __func__, 1);
2509 if (!ccba)
2510 return ERROR_INT("ccba not defined", __func__, 1);
2511
2512 if ((svgstr = ccbaWriteSVGString(ccba)) == NULL)
2513 return ERROR_INT("svgstr not made", __func__, 1);
2514
2515 l_binaryWrite(filename, "w", svgstr, strlen(svgstr));
2516 LEPT_FREE(svgstr);
2517
2518 return 0;
2519 }
2520
2521
2522 /*!
2523 * \brief ccbaWriteSVGString()
2524 *
2525 * \param[in] ccba
2526 * \return string in svg-formatted, that can be written to file,
2527 * or NULL on error.
2528 */
2529 char *
2530 ccbaWriteSVGString(CCBORDA *ccba)
2531 {
2532 char *svgstr;
2533 char smallbuf[256];
2534 char line0[] = "<?xml version=\"1.0\" encoding=\"iso-8859-1\"?>";
2535 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\">";
2536 char line2[] = "<svg>";
2537 char line3[] = "<polygon style=\"stroke-width:1;stroke:black;\" points=\"";
2538 char line4[] = "\" />";
2539 char line5[] = "</svg>";
2540 char space[] = " ";
2541 l_int32 i, j, ncc, npt, x, y;
2542 CCBORD *ccb;
2543 PTA *pta;
2544 SARRAY *sa;
2545
2546 if (!ccba)
2547 return (char *)ERROR_PTR("ccba not defined", __func__, NULL);
2548
2549 sa = sarrayCreate(0);
2550 sarrayAddString(sa, line0, L_COPY);
2551 sarrayAddString(sa, line1, L_COPY);
2552 sarrayAddString(sa, line2, L_COPY);
2553 ncc = ccbaGetCount(ccba);
2554 for (i = 0; i < ncc; i++) {
2555 if ((ccb = ccbaGetCcb(ccba, i)) == NULL) {
2556 sarrayDestroy(&sa);
2557 return (char *)ERROR_PTR("ccb not found", __func__, NULL);
2558 }
2559 if ((pta = ccb->spglobal) == NULL) {
2560 sarrayDestroy(&sa);
2561 ccbDestroy(&ccb);
2562 return (char *)ERROR_PTR("spglobal not made", __func__, NULL);
2563 }
2564 sarrayAddString(sa, line3, L_COPY);
2565 npt = ptaGetCount(pta);
2566 for (j = 0; j < npt; j++) {
2567 ptaGetIPt(pta, j, &x, &y);
2568 snprintf(smallbuf, sizeof(smallbuf), "%0d,%0d", x, y);
2569 sarrayAddString(sa, smallbuf, L_COPY);
2570 }
2571 sarrayAddString(sa, line4, L_COPY);
2572 ccbDestroy(&ccb);
2573 }
2574 sarrayAddString(sa, line5, L_COPY);
2575 sarrayAddString(sa, space, L_COPY);
2576
2577 svgstr = sarrayToString(sa, 1);
2578 /* lept_stderr("%s", svgstr); */
2579
2580 sarrayDestroy(&sa);
2581 return svgstr;
2582 }