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

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

CPLQuadTreeDestroy()

void CPLQuadTreeDestroy

(

CPLQuadTree *

hQuadTree

)

Destroy a quadtree.

Parameters

hQuadTree

the quad tree to destroy

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

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

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