1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 - This software is distributed in the hope that it will be
4 - useful, but with NO WARRANTY OF ANY KIND.
5 - No author or distributor accepts responsibility to anyone for the
6 - consequences of using this software, or for whether it serves any
7 - particular purpose or works at all, unless he or she says so in
8 - writing. Everyone is granted permission to copy, modify and
9 - redistribute this source code, for commercial or non-commercial
10 - purposes, with the following restrictions: (1) the origin of this
11 - source code must not be misrepresented; (2) modified versions must
12 - be plainly marked as such; and (3) this notice may not be removed
13 - or altered from any source or modified source distribution.
14 *====================================================================*/
15
16
17 /*
18 * pts.c
19 *
20 * Pta creation, destruction, copy, clone, empty
21 * PTA *ptaCreate()
22 * void ptaDestroy()
23 * PTA *ptaCopy()
24 * PTA *ptaClone()
25 * l_int32 ptaEmpty()
26 *
27 * Pta array extension
28 * l_int32 ptaAddPt()
29 * l_int32 ptaExtendArrays()
30 *
31 * Pta rearrangements
32 * l_int32 ptaJoin()
33 * PTA *ptaReverse()
34 * PTA *ptaCyclicPerm()
35 * PTA *ptaSort()
36 * PTA *ptaRemoveDuplicates()
37 *
38 * Pta Accessors
39 * l_int32 ptaGetRefcount()
40 * l_int32 ptaChangeRefcount()
41 * l_int32 ptaGetCount()
42 * l_int32 ptaGetPt()
43 * l_int32 ptaGetIPt()
44 * l_int32 ptaGetArrays()
45 *
46 * Ptaa creation, destruction
47 * PTAA *ptaaCreate()
48 * void ptaaDestroy()
49 *
50 * Ptaa array extension
51 * l_int32 ptaaAddPta()
52 * l_int32 ptaaExtendArray()
53 *
54 * Ptaa Accessors
55 * l_int32 ptaaGetCount()
56 * l_int32 ptaaGetPta()
57 *
58 * Ptaa serialized I/O
59 * PTAA *ptaaRead()
60 * PTAA *ptaaReadStream()
61 * l_int32 ptaaWrite()
62 * l_int32 ptaaWriteStream()
63 *
64 * Pta serialized I/O
65 * PTA *ptaRead()
66 * PTA *ptaReadStream()
67 * l_int32 ptaWrite()
68 * l_int32 ptaWriteStream()
69 *
70 * In use
71 * BOX *ptaGetExtent()
72 * PTA *ptaGetInsideBox()
73 * PTA *pixFindCornerPixels()
74 * l_int32 pixPlotAlongPta()
75 * l_int32 ptaContainsPt()
76 * l_int32 ptaTestIntersection()
77 * PTA *ptaTransform()
78 * PTA *ptaSubsample()
79 * l_int32 ptaGetLinearLSF()
80 * PTA *ptaGetPixelsFromPix()
81 * PIX *pixGenerateFromPta()
82 * PTA *ptaGetBoundaryPixels()
83 * PTAA *ptaaGetBoundaryPixels()
84 */
85
86 #include <stdio.h>
87 #include <stdlib.h>
88 #include <string.h>
89 #include "allheaders.h"
90
91 static const l_int32 INITIAL_PTR_ARRAYSIZE = 20; /* n'import quoi */
92
93 /* Default spreading factor for hashing pts in a plane */
94 static const l_int32 DEFAULT_SPREADING_FACTOR = 7500;
95
96
97 /*---------------------------------------------------------------------*
98 * PTA creation, destruction, copy, clone *
99 *---------------------------------------------------------------------*/
100 /*!
101 * ptaCreate()
102 *
103 * Input: n (initial array sizes)
104 * Return: pta, or null on error.
105 */
106 PTA *
ptaCreate(l_int32 n)107 ptaCreate(l_int32 n)
108 {
109 PTA *pta;
110
111 PROCNAME("ptaCreate");
112
113 if (n <= 0)
114 n = INITIAL_PTR_ARRAYSIZE;
115
116 if ((pta = (PTA *)CALLOC(1, sizeof(PTA))) == NULL)
117 return (PTA *)ERROR_PTR("pta not made", procName, NULL);
118 pta->n = 0;
119 pta->nalloc = n;
120 ptaChangeRefcount(pta, 1); /* sets to 1 */
121
122 if ((pta->x = (l_float32 *)CALLOC(n, sizeof(l_float32))) == NULL)
123 return (PTA *)ERROR_PTR("x array not made", procName, NULL);
124 if ((pta->y = (l_float32 *)CALLOC(n, sizeof(l_float32))) == NULL)
125 return (PTA *)ERROR_PTR("y array not made", procName, NULL);
126
127 return pta;
128 }
129
130
131 /*!
132 * ptaDestroy()
133 *
134 * Input: &pta (<to be nulled>)
135 * Return: void
136 *
137 * Note:
138 * - Decrements the ref count and, if 0, destroys the pta.
139 * - Always nulls the input ptr.
140 */
141 void
ptaDestroy(PTA ** ppta)142 ptaDestroy(PTA **ppta)
143 {
144 PTA *pta;
145
146 PROCNAME("ptaDestroy");
147
148 if (ppta == NULL) {
149 L_WARNING("ptr address is NULL!", procName);
150 return;
151 }
152
153 if ((pta = *ppta) == NULL)
154 return;
155
156 ptaChangeRefcount(pta, -1);
157 if (ptaGetRefcount(pta) <= 0) {
158 FREE(pta->x);
159 FREE(pta->y);
160 FREE(pta);
161 }
162
163 *ppta = NULL;
164 return;
165 }
166
167
168 /*!
169 * ptaCopy()
170 *
171 * Input: pta
172 * Return: copy of pta, or null on error
173 */
174 PTA *
ptaCopy(PTA * pta)175 ptaCopy(PTA *pta)
176 {
177 l_int32 i;
178 l_float32 x, y;
179 PTA *npta;
180
181 PROCNAME("ptaCopy");
182
183 if (!pta)
184 return (PTA *)ERROR_PTR("pta not defined", procName, NULL);
185
186 if ((npta = ptaCreate(pta->nalloc)) == NULL)
187 return (PTA *)ERROR_PTR("npta not made", procName, NULL);
188
189 for (i = 0; i < pta->n; i++) {
190 ptaGetPt(pta, i, &x, &y);
191 ptaAddPt(npta, x, y);
192 }
193
194 return npta;
195 }
196
197
198 /*!
199 * ptaClone()
200 *
201 * Input: pta
202 * Return: ptr to same pta, or null on error
203 */
204 PTA *
ptaClone(PTA * pta)205 ptaClone(PTA *pta)
206 {
207 PROCNAME("ptaClone");
208
209 if (!pta)
210 return (PTA *)ERROR_PTR("pta not defined", procName, NULL);
211
212 ptaChangeRefcount(pta, 1);
213 return pta;
214 }
215
216
217 /*!
218 * ptaEmpty()
219 *
220 * Input: pta
221 * Return: 0 if OK, 1 on error
222 *
223 * Note: this only resets the "n" field, for reuse
224 */
225 l_int32
ptaEmpty(PTA * pta)226 ptaEmpty(PTA *pta)
227 {
228 PROCNAME("ptaEmpty");
229
230 if (!pta)
231 return ERROR_INT("ptad not defined", procName, 1);
232 pta->n = 0;
233 return 0;
234 }
235
236
237 /*---------------------------------------------------------------------*
238 * PTA array extension *
239 *---------------------------------------------------------------------*/
240 /*!
241 * ptaAddPt()
242 *
243 * Input: pta
244 * x, y
245 * Return: 0 if OK, 1 on error
246 */
247 l_int32
ptaAddPt(PTA * pta,l_float32 x,l_float32 y)248 ptaAddPt(PTA *pta,
249 l_float32 x,
250 l_float32 y)
251 {
252 l_int32 n;
253
254 PROCNAME("ptaAddPt");
255
256 if (!pta)
257 return ERROR_INT("pta not defined", procName, 1);
258
259 n = pta->n;
260 if (n >= pta->nalloc)
261 ptaExtendArrays(pta);
262 pta->x[n] = x;
263 pta->y[n] = y;
264 pta->n++;
265
266 return 0;
267 }
268
269
270 /*!
271 * ptaExtendArrays()
272 *
273 * Input: pta
274 * Return: 0 if OK; 1 on error
275 */
276 l_int32
ptaExtendArrays(PTA * pta)277 ptaExtendArrays(PTA *pta)
278 {
279 PROCNAME("ptaExtendArrays");
280
281 if (!pta)
282 return ERROR_INT("pta not defined", procName, 1);
283
284 if ((pta->x = (l_float32 *)reallocNew((void **)&pta->x,
285 sizeof(l_float32) * pta->nalloc,
286 2 * sizeof(l_float32) * pta->nalloc)) == NULL)
287 return ERROR_INT("new x array not returned", procName, 1);
288 if ((pta->y = (l_float32 *)reallocNew((void **)&pta->y,
289 sizeof(l_float32) * pta->nalloc,
290 2 * sizeof(l_float32) * pta->nalloc)) == NULL)
291 return ERROR_INT("new y array not returned", procName, 1);
292
293 pta->nalloc = 2 * pta->nalloc;
294 return 0;
295 }
296
297
298
299 /*---------------------------------------------------------------------*
300 * Pta rearrangements *
301 *---------------------------------------------------------------------*/
302 /*!
303 * ptaJoin()
304 *
305 * Input: ptad (dest pta; add to this one)
306 * ptas (source pta; add from this one)
307 * istart (starting index in ptas)
308 * iend (ending index in ptas; use 0 to cat all)
309 * Return: 0 if OK, 1 on error
310 *
311 * Notes:
312 * (1) istart < 0 is taken to mean 'read from the start' (istart = 0)
313 * (2) iend <= 0 means 'read to the end'
314 */
315 l_int32
ptaJoin(PTA * ptad,PTA * ptas,l_int32 istart,l_int32 iend)316 ptaJoin(PTA *ptad,
317 PTA *ptas,
318 l_int32 istart,
319 l_int32 iend)
320 {
321 l_int32 ns, i, x, y;
322
323 PROCNAME("ptaJoin");
324
325 if (!ptad)
326 return ERROR_INT("ptad not defined", procName, 1);
327 if (!ptas)
328 return ERROR_INT("ptas not defined", procName, 1);
329 ns = ptaGetCount(ptas);
330 if (istart < 0)
331 istart = 0;
332 if (istart >= ns)
333 return ERROR_INT("istart out of bounds", procName, 1);
334 if (iend <= 0)
335 iend = ns - 1;
336 if (iend >= ns)
337 return ERROR_INT("iend out of bounds", procName, 1);
338 if (istart > iend)
339 return ERROR_INT("istart > iend; no pts", procName, 1);
340
341 for (i = istart; i <= iend; i++) {
342 ptaGetIPt(ptas, i, &x, &y);
343 ptaAddPt(ptad, x, y);
344 }
345
346 return 0;
347 }
348
349
350 /*!
351 * ptaReverse()
352 *
353 * Input: ptas
354 * type (0 for float values; 1 for integer values)
355 * Return: ptad (reversed pta), or null on error
356 */
357 PTA *
ptaReverse(PTA * ptas,l_int32 type)358 ptaReverse(PTA *ptas,
359 l_int32 type)
360 {
361 l_int32 n, i, ix, iy;
362 l_float32 x, y;
363 PTA *ptad;
364
365 PROCNAME("ptaReverse");
366
367 if (!ptas)
368 return (PTA *)ERROR_PTR("ptas not defined", procName, NULL);
369
370 n = ptaGetCount(ptas);
371 if ((ptad = ptaCreate(n)) == NULL)
372 return (PTA *)ERROR_PTR("ptad not made", procName, NULL);
373 for (i = n - 1; i >= 0; i--) {
374 if (type == 0) {
375 ptaGetPt(ptas, i, &x, &y);
376 ptaAddPt(ptad, x, y);
377 }
378 else { /* type == 1 */
379 ptaGetIPt(ptas, i, &ix, &iy);
380 ptaAddPt(ptad, ix, iy);
381 }
382 }
383
384 return ptad;
385 }
386
387
388 /*!
389 * ptaCyclicPerm()
390 *
391 * Input: ptas
392 * xs, ys (start point; must be in ptas)
393 * Return: ptad (cyclic permutation, starting and ending at (xs, ys),
394 * or null on error
395 *
396 * Note: we check to insure that ptas is a closed path where
397 * the first and last points are identical, and the
398 * resulting pta also starts and ends on the same point
399 * (which in this case is (xs, ys).
400 */
401 PTA *
ptaCyclicPerm(PTA * ptas,l_int32 xs,l_int32 ys)402 ptaCyclicPerm(PTA *ptas,
403 l_int32 xs,
404 l_int32 ys)
405 {
406 l_int32 n, i, x, y, j, index, state;
407 l_int32 x1, y1, x2, y2;
408 PTA *ptad;
409
410 PROCNAME("ptaCyclicPerm");
411
412 if (!ptas)
413 return (PTA *)ERROR_PTR("ptas not defined", procName, NULL);
414
415 n = ptaGetCount(ptas);
416
417 /* verify input data */
418 ptaGetIPt(ptas, 0, &x1, &y1);
419 ptaGetIPt(ptas, n - 1, &x2, &y2);
420 if (x1 != x2 || y1 != y2)
421 return (PTA *)ERROR_PTR("start and end pts not same", procName, NULL);
422 state = L_NOT_FOUND;
423 for (i = 0; i < n; i++) {
424 ptaGetIPt(ptas, i, &x, &y);
425 if (x == xs && y == ys) {
426 state = L_FOUND;
427 break;
428 }
429 }
430 if (state == L_NOT_FOUND)
431 return (PTA *)ERROR_PTR("start pt not in ptas", procName, NULL);
432
433 if ((ptad = ptaCreate(n)) == NULL)
434 return (PTA *)ERROR_PTR("ptad not made", procName, NULL);
435 for (j = 0; j < n - 1; j++) {
436 if (i + j < n - 1)
437 index = i + j;
438 else
439 index = (i + j + 1) % n;
440 ptaGetIPt(ptas, index, &x, &y);
441 ptaAddPt(ptad, x, y);
442 }
443 ptaAddPt(ptad, xs, ys);
444
445 return ptad;
446 }
447
448
449 /*!
450 * ptaSort()
451 *
452 * Input: ptas
453 * sorttype (L_SORT_BY_X, L_SORT_BY_Y)
454 * sortorder (L_SORT_INCREASING, L_SORT_DECREASING)
455 * &naindex (<optional return> index of sorted order into
456 * original array)
457 * Return: ptad (sorted version of ptas), or null on error
458 */
459 PTA *
ptaSort(PTA * ptas,l_int32 sorttype,l_int32 sortorder,NUMA ** pnaindex)460 ptaSort(PTA *ptas,
461 l_int32 sorttype,
462 l_int32 sortorder,
463 NUMA **pnaindex)
464 {
465 l_int32 i, index, n;
466 l_float32 x, y;
467 PTA *ptad;
468 NUMA *na, *naindex;
469
470 PROCNAME("ptaSort");
471
472 if (!ptas)
473 return (PTA *)ERROR_PTR("ptas not defined", procName, NULL);
474 if (sorttype != L_SORT_BY_X && sorttype != L_SORT_BY_Y)
475 return (PTA *)ERROR_PTR("invalid sort type", procName, NULL);
476 if (sortorder != L_SORT_INCREASING && sortorder != L_SORT_DECREASING)
477 return (PTA *)ERROR_PTR("invalid sort order", procName, NULL);
478
479 /* Build up numa of specific data */
480 n = ptaGetCount(ptas);
481 if ((na = numaCreate(n)) == NULL)
482 return (PTA *)ERROR_PTR("na not made", procName, NULL);
483 for (i = 0; i < n; i++) {
484 ptaGetPt(ptas, i, &x, &y);
485 if (sorttype == L_SORT_BY_X)
486 numaAddNumber(na, x);
487 else
488 numaAddNumber(na, y);
489 }
490
491 /* Get the sort index for data array */
492 if ((naindex = numaGetSortIndex(na, sortorder)) == NULL)
493 return (PTA *)ERROR_PTR("naindex not made", procName, NULL);
494
495 /* Build up sorted pta using sort index */
496 if ((ptad = ptaCreate(n)) == NULL)
497 return (PTA *)ERROR_PTR("ptad not made", procName, NULL);
498 for (i = 0; i < n; i++) {
499 numaGetIValue(naindex, i, &index);
500 ptaGetPt(ptas, index, &x, &y);
501 ptaAddPt(ptad, x, y);
502 }
503
504 if (pnaindex)
505 *pnaindex = naindex;
506 else
507 numaDestroy(&naindex);
508 numaDestroy(&na);
509 return ptad;
510 }
511
512
513 /*!
514 * ptaRemoveDuplicates()
515 *
516 * Input: ptas (assumed to be integer values)
517 * factor (should be larger than the largest point value;
518 * use 0 for default)
519 * Return: ptad (with duplicates removed), or null on error
520 */
521 PTA *
ptaRemoveDuplicates(PTA * ptas,l_uint32 factor)522 ptaRemoveDuplicates(PTA *ptas,
523 l_uint32 factor)
524 {
525 l_int32 nsize, i, j, k, index, n, nvals;
526 l_int32 x, y, xk, yk;
527 l_int32 *ia;
528 PTA *ptad;
529 NUMA *na;
530 NUMAHASH *nahash;
531
532 PROCNAME("ptaRemoveDuplicates");
533
534 if (!ptas)
535 return (PTA *)ERROR_PTR("ptas not defined", procName, NULL);
536 if (factor == 0)
537 factor = DEFAULT_SPREADING_FACTOR;
538
539 /* Build up numaHash of indices, hashed by a key that is
540 * a large linear combination of x and y values designed to
541 * randomize the key. */
542 nsize = 5507; /* buckets in hash table; prime */
543 nahash = numaHashCreate(nsize, 2);
544 n = ptaGetCount(ptas);
545 for (i = 0; i < n; i++) {
546 ptaGetIPt(ptas, i, &x, &y);
547 numaHashAdd(nahash, factor * x + y, (l_float32)i);
548 }
549
550 if ((ptad = ptaCreate(n)) == NULL)
551 return (PTA *)ERROR_PTR("ptad not made", procName, NULL);
552 for (i = 0; i < nsize; i++) {
553 na = numaHashGetNuma(nahash, i);
554 if (!na) continue;
555
556 nvals = numaGetCount(na);
557 /* If more than 1 pt, compare exhaustively with double loop;
558 * otherwise, just enter it. */
559 if (nvals > 1) {
560 if ((ia = (l_int32 *)CALLOC(nvals, sizeof(l_int32))) == NULL)
561 return (PTA *)ERROR_PTR("ia not made", procName, NULL);
562 for (j = 0; j < nvals; j++) {
563 if (ia[j] == 1) continue;
564 numaGetIValue(na, j, &index);
565 ptaGetIPt(ptas, index, &x, &y);
566 ptaAddPt(ptad, x, y);
567 for (k = j + 1; k < nvals; k++) {
568 if (ia[k] == 1) continue;
569 numaGetIValue(na, k, &index);
570 ptaGetIPt(ptas, index, &xk, &yk);
571 if (x == xk && y == yk) /* duplicate */
572 ia[k] = 1;
573 }
574 }
575 FREE(ia);
576 }
577 else {
578 numaGetIValue(na, 0, &index);
579 ptaGetIPt(ptas, index, &x, &y);
580 ptaAddPt(ptad, x, y);
581 }
582 numaDestroy(&na); /* the clone */
583 }
584
585 numaHashDestroy(&nahash);
586 return ptad;
587 }
588
589
590
591 /*---------------------------------------------------------------------*
592 * Pta accessors *
593 *---------------------------------------------------------------------*/
594 l_int32
ptaGetRefcount(PTA * pta)595 ptaGetRefcount(PTA *pta)
596 {
597 PROCNAME("ptaGetRefcount");
598
599 if (!pta)
600 return ERROR_INT("pta not defined", procName, 1);
601 return pta->refcount;
602 }
603
604
605 l_int32
ptaChangeRefcount(PTA * pta,l_int32 delta)606 ptaChangeRefcount(PTA *pta,
607 l_int32 delta)
608 {
609 PROCNAME("ptaChangeRefcount");
610
611 if (!pta)
612 return ERROR_INT("pta not defined", procName, 1);
613 pta->refcount += delta;
614 return 0;
615 }
616
617
618 /*!
619 * ptaGetCount()
620 *
621 * Input: pta
622 * Return: count, or 0 if no pta
623 */
624 l_int32
ptaGetCount(PTA * pta)625 ptaGetCount(PTA *pta)
626 {
627 PROCNAME("ptaGetCount");
628
629 if (!pta)
630 return ERROR_INT("pta not defined", procName, 0);
631
632 return pta->n;
633 }
634
635
636 /*!
637 * ptaGetPt()
638 *
639 * Input: pta
640 * index (into arrays)
641 * &x, &y (<return> float values)
642 * Return: 0 if OK; 1 on error
643 */
644 l_int32
ptaGetPt(PTA * pta,l_int32 index,l_float32 * px,l_float32 * py)645 ptaGetPt(PTA *pta,
646 l_int32 index,
647 l_float32 *px,
648 l_float32 *py)
649 {
650 PROCNAME("ptaGetPt");
651
652 if (!pta)
653 return ERROR_INT("pta not defined", procName, 1);
654
655 *px = pta->x[index];
656 *py = pta->y[index];
657 return 0;
658 }
659
660
661 /*!
662 * ptaGetIPt()
663 *
664 * Input: pta
665 * index (into arrays)
666 * &x, &y (<return> integer values)
667 * Return: 0 if OK; 1 on error
668 */
669 l_int32
ptaGetIPt(PTA * pta,l_int32 index,l_int32 * px,l_int32 * py)670 ptaGetIPt(PTA *pta,
671 l_int32 index,
672 l_int32 *px,
673 l_int32 *py)
674 {
675 PROCNAME("ptaGetIPt");
676
677 if (!pta)
678 return ERROR_INT("pta not defined", procName, 1);
679
680 *px = (l_int32)(pta->x[index] + 0.5);
681 *py = (l_int32)(pta->y[index] + 0.5);
682 return 0;
683 }
684
685
686 /*!
687 * ptaGetArrays()
688 *
689 * Input: pta
690 * &nax, &nay (<return> numas of x and y arrays)
691 * Return: 0 if OK; 1 on error or if pta is empty
692 *
693 * Notes:
694 * (1) This copies the internal arrays into new Numas, and returns them.
695 * (2) Manipulates internal arrays in pta and numa directly.
696 */
697 l_int32
ptaGetArrays(PTA * pta,NUMA ** pnax,NUMA ** pnay)698 ptaGetArrays(PTA *pta,
699 NUMA **pnax,
700 NUMA **pnay)
701 {
702 l_int32 i, n;
703 NUMA *nax, *nay;
704
705 PROCNAME("ptaGetArrays");
706
707 if (!pta)
708 return ERROR_INT("pta not defined", procName, 1);
709 if (!pnax)
710 return ERROR_INT("&nax not defined", procName, 1);
711 if (!pnay)
712 return ERROR_INT("&nay not defined", procName, 1);
713
714 *pnax = *pnay = NULL;
715 if ((n = ptaGetCount(pta)) == 0)
716 return ERROR_INT("pta is empty", procName, 1);
717
718 if ((nax = numaCreate(n)) == NULL)
719 return ERROR_INT("nax not made", procName, 1);
720 *pnax = nax;
721 if ((nay = numaCreate(n)) == NULL)
722 return ERROR_INT("nay not made", procName, 1);
723 *pnay = nay;
724
725 /* use arrays directly for efficiency */
726 for (i = 0; i < n; i++) {
727 nax->array[i] = pta->x[i];
728 nay->array[i] = pta->y[i];
729 }
730 nax->n = nay->n = n;
731
732 return 0;
733 }
734
735
736
737 /*---------------------------------------------------------------------*
738 * PTAA creation, destruction *
739 *---------------------------------------------------------------------*/
740 /*!
741 * ptaaCreate()
742 *
743 * Input: n (initial number of ptrs)
744 * Return: ptaa, or null on error
745 */
746 PTAA *
ptaaCreate(l_int32 n)747 ptaaCreate(l_int32 n)
748 {
749 PTAA *ptaa;
750
751 PROCNAME("ptaaCreate");
752
753 if (n <= 0)
754 n = INITIAL_PTR_ARRAYSIZE;
755
756 if ((ptaa = (PTAA *)CALLOC(1, sizeof(PTAA))) == NULL)
757 return (PTAA *)ERROR_PTR("ptaa not made", procName, NULL);
758 ptaa->n = 0;
759 ptaa->nalloc = n;
760
761 if ((ptaa->pta = (PTA **)CALLOC(n, sizeof(PTA *))) == NULL)
762 return (PTAA *)ERROR_PTR("pta ptrs not made", procName, NULL);
763
764 return ptaa;
765 }
766
767
768 /*!
769 * ptaaDestroy()
770 *
771 * Input: &ptaa <to be nulled>
772 * Return: void
773 */
774 void
ptaaDestroy(PTAA ** pptaa)775 ptaaDestroy(PTAA **pptaa)
776 {
777 l_int32 i;
778 PTAA *ptaa;
779
780 PROCNAME("ptaaDestroy");
781
782 if (pptaa == NULL) {
783 L_WARNING("ptr address is NULL!", procName);
784 return;
785 }
786
787 if ((ptaa = *pptaa) == NULL)
788 return;
789
790 for (i = 0; i < ptaa->n; i++)
791 ptaDestroy(&ptaa->pta[i]);
792 FREE(ptaa->pta);
793
794 FREE(ptaa);
795 *pptaa = NULL;
796 return;
797 }
798
799
800 /*---------------------------------------------------------------------*
801 * PTAA array extension *
802 *---------------------------------------------------------------------*/
803 /*!
804 * ptaaAddPta()
805 *
806 * Input: ptaa
807 * pta (to be added)
808 * copyflag (L_INSERT, L_COPY, L_CLONE)
809 * Return: 0 if OK, 1 on error
810 */
811 l_int32
ptaaAddPta(PTAA * ptaa,PTA * pta,l_int32 copyflag)812 ptaaAddPta(PTAA *ptaa,
813 PTA *pta,
814 l_int32 copyflag)
815 {
816 l_int32 n;
817 PTA *ptac;
818
819 PROCNAME("ptaaAddPta");
820
821 if (!ptaa)
822 return ERROR_INT("ptaa not defined", procName, 1);
823 if (!pta)
824 return ERROR_INT("pta not defined", procName, 1);
825
826 if (copyflag == L_INSERT)
827 ptac = pta;
828 else if (copyflag == L_COPY) {
829 if ((ptac = ptaCopy(pta)) == NULL)
830 return ERROR_INT("ptac not made", procName, 1);
831 }
832 else if (copyflag == L_CLONE) {
833 if ((ptac = ptaClone(pta)) == NULL)
834 return ERROR_INT("pta clone not made", procName, 1);
835 }
836 else
837 return ERROR_INT("invalid copyflag", procName, 1);
838
839 n = ptaaGetCount(ptaa);
840 if (n >= ptaa->nalloc)
841 ptaaExtendArray(ptaa);
842 ptaa->pta[n] = ptac;
843 ptaa->n++;
844
845 return 0;
846 }
847
848
849 /*!
850 * ptaaExtendArray()
851 *
852 * Input: ptaa
853 * Return: 0 if OK, 1 on error
854 */
855 l_int32
ptaaExtendArray(PTAA * ptaa)856 ptaaExtendArray(PTAA *ptaa)
857 {
858 PROCNAME("ptaaExtendArray");
859
860 if (!ptaa)
861 return ERROR_INT("ptaa not defined", procName, 1);
862
863 if ((ptaa->pta = (PTA **)reallocNew((void **)&ptaa->pta,
864 sizeof(PTA *) * ptaa->nalloc,
865 2 * sizeof(PTA *) * ptaa->nalloc)) == NULL)
866 return ERROR_INT("new ptr array not returned", procName, 1);
867
868 ptaa->nalloc = 2 * ptaa->nalloc;
869 return 0;
870 }
871
872
873 /*---------------------------------------------------------------------*
874 * Ptaa accessors *
875 *---------------------------------------------------------------------*/
876 /*!
877 * ptaaGetCount()
878 *
879 * Input: ptaa
880 * Return: count, or 0 if no ptaa
881 */
882 l_int32
ptaaGetCount(PTAA * ptaa)883 ptaaGetCount(PTAA *ptaa)
884 {
885 PROCNAME("ptaaGetCount");
886
887 if (!ptaa)
888 return ERROR_INT("ptaa not defined", procName, 0);
889
890 return ptaa->n;
891 }
892
893
894 /*!
895 * ptaaGetPta()
896 *
897 * Input: ptaa
898 * index (to the i-th pta)
899 * accessflag (L_COPY or L_CLONE)
900 * Return: pta, or null on error
901 */
902 PTA *
ptaaGetPta(PTAA * ptaa,l_int32 index,l_int32 accessflag)903 ptaaGetPta(PTAA *ptaa,
904 l_int32 index,
905 l_int32 accessflag)
906 {
907 PROCNAME("ptaaGetPta");
908
909 if (!ptaa)
910 return (PTA *)ERROR_PTR("ptaa not defined", procName, NULL);
911 if (index < 0 || index >= ptaa->n)
912 return (PTA *)ERROR_PTR("index not valid", procName, NULL);
913
914 if (accessflag == L_COPY)
915 return ptaCopy(ptaa->pta[index]);
916 else if (accessflag == L_CLONE)
917 return ptaClone(ptaa->pta[index]);
918 else
919 return (PTA *)ERROR_PTR("invalid accessflag", procName, NULL);
920 }
921
922
923
924 /*---------------------------------------------------------------------*
925 * Ptaa serialized I/O *
926 *---------------------------------------------------------------------*/
927 /*!
928 * ptaaRead()
929 *
930 * Input: filename
931 * Return: ptaa, or null on error
932 */
933 PTAA *
ptaaRead(const char * filename)934 ptaaRead(const char *filename)
935 {
936 FILE *fp;
937 PTAA *ptaa;
938
939 PROCNAME("ptaaRead");
940
941 if (!filename)
942 return (PTAA *)ERROR_PTR("filename not defined", procName, NULL);
943 if ((fp = fopenReadStream(filename)) == NULL)
944 return (PTAA *)ERROR_PTR("stream not opened", procName, NULL);
945
946 if ((ptaa = ptaaReadStream(fp)) == NULL) {
947 fclose(fp);
948 return (PTAA *)ERROR_PTR("ptaa not read", procName, NULL);
949 }
950
951 fclose(fp);
952 return ptaa;
953 }
954
955
956 /*!
957 * ptaaReadStream()
958 *
959 * Input: stream
960 * Return: ptaa, or null on error
961 */
962 PTAA *
ptaaReadStream(FILE * fp)963 ptaaReadStream(FILE *fp)
964 {
965 l_int32 i, n, version;
966 PTA *pta;
967 PTAA *ptaa;
968
969 PROCNAME("ptaaReadStream");
970
971 if (!fp)
972 return (PTAA *)ERROR_PTR("stream not defined", procName, NULL);
973
974 if (fscanf(fp, "\nPtaa Version %d\n", &version) != 1)
975 return (PTAA *)ERROR_PTR("not a ptaa file", procName, NULL);
976 if (version != PTA_VERSION_NUMBER)
977 return (PTAA *)ERROR_PTR("invalid ptaa version", procName, NULL);
978 if (fscanf(fp, "Number of Pta = %d\n", &n) != 1)
979 return (PTAA *)ERROR_PTR("not a ptaa file", procName, NULL);
980
981 if ((ptaa = ptaaCreate(n)) == NULL)
982 return (PTAA *)ERROR_PTR("ptaa not made", procName, NULL);
983 for (i = 0; i < n; i++) {
984 if ((pta = ptaReadStream(fp)) == NULL)
985 return (PTAA *)ERROR_PTR("error reading pta", procName, NULL);
986 ptaaAddPta(ptaa, pta, L_INSERT);
987 }
988
989 return ptaa;
990 }
991
992
993 /*!
994 * ptaaWrite()
995 *
996 * Input: filename
997 * ptaa
998 * type (0 for float values; 1 for integer values)
999 * Return: 0 if OK, 1 on error
1000 */
1001 l_int32
ptaaWrite(const char * filename,PTAA * ptaa,l_int32 type)1002 ptaaWrite(const char *filename,
1003 PTAA *ptaa,
1004 l_int32 type)
1005 {
1006 FILE *fp;
1007
1008 PROCNAME("ptaaWrite");
1009
1010 if (!filename)
1011 return ERROR_INT("filename not defined", procName, 1);
1012 if (!ptaa)
1013 return ERROR_INT("ptaa not defined", procName, 1);
1014
1015 if ((fp = fopen(filename, "w")) == NULL)
1016 return ERROR_INT("stream not opened", procName, 1);
1017 if (ptaaWriteStream(fp, ptaa, type))
1018 return ERROR_INT("ptaa not written to stream", procName, 1);
1019 fclose(fp);
1020
1021 return 0;
1022 }
1023
1024
1025 /*!
1026 * ptaaWriteStream()
1027 *
1028 * Input: stream
1029 * ptaa
1030 * type (0 for float values; 1 for integer values)
1031 * Return: 0 if OK; 1 on error
1032 */
1033 l_int32
ptaaWriteStream(FILE * fp,PTAA * ptaa,l_int32 type)1034 ptaaWriteStream(FILE *fp,
1035 PTAA *ptaa,
1036 l_int32 type)
1037 {
1038 l_int32 i, n;
1039 PTA *pta;
1040
1041 PROCNAME("ptaaWriteStream");
1042
1043 if (!fp)
1044 return ERROR_INT("stream not defined", procName, 1);
1045 if (!ptaa)
1046 return ERROR_INT("ptaa not defined", procName, 1);
1047
1048 n = ptaaGetCount(ptaa);
1049 fprintf(fp, "\nPtaa Version %d\n", PTA_VERSION_NUMBER);
1050 fprintf(fp, "Number of Pta = %d\n", n);
1051 for (i = 0; i < n; i++) {
1052 pta = ptaaGetPta(ptaa, i, L_CLONE);
1053 ptaWriteStream(fp, pta, type);
1054 ptaDestroy(&pta);
1055 }
1056
1057 return 0;
1058 }
1059
1060
1061 /*---------------------------------------------------------------------*
1062 * Pta serialized I/O *
1063 *---------------------------------------------------------------------*/
1064 /*!
1065 * ptaRead()
1066 *
1067 * Input: filename
1068 * Return: pta, or null on error
1069 */
1070 PTA *
ptaRead(const char * filename)1071 ptaRead(const char *filename)
1072 {
1073 FILE *fp;
1074 PTA *pta;
1075
1076 PROCNAME("ptaRead");
1077
1078 if (!filename)
1079 return (PTA *)ERROR_PTR("filename not defined", procName, NULL);
1080 if ((fp = fopenReadStream(filename)) == NULL)
1081 return (PTA *)ERROR_PTR("stream not opened", procName, NULL);
1082
1083 if ((pta = ptaReadStream(fp)) == NULL) {
1084 fclose(fp);
1085 return (PTA *)ERROR_PTR("pta not read", procName, NULL);
1086 }
1087
1088 fclose(fp);
1089 return pta;
1090 }
1091
1092
1093 /*!
1094 * ptaReadStream()
1095 *
1096 * Input: stream
1097 * Return: pta, or null on error
1098 */
1099 PTA *
ptaReadStream(FILE * fp)1100 ptaReadStream(FILE *fp)
1101 {
1102 char typestr[128];
1103 l_int32 i, n, ix, iy, type, version;
1104 l_float32 x, y;
1105 PTA *pta;
1106
1107 PROCNAME("ptaReadStream");
1108
1109 if (!fp)
1110 return (PTA *)ERROR_PTR("stream not defined", procName, NULL);
1111
1112 if (fscanf(fp, "\n Pta Version %d\n", &version) != 1)
1113 return (PTA *)ERROR_PTR("not a pta file", procName, NULL);
1114 if (version != PTA_VERSION_NUMBER)
1115 return (PTA *)ERROR_PTR("invalid pta version", procName, NULL);
1116 if (fscanf(fp, " Number of pts = %d; format = %s\n", &n, typestr) != 2)
1117 return (PTA *)ERROR_PTR("not a pta file", procName, NULL);
1118 if (!strcmp(typestr, "float"))
1119 type = 0;
1120 else /* typestr is "integer" */
1121 type = 1;
1122
1123 if ((pta = ptaCreate(n)) == NULL)
1124 return (PTA *)ERROR_PTR("pta not made", procName, NULL);
1125 for (i = 0; i < n; i++) {
1126 if (type == 0) { /* data is float */
1127 fscanf(fp, " (%f, %f)\n", &x, &y);
1128 ptaAddPt(pta, x, y);
1129 }
1130 else { /* data is integer */
1131 fscanf(fp, " (%d, %d)\n", &ix, &iy);
1132 ptaAddPt(pta, ix, iy);
1133 }
1134 }
1135
1136 return pta;
1137 }
1138
1139
1140 /*!
1141 * ptaWrite()
1142 *
1143 * Input: filename
1144 * pta
1145 * type (0 for float values; 1 for integer values)
1146 * Return: 0 if OK, 1 on error
1147 */
1148 l_int32
ptaWrite(const char * filename,PTA * pta,l_int32 type)1149 ptaWrite(const char *filename,
1150 PTA *pta,
1151 l_int32 type)
1152 {
1153 FILE *fp;
1154
1155 PROCNAME("ptaWrite");
1156
1157 if (!filename)
1158 return ERROR_INT("filename not defined", procName, 1);
1159 if (!pta)
1160 return ERROR_INT("pta not defined", procName, 1);
1161
1162 if ((fp = fopen(filename, "w")) == NULL)
1163 return ERROR_INT("stream not opened", procName, 1);
1164 if (ptaWriteStream(fp, pta, type))
1165 return ERROR_INT("pta not written to stream", procName, 1);
1166 fclose(fp);
1167
1168 return 0;
1169 }
1170
1171
1172 /*!
1173 * ptaWriteStream()
1174 *
1175 * Input: stream
1176 * pta
1177 * type (0 for float values; 1 for integer values)
1178 * Return: 0 if OK; 1 on error
1179 */
1180 l_int32
ptaWriteStream(FILE * fp,PTA * pta,l_int32 type)1181 ptaWriteStream(FILE *fp,
1182 PTA *pta,
1183 l_int32 type)
1184 {
1185 l_int32 i, n, ix, iy;
1186 l_float32 x, y;
1187
1188 PROCNAME("ptaWriteStream");
1189
1190 if (!fp)
1191 return ERROR_INT("stream not defined", procName, 1);
1192 if (!pta)
1193 return ERROR_INT("pta not defined", procName, 1);
1194
1195 n = ptaGetCount(pta);
1196 fprintf(fp, "\n Pta Version %d\n", PTA_VERSION_NUMBER);
1197 if (type == 0)
1198 fprintf(fp, " Number of pts = %d; format = float\n", n);
1199 else /* type == 1 */
1200 fprintf(fp, " Number of pts = %d; format = integer\n", n);
1201 for (i = 0; i < n; i++) {
1202 if (type == 0) { /* data is float */
1203 ptaGetPt(pta, i, &x, &y);
1204 fprintf(fp, " (%f, %f)\n", x, y);
1205 }
1206 else { /* data is integer */
1207 ptaGetIPt(pta, i, &ix, &iy);
1208 fprintf(fp, " (%d, %d)\n", ix, iy);
1209 }
1210 }
1211
1212 return 0;
1213 }
1214
1215
1216
1217 /*---------------------------------------------------------------------*
1218 * In use *
1219 *---------------------------------------------------------------------*/
1220 /*!
1221 * ptaGetExtent()
1222 *
1223 * Input: pta
1224 * Return: box, or null on error
1225 *
1226 * Notes:
1227 * (1) Returns a box of minimum size containing pts in pta.
1228 */
1229 BOX *
ptaGetExtent(PTA * pta)1230 ptaGetExtent(PTA *pta)
1231 {
1232 l_int32 n, i, x, y, minx, maxx, miny, maxy;
1233
1234 PROCNAME("ptaGetExtent");
1235
1236 if (!pta)
1237 return (BOX *)ERROR_PTR("pta not defined", procName, NULL);
1238
1239 minx = 10000000;
1240 miny = 10000000;
1241 maxx = -10000000;
1242 maxy = -10000000;
1243 n = ptaGetCount(pta);
1244 for (i = 0; i < n; i++) {
1245 ptaGetIPt(pta, i, &x, &y);
1246 if (x < minx) minx = x;
1247 if (x > maxx) maxx = x;
1248 if (y < miny) miny = y;
1249 if (y > maxy) maxy = y;
1250 }
1251
1252 return boxCreate(minx, miny, maxx - minx + 1, maxy - miny + 1);
1253 }
1254
1255
1256 /*!
1257 * ptaGetInsideBox()
1258 *
1259 * Input: ptas (input pts)
1260 * box
1261 * Return: ptad (of pts in ptas that are inside the box),
1262 * or null on error
1263 */
1264 PTA *
ptaGetInsideBox(PTA * ptas,BOX * box)1265 ptaGetInsideBox(PTA *ptas,
1266 BOX *box)
1267 {
1268 PTA *ptad;
1269 l_int32 n, i, contains;
1270 l_float32 x, y;
1271
1272 PROCNAME("ptaGetInsideBox");
1273
1274 if (!ptas)
1275 return (PTA *)ERROR_PTR("ptas not defined", procName, NULL);
1276 if (!box)
1277 return (PTA *)ERROR_PTR("box not defined", procName, NULL);
1278
1279 n = ptaGetCount(ptas);
1280 ptad = ptaCreate(0);
1281 for (i = 0; i < n; i++) {
1282 ptaGetPt(ptas, i, &x, &y);
1283 boxContainsPt(box, x, y, &contains);
1284 if (contains)
1285 ptaAddPt(ptad, x, y);
1286 }
1287
1288 return ptad;
1289 }
1290
1291
1292 /*!
1293 * pixFindCornerPixels()
1294 *
1295 * Input: pixs (1 bpp)
1296 * Return: pta, or null on error
1297 *
1298 * Notes:
1299 * (1) Finds the 4 corner-most pixels, as defined by a search
1300 * inward from each corner, using a 45 degree line.
1301 */
1302 PTA *
pixFindCornerPixels(PIX * pixs)1303 pixFindCornerPixels(PIX *pixs)
1304 {
1305 l_int32 i, j, x, y, w, h, wpl, mindim, found;
1306 l_uint32 *data, *line;
1307 PTA *pta;
1308
1309 PROCNAME("pixFindCornerPixels");
1310
1311 if (!pixs)
1312 return (PTA *)ERROR_PTR("pixs not defined", procName, NULL);
1313 if (pixGetDepth(pixs) != 1)
1314 return (PTA *)ERROR_PTR("pixs not 1 bpp", procName, NULL);
1315
1316 w = pixGetWidth(pixs);
1317 h = pixGetHeight(pixs);
1318 mindim = L_MIN(w, h);
1319 data = pixGetData(pixs);
1320 wpl = pixGetWpl(pixs);
1321
1322 if ((pta = ptaCreate(4)) == NULL)
1323 return (PTA *)ERROR_PTR("pta not made", procName, NULL);
1324
1325 for (found = FALSE, i = 0; i < mindim; i++) {
1326 for (j = 0; j <= i; j++) {
1327 y = i - j;
1328 line = data + y * wpl;
1329 if (GET_DATA_BIT(line, j)) {
1330 ptaAddPt(pta, j, y);
1331 found = TRUE;
1332 break;
1333 }
1334 }
1335 if (found == TRUE)
1336 break;
1337 }
1338
1339 for (found = FALSE, i = 0; i < mindim; i++) {
1340 for (j = 0; j <= i; j++) {
1341 y = i - j;
1342 line = data + y * wpl;
1343 x = w - 1 - j;
1344 if (GET_DATA_BIT(line, x)) {
1345 ptaAddPt(pta, x, y);
1346 found = TRUE;
1347 break;
1348 }
1349 }
1350 if (found == TRUE)
1351 break;
1352 }
1353
1354 for (found = FALSE, i = 0; i < mindim; i++) {
1355 for (j = 0; j <= i; j++) {
1356 y = h - 1 - i + j;
1357 line = data + y * wpl;
1358 if (GET_DATA_BIT(line, j)) {
1359 ptaAddPt(pta, j, y);
1360 found = TRUE;
1361 break;
1362 }
1363 }
1364 if (found == TRUE)
1365 break;
1366 }
1367
1368 for (found = FALSE, i = 0; i < mindim; i++) {
1369 for (j = 0; j <= i; j++) {
1370 y = h - 1 - i + j;
1371 line = data + y * wpl;
1372 x = w - 1 - j;
1373 if (GET_DATA_BIT(line, x)) {
1374 ptaAddPt(pta, x, y);
1375 found = TRUE;
1376 break;
1377 }
1378 }
1379 if (found == TRUE)
1380 break;
1381 }
1382
1383 return pta;
1384 }
1385
1386
1387 /*!
1388 * pixPlotAlongPta()
1389 *
1390 * Input: pixs (any depth)
1391 * pta (set of points on which to plot)
1392 * outformat (GPLOT_PNG, GPLOT_PS, GPLOT_EPS, GPLOT_X11,
1393 * GPLOT_LATEX)
1394 * title (<optional> for plot; can be null)
1395 * Return: 0 if OK, 1 on error
1396 *
1397 * Notes:
1398 * (1) We remove any existing colormap and clip the pta to the input pixs.
1399 * (2) This is a debugging function, and does not remove temporary
1400 * plotting files that it generates.
1401 * (3) If the image is RGB, three separate plots are generated.
1402 */
1403 l_int32
pixPlotAlongPta(PIX * pixs,PTA * pta,l_int32 outformat,const char * title)1404 pixPlotAlongPta(PIX *pixs,
1405 PTA *pta,
1406 l_int32 outformat,
1407 const char *title)
1408 {
1409 char buffer[128];
1410 char *rtitle, *gtitle, *btitle;
1411 static l_int32 count = 0; /* require separate temp files for each call */
1412 l_int32 i, x, y, d, w, h, npts, rval, gval, bval;
1413 l_uint32 val;
1414 NUMA *na, *nar, *nag, *nab;
1415 PIX *pixt;
1416
1417 PROCNAME("pixPlotAlongLine");
1418
1419 if (!pixs)
1420 return ERROR_INT("pixs not defined", procName, 1);
1421 if (!pta)
1422 return ERROR_INT("pta not defined", procName, 1);
1423 if (outformat != GPLOT_PNG && outformat != GPLOT_PS &&
1424 outformat != GPLOT_EPS && outformat != GPLOT_X11 &&
1425 outformat != GPLOT_LATEX) {
1426 L_WARNING("outformat invalid; using GPLOT_PNG", procName);
1427 outformat = GPLOT_PNG;
1428 }
1429
1430 pixt = pixRemoveColormap(pixs, REMOVE_CMAP_BASED_ON_SRC);
1431 d = pixGetDepth(pixt);
1432 w = pixGetWidth(pixt);
1433 h = pixGetHeight(pixt);
1434 npts = ptaGetCount(pta);
1435 if (d == 32) {
1436 nar = numaCreate(npts);
1437 nag = numaCreate(npts);
1438 nab = numaCreate(npts);
1439 for (i = 0; i < npts; i++) {
1440 ptaGetIPt(pta, i, &x, &y);
1441 if (x < 0 || x >= w)
1442 continue;
1443 if (y < 0 || y >= h)
1444 continue;
1445 pixGetPixel(pixt, x, y, &val);
1446 rval = GET_DATA_BYTE(&val, COLOR_RED);
1447 gval = GET_DATA_BYTE(&val, COLOR_GREEN);
1448 bval = GET_DATA_BYTE(&val, COLOR_BLUE);
1449 numaAddNumber(nar, rval);
1450 numaAddNumber(nag, gval);
1451 numaAddNumber(nab, bval);
1452 }
1453
1454 sprintf(buffer, "junkplot.%d", count++);
1455 rtitle = stringJoin("Red: ", title);
1456 gplotSimple1(nar, outformat, buffer, rtitle);
1457 sprintf(buffer, "junkplot.%d", count++);
1458 gtitle = stringJoin("Green: ", title);
1459 gplotSimple1(nag, outformat, buffer, gtitle);
1460 sprintf(buffer, "junkplot.%d", count++);
1461 btitle = stringJoin("Blue: ", title);
1462 gplotSimple1(nab, outformat, buffer, btitle);
1463 numaDestroy(&nar);
1464 numaDestroy(&nag);
1465 numaDestroy(&nab);
1466 FREE(rtitle);
1467 FREE(gtitle);
1468 FREE(btitle);
1469 }
1470 else {
1471 na = numaCreate(npts);
1472 for (i = 0; i < npts; i++) {
1473 ptaGetIPt(pta, i, &x, &y);
1474 if (x < 0 || x >= w)
1475 continue;
1476 if (y < 0 || y >= h)
1477 continue;
1478 pixGetPixel(pixt, x, y, &val);
1479 numaAddNumber(na, (l_float32)val);
1480 }
1481
1482 sprintf(buffer, "junkplot.%d", count++);
1483 gplotSimple1(na, outformat, buffer, title);
1484 numaDestroy(&na);
1485 }
1486 pixDestroy(&pixt);
1487 return 0;
1488 }
1489
1490
1491 /*!
1492 * ptaContainsPt()
1493 *
1494 * Input: pta
1495 * x, y (point)
1496 * Return: 1 if contained, 0 otherwise or on error
1497 */
1498 l_int32
ptaContainsPt(PTA * pta,l_int32 x,l_int32 y)1499 ptaContainsPt(PTA *pta,
1500 l_int32 x,
1501 l_int32 y)
1502 {
1503 l_int32 i, n, ix, iy;
1504
1505 PROCNAME("ptaContainsPt");
1506
1507 if (!pta)
1508 return ERROR_INT("pta not defined", procName, 0);
1509
1510 n = ptaGetCount(pta);
1511 for (i = 0; i < n; i++) {
1512 ptaGetIPt(pta, i, &ix, &iy);
1513 if (x == ix && y == iy)
1514 return 1;
1515 }
1516 return 0;
1517 }
1518
1519
1520 /*!
1521 * ptaTestIntersection()
1522 *
1523 * Input: pta1, pta2
1524 * Return: bval which is 1 if they have any elements in common;
1525 * 0 otherwise or on error.
1526 */
1527 l_int32
ptaTestIntersection(PTA * pta1,PTA * pta2)1528 ptaTestIntersection(PTA *pta1,
1529 PTA *pta2)
1530 {
1531 l_int32 i, j, n1, n2, x1, y1, x2, y2;
1532
1533 PROCNAME("ptaTestIntersection");
1534
1535 if (!pta1)
1536 return ERROR_INT("pta1 not defined", procName, 0);
1537 if (!pta2)
1538 return ERROR_INT("pta2 not defined", procName, 0);
1539
1540 n1 = ptaGetCount(pta1);
1541 n2 = ptaGetCount(pta2);
1542 for (i = 0; i < n1; i++) {
1543 ptaGetIPt(pta1, i, &x1, &y1);
1544 for (j = 0; j < n2; j++) {
1545 ptaGetIPt(pta2, i, &x2, &y2);
1546 if (x1 == x2 && y1 == y2)
1547 return 1;
1548 }
1549 }
1550
1551 return 0;
1552 }
1553
1554
1555 /*!
1556 * ptaTransform()
1557 *
1558 * Input: pta
1559 * shiftx, shifty
1560 * scalex, scaley
1561 * Return: pta, or null on error
1562 *
1563 * Notes:
1564 * (1) Shift first, then scale.
1565 */
1566 PTA *
ptaTransform(PTA * ptas,l_int32 shiftx,l_int32 shifty,l_float32 scalex,l_float32 scaley)1567 ptaTransform(PTA *ptas,
1568 l_int32 shiftx,
1569 l_int32 shifty,
1570 l_float32 scalex,
1571 l_float32 scaley)
1572 {
1573 l_int32 n, i, x, y;
1574 PTA *ptad;
1575
1576 PROCNAME("ptaTransform");
1577
1578 if (!ptas)
1579 return (PTA *)ERROR_PTR("ptas not defined", procName, NULL);
1580 n = ptaGetCount(ptas);
1581 ptad = ptaCreate(n);
1582 for (i = 0; i < n; i++) {
1583 ptaGetIPt(ptas, i, &x, &y);
1584 x = (l_int32)(scalex * (x + shiftx) + 0.5);
1585 y = (l_int32)(scaley * (y + shifty) + 0.5);
1586 ptaAddPt(ptad, x, y);
1587 }
1588
1589 return ptad;
1590 }
1591
1592
1593 /*!
1594 * ptaSubsample()
1595 *
1596 * Input: ptas
1597 * subfactor (subsample factor, >= 1)
1598 * Return: ptad (evenly sampled pt values from ptas, or null on error
1599 */
1600 PTA *
ptaSubsample(PTA * ptas,l_int32 subfactor)1601 ptaSubsample(PTA *ptas,
1602 l_int32 subfactor)
1603 {
1604 l_int32 n, i;
1605 l_float32 x, y;
1606 PTA *ptad;
1607
1608 PROCNAME("pixSubsample");
1609
1610 if (!ptas)
1611 return (PTA *)ERROR_PTR("ptas not defined", procName, NULL);
1612 if (subfactor < 1)
1613 return (PTA *)ERROR_PTR("subfactor < 1", procName, NULL);
1614
1615 ptad = ptaCreate(0);
1616 n = ptaGetCount(ptas);
1617 for (i = 0; i < n; i++) {
1618 if (i % subfactor != 0) continue;
1619 ptaGetPt(ptas, i, &x, &y);
1620 ptaAddPt(ptad, x, y);
1621 }
1622
1623 return ptad;
1624 }
1625
1626
1627 /*!
1628 * ptaGetLinearLSF()
1629 *
1630 * Input: pta
1631 * &a (<optional return> slope a of least square fit: y = ax + b)
1632 * &b (<optional return> intercept b of least square fit)
1633 * &nafit (<optional return> numa of least square fit)
1634 * Return: 0 if OK, 1 on error
1635 *
1636 * Notes:
1637 * (1) At least one of: &a and &b must not be null.
1638 * (2) If both &a and &b are defined, this returns a and b that minimize:
1639 *
1640 * sum (yi - axi -b)^2
1641 * i
1642 *
1643 * The method is simple: differentiate this expression w/rt a and b,
1644 * and solve the resulting two equations for a and b in terms of
1645 * various sums over the input data (xi, yi).
1646 * (3) We also allow two special cases, where either a = 0 or b = 0:
1647 * (a) If &a is given and &b = null, find the linear LSF that
1648 * goes through the origin (b = 0).
1649 * (b) If &b is given and &a = null, find the linear LSF with
1650 * zero slope (a = 0).
1651 * (4) If @nafit is defined, this returns an array of fitted values,
1652 * corresponding to the two implicit Numa arrays (nax and nay) in pta.
1653 * Thus, just as you can plot the data in pta as nay vs. nax,
1654 * you can plot the linear least square fit as nafit vs. nax.
1655 */
1656 l_int32
ptaGetLinearLSF(PTA * pta,l_float32 * pa,l_float32 * pb,NUMA ** pnafit)1657 ptaGetLinearLSF(PTA *pta,
1658 l_float32 *pa,
1659 l_float32 *pb,
1660 NUMA **pnafit)
1661 {
1662 l_int32 n, i;
1663 l_float32 factor, sx, sy, sxx, sxy, val;
1664 l_float32 *xa, *ya;
1665
1666 PROCNAME("ptaGetLinearLSF");
1667
1668 if (!pta)
1669 return ERROR_INT("pta not defined", procName, 1);
1670 if (!pa && !pb)
1671 return ERROR_INT("&a and/or &b not defined", procName, 1);
1672 if (pa) *pa = 0.0;
1673 if (pb) *pb = 0.0;
1674
1675 if ((n = ptaGetCount(pta)) < 2)
1676 return ERROR_INT("less than 2 pts not found", procName, 1);
1677 xa = pta->x; /* not a copy */
1678 ya = pta->y; /* not a copy */
1679
1680 sx = sy = sxx = sxy = 0.;
1681 if (pa && pb) {
1682 for (i = 0; i < n; i++) {
1683 sx += xa[i];
1684 sy += ya[i];
1685 sxx += xa[i] * xa[i];
1686 sxy += xa[i] * ya[i];
1687 }
1688 factor = n * sxx - sx * sx;
1689 if (factor == 0.0)
1690 return ERROR_INT("no solution found", procName, 1);
1691 factor = 1. / factor;
1692
1693 *pa = factor * ((l_float32)n * sxy - sx * sy);
1694 *pb = factor * (sxx * sy - sx * sxy);
1695 }
1696 else if (pa) { /* line through origin */
1697 for (i = 0; i < n; i++) {
1698 sxx += xa[i] * xa[i];
1699 sxy += xa[i] * ya[i];
1700 }
1701 if (sxx == 0.0)
1702 return ERROR_INT("no solution found", procName, 1);
1703 *pa = sxy / sxx;
1704 }
1705 else { /* a = 0; horizontal line */
1706 for (i = 0; i < n; i++)
1707 sy += ya[i];
1708 *pb = sy / (l_float32)n;
1709 }
1710
1711 if (pnafit) {
1712 *pnafit = numaCreate(n);
1713 for (i = 0; i < n; i++) {
1714 val = (*pa) * xa[i] + *pb;
1715 numaAddNumber(*pnafit, val);
1716 }
1717 }
1718
1719 return 0;
1720 }
1721
1722
1723 /*!
1724 * ptaGetPixelsFromPix()
1725 *
1726 * Input: pixs (1 bpp)
1727 * box (<optional> can be null)
1728 * Return: pta, or null on error
1729 *
1730 * Notes:
1731 * (1) Generates a pta of fg pixels in the pix, within the box.
1732 * If box == NULL, it uses the entire pix.
1733 */
1734 PTA *
ptaGetPixelsFromPix(PIX * pixs,BOX * box)1735 ptaGetPixelsFromPix(PIX *pixs,
1736 BOX *box)
1737 {
1738 l_int32 i, j, w, h, wpl, xstart, xend, ystart, yend, bw, bh;
1739 l_uint32 *data, *line;
1740 PTA *pta;
1741
1742 PROCNAME("ptaGetPixelsFromPix");
1743
1744 if (!pixs || (pixGetDepth(pixs) != 1))
1745 return (PTA *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
1746
1747 pixGetDimensions(pixs, &w, &h, NULL);
1748 data = pixGetData(pixs);
1749 wpl = pixGetWpl(pixs);
1750 xstart = ystart = 0;
1751 xend = w - 1;
1752 yend = h - 1;
1753 if (box) {
1754 boxGetGeometry(box, &xstart, &ystart, &bw, &bh);
1755 xend = xstart + bw - 1;
1756 yend = ystart + bh - 1;
1757 }
1758
1759 if ((pta = ptaCreate(0)) == NULL)
1760 return (PTA *)ERROR_PTR("pta not made", procName, NULL);
1761 for (i = ystart; i <= yend; i++) {
1762 line = data + i * wpl;
1763 for (j = xstart; j <= xend; j++) {
1764 if (GET_DATA_BIT(line, j))
1765 ptaAddPt(pta, j, i);
1766 }
1767 }
1768
1769 return pta;
1770 }
1771
1772
1773 /*!
1774 * pixGenerateFromPta()
1775 *
1776 * Input: pta
1777 * w, h (of pix)
1778 * Return: pix (1 bpp), or null on error
1779 *
1780 * Notes:
1781 * (1) Points are rounded to nearest ints.
1782 * (2) Any points outside (w,h) are silently discarded.
1783 * (3) Output 1 bpp pix has values 1 for each point in the pta.
1784 */
1785 PIX *
pixGenerateFromPta(PTA * pta,l_int32 w,l_int32 h)1786 pixGenerateFromPta(PTA *pta,
1787 l_int32 w,
1788 l_int32 h)
1789 {
1790 l_int32 n, i, x, y;
1791 PIX *pix;
1792
1793 PROCNAME("pixGenerateFromPta");
1794
1795 if (!pta)
1796 return (PIX *)ERROR_PTR("pta not defined", procName, NULL);
1797
1798 if ((pix = pixCreate(w, h, 1)) == NULL)
1799 return (PIX *)ERROR_PTR("pix not made", procName, NULL);
1800 n = ptaGetCount(pta);
1801 for (i = 0; i < n; i++) {
1802 ptaGetIPt(pta, i, &x, &y);
1803 if (x < 0 || x >= w || y < 0 || y >= h)
1804 continue;
1805 pixSetPixel(pix, x, y, 1);
1806 }
1807
1808 return pix;
1809 }
1810
1811
1812 /*!
1813 * ptaGetBoundaryPixels()
1814 *
1815 * Input: pixs (1 bpp)
1816 * type (L_BOUNDARY_FG, L_BOUNDARY_BG)
1817 * Return: pta, or null on error
1818 *
1819 * Notes:
1820 * (1) This generates a pta of either fg or bg boundary pixels.
1821 */
1822 PTA *
ptaGetBoundaryPixels(PIX * pixs,l_int32 type)1823 ptaGetBoundaryPixels(PIX *pixs,
1824 l_int32 type)
1825 {
1826 PIX *pixt;
1827 PTA *pta;
1828
1829 PROCNAME("ptaGetBoundaryPixels");
1830
1831 if (!pixs || (pixGetDepth(pixs) != 1))
1832 return (PTA *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
1833 if (type != L_BOUNDARY_FG && type != L_BOUNDARY_BG)
1834 return (PTA *)ERROR_PTR("invalid type", procName, NULL);
1835
1836 if (type == L_BOUNDARY_FG)
1837 pixt = pixMorphSequence(pixs, "e3.3", 0);
1838 else
1839 pixt = pixMorphSequence(pixs, "d3.3", 0);
1840 pixXor(pixt, pixt, pixs);
1841 pta = ptaGetPixelsFromPix(pixt, NULL);
1842
1843 pixDestroy(&pixt);
1844 return pta;
1845 }
1846
1847
1848 /*!
1849 * ptaaGetBoundaryPixels()
1850 *
1851 * Input: pixs (1 bpp)
1852 * type (L_BOUNDARY_FG, L_BOUNDARY_BG)
1853 * connectivity (4 or 8)
1854 * &boxa (<optional return> bounding boxes of the c.c.)
1855 * &pixa (<optional return> pixa of the c.c.)
1856 * Return: ptaa, or null on error
1857 *
1858 * Notes:
1859 * (1) This generates a ptaa of either fg or bg boundary pixels,
1860 * where each pta has the boundary pixels for a connected
1861 * component.
1862 * (2) We can't simply find all the boundary pixels and then select
1863 * those within the bounding box of each component, because
1864 * bounding boxes can overlap. It is necessary to extract and
1865 * dilate or erode each component separately. Note also that
1866 * special handling is required for bg pixels when the
1867 * component touches the pix boundary.
1868 */
1869 PTAA *
ptaaGetBoundaryPixels(PIX * pixs,l_int32 type,l_int32 connectivity,BOXA ** pboxa,PIXA ** ppixa)1870 ptaaGetBoundaryPixels(PIX *pixs,
1871 l_int32 type,
1872 l_int32 connectivity,
1873 BOXA **pboxa,
1874 PIXA **ppixa)
1875 {
1876 l_int32 i, n, w, h, x, y, bw, bh, left, right, top, bot;
1877 BOXA *boxa;
1878 PIX *pixt1, *pixt2;
1879 PIXA *pixa;
1880 PTA *pta1, *pta2;
1881 PTAA *ptaa;
1882
1883 PROCNAME("ptaaGetBoundaryPixels");
1884
1885 if (pboxa) *pboxa = NULL;
1886 if (ppixa) *ppixa = NULL;
1887 if (!pixs || (pixGetDepth(pixs) != 1))
1888 return (PTAA *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
1889 if (type != L_BOUNDARY_FG && type != L_BOUNDARY_BG)
1890 return (PTAA *)ERROR_PTR("invalid type", procName, NULL);
1891 if (connectivity != 4 && connectivity != 8)
1892 return (PTAA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
1893
1894 pixGetDimensions(pixs, &w, &h, NULL);
1895 boxa = pixConnComp(pixs, &pixa, connectivity);
1896 n = boxaGetCount(boxa);
1897 ptaa = ptaaCreate(0);
1898 for (i = 0; i < n; i++) {
1899 pixt1 = pixaGetPix(pixa, i, L_CLONE);
1900 boxaGetBoxGeometry(boxa, i, &x, &y, &bw, &bh);
1901 left = right = top = bot = 0;
1902 if (type == L_BOUNDARY_BG) {
1903 if (x > 0) left = 1;
1904 if (y > 0) top = 1;
1905 if (x + bw < w) right = 1;
1906 if (y + bh < h) bot = 1;
1907 pixt2 = pixAddBorderGeneral(pixt1, left, right, top, bot, 0);
1908 }
1909 else
1910 pixt2 = pixClone(pixt1);
1911 pta1 = ptaGetBoundaryPixels(pixt2, type);
1912 pta2 = ptaTransform(pta1, x - left, y - top, 1.0, 1.0);
1913 ptaaAddPta(ptaa, pta2, L_INSERT);
1914 ptaDestroy(&pta1);
1915 pixDestroy(&pixt1);
1916 pixDestroy(&pixt2);
1917 }
1918
1919 if (pboxa)
1920 *pboxa = boxa;
1921 else
1922 boxaDestroy(&boxa);
1923 if (ppixa)
1924 *ppixa = pixa;
1925 else
1926 pixaDestroy(&pixa);
1927 return ptaa;
1928 }
1929
1930
1931