Leptonica  1.82.0
Image processing and image analysis suite
ptafunc2.c File Reference
#include "allheaders.h"

Go to the source code of this file.

Functions

PTAptaSort (PTA *ptas, l_int32 sorttype, l_int32 sortorder, NUMA **pnaindex)
 
l_ok ptaGetSortIndex (PTA *ptas, l_int32 sorttype, l_int32 sortorder, NUMA **pnaindex)
 
PTAptaSortByIndex (PTA *ptas, NUMA *naindex)
 
PTAAptaaSortByIndex (PTAA *ptaas, NUMA *naindex)
 
l_ok ptaGetRankValue (PTA *pta, l_float32 fract, PTA *ptasort, l_int32 sorttype, l_float32 *pval)
 
PTAptaSort2d (PTA *pta)
 
l_ok ptaEqual (PTA *pta1, PTA *pta2, l_int32 *psame)
 
L_ASETl_asetCreateFromPta (PTA *pta)
 
l_ok ptaRemoveDupsByAset (PTA *ptas, PTA **pptad)
 
l_ok ptaUnionByAset (PTA *pta1, PTA *pta2, PTA **pptad)
 
l_ok ptaIntersectionByAset (PTA *pta1, PTA *pta2, PTA **pptad)
 
L_HASHMAPl_hmapCreateFromPta (PTA *pta)
 
l_ok ptaRemoveDupsByHmap (PTA *ptas, PTA **pptad, L_HASHMAP **phmap)
 
l_ok ptaUnionByHmap (PTA *pta1, PTA *pta2, PTA **pptad)
 
l_ok ptaIntersectionByHmap (PTA *pta1, PTA *pta2, PTA **pptad)
 

Detailed Description

     --------------------------------------
     This file has these Pta utilities:
  • sorting
  • ordered set operations
  • hash map operations --------------------------------------
     Sorting
          PTA        *ptaSort()
          l_int32     ptaGetSortIndex()
          PTA        *ptaSortByIndex()
          PTAA       *ptaaSortByIndex()
          l_int32     ptaGetRankValue()
          PTA        *ptaSort2d()
          l_int32     ptaEqual()
     Set operations using aset (rbtree)
          L_ASET     *l_asetCreateFromPta()
          PTA        *ptaRemoveDupsByAset()
          PTA        *ptaUnionByAset()
          PTA        *ptaIntersectionByAset()
     Hashmap operations
         L_HASHMAP   *l_hmapCreateFromPta()
         l_int32      ptaRemoveDupsByHmap()
         l_int32      ptaUnionByHmap()
         l_int32      ptaIntersectionByHmap()
We have two implementations of set operations on an array of points:
  (1) Using an underlying tree (rbtree)
      This uses a good 64 bit hashing function for the key,
      that is not expected to have hash collisions (and we do
      not test for them).  The tree is built up of the keys,
      values, and is traversed looking for the key in O(log n).
  (2) Building a hashmap from the keys (hashmap)
      This uses a fast 64 bit hashing function for the key, which
      is then hashed into a hashtable.  Collisions of hashkeys are
      very rare, but the hashtable is designed to allow more than one
      hashitem in a table entry.  The hashitems are put in a list at
      each hashtable entry, which is traversed looking for the key.
 

Definition in file ptafunc2.c.

Function Documentation

◆ l_asetCreateFromPta()

L_ASET* l_asetCreateFromPta ( PTA pta)

l_asetCreateFromPta()

Parameters
[in]pta
Returns
set using a 64-bit hash of (x,y) as the key

Definition at line 449 of file ptafunc2.c.

Referenced by ptaIntersectionByAset().

◆ l_hmapCreateFromPta()

L_HASHMAP* l_hmapCreateFromPta ( PTA pta)

l_hmapCreateFromPta()

Parameters
[in]ptainput pta
Returns
hmap hashmap, or NULL on error
 Notes:
      (1) The indices into pta are stored in the val field of the hashitems.
          This is necessary so that hmap and pta can be used together.

Definition at line 654 of file ptafunc2.c.

References l_hashPtToUint64(), ptaGetCount(), and ptaGetIPt().

Referenced by ptaIntersectionByHmap(), and ptaRemoveDupsByHmap().

◆ ptaaSortByIndex()

PTAA* ptaaSortByIndex ( PTAA ptaas,
NUMA naindex 
)

ptaaSortByIndex()

