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
CPLQuadTree * | CPLQuadTreeCreate (const CPLRectObj *pGlobalBounds, CPLQuadTreeGetBoundsFunc pfnGetBounds)
| Create a new quadtree.
CPLQuadTree * | CPLQuadTreeCreateEx (const CPLRectObj *pGlobalBounds, CPLQuadTreeGetBoundsExFunc pfnGetBounds, void *pUserData)
| 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.
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.
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 | CPLQuadTreeRemove (CPLQuadTree *hQuadtree, void *hFeature, const CPLRectObj *psBounds)
| Remove a feature from 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.
bool | CPLQuadTreeHasMatch (const CPLQuadTree *hQuadtree, const CPLRectObj *pAoi)
| Returns whether the quadtree has at least one element 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)
| 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

  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

## ◆ CPLQuadTreeCreateEx()

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

Create a new quadtree.

Parameters

  pGlobalBounds | a pointer to the global extent of all the elements that will be inserted
  pfnGetBoundsEx | 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.
  pUserData | user data passed to pfnGetBoundsEx

Returns
  a newly allocated quadtree

## ◆ CPLQuadTreeDestroy()

void CPLQuadTreeDestroy | ( | CPLQuadTree * | hQuadTree | ) |

Destroy a quadtree.

Parameters

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

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

  hQuadTree | the quad tree
  pfnForeach | the function called on each element.
  pUserData | the user data provided to the function.

## ◆ CPLQuadTreeGetAdvisedMaxDepth()

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

## ◆ CPLQuadTreeHasMatch()

bool CPLQuadTreeHasMatch | ( | const CPLQuadTree * | hQuadTree,
|  | const CPLRectObj * | pAoi
| ) |  |

Returns whether the quadtree has at least one element whose bounding box intersects the provided area of interest.

Parameters

  hQuadTree | the quad tree
  pAoi | the pointer to the area of interest

## ◆ CPLQuadTreeInsert()

void CPLQuadTreeInsert | ( | CPLQuadTree * | hQuadTree,
|  | void * | hFeature
| ) |  |

Insert a feature into a quadtree.

Parameters

  hQuadTree | the quad tree
  hFeature | the feature to insert

## ◆ CPLQuadTreeInsertWithBounds()

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

## ◆ CPLQuadTreeRemove()

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

Remove a feature from a quadtree.

Currently the quadtree is not re-balanced.

Parameters

  hQuadTree | the quad tree
  hFeature | the feature to remove
  psBounds | bounds 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

  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

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

  hQuadTree | the quad tree
  nBucketCapacity | the 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

  hQuadTree | the quad tree
  nMaxDepth | the maximum depth allowed