SDTS_AL
Classes | Functions

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:
pGlobalBoundsa pointer to the global extent of all the elements that will be inserted
pfnGetBoundsa 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:
hQuadTreethe 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:
hQuadTreethe quad tree
pfnForeachthe function called on each element.
pUserDatathe user data provided to the function.
int CPL_DLL CPLQuadTreeGetAdvisedMaxDepth ( int  nExpectedFeatures)

Returns the optimal depth of a quadtree to hold nExpectedFeatures

Parameters:
nExpectedFeaturesthe 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:
hQuadTreethe quad tree
hFeaturethe 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:
hQuadTreethe quad tree
pAoithe pointer to the area of interest
pnFeatureCountthe 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:
hQuadTreethe quad tree
nBucketCapacitythe 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:
hQuadTreethe quad tree
nMaxDepththe maximum depth allowed

Generated for GDAL by doxygen 1.7.3.