#include "allheaders.h"

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

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

PTA *	ptaSortByIndex (PTA ptas, NUMA naindex)

PTAA *	ptaaSortByIndex (PTAA ptaas, NUMA naindex)

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

PTA *	ptaSort2d (PTA *pta)

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

L_ASET *	l_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_HASHMAP *	l_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 435 of file ptafunc2.c.

Referenced by ptaIntersectionByAset().

◆ l_hmapCreateFromPta()

L_HASHMAP * l_hmapCreateFromPta ( PTA * pta )

l_hmapCreateFromPta()

Parameters

[in] pta input 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 632 of file ptafunc2.c.

Referenced by ptaIntersectionByHmap(), and ptaRemoveDupsByHmap().

◆ ptaaSortByIndex()

PTAA * ptaaSortByIndex	(	PTAA *	ptaas,
		NUMA *	naindex )

ptaaSortByIndex()

Parameters

[in]	ptaas
[in]	naindex	na that maps from the new ptaa to the input ptaa

Returns: ptaad sorted, or NULL on error

Definition at line 220 of file ptafunc2.c.

References L_COPY, and L_INSERT.

◆ ptaEqual()

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

ptaEqual()

Parameters

[in]	pta1
[in]	pta2
[out]	psame	1 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 387 of file ptafunc2.c.

References ptaSort2d().

◆ ptaGetRankValue()

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

ptaGetRankValue()

Parameters

[in]	pta
[in]	fract	use 0.0 for smallest, 1.0 for largest
[in]	ptasort	[optional] version of pta sorted by sorttype
[in]	sorttype	L_SORT_BY_X, L_SORT_BY_Y
[out]	pval	rankval: the x or y value at fract

Returns: 0 if OK, 1 on error

Definition at line 257 of file ptafunc2.c.

References L_SORT_BY_X, L_SORT_BY_Y, L_SORT_INCREASING, and ptaSort().

◆ ptaGetSortIndex()

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

ptaGetSortIndex()

Parameters

[in]	ptas
[in]	sorttype	L_SORT_BY_X, L_SORT_BY_Y
[in]	sortorder	L_SORT_INCREASING, L_SORT_DECREASING
[out]	pnaindex	index of sorted order into original array

Returns: 0 if OK, 1 on error

Definition at line 137 of file ptafunc2.c.

References L_SORT_BY_X, L_SORT_BY_Y, L_SORT_DECREASING, and L_SORT_INCREASING.

Referenced by ptaSort().

◆ ptaIntersectionByAset()

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

ptaIntersectionByAset()

Parameters

[in]	pta1
[in]	pta2
[out]	pptad	intersection 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 570 of file ptafunc2.c.

References l_asetCreateFromPta().

◆ ptaIntersectionByHmap()

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

ptaIntersectionByHmap()

Parameters

[in]	pta1
[in]	pta2
[out]	pptad	intersection 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 759 of file ptafunc2.c.

References L_Hashitem::count, and l_hmapCreateFromPta().

◆ ptaRemoveDupsByAset()

l_ok ptaRemoveDupsByAset	(	PTA *	ptas,
		PTA **	pptad )

ptaRemoveDupsByAset()

Parameters

[in]	ptas	assumed to be integer values
[out]	pptad	assumed 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 473 of file ptafunc2.c.

Referenced by ptaUnionByAset().

◆ ptaRemoveDupsByHmap()

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

ptaRemoveDupsByHmap()

Parameters

[in]	ptas
[out]	pptad	set 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 667 of file ptafunc2.c.

References L_Hashmap::hashtab, l_hmapCreateFromPta(), L_Hashitem::next, 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]	sorttype	L_SORT_BY_X, L_SORT_BY_Y
[in]	sortorder	L_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, 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 307 of file ptafunc2.c.

References L_SORT_BY_Y, L_SORT_INCREASING, and ptaSort().

Referenced by ptaEqual().

◆ ptaSortByIndex()

PTA * ptaSortByIndex	(	PTA *	ptas,
		NUMA *	naindex )

ptaSortByIndex()

Parameters

[in]	ptas
[in]	naindex	na that maps from the new pta to the input pta

Returns: ptad sorted, or NULL on error

Definition at line 186 of file ptafunc2.c.

Referenced by ptaSort().

◆ ptaUnionByAset()

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

ptaUnionByAset()

Parameters

[in]	pta1
[in]	pta2
[out]	pptad	union 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 527 of file ptafunc2.c.

References ptaRemoveDupsByAset().

◆ ptaUnionByHmap()

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

ptaUnionByHmap()

Parameters

[in]	pta1
[in]	pta2
[out]	pptad	union 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 720 of file ptafunc2.c.

References ptaRemoveDupsByHmap().

Functions

Detailed Description

Function Documentation

◆ l_asetCreateFromPta()

◆ l_hmapCreateFromPta()

◆ ptaaSortByIndex()

◆ ptaEqual()

◆ ptaGetRankValue()

◆ ptaGetSortIndex()

◆ ptaIntersectionByAset()

◆ ptaIntersectionByHmap()

◆ ptaRemoveDupsByAset()

◆ ptaRemoveDupsByHmap()

◆ ptaSort()

◆ ptaSort2d()

◆ ptaSortByIndex()

◆ ptaUnionByAset()

◆ ptaUnionByHmap()