Quadtrees
Eina » Data Types

Quadtree operations. More...

## Typedefs

typedef struct _Eina_QuadTree | Eina_QuadTree
| A quadtree is a data structure where each node contains four child nodes.
typedef struct _Eina_QuadTree_Item | Eina_QuadTree_Item
| A quadtree item is a holder for (void *) data items inside a quadtree, that includes some state tracking for lifecycle management and optimization purposes.
typedef Eina_Quad_Direction(* | Eina_Quad_Callback) (const void *object, size_t middle)
| Signature for a callback routine used to determine the location of an object within a quadtree.

## Enumerations

enum | Eina_Quad_Direction { EINA_QUAD_LEFT , EINA_QUAD_RIGHT , EINA_QUAD_BOTH }

## Functions

EINA_API Eina_QuadTree * | eina_quadtree_new (size_t w, size_t h, Eina_Quad_Callback vertical, Eina_Quad_Callback horizontal)
| Constructs a quadtree object.
EINA_API void | eina_quadtree_free (Eina_QuadTree *q)
| Destructs quadtree and its data.
EINA_API void | eina_quadtree_resize (Eina_QuadTree *q, size_t w, size_t h)
| Changes the width and height of the quadtree.
EINA_API void | eina_quadtree_cycle (Eina_QuadTree *q)
| Sets the quadtree's index to 0.
EINA_API void | eina_quadtree_increase (Eina_QuadTree_Item *object)
| Increases the index of the quadtree item by one.
EINA_API Eina_QuadTree_Item * | eina_quadtree_add (Eina_QuadTree *q, const void *object)
| Inserts a data object into the quadtree.
EINA_API Eina_Bool | eina_quadtree_del (Eina_QuadTree_Item *object)
| Deletes a given quadtree item from the quadtree.
EINA_API Eina_Bool | eina_quadtree_change (Eina_QuadTree_Item *object)
| Marks an object within the quadtree as needing changed.
EINA_API Eina_Bool | eina_quadtree_hide (Eina_QuadTree_Item *object)
| Sets `object` invisible.
EINA_API Eina_Bool | eina_quadtree_show (Eina_QuadTree_Item *object)
| Sets `object` to visible.
EINA_API Eina_Inlist * | eina_quadtree_collide (Eina_QuadTree *q, int x, int y, int w, int h)
| Retrieves items in quadtree inside the target geometry.
EINA_API void * | eina_quadtree_object (Eina_Inlist *list)
| Retrieves the quadtree item's data for the given inline list.

## Detailed Description

Quadtree operations.

## Typedef Documentation

## Eina_QuadTree

typedef struct _Eina_QuadTree Eina_QuadTree

A quadtree is a data structure where each node contains four child nodes.

It can be used to partition 2D spaces through subdivision into quadrants.

## Eina_Quad_Callback

typedef Eina_Quad_Direction(* Eina_Quad_Callback) (const void *object, size_t middle)

Signature for a callback routine used to determine the location of an object within a quadtree.

These are used in sorting by determining where in the tree the given data `object` belongs, using `middle` as the division line for the two halves of the space.

## Function Documentation

## eina_quadtree_new()

EINA_API Eina_QuadTree * eina_quadtree_new | ( | size_t | w,
|  | size_t | h,
|  | Eina_Quad_Callback | vertical,
|  | Eina_Quad_Callback | horizontal )

Constructs a quadtree object.

Parameters

  [in] | w | The geometric width of the quadtree.
  [in] | h | The geometric height of the quadtree.
  [in] | vertical | The callback for vertical direction determination.
  [in] | horizontal | The callback for horizontal direction determination.

Returns
  The newly allocated and initialized quadtree, or `NULL` on error.

The vertical and horizontal callbacks are used to assist in determining which quadrant a given data item belongs to.

References EINA_MAGIC_SET, and EINA_TRUE.

## eina_quadtree_free()

EINA_API void eina_quadtree_free | ( | Eina_QuadTree * | q | ) |

Destructs quadtree and its data.

Parameters

  [in] | q | The quadtree to be freed.

Frees the memory for the Eina_QuadTree object, and any memory used by its change tracking and garbage collection internals.

References EINA_INLIST_CONTAINER_GET, EINA_LIST_FREE, EINA_MAGIC_SET, and _Eina_Inlist::next.

## eina_quadtree_resize()

EINA_API void eina_quadtree_resize | ( | Eina_QuadTree * | q,
|  | size_t | w,
|  | size_t | h )

Changes the width and height of the quadtree.

