Quad tree implementation.
More...
#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 * | CPLQuadTreeCreate (const CPLRectObj *pGlobalBounds, CPLQuadTreeGetBoundsFunc pfnGetBounds) |
| Create a new quadtree.
|
void | CPLQuadTreeDestroy (CPLQuadTree *hQuadtree) |
| Destroy a quadtree.
|
void | CPLQuadTreeSetBucketCapacity (CPLQuadTree *hQuadtree, int nBucketCapacity) |
| Set the maximum capacity of a node of a quadtree.
|
int | CPLQuadTreeGetAdvisedMaxDepth (int nExpectedFeatures) |
| Returns the optimal depth of a quadtree to hold nExpectedFeatures.
|
void | CPLQuadTreeSetMaxDepth (CPLQuadTree *hQuadtree, int nMaxDepth) |
| Set the maximum depth of a quadtree.
|
void | CPLQuadTreeInsert (CPLQuadTree *hQuadtree, void *hFeature) |
| Insert a feature into a quadtree.
|
void ** | CPLQuadTreeSearch (const CPLQuadTree *hQuadtree, const CPLRectObj *pAoi, int *pnFeatureCount) |
| Returns all the elements inserted whose bounding box intersects the provided area of interest.
|
void | CPLQuadTreeForeach (const CPLQuadTree *hQuadtree, CPLQuadTreeForeachFunc pfnForeach, void *pUserData) |
| Walk through the quadtree and runs the provided function on all the elements.
|
void | CPLQuadTreeDump (const CPLQuadTree *hQuadtree, CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc, void *pUserData) |
void | CPLQuadTreeGetStats (const CPLQuadTree *hQuadtree, int *pnFeatureCount, int *pnNodeCount, int *pnMaxDepth, int *pnMaxBucketCapacity) |
Detailed Description
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
Function Documentation
CPLQuadTree* CPLQuadTreeCreate |
( |
const CPLRectObj * |
pGlobalBounds, |
|
|
CPLQuadTreeGetBoundsFunc |
pfnGetBounds | |
|
) |
| | |
Create a new quadtree.
- Parameters:
-
| 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 |
- Returns:
- a newly allocated quadtree
Destroy a quadtree.
- Parameters:
-
| hQuadTree | the quad tree to destroy |
void 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.
- Parameters:
-
| hQuadTree | the quad tree |
| pfnForeach | the function called on each element. |
| pUserData | the user data provided to the function. |
int CPLQuadTreeGetAdvisedMaxDepth |
( |
int |
nExpectedFeatures |
) |
|
Returns the optimal depth of a quadtree to hold nExpectedFeatures.
- Parameters:
-
| nExpectedFeatures | the expected maximum number of elements to be inserted |
- Returns:
- the optimal depth of a quadtree to hold nExpectedFeatures
void CPLQuadTreeInsert |
( |
CPLQuadTree * |
hQuadTree, |
|
|
void * |
hFeature | |
|
) |
| | |
Insert a feature into a quadtree.
- Parameters:
-
| hQuadTree | the quad tree |
| hFeature | the feature to insert |
void** CPLQuadTreeSearch |
( |
const CPLQuadTree * |
hQuadTree, |
|
|
const CPLRectObj * |
pAoi, |
|
|
int * |
pnFeatureCount | |
|
) |
| | |
Returns all the elements inserted whose bounding box intersects the provided area of interest.
- Parameters:
-
| hQuadTree | the quad tree |
| pAoi | the pointer to the area of interest |
| pnFeatureCount | the user data provided to the function. |
- Returns:
- an array of features that must be freed with CPLFree
void 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.
- Parameters:
-
| hQuadTree | the quad tree |
| nBucketCapacity | the maximum capactiy of a node of a quadtree |
void 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.
- Parameters:
-
| hQuadTree | the quad tree |
| nMaxDepth | the maximum depth allowed |