Classes | Functions

cpl_quad_tree.h File Reference

#include "cpl_port.h"

Go to the source code of this file.

Classes

struct  CPLRectObj

Functions

CPLQuadTreeCPLQuadTreeCreate (const CPLRectObj *pGlobalBounds, CPLQuadTreeGetBoundsFunc pfnGetBounds)
void CPLQuadTreeDestroy (CPLQuadTree *hQuadtree)
void CPLQuadTreeSetBucketCapacity (CPLQuadTree *hQuadtree, int nBucketCapacity)
int CPLQuadTreeGetAdvisedMaxDepth (int nExpectedFeatures)
void CPLQuadTreeSetMaxDepth (CPLQuadTree *hQuadtree, int nMaxDepth)
void CPLQuadTreeInsert (CPLQuadTree *hQuadtree, void *hFeature)
void CPLQuadTreeInsertWithBounds (CPLQuadTree *hQuadtree, void *hFeature, const CPLRectObj *psBounds)
void ** CPLQuadTreeSearch (const CPLQuadTree *hQuadtree, const CPLRectObj *pAoi, int *pnFeatureCount)
void CPLQuadTreeForeach (const CPLQuadTree *hQuadtree, CPLQuadTreeForeachFunc pfnForeach, void *pUserData)

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. 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.
Returns:
a newly allocated quadtree
void CPLQuadTreeDestroy ( CPLQuadTree hQuadTree  ) 

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 CPLQuadTreeInsertWithBounds ( CPLQuadTree hQuadTree,
void *  hFeature,
const CPLRectObj psBounds 
)

Insert a feature into a quadtree

Parameters:
hQuadTree the quad tree
hFeature the feature to insert
psBounds bounds of the feature
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

Generated for GDAL by doxygen 1.7.1.