|
GRASS 8 Programmer's Manual 8.6.0dev(2026)-f6f2c534ea
|
R-Tree library - Multidimensional index. More...
#include <stdlib.h>#include <sys/types.h>#include <unistd.h>#include <assert.h>#include <string.h>#include <errno.h>#include <grass/gis.h>#include <grass/glocale.h>#include "index.h"
Go to the source code of this file.
Functions | |
| struct RTree * | RTreeCreateTree (int fd, off_t rootpos, int ndims) |
| Create new empty R*-Tree. | |
| void | RTreeSetOverflow (struct RTree *t, char overflow) |
| Enable/disable R*-tree forced reinsertion (overflow) | |
| void | RTreeDestroyTree (struct RTree *t) |
| Destroy an R*-Tree. | |
| int | RTreeSearch (struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg) |
| Search an R*-Tree. | |
| int | RTreeInsertRect (struct RTree_Rect *r, int tid, struct RTree *t) |
| Insert an item into a R*-Tree. | |
| int | RTreeDeleteRect (struct RTree_Rect *r, int tid, struct RTree *t) |
| Delete an item from a R*-Tree. | |
| struct RTree_ListNode * | RTreeNewListNode (void) |
| void | RTreeFreeListNode (struct RTree_ListNode *p) |
| void | RTreeReInsertNode (struct RTree_Node *n, struct RTree_ListNode **ee) |
| void | RTreeFreeListBranch (struct RTree_ListBranch *p) |
R-Tree library - Multidimensional index.
Higher level functions for managing R*-Trees.
(C) 2010-2012 by the GRASS Development Team
This program is free software under the GNU General Public License (>=v2). Read the file COPYING that comes with GRASS for details.
Definition in file vector/rtree/index.c.
Create new empty R*-Tree.
This method creates a new RTree, either in memory (fd < 0) or in file. If the file descriptor is positive, the corresponding file must have been opened for reading and writing. This method must also be called if an existing tree previously saved to file is going to be accessed.
| fd | file descriptor to hold data, negative toggles memory mode |
| rootpos | offset in file to root node (past any header info) |
| ndims | number of dimensions for the new tree: min 2, max 20 |
Definition at line 66 of file vector/rtree/index.c.
References _, err(), RTree::fd, G_fatal_error(), RTree_Node::level, malloc(), MAXCARD, MAXLEVEL, RTree::ndims, NODE_BUFFER_SIZE, NULL, RTree::rootpos, RTreeAllocBoundary(), RTreeAllocNode(), RTreeDeleteRectF(), RTreeDeleteRectM(), RTreeFreeNode(), RTreeInsertRectF(), RTreeInsertRectM(), RTreeSearchF(), RTreeSearchM(), RTreeValidChildF(), RTreeValidChildM(), and RTreeWriteNode().
Referenced by dig_spidx_free_areas(), dig_spidx_free_isles(), dig_spidx_free_lines(), dig_spidx_free_nodes(), dig_spidx_init(), line_check_intersection(), Vect_break_polygons_file(), Vect_line_intersection(), Vect_snap_line(), and Vect_spatial_index_init().
Delete an item from a R*-Tree.
This method deletes an item from the RTree. The rectangle passed to this method does not need to be the exact rectangle, the only requirement is that this rectangle overlaps with the rectangle to be deleted. The rectangle to be deleted is identified by its id.
| r | pointer to rectangle to use for searching |
| tid | id of the data to be deleted, must be > 0 |
| t | pointer to RTree structure |
Definition at line 355 of file vector/rtree/index.c.
References assert, RTree_Child::id, r, and t.
Referenced by dig_spidx_del_area(), dig_spidx_del_isle(), dig_spidx_del_line(), dig_spidx_del_node(), and Vect_spatial_index_del_item().
Destroy an R*-Tree.
This method releases all memory allocated to a RTree. It deletes all rectangles and all memory allocated for internal support data. Note that for a file-based RTree, the file is not deleted and not closed. The file can thus be used to permanently store an RTree.
| t | pointer to RTree structure |
Definition at line 235 of file vector/rtree/index.c.
References assert, free(), MAXCARD, MAXLEVEL, NODE_BUFFER_SIZE, RTreeDestroyNode(), RTreeFreeBoundary(), and t.
Referenced by dig_spidx_free(), dig_spidx_free_areas(), dig_spidx_free_isles(), dig_spidx_free_lines(), dig_spidx_free_nodes(), line_check_intersection(), Vect_break_polygons_file(), Vect_line_intersection(), Vect_snap_line(), and Vect_spatial_index_destroy().
| void RTreeFreeListBranch | ( | struct RTree_ListBranch * | p | ) |
Definition at line 400 of file vector/rtree/index.c.
References RTree_ListBranch::b, free(), and RTreeFreeBoundary().
Referenced by RTreeInsertRectF(), and RTreeInsertRectM().
| void RTreeFreeListNode | ( | struct RTree_ListNode * | p | ) |
Definition at line 379 of file vector/rtree/index.c.
References free().
Referenced by RTreeDeleteRectF(), and RTreeDeleteRectM().
Insert an item into a R*-Tree.
| r | pointer to rectangle to use for searching |
| tid | data id stored with rectangle, must be > 0 |
| t | pointer to RTree structure |
Definition at line 328 of file vector/rtree/index.c.
Referenced by dig_spidx_add_area(), dig_spidx_add_isle(), dig_spidx_add_line(), dig_spidx_add_node(), line_check_intersection(), Vect_break_polygons_file(), Vect_line_intersection(), Vect_snap_line(), and Vect_spatial_index_add_item().
| struct RTree_ListNode * RTreeNewListNode | ( | void | ) |
Definition at line 374 of file vector/rtree/index.c.
References malloc().
Referenced by RTreeReInsertNode().
| void RTreeReInsertNode | ( | struct RTree_Node * | n, |
| struct RTree_ListNode ** | ee | ||
| ) |
Definition at line 388 of file vector/rtree/index.c.
References l, and RTreeNewListNode().
| int RTreeSearch | ( | struct RTree * | t, |
| struct RTree_Rect * | r, | ||
| SearchHitCallback * | shcb, | ||
| void * | cbarg | ||
| ) |
Search an R*-Tree.
Search in an RTree for all data rectangles that overlap or touch the argument rectangle. Return the number of qualifying data rectangles. The search stops if the SearchHitCallBack function returns 0 (zero) or if there are no more qualifying data rectangles.
| t | pointer to RTree structure |
| r | pointer to rectangle to use for searching |
| shcb | Search Hit CallBack function |
| cbarg | custom pointer used as argument for the shcb fn |
Definition at line 311 of file vector/rtree/index.c.
Referenced by dig_find_area_box(), dig_find_isle_box(), dig_find_line_box(), dig_find_node(), dig_select_areas(), dig_select_isles(), dig_select_lines(), dig_select_nodes(), line_check_intersection(), Vect_break_polygons_file(), Vect_line_intersection(), Vect_snap_line(), and Vect_spatial_index_select().
Enable/disable R*-tree forced reinsertion (overflow)
For dynamic R*-trees with runtime insertion and deletion, forced reinsertion results in a more compact tree, searches are a bit faster. For static R*-trees (no insertion/deletion after creation) forced reinsertion can be disabled at the cost of slower searches.
| t | pointer to RTree structure |
| overflow | binary flag |
Definition at line 218 of file vector/rtree/index.c.
References t.
Referenced by line_check_intersection(), Vect_line_intersection(), and Vect_snap_line().