GRASS GIS 8 Programmer's Manual
8.2.2dev(2023)-3d2c704037
|
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <grass/config.h>
Go to the source code of this file.
Data Structures | |
struct | RTree_Rect |
union | RTree_Child |
struct | RTree_Branch |
struct | RTree_Node |
struct | nstack |
struct | NodeBuffer |
struct | RTree_PartitionVars |
struct | RTree |
struct | RTree::_recycle |
Macros | |
#define | TRUE 1 |
#define | FALSE 0 |
#define | MAXCARD 9 |
#define | NODECARD MAXCARD |
#define | LEAFCARD MAXCARD |
#define | MAXLEVEL 20 /* 8^MAXLEVEL items are guaranteed to fit into the tree */ |
#define | NODE_BUFFER_SIZE 32 |
Typedefs | |
typedef double | RectReal |
typedef int | SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg) |
typedef int | rt_search_fn(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *) |
typedef int | rt_insert_fn(struct RTree_Rect *, union RTree_Child, int, struct RTree *) |
typedef int | rt_delete_fn(struct RTree_Rect *, union RTree_Child, struct RTree *) |
typedef int | rt_valid_child_fn(union RTree_Child *) |
Functions | |
int | RTreeSearch (struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *) |
Search an R*-Tree. More... | |
int | RTreeInsertRect (struct RTree_Rect *, int, struct RTree *) |
Insert an item into a R*-Tree. More... | |
void | RTreeSetRect1D (struct RTree_Rect *r, struct RTree *t, double x_min, double x_max) |
Set one dimensional coordinates of a rectangle for a given tree. More... | |
void | RTreeSetRect2D (struct RTree_Rect *r, struct RTree *t, double x_min, double x_max, double y_min, double y_max) |
Set two dimensional coordinates of a rectangle for a given tree. More... | |
void | RTreeSetRect3D (struct RTree_Rect *r, struct RTree *t, double x_min, double x_max, double y_min, double y_max, double z_min, double z_max) |
Set three dimensional coordinates of a rectangle for a given tree. More... | |
void | RTreeSetRect4D (struct RTree_Rect *r, struct RTree *t, double x_min, double x_max, double y_min, double y_max, double z_min, double z_max, double t_min, double t_max) |
Set 4 dimensional coordinates of a rectangle for a given tree. More... | |
int | RTreeDeleteRect (struct RTree_Rect *, int, struct RTree *) |
Delete an item from a R*-Tree. More... | |
void | RTreePrintRect (struct RTree_Rect *, int, struct RTree *) |
struct RTree * | RTreeCreateTree (int, off_t, int) |
Create new empty R*-Tree. More... | |
void | RTreeSetOverflow (struct RTree *, char) |
Enable/disable R*-tree forced reinsertion (overflow) More... | |
void | RTreeDestroyTree (struct RTree *) |
Destroy an R*-Tree. More... | |
int | RTreeOverlap (struct RTree_Rect *, struct RTree_Rect *, struct RTree *) |
int | RTreeContained (struct RTree_Rect *, struct RTree_Rect *, struct RTree *) |
int | RTreeContains (struct RTree_Rect *, struct RTree_Rect *, struct RTree *) |
struct RTree_Node * | RTreeAllocNode (struct RTree *, int) |
void | RTreeInitNode (struct RTree *, struct RTree_Node *, int) |
void | RTreeCopyNode (struct RTree_Node *, struct RTree_Node *, struct RTree *) |
void | RTreeFreeNode (struct RTree_Node *) |
void | RTreeDestroyNode (struct RTree_Node *, int) |
struct RTree_Rect * | RTreeAllocRect (struct RTree *t) |
Create a new rectangle for a given tree. More... | |
void | RTreeFreeRect (struct RTree_Rect *r) |
Delete a rectangle. More... | |
RectReal * | RTreeAllocBoundary (struct RTree *t) |
Allocate the boundary array of a rectangle for a given tree. More... | |
void | RTreeFreeBoundary (struct RTree_Rect *r) |
Delete the boundary of a rectangle. More... | |
size_t | RTreeReadNode (struct RTree_Node *, off_t, struct RTree *) |
size_t | RTreeWriteNode (struct RTree_Node *, struct RTree *) |
off_t | RTreeGetNodePos (struct RTree *) |
void | RTreeFlushBuffer (struct RTree *) |
#define MAXCARD 9 |
Definition at line 46 of file rtree.h.
Referenced by RTreeAllocNode(), RTreeCopyNode(), RTreeCreateTree(), RTreeDestroyTree(), RTreeFreeNode(), RTreeReadNode(), and RTreeWriteNode().
#define MAXLEVEL 20 /* 8^MAXLEVEL items are guaranteed to fit into the tree */ |
#define NODE_BUFFER_SIZE 32 |
Definition at line 55 of file rtree.h.
Referenced by RTreeAddNodePos(), RTreeCreateTree(), RTreeDestroyTree(), RTreeFlushBuffer(), RTreeGetNode(), and RTreeNodeChanged().
typedef int rt_delete_fn(struct RTree_Rect *, union RTree_Child, struct RTree *) |
typedef int rt_insert_fn(struct RTree_Rect *, union RTree_Child, int, struct RTree *) |
typedef int rt_search_fn(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *) |
typedef int rt_valid_child_fn(union RTree_Child *) |
typedef int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg) |
Allocate the boundary array of a rectangle for a given tree.
This method allocated the boundary coordinates array in provided rectangle. It does not release previously allocated memory.
r | The pointer to rectangle to initialize the boundary coordinates. This is usually a rectangle that was created on the stack or self allocated. |
t | The pointer to a RTree struct |
Definition at line 83 of file rect.c.
References assert, RTree_Rect::boundary, malloc(), and RTree::rectsize.
Referenced by RTreeAllocNode(), RTreeAllocRect(), and RTreeCreateTree().
struct RTree_Node* RTreeAllocNode | ( | struct RTree * | , |
int | |||
) |
Definition at line 77 of file node.c.
References assert, RTree_Rect::boundary, RTree_Node::branch, RTree_Node::count, RTree_Node::level, malloc(), MAXCARD, RTree_Branch::rect, and RTreeAllocBoundary().
Referenced by RTreeCreateTree(), and RTreeInsertRectF().
struct RTree_Rect* RTreeAllocRect | ( | struct RTree * | t | ) |
Create a new rectangle for a given tree.
This method allocates a new rectangle and initializes the internal boundary coordinates based on the tree dimension.
Hence a call to RTreeNewBoundary() is not necessary.
t | The pointer to a RTree struct |
Definition at line 44 of file rect.c.
References assert, RTree_Rect::boundary, malloc(), r, and RTreeAllocBoundary().
int RTreeContained | ( | struct RTree_Rect * | , |
struct RTree_Rect * | , | ||
struct RTree * | |||
) |
int RTreeContains | ( | struct RTree_Rect * | , |
struct RTree_Rect * | , | ||
struct RTree * | |||
) |
void RTreeCopyNode | ( | struct RTree_Node * | , |
struct RTree_Node * | , | ||
struct RTree * | |||
) |
Definition at line 112 of file node.c.
References assert, RTree_Node::branch, RTree_Node::count, RTree_Node::level, MAXCARD, and RTreeCopyBranch().
struct RTree* RTreeCreateTree | ( | int | fd, |
off_t | rootpos, | ||
int | ndims | ||
) |
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 61 of file vector/rtree/index.c.
References RTree::_recycle::alloc, RTree::_recycle::avail, RTree_Rect::boundary, RTree::branchsize, RTree::fd, RTree::free_nodes, RTree_Node::level, malloc(), MAXCARD, MAXLEVEL, RTree::ndims, RTree::ndims_alloc, NODE_BUFFER_SIZE, RTree::nsides, RTree::nsides_alloc, NULL, RTree::_recycle::pos, RTree_Branch::rect, RTree::rectsize, RTree::rootpos, RTreeAllocBoundary(), RTreeAllocNode(), RTreeDeleteRectF(), RTreeDeleteRectM(), RTreeFreeNode(), RTreeInsertRectF(), RTreeInsertRectM(), RTreeSearchF(), RTreeSearchM(), RTreeValidChildF(), RTreeValidChildM(), and RTreeWriteNode().
Referenced by Vect_spatial_index_init().
int RTreeDeleteRect | ( | struct RTree_Rect * | r, |
int | tid, | ||
struct RTree * | t | ||
) |
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 342 of file vector/rtree/index.c.
References assert, RTree::delete_rect, and RTree_Child::id.
Referenced by dig_spidx_del_area(), dig_spidx_del_isle(), dig_spidx_del_node(), and Vect_spatial_index_del_item().
void RTreeDestroyNode | ( | struct RTree_Node * | , |
int | |||
) |
Definition at line 291 of file node.c.
References RTree_Node::branch, RTree_Branch::child, RTree_Node::level, RTree_Child::ptr, RTreeDestroyNode(), and RTreeFreeNode().
Referenced by RTreeDestroyNode(), and RTreeDestroyTree().
void RTreeDestroyTree | ( | struct RTree * | t | ) |
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 222 of file vector/rtree/index.c.
References RTree::_recycle::alloc, assert, RTree_Node::branch, RTree::BranchBuf, RTree::c, RTree::center_n, RTree_PartitionVars::cover, RTree::fd, free(), RTree::free_nodes, RTree::leafcard, RTree_Node::level, MAXCARD, MAXLEVEL, NodeBuffer::n, RTree::nb, NODE_BUFFER_SIZE, RTree::nodecard, RTree::ns, RTree::orect, RTree::p, RTree::_recycle::pos, RTree_Branch::rect, RTree::root, RTreeDestroyNode(), RTreeFreeBoundary(), and RTree::used.
Referenced by dig_spidx_free(), and Vect_spatial_index_destroy().
void RTreeFlushBuffer | ( | struct RTree * | ) |
Definition at line 230 of file io.c.
References NodeBuffer::dirty, NodeBuffer::n, RTree::nb, NODE_BUFFER_SIZE, NodeBuffer::pos, RTree::rootlevel, and RTreeRewriteNode().
void RTreeFreeBoundary | ( | struct RTree_Rect * | r | ) |
Delete the boundary of a rectangle.
This method deletes (free) the memory of the boundary of a rectangle and sets the boundary pointer to NULL.
r | The pointer to the rectangle to delete the boundary from. |
Definition at line 100 of file rect.c.
References assert, RTree_Rect::boundary, free(), and NULL.
Referenced by RTreeDestroyTree(), RTreeFreeListBranch(), RTreeFreeNode(), and RTreeFreeRect().
void RTreeFreeNode | ( | struct RTree_Node * | ) |
Definition at line 98 of file node.c.
References assert, RTree_Node::branch, free(), MAXCARD, RTree_Branch::rect, and RTreeFreeBoundary().
Referenced by RTreeCreateTree(), and RTreeDestroyNode().
void RTreeFreeRect | ( | struct RTree_Rect * | r | ) |
Delete a rectangle.
This method deletes (free) the allocated memory of a rectangle.
r | The pointer to the rectangle to be deleted |
Definition at line 65 of file rect.c.
References assert, free(), and RTreeFreeBoundary().
off_t RTreeGetNodePos | ( | struct RTree * | ) |
Definition at line 72 of file io.c.
References RTree::_recycle::avail, RTree::fd, RTree::free_nodes, and RTree::_recycle::pos.
void RTreeInitNode | ( | struct RTree * | , |
struct RTree_Node * | , | ||
int | |||
) |
int RTreeInsertRect | ( | struct RTree_Rect * | r, |
int | tid, | ||
struct RTree * | t | ||
) |
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 315 of file vector/rtree/index.c.
References assert, RTree_Child::id, RTree::insert_rect, and RTree::n_leafs.
Referenced by dig_spidx_add_area(), dig_spidx_add_isle(), dig_spidx_add_node(), and Vect_spatial_index_add_item().
int RTreeOverlap | ( | struct RTree_Rect * | , |
struct RTree_Rect * | , | ||
struct RTree * | |||
) |
void RTreePrintRect | ( | struct RTree_Rect * | , |
int | , | ||
struct RTree * | |||
) |
Definition at line 306 of file rect.c.
Referenced by RTreePrintNode().
size_t RTreeReadNode | ( | struct RTree_Node * | , |
off_t | , | ||
struct RTree * | |||
) |
Definition at line 95 of file io.c.
References RTree_Node::branch, RTree_Node::count, RTree::fd, RTree_Node::level, MAXCARD, and RTreeReadBranch().
Referenced by RTreeGetNode().
int RTreeSearch | ( | struct RTree * | t, |
struct RTree_Rect * | r, | ||
SearchHitCallback * | shcb, | ||
void * | cbarg | ||
) |
Search an R*-Tree.
Search in an RTree for all data retangles 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 298 of file vector/rtree/index.c.
References assert, and RTree::search_rect.
Referenced by dig_find_area_box(), dig_find_isle_box(), dig_find_node(), dig_select_areas(), dig_select_isles(), dig_select_lines(), dig_select_nodes(), and Vect_spatial_index_select().
void RTreeSetOverflow | ( | struct RTree * | t, |
char | overflow | ||
) |
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 204 of file vector/rtree/index.c.
References RTree::overflow.
void RTreeSetRect1D | ( | struct RTree_Rect * | r, |
struct RTree * | t, | ||
double | x_min, | ||
double | x_max | ||
) |
Set one dimensional coordinates of a rectangle for a given tree.
All coordinates of the rectangle will be initialized to 0 before the x coordinates are set.
r | The pointer to the rectangle |
t | The pointer to the RTree |
x_min | The lower x coordinate |
x_max | The higher x coordinate |
Definition at line 130 of file rect.c.
References RTree_Rect::boundary, RTree::ndims_alloc, and RTreeInitRect().
void RTreeSetRect2D | ( | struct RTree_Rect * | r, |
struct RTree * | t, | ||
double | x_min, | ||
double | x_max, | ||
double | y_min, | ||
double | y_max | ||
) |
Set two dimensional coordinates of a rectangle for a given tree.
All coordinates of the rectangle will be initialized to 0 before the x and y coordinates are set.
r | The pointer to the rectangle |
t | The pointer to the RTree |
x_min | The lower x coordinate |
x_max | The higher x coordinate |
y_min | The lower y coordinate |
y_max | The higher y coordinate |
Definition at line 151 of file rect.c.
References RTree_Rect::boundary, RTree::ndims_alloc, and RTreeInitRect().
void RTreeSetRect3D | ( | struct RTree_Rect * | r, |
struct RTree * | t, | ||
double | x_min, | ||
double | x_max, | ||
double | y_min, | ||
double | y_max, | ||
double | z_min, | ||
double | z_max | ||
) |
Set three dimensional coordinates of a rectangle for a given tree.
All coordinates of the rectangle will be initialized to 0 before the x,y and z coordinates are set.
r | The pointer to the rectangle |
t | The pointer to the RTree |
x_min | The lower x coordinate |
x_max | The higher x coordinate |
y_min | The lower y coordinate |
y_max | The higher y coordinate |
z_min | The lower z coordinate |
z_max | The higher z coordinate |
Definition at line 176 of file rect.c.
References RTree_Rect::boundary, RTree::ndims_alloc, and RTreeInitRect().
void RTreeSetRect4D | ( | struct RTree_Rect * | r, |
struct RTree * | t, | ||
double | x_min, | ||
double | x_max, | ||
double | y_min, | ||
double | y_max, | ||
double | z_min, | ||
double | z_max, | ||
double | t_min, | ||
double | t_max | ||
) |
Set 4 dimensional coordinates of a rectangle for a given tree.
All coordinates of the rectangle will be initialized to 0 before the x,y,z and t coordinates are set.
r | The pointer to the rectangle |
t | The pointer to the RTree |
x_min | The lower x coordinate |
x_max | The higher x coordinate |
y_min | The lower y coordinate |
y_max | The higher y coordinate |
z_min | The lower z coordinate |
z_max | The higher z coordinate |
t_min | The lower t coordinate |
t_max | The higher t coordinate |
Definition at line 206 of file rect.c.
References assert, RTree_Rect::boundary, RTree::ndims, RTree::ndims_alloc, and RTreeInitRect().
size_t RTreeWriteNode | ( | struct RTree_Node * | , |
struct RTree * | |||
) |
Definition at line 169 of file io.c.
References RTree_Node::branch, RTree_Node::count, RTree::fd, G_fatal_error(), RTree_Node::level, MAXCARD, and RTreeWriteBranch().
Referenced by RTreeCreateTree(), and RTreeRewriteNode().