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