Classes | Typedefs | Functions

# 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 | CPLQuadTreeInsertWithBounds (CPLQuadTree *hQuadtree, void *hFeature, const CPLRectObj *psBounds)
| 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. 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 1.7.1.