![]() |
Leptonica
1.82.0
Image processing and image analysis suite
|
#include "allheaders.h"
Go to the source code of this file.
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) |
-------------------------------------- This file has these Pta utilities:
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.
[in] | pta |
Definition at line 449 of file ptafunc2.c.
Referenced by ptaIntersectionByAset().
[in] | pta | input pta |
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().
[in] | ptaas | |
[in] | naindex | na that maps from the new ptaa to the input ptaa |
Definition at line 226 of file ptafunc2.c.
References L_COPY, L_INSERT, numaGetCount(), numaGetIValue(), ptaaAddPta(), ptaaCreate(), ptaaGetCount(), and ptaaGetPta().
[in] | pta1 | |
[in] | pta2 | |
[out] | psame | 1 if same; 0 if different |
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().
l_ok ptaGetRankValue | ( | PTA * | pta, |
l_float32 | fract, | ||
PTA * | ptasort, | ||
l_int32 | sorttype, | ||
l_float32 * | pval | ||
) |
[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 |
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().
[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 |
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().
[in] | pta1 | |
[in] | pta2 | |
[out] | pptad | intersection of the two point arrays |
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().
[in] | pta1 | |
[in] | pta2 | |
[out] | pptad | intersection of the two point arrays |
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().
[in] | ptas | assumed to be integer values |
[out] | pptad | assumed to be integer values |
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().
[in] | ptas | |
[out] | pptad | set of unique values |
[out] | phmap | [optional] hashmap used for lookup |
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().
[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 |
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().
[in] | ptas |
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().
[in] | ptas | |
[in] | naindex | na that maps from the new pta to the input pta |
Definition at line 190 of file ptafunc2.c.
References numaGetCount(), numaGetIValue(), ptaAddPt(), ptaCreate(), and ptaGetPt().
Referenced by ptaSort().
[in] | pta1 | |
[in] | pta2 | |
[out] | pptad | union of the two point arrays |
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().
[in] | pta1 | |
[in] | pta2 | |
[out] | pptad | union of the two point arrays |
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().