pico_qt.h File Reference

A simple quadtree library. More...

#include <stdbool.h>
#include <stdint.h>

Include dependency graph for pico_qt.h:

Go to the source code of this file.

Classes
struct	qt_rect_t
	Rectangle for representing bounds. More...

Macros
#define	PICO_QT_VALUE_TYPE   uint32_t

Typedefs
typedef float	qt_float
	Single precision floating point type.
typedef PICO_QT_VALUE_TYPE	qt_value_t
	Node value type (default: uint32_t)
typedef struct qt_t	qt_t
	Quadtree data structure.

Functions
qt_rect_t	qt_make_rect (qt_float x, qt_float y, qt_float w, qt_float h)
	Utility function for creating a rectangle.
qt_t *	qt_create (qt_rect_t bounds, int max_depth, void *mem_ctx)
	Creates a quadtree with the specified global bounds.
void	qt_destroy (qt_t *qt)
	Destroys a quadtree.
void	qt_reset (qt_t *qt)
	Removes all nodes in the tree.
void	qt_insert (qt_t *qt, qt_rect_t bounds, qt_value_t value)
	Inserts a value with the specified bounds into a quadtree.
bool	qt_remove (qt_t *qt, qt_value_t value)
	Searches for and removes a value in a quadtree.
qt_value_t *	qt_query (const qt_t *qt, qt_rect_t area, int *size)
	Returns all values associated with items that are either overlapping or contained within the search area.
qt_rect_t *	qt_grid_rects (const qt_t *qt, int *size)
	Returns all bounds associated with the quadtree's recursive grid structure.
void	qt_free (qt_t *qt, void *array)
	Function for deallocating arrays.
void	qt_clear (qt_t *qt)
	Removes all items in the tree.
void	qt_clean (qt_t *qt)
	Resets the tree and reinserts all items.

Detailed Description

A simple quadtree library.

---

Licensing information at end of header

Features:

• Written in C99
• Single header library for easy build system integration
• Simple and concise API
• Permissive license (zlib or public domain)

Summary:

This library builds and manages Quadtrees.

A quadtree is a data structure that can be used to perform efficient spatial queries. Items (values + bounds) are inserted into the tree. During this process, space in a quadtree is subdivided to make subsequent retrieval fast. Queries return values for all items that are contained within or overlap the search area.

Currently, values are numeric. If uintptr_t is used they can also store a pointer. An integer value could represent an entity ID, an array index, a key for a hashtable etc...

Depth:

There is a tradeoff between space and time complexity. Lower depth values have smaller space requirements, but higher search times. Indeed, a tree with a depth of zero reduces to a linear bounds check. Higher values speed up searches, but at the cost of increased space. There are, however, diminishing returns with regard to increasing the max depth too high. Eventually all of the additional space is wasted with no benefit to performance.

Usage:

To use this library in your project, add the following

‍#define PICO_QT_IMPLEMENTATION #include "pico_qt.h"

to a source file (once), then simply include the header normally.

Must be defined before PICO_QT_IMPLEMENTATION

Customization:

A few macros can be overridden simply by defining them before including this source file. Here is a list of them.

PICO_QT_VALUE_TYPE PICO_QT_BLOCK_SIZE PICO_QT_ASSERT PICO_QT_MALLOC PICO_QT_REALLOC PICO_QT_FREE PICO_QT_MEMCPY PICO_QT_MEMSET

Macro Definition Documentation

PICO_QT_VALUE_TYPE

#define PICO_QT_VALUE_TYPE   uint32_t

Typedef Documentation

qt_float

typedef float qt_float

Single precision floating point type.

qt_value_t

typedef PICO_QT_VALUE_TYPE qt_value_t

Node value type (default: uint32_t)

qt_t

typedef struct qt_t qt_t

Quadtree data structure.

Function Documentation

qt_make_rect()

qt_rect_t qt_make_rect	(	qt_float	x,
		qt_float	y,
		qt_float	w,
		qt_float	h
	)

Utility function for creating a rectangle.

qt_create()

qt_t * qt_create	(	qt_rect_t	bounds,
		int	max_depth,
		void *	mem_ctx
	)

Creates a quadtree with the specified global bounds.

Parameters

bounds	The global bounds
max_depth	Maximum height of the quadtree. See the summary for more

Returns

A quadtree instance

qt_destroy()

void qt_destroy

(

qt_t *

qt

)

Destroys a quadtree.

Parameters

qt	The quadtree instance to destroy

qt_reset()

void qt_reset

(

qt_t *

qt

)

Removes all nodes in the tree.

Parameters

qt	The quadtree instance

qt_insert()

void qt_insert	(	qt_t *	qt,
		qt_rect_t	bounds,
		qt_value_t	value
	)

Inserts a value with the specified bounds into a quadtree.

Parameters

qt	The quadtree instance
bounds	The bounds associated with the value
value	The value to store in the tree

qt_remove()

bool qt_remove	(	qt_t *	qt,
		qt_value_t	value
	)

Searches for and removes a value in a quadtree.

This function is very inefficient. If numerous values need to be removed and reinserted it is advisable to simply rebuild the tree.

Parameters

qt	The quadtree instance
value	The value to remove

Returns

True if the item was found, and false otherwise

qt_query()

qt_value_t * qt_query	(	const qt_t *	qt,
		qt_rect_t	area,
		int *	size
	)

Returns all values associated with items that are either overlapping or contained within the search area.

Parameters

qt	The quadtree instance
area	The search area
size	The number of values returned

Returns

The values of items contained within the search area. This array is dynamically allocated and should be deallocated by using qt_free after use

qt_grid_rects()

qt_rect_t * qt_grid_rects	(	const qt_t *	qt,
		int *	size
	)

Returns all bounds associated with the quadtree's recursive grid structure.

You must free this array with qt_free when done. This function is useful for e.g. debug rendering the tree's grid-like structure.

Parameters

qt	The quadtree instance.
size	The number of elements in the returned array.

Returns

For each node in the quadtree there are four bounds associated. All bounds are collated into a single dynamically allocated array.

qt_free()

void qt_free	(	qt_t *	qt,
		void *	array
	)

Function for deallocating arrays.

This function can deallocate arrays returned from qt_query or from qt_grid_rects.

qt_clear()

void qt_clear

(

qt_t *

qt

)

Removes all items in the tree.

This function preserves the internal structure of the tree making it much faster than qt_reset. Reinserting values is probably faster too, however, repeated calls to this function may result in fragmentation of the tree. The function qt_clean can repair this fragmentation, however, it is expensive.

Parameters

qt	The quadtree instance

qt_clean()

void qt_clean

(

qt_t *

qt

)

Resets the tree and reinserts all items.

This function can repair fragmentation resulting from repeated use of qt_remove or qt_clear. This is an expensive operation since it must extract all of the items from the tree, remove all of the nodes, and then reinsert all of the items.

Parameters

qt	The quadtree instance