# cpl_quad_tree.h File Reference

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

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