cpl_quad_tree.h File Reference

#include "cpl_port.h"

Go to the source code of this file.

Classes

struct  CPLRectObj

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 ** CPLQuadTreeSearch (const CPLQuadTree *hQuadtree, const CPLRectObj *pAoi, int *pnFeatureCount)
void CPL_DLL 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 CPL_DLL* 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
void CPL_DLL CPLQuadTreeDestroy ( CPLQuadTree hQuadTree  ) 

Destroy a quadtree

Parameters:
hQuadTree the quad tree to destroy
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.

Parameters:
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

Parameters:
nExpectedFeatures the expected maximum number of elements to be inserted
Returns:
the optimal depth of a quadtree to hold nExpectedFeatures
void CPL_DLL CPLQuadTreeInsert ( CPLQuadTree hQuadTree,
void *  hFeature 
)

Insert a feature into a quadtree

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

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 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.

Parameters:
hQuadTree the quad tree
nBucketCapacity the maximum capactiy 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.

Parameters:
hQuadTree the quad tree
nMaxDepth the maximum depth allowed

Generated on 2 Aug 2014 for SDTS_AL by  doxygen 1.6.1