Parameters
[in]ptaas
[in]naindexna that maps from the new ptaa to the input ptaa
Returns
ptaad sorted, or NULL on error

Definition at line 226 of file ptafunc2.c.

References L_COPY, L_INSERT, numaGetCount(), numaGetIValue(), ptaaAddPta(), ptaaCreate(), ptaaGetCount(), and ptaaGetPta().

◆ ptaEqual()

l_ok ptaEqual ( PTA pta1,
PTA pta2,
l_int32 *  psame 
)

ptaEqual()

Parameters
[in]pta1
[in]pta2
[out]psame1 if same; 0 if different
Returns
0 if OK; 1 on error
Notes:
     (1) Equality is defined as having the same set of points,
         independent of the order in which they are presented.

Definition at line 399 of file ptafunc2.c.

References ptaDestroy(), ptaGetCount(), ptaGetPt(), and ptaSort2d().

◆ ptaGetRankValue()

l_ok ptaGetRankValue ( PTA pta,
l_float32  fract,
PTA ptasort,
l_int32  sorttype,
l_float32 *  pval 
)

ptaGetRankValue()

Parameters
[in]pta
[in]fractuse 0.0 for smallest, 1.0 for largest
[in]ptasort[optional] version of pta sorted by sorttype
[in]sorttypeL_SORT_BY_X, L_SORT_BY_Y
[out]pvalrankval: the x or y value at fract
Returns
0 if OK, 1 on error

Definition at line 265 of file ptafunc2.c.

References L_SORT_BY_X, L_SORT_BY_Y, L_SORT_INCREASING, ptaDestroy(), ptaGetCount(), ptaGetPt(), and ptaSort().

◆ ptaGetSortIndex()

l_ok ptaGetSortIndex ( PTA ptas,
l_int32  sorttype,
l_int32  sortorder,
NUMA **  pnaindex 
)

ptaGetSortIndex()

Parameters
[in]ptas
[in]sorttypeL_SORT_BY_X, L_SORT_BY_Y
[in]sortorderL_SORT_INCREASING, L_SORT_DECREASING
[out]pnaindexindex of sorted order into original array
Returns
0 if OK, 1 on error

Definition at line 139 of file ptafunc2.c.

References L_SORT_BY_X, L_SORT_BY_Y, L_SORT_DECREASING, L_SORT_INCREASING, numaAddNumber(), numaCreate(), numaDestroy(), numaGetSortIndex(), ptaGetCount(), and ptaGetPt().

Referenced by ptaSort().

◆ ptaIntersectionByAset()

l_ok ptaIntersectionByAset ( PTA pta1,
PTA pta2,
PTA **  pptad 
)

ptaIntersectionByAset()

Parameters
[in]pta1
[in]pta2
[out]pptadintersection of the two point arrays
Returns
0 if OK; 1 on error
Notes:
     (1) See sarrayIntersectionByAset() for the approach.
     (2) The key is a 64-bit hash from the (x,y) pair.
     (3) This is slower than ptaIntersectionByHmap(), mostly because
         of the nlogn sort to build up the rbtree.  Do not use for
         large numbers of points (say, > 100K).

Definition at line 590 of file ptafunc2.c.

References l_asetCreateFromPta(), ptaCreate(), and ptaGetCount().

◆ ptaIntersectionByHmap()

l_ok ptaIntersectionByHmap ( PTA pta1,
PTA pta2,
PTA **  pptad 
)

ptaIntersectionByHmap()

Parameters
[in]pta1
[in]pta2
[out]pptadintersection of the two point arrays
Returns
0 if OK; 1 on error
 Notes:
      (1) Make pta with pts common to both input arrays.

Definition at line 789 of file ptafunc2.c.

References L_Hashitem::count, l_hashPtToUint64(), l_hmapCreateFromPta(), ptaAddPt(), ptaCreate(), ptaGetCount(), and ptaGetIPt().

◆ ptaRemoveDupsByAset()

l_ok ptaRemoveDupsByAset ( PTA ptas,
PTA **  pptad 
)

ptaRemoveDupsByAset()

Parameters
[in]ptasassumed to be integer values
[out]pptadassumed to be integer values
Returns
0 if OK; 1 on error
Notes:
     (1) This is slower than ptaRemoveDupsByHmap(), mostly because
         of the nlogn sort to build up the rbtree.  Do not use for
         large numbers of points (say, > 100K).

