SDTS_AL
|
#include "cpl_port.h"
Go to the source code of this file.
Classes | |
struct | CPLRectObj |
Typedefs | |
typedef struct _CPLQuadTree | CPLQuadTree |
typedef void(* | CPLQuadTreeGetBoundsFunc) (const void *hFeature, CPLRectObj *pBounds) |
typedef int(* | CPLQuadTreeForeachFunc) (void *pElt, void *pUserData) |
typedef void(* | CPLQuadTreeDumpFeatureFunc) (const void *hFeature, int nIndentLevel, void *pUserData) |
Functions | |
CPLQuadTree CPL_DLL * | CPLQuadTreeCreate (const CPLRectObj *pGlobalBounds, CPLQuadTreeGetBoundsFunc pfnGetBounds) |
void CPL_DLL | CPLQuadTreeDestroy (CPLQuadTree *hQuadtree) |
void CPL_DLL | CPLQuadTreeSetBucketCapacity (CPLQuadTree *hQuadtree, int nBucketCapacity) |
int CPL_DLL | CPLQuadTreeGetAdvisedMaxDepth (int nExpectedFeatures) |
void CPL_DLL | CPLQuadTreeSetMaxDepth (CPLQuadTree *hQuadtree, int nMaxDepth) |
void CPL_DLL | CPLQuadTreeInsert (CPLQuadTree *hQuadtree, void *hFeature) |
void CPL_DLL | CPLQuadTreeInsertWithBounds (CPLQuadTree *hQuadtree, void *hFeature, const CPLRectObj *psBounds) |
void CPL_DLL ** | CPLQuadTreeSearch (const CPLQuadTree *hQuadtree, const CPLRectObj *pAoi, int *pnFeatureCount) |
void CPL_DLL | CPLQuadTreeForeach (const CPLQuadTree *hQuadtree, CPLQuadTreeForeachFunc pfnForeach, void *pUserData) |
void CPL_DLL | CPLQuadTreeDump (const CPLQuadTree *hQuadtree, CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc, void *pUserData) |
void CPL_DLL | CPLQuadTreeGetStats (const CPLQuadTree *hQuadtree, int *pnFeatureCount, int *pnNodeCount, int *pnMaxDepth, int *pnMaxBucketCapacity) |
Quad tree implementation.
A quadtree is a tree data structure in which each internal node has up to four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions
typedef struct _CPLQuadTree CPLQuadTree |
Opaque type for a quad tree
typedef void(* CPLQuadTreeDumpFeatureFunc) (const void *hFeature, int nIndentLevel, void *pUserData) |
CPLQuadTreeDumpFeatureFunc
typedef int(* CPLQuadTreeForeachFunc) (void *pElt, void *pUserData) |
CPLQuadTreeForeachFunc
typedef void(* CPLQuadTreeGetBoundsFunc) (const void *hFeature, CPLRectObj *pBounds) |
CPLQuadTreeGetBoundsFunc
CPLQuadTree CPL_DLL* CPLQuadTreeCreate | ( | const CPLRectObj * | pGlobalBounds, |
CPLQuadTreeGetBoundsFunc | pfnGetBounds | ||
) |
Create a new quadtree
pGlobalBounds | a pointer to the global extent of all the elements that will be inserted |
pfnGetBounds | a user provided function to get the bounding box of the inserted elements. If it is set to NULL, then CPLQuadTreeInsertWithBounds() must be used, and extra memory will be used to keep features bounds in the quad tree. |
void CPL_DLL CPLQuadTreeDestroy | ( | CPLQuadTree * | hQuadTree | ) |
Destroy a quadtree
hQuadTree | the quad tree to destroy |
void CPL_DLL CPLQuadTreeDump | ( | const CPLQuadTree * | hQuadTree, |
CPLQuadTreeDumpFeatureFunc | pfnDumpFeatureFunc, | ||
void * | pUserData | ||
) |
Dump quad tree
void CPL_DLL CPLQuadTreeForeach | ( | const CPLQuadTree * | hQuadTree, |
CPLQuadTreeForeachFunc | pfnForeach, | ||
void * | pUserData | ||
) |
Walk through the quadtree and runs the provided function on all the elements
This function is provided with the user_data argument of pfnForeach. It must return TRUE to go on the walk through the hash set, or FALSE to make it stop.
Note : the structure of the quadtree must NOT be modified during the walk.
hQuadTree | the quad tree |
pfnForeach | the function called on each element. |
pUserData | the user data provided to the function. |
int CPL_DLL CPLQuadTreeGetAdvisedMaxDepth | ( | int | nExpectedFeatures | ) |
Returns the optimal depth of a quadtree to hold nExpectedFeatures
nExpectedFeatures | the expected maximum number of elements to be inserted. |
void CPL_DLL CPLQuadTreeGetStats | ( | const CPLQuadTree * | hQuadTree, |
int * | pnFeatureCount, | ||
int * | pnNodeCount, | ||
int * | pnMaxDepth, | ||
int * | pnMaxBucketCapacity | ||
) |
Get stats
void CPL_DLL CPLQuadTreeInsert | ( | CPLQuadTree * | hQuadTree, |
void * | hFeature | ||
) |
Insert a feature into a quadtree
hQuadTree | the quad tree |
hFeature | the feature to insert |
void CPL_DLL CPLQuadTreeInsertWithBounds | ( | CPLQuadTree * | hQuadTree, |
void * | hFeature, | ||
const CPLRectObj * | psBounds | ||
) |
Insert a feature into a quadtree
hQuadTree | the quad tree |
hFeature | the feature to insert |
psBounds | bounds of the feature |
void CPL_DLL** CPLQuadTreeSearch | ( | const CPLQuadTree * | hQuadTree, |
const CPLRectObj * | pAoi, | ||
int * | pnFeatureCount | ||
) |
Returns all the elements inserted whose bounding box intersects the provided area of interest
hQuadTree | the quad tree |
pAoi | the pointer to the area of interest |
pnFeatureCount | the user data provided to the function. |
void CPL_DLL CPLQuadTreeSetBucketCapacity | ( | CPLQuadTree * | hQuadTree, |
int | nBucketCapacity | ||
) |
Set the maximum capacity of a node of a quadtree. The default value is 8. Note that the maximum capacity will only be honoured if the features inserted have a point geometry. Otherwise it may be exceeded.
hQuadTree | the quad tree |
nBucketCapacity | the maximum capacity of a node of a quadtree |
void CPL_DLL CPLQuadTreeSetMaxDepth | ( | CPLQuadTree * | hQuadTree, |
int | nMaxDepth | ||
) |
Set the maximum depth of a quadtree. By default, quad trees have no maximum depth, but a maximum bucket capacity.
hQuadTree | the quad tree |
nMaxDepth | the maximum depth allowed |