Quadtree operations. More...
Typedefs | |
| typedef struct _Eina_QuadTree | Eina_QuadTree |
| A quadtree is a data structure where each node contains four child nodes. More... | |
| 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. More... | |
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. More... | |
| EINA_API void | eina_quadtree_free (Eina_QuadTree *q) |
| Destructs quadtree and its data. More... | |
| EINA_API void | eina_quadtree_resize (Eina_QuadTree *q, size_t w, size_t h) |
| Changes the width and height of the quadtree. More... | |
| EINA_API void | eina_quadtree_cycle (Eina_QuadTree *q) |
| Sets the quadtree's index to 0. More... | |
| EINA_API void | eina_quadtree_increase (Eina_QuadTree_Item *object) |
| Increases the index of the quadtree item by one. More... | |
| EINA_API Eina_QuadTree_Item * | eina_quadtree_add (Eina_QuadTree *q, const void *object) |
| Inserts a data object into the quadtree. More... | |
| EINA_API Eina_Bool | eina_quadtree_del (Eina_QuadTree_Item *object) |
| Deletes a given quadtree item from the quadtree. More... | |
| EINA_API Eina_Bool | eina_quadtree_change (Eina_QuadTree_Item *object) |
| Marks an object within the quadtree as needing changed. More... | |
| EINA_API Eina_Bool | eina_quadtree_hide (Eina_QuadTree_Item *object) |
Sets object invisible. More... | |
| EINA_API Eina_Bool | eina_quadtree_show (Eina_QuadTree_Item *object) |
Sets object to visible. More... | |
| 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. More... | |
| EINA_API void * | eina_quadtree_object (Eina_Inlist *list) |
| Retrieves the quadtree item's data for the given inline list. More... | |
Quadtree operations.
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 |
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.
| 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.
| [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. |
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_API void eina_quadtree_free | ( | Eina_QuadTree * | q | ) |
Destructs quadtree and its data.
| [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, eina_mempool_free(), and eina_trash_pop().
| EINA_API void eina_quadtree_resize | ( | Eina_QuadTree * | q, |
| size_t | w, | ||
| size_t | h | ||
| ) |
Changes the width and height of the quadtree.
| [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_API void eina_quadtree_cycle | ( | Eina_QuadTree * | q | ) |
Sets the quadtree's index to 0.
| [in,out] | q | The quadtree to cycle. |
| EINA_API void eina_quadtree_increase | ( | Eina_QuadTree_Item * | object | ) |
Increases the index of the quadtree item by one.
| [in,out] | object | The quadtree item to increase. |
If necessary, records that the root is no longer sorted.
References EINA_FALSE.
| EINA_API Eina_QuadTree_Item * eina_quadtree_add | ( | Eina_QuadTree * | q, |
| const void * | object | ||
| ) |
Inserts a data object into the quadtree.
| [in,out] | q | The quadtree to add object to. |
| [in] | object | A data object to store in the quadtree. |
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, eina_mempool_malloc(), eina_trash_pop(), and EINA_TRUE.
| EINA_API Eina_Bool eina_quadtree_del | ( | Eina_QuadTree_Item * | object | ) |
Deletes a given quadtree item from the quadtree.
| [in] | object | The quadtree item to be deleted. |
Moves the item to the quadtree's internal garbage heap for later reclamation.
References EINA_FALSE, eina_list_remove(), EINA_MAGIC_SET, eina_mempool_free(), eina_trash_push(), and EINA_TRUE.
| EINA_API Eina_Bool eina_quadtree_change | ( | Eina_QuadTree_Item * | object | ) |
Marks an object within the quadtree as needing changed.
| [in,out] | object | The object that has changed. |
References EINA_FALSE, eina_inlist_append(), EINA_INLIST_GET, and EINA_TRUE.
Referenced by eina_quadtree_show().
| EINA_API Eina_Bool eina_quadtree_hide | ( | Eina_QuadTree_Item * | object | ) |
Sets object invisible.
| [in,out] | object | The item within the quadtree to hide. |
object was successfully hidden, or EINA_FALSE if it wasn't in the quadtree. References EINA_FALSE, and EINA_TRUE.
| EINA_API Eina_Bool eina_quadtree_show | ( | Eina_QuadTree_Item * | object | ) |
Sets object to visible.
| [in,out] | object | The item within the quadtree to show. |
object was successfully shown, or EINA_FALSE if it wasn't in the quadtree. References EINA_FALSE, eina_quadtree_change(), and EINA_TRUE.
| 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.
| [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. |
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, and _Eina_Rectangle::w.
| EINA_API void * eina_quadtree_object | ( | Eina_Inlist * | list | ) |
Retrieves the quadtree item's data for the given inline list.
| [in] | list | The inline list item to lookup |
NULL if none could be found. References EINA_INLIST_CONTAINER_GET.