Definition at line 489 of file ptafunc2.c.

Referenced by generatePtaBoxa(), generatePtaHashBoxa(), generatePtaPolyline(), and ptaUnionByAset().

◆ ptaRemoveDupsByHmap()

l_ok ptaRemoveDupsByHmap ( PTA ptas,
PTA **  pptad,
L_HASHMAP **  phmap 
)

ptaRemoveDupsByHmap()

Parameters
[in]ptas
[out]pptadset of unique values
[out]phmap[optional] hashmap used for lookup
Returns
0 if OK; 1 on error
 Notes:
      (1) Generates a set of (unique) points from ptas.

Definition at line 692 of file ptafunc2.c.

References L_Hashmap::hashtab, l_hmapCreateFromPta(), L_Hashitem::next, ptaAddPt(), ptaCreate(), ptaGetIPt(), L_Hashmap::tabsize, and L_Hashitem::val.

Referenced by ptaUnionByHmap().

◆ ptaSort()

PTA* ptaSort ( PTA ptas,
l_int32  sorttype,
l_int32  sortorder,
NUMA **  pnaindex 
)

ptaSort()

Parameters
[in]ptas
[in]sorttypeL_SORT_BY_X, L_SORT_BY_Y
[in]sortorderL_SORT_INCREASING, L_SORT_DECREASING
[out]pnaindex[optional] index of sorted order into original array
Returns
ptad sorted version of ptas, or NULL on error

Definition at line 97 of file ptafunc2.c.

References L_SORT_BY_X, L_SORT_BY_Y, L_SORT_DECREASING, L_SORT_INCREASING, numaDestroy(), ptaGetSortIndex(), and ptaSortByIndex().

Referenced by ptaGetRankValue(), and ptaSort2d().

◆ ptaSort2d()

PTA* ptaSort2d ( PTA pta)

ptaSort2d()

Parameters
[in]ptas
Returns
ptad, or NULL on error
Notes:
     (1) Sort increasing by row-major, scanning down from the UL corner,
         where for each value of y, order the pts from left to right.

Definition at line 317 of file ptafunc2.c.

References L_SORT_BY_Y, L_SORT_INCREASING, numaAddNumber(), numaCreate(), numaDestroy(), numaGetCount(), numaGetFValue(), numaGetIValue(), numaSort(), ptaAddPt(), ptaCreate(), ptaDestroy(), ptaGetCount(), ptaGetPt(), and ptaSort().

Referenced by ptaEqual().

◆ ptaSortByIndex()

PTA* ptaSortByIndex ( PTA ptas,
NUMA naindex 
)

ptaSortByIndex()

Parameters
[in]ptas
[in]naindexna that maps from the new pta to the input pta
Returns
ptad sorted, or NULL on error

Definition at line 190 of file ptafunc2.c.

References numaGetCount(), numaGetIValue(), ptaAddPt(), ptaCreate(), and ptaGetPt().

Referenced by ptaSort().

◆ ptaUnionByAset()

l_ok ptaUnionByAset ( PTA pta1,
PTA pta2,
PTA **  pptad 
)

ptaUnionByAset()

Parameters
[in]pta1
[in]pta2
[out]pptadunion of the two point arrays
Returns
0 if OK; 1 on error
Notes:
     (1) See sarrayRemoveDupsByAset() for the approach.
     (2) The key is a 64-bit hash from the (x,y) pair.
     (3) This is slower than ptaUnionByHmap(), mostly because of the
         nlogn sort to build up the rbtree.  Do not use for large
         numbers of points (say, > 100K).
     (4) The *Aset() functions use the sorted l_Aset, which is just
         an rbtree in disguise.

Definition at line 545 of file ptafunc2.c.

References ptaCopy(), ptaDestroy(), ptaJoin(), and ptaRemoveDupsByAset().

◆ ptaUnionByHmap()

l_ok ptaUnionByHmap ( PTA pta1,
PTA pta2,
PTA **  pptad 
)

ptaUnionByHmap()

Parameters
[in]pta1
[in]pta2
[out]pptadunion of the two point arrays
Returns
0 if OK; 1 on error
 Notes:
      (1) Make pta with points found in either of the input arrays.

Definition at line 748 of file ptafunc2.c.

References ptaCopy(), ptaDestroy(), ptaJoin(), and ptaRemoveDupsByHmap().