A simple quadtree library. More...

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

Include dependency graph for pico_qt.h:

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

Typedefs
typedef float	qt_float
	Single precision floating point type. More...

typedef uint32_t	qt_value_t
	Value data type that can store an integer. More...

typedef struct qt_t	qt_t
	Quadtree data structure. More...

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

qt_t *	qt_create (qt_rect_t bounds, int max_depth, void *mem_ctx)
	Creates a quadtree with the specified global bounds. More...

void	qt_destroy (qt_t *qt)
	Destroys a quadtree. More...

void	qt_reset (qt_t *qt)
	Removes all nodes in the tree. More...

void	qt_insert (qt_t *qt, qt_rect_t bounds, qt_value_t value)
	Inserts a value with the specified bounds into a quadtree. More...

bool	qt_remove (qt_t *qt, qt_value_t value)
	Searches for and removes a value in a quadtree. More...

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

qt_rect_t *	qt_grid_rects (const qt_t qt, int size)
	Returns all bounds associated with the quadtree's recursive grid structure. More...

void	qt_free (qt_t qt, void array)
	Function for deallocating arrays. More...

void	qt_clear (qt_t *qt)
	Removes all items in the tree. More...

void	qt_clean (qt_t *qt)
	Resets the tree and reinserts all items. More...

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_USE_DOUBLE PICO_QT_USE_UINTPTR PICO_QT_BLOCK_SIZE PICO_QT_ASSERT PICO_QT_MALLOC PICO_QT_REALLOC PICO_QT_FREE PICO_QT_MEMCPY PICO_QT_MEMSET

Typedef Documentation

◆ qt_float

typedef float qt_float

Single precision floating point type.

◆ qt_value_t

typedef uint32_t qt_value_t

Value data type that can store an integer.

◆ 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

Classes

Typedefs

Functions

Detailed Description

Licensing information at end of header

Features:

Summary:

Depth:

Usage:

Customization:

Typedef Documentation

◆ qt_float

◆ qt_value_t

◆ qt_t

Function Documentation

◆ qt_make_rect()

◆ qt_create()

◆ qt_destroy()

◆ qt_reset()

◆ qt_insert()

◆ qt_remove()

◆ qt_query()

◆ qt_grid_rects()

◆ qt_free()

◆ qt_clear()

◆ qt_clean()