Parameters

  [in,out] | q | The quadtree to resize.
  [in] | w | The new geometric width for the quadtree.
  [in] | h | The new geometric height for the quadtree.

Sets the width and height of the quadtree, but the actual update is done lazily.

References EINA_TRUE.

## eina_quadtree_cycle()

EINA_API void eina_quadtree_cycle | ( | Eina_QuadTree * | q | ) |

Sets the quadtree's index to 0.

Parameters

  [in,out] | q | The quadtree to cycle.

## eina_quadtree_increase()

EINA_API void eina_quadtree_increase | ( | Eina_QuadTree_Item * | object | ) |

Increases the index of the quadtree item by one.

Parameters

  [in,out] | object | The quadtree item to increase.

If necessary, records that the root is no longer sorted.

References EINA_FALSE.

## eina_quadtree_add()

EINA_API Eina_QuadTree_Item * eina_quadtree_add | ( | Eina_QuadTree * | q,
|  | const void * | object )

Inserts a data object into the quadtree.

Parameters

  [in,out] | q | The quadtree to add `object` to.
  [in] | object | A data object to store in the quadtree.

Returns
  Pointer to the stored quadtree item.

Creates an Eina_QuadTree_Item (or recycles one from the quadtree's trash) and stores the data `object` in it, then arranges to lazily insert the item into the quadtree (i.e. insertion is delayed until it needs to be used.)

References EINA_FALSE, eina_inlist_append(), EINA_INLIST_GET, EINA_MAGIC_SET, and EINA_TRUE.

## eina_quadtree_del()

EINA_API Eina_Bool eina_quadtree_del | ( | Eina_QuadTree_Item * | object | ) |

Deletes a given quadtree item from the quadtree.

Parameters

  [in] | object | The quadtree item to be deleted.

Returns
  EINA_TRUE on success, EINA_FALSE otherwise.

Moves the item to the quadtree's internal garbage heap for later reclamation.

References EINA_FALSE, eina_list_remove(), EINA_MAGIC_SET, and EINA_TRUE.

## eina_quadtree_change()

EINA_API Eina_Bool eina_quadtree_change | ( | Eina_QuadTree_Item * | object | ) |

Marks an object within the quadtree as needing changed.

Parameters

  [in,out] | object | The object that has changed.

Returns
  EINA_TRUE if change successfully noted, or EINA_FALSE otherwise.

References EINA_FALSE, eina_inlist_append(), EINA_INLIST_GET, and EINA_TRUE.

Referenced by eina_quadtree_show().

## eina_quadtree_hide()

EINA_API Eina_Bool eina_quadtree_hide | ( | Eina_QuadTree_Item * | object | ) |

Sets `object` invisible.

Parameters

  [in,out] | object | The item within the quadtree to hide.

Returns
  EINA_TRUE if `object` was successfully hidden, or EINA_FALSE if it wasn't in the quadtree.

References EINA_FALSE, and EINA_TRUE.

## eina_quadtree_show()

EINA_API Eina_Bool eina_quadtree_show | ( | Eina_QuadTree_Item * | object | ) |

Sets `object` to visible.

Parameters

  [in,out] | object | The item within the quadtree to show.

Returns
  EINA_TRUE if `object` was successfully shown, or EINA_FALSE if it wasn't in the quadtree.

References EINA_FALSE, eina_quadtree_change(), and EINA_TRUE.

## eina_quadtree_collide()

EINA_API Eina_Inlist * eina_quadtree_collide | ( | Eina_QuadTree * | q,
|  | int | x,
|  | int | y,
|  | int | w,
|  | int | h )

Retrieves items in quadtree inside the target geometry.

Parameters

  [in,out] | q | The quadtree to recompute.
  [in] | x | New target X coordinate.
  [in] | y | New target Y coordinate.
  [in] | w | New target width.
  [in] | h | New target height.

Returns
  The list of collided items or `NULL` on error.

Forces a rebuild and resort of the quadtree if needed due to pending changes, then performs a collision detection to find items whose geometry is contained within or intersects the given target geometry.

References DBG, EINA_FALSE, EINA_RECTANGLE_SET, EINA_TRUE, _Eina_Rectangle::h, _Eina_Rectangle::w, _Eina_Rectangle::x, and _Eina_Rectangle::y.

## eina_quadtree_object()

EINA_API void * eina_quadtree_object | ( | Eina_Inlist * | list | ) |

Retrieves the quadtree item's data for the given inline list.

Parameters

  [in] | list | The inline list item to lookup

Returns
  The contained data object in the Eina_QuadTree_Item, or `NULL` if none could be found.

References EINA_INLIST_CONTAINER_GET.