GDAL
Classes | Typedefs | Functions
cpl_quad_tree.h File Reference

Quad tree implementation. More...

#include "cpl_port.h"
#include <stdbool.h>

Go to the source code of this file.

Classes

struct  CPLRectObj
 Describe a rectangle. More...
 

Typedefs

typedef struct _CPLQuadTree CPLQuadTree
 Opaque type for a quad tree.
 
typedef void(* CPLQuadTreeGetBoundsFunc) (const void *hFeature, CPLRectObj *pBounds)
 CPLQuadTreeGetBoundsFunc.
 
typedef void(* CPLQuadTreeGetBoundsExFunc) (const void *hFeature, void *pUserData, CPLRectObj *pBounds)
 CPLQuadTreeGetBoundsExFunc.
 
typedef int(* CPLQuadTreeForeachFunc) (void *pElt, void *pUserData)
 CPLQuadTreeForeachFunc.
 
typedef void(* CPLQuadTreeDumpFeatureFunc) (const void *hFeature, int nIndentLevel, void *pUserData)
 CPLQuadTreeDumpFeatureFunc.
 

Functions

CPLQuadTreeCPLQuadTreeCreate (const CPLRectObj *pGlobalBounds, CPLQuadTreeGetBoundsFunc pfnGetBounds)
 Create a new quadtree. More...
 
CPLQuadTreeCPLQuadTreeCreateEx (const CPLRectObj *pGlobalBounds, CPLQuadTreeGetBoundsExFunc pfnGetBounds, void *pUserData)
 Create a new quadtree. More...
 
void CPLQuadTreeDestroy (CPLQuadTree *hQuadtree)
 Destroy a quadtree. More...
 
void CPLQuadTreeSetBucketCapacity (CPLQuadTree *hQuadtree, int nBucketCapacity)
 Set the maximum capacity of a node of a quadtree. More...
 
void CPLQuadTreeForceUseOfSubNodes (CPLQuadTree *hQuadTree)
 Force the quadtree to insert as much as possible a feature whose bbox spread over multiple subnodes into those subnodes, rather than in the list of features attached to the node. More...
 
int CPLQuadTreeGetAdvisedMaxDepth (int nExpectedFeatures)
 Returns the optimal depth of a quadtree to hold nExpectedFeatures. More...
 
void CPLQuadTreeSetMaxDepth (CPLQuadTree *hQuadtree, int nMaxDepth)
 Set the maximum depth of a quadtree. More...
 
void CPLQuadTreeInsert (CPLQuadTree *hQuadtree, void *hFeature)
 Insert a feature into a quadtree. More...
 
void CPLQuadTreeInsertWithBounds (CPLQuadTree *hQuadtree, void *hFeature, const CPLRectObj *psBounds)
 Insert a feature into a quadtree. More...
 
void CPLQuadTreeRemove (CPLQuadTree *hQuadtree, void *hFeature, const CPLRectObj *psBounds)
 Remove a feature from a quadtree. More...
 
void ** CPLQuadTreeSearch (const CPLQuadTree *hQuadtree, const CPLRectObj *pAoi, int *pnFeatureCount)
 Returns all the elements inserted whose bounding box intersects the provided area of interest. More...
 
void CPLQuadTreeForeach (const CPLQuadTree *hQuadtree, CPLQuadTreeForeachFunc pfnForeach, void *pUserData)
 Walk through the quadtree and runs the provided function on all the elements. More...
 
void CPLQuadTreeDump (const CPLQuadTree *hQuadtree, CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc, void *pUserData)
 Dump quad tree.
 
void CPLQuadTreeGetStats (const CPLQuadTree *hQuadtree, int *pnFeatureCount, int *pnNodeCount, int *pnMaxDepth, int *pnMaxBucketCapacity)
 Get stats.
 

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

◆ CPLQuadTreeCreate()

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

◆ CPLQuadTreeCreateEx()

CPLQuadTree * CPLQuadTreeCreateEx ( const CPLRectObj pGlobalBounds,
CPLQuadTreeGetBoundsExFunc  pfnGetBoundsEx,
void *  pUserData 
)

Create a new quadtree.

Parameters
pGlobalBoundsa pointer to the global extent of all the elements that will be inserted
pfnGetBoundsExa 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.
pUserDatauser data passed to pfnGetBoundsEx
Returns
a newly allocated quadtree

◆ CPLQuadTreeDestroy()

void CPLQuadTreeDestroy ( CPLQuadTree hQuadTree)

Destroy a quadtree.

Parameters
hQuadTreethe quad tree to destroy

◆ CPLQuadTreeForceUseOfSubNodes()

void CPLQuadTreeForceUseOfSubNodes ( CPLQuadTree hQuadTree)

Force the quadtree to insert as much as possible a feature whose bbox spread over multiple subnodes into those subnodes, rather than in the list of features attached to the node.

Parameters
hQuadTreethe quad tree

◆ CPLQuadTreeForeach()

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
hQuadTreethe quad tree
pfnForeachthe function called on each element.
pUserDatathe user data provided to the function.

◆ CPLQuadTreeGetAdvisedMaxDepth()

int 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

◆ CPLQuadTreeInsert()

void CPLQuadTreeInsert ( CPLQuadTree hQuadTree,
void *  hFeature 
)

Insert a feature into a quadtree.

Parameters
hQuadTreethe quad tree
hFeaturethe feature to insert

◆ CPLQuadTreeInsertWithBounds()

void CPLQuadTreeInsertWithBounds ( CPLQuadTree hQuadTree,
void *  hFeature,
const CPLRectObj psBounds 
)

Insert a feature into a quadtree.

Parameters
hQuadTreethe quad tree
hFeaturethe feature to insert
psBoundsbounds of the feature

◆ CPLQuadTreeRemove()

void CPLQuadTreeRemove ( CPLQuadTree hQuadTree,
void *  hFeature,
const CPLRectObj psBounds 
)

Remove a feature from a quadtree.

Currently the quadtree is not re-balanced.

Parameters
hQuadTreethe quad tree
hFeaturethe feature to remove
psBoundsbounds of the feature (or NULL if pfnGetBounds has been filled)

◆ CPLQuadTreeSearch()

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

◆ CPLQuadTreeSetBucketCapacity()

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
hQuadTreethe quad tree
nBucketCapacitythe maximum capacity of a node of a quadtree

◆ CPLQuadTreeSetMaxDepth()

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
hQuadTreethe quad tree
nMaxDepththe maximum depth allowed