GRASS GIS 7 Programmer's Manual  7.5.svn(2018)-r72846
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
rtree.h File Reference
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <grass/config.h>
Include dependency graph for rtree.h:
This graph shows which files directly or indirectly include this file:

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 RTreeRTreeCreateTree (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_NodeRTreeAllocNode (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_RectRTreeAllocRect (struct RTree *t)
 Create a new rectangle for a given tree. More...
 
void RTreeFreeRect (struct RTree_Rect *r)
 Delete a rectangle. More...
 
RectRealRTreeAllocBoundary (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 *)
 

Macro Definition Documentation

#define FALSE   0

Definition at line 38 of file rtree.h.

#define LEAFCARD   MAXCARD

Definition at line 48 of file rtree.h.

#define MAXLEVEL   20 /* 8^MAXLEVEL items are guaranteed to fit into the tree */

Definition at line 52 of file rtree.h.

#define NODE_BUFFER_SIZE   32
#define NODECARD   MAXCARD

Definition at line 47 of file rtree.h.

#define TRUE   1

Definition at line 35 of file rtree.h.

Typedef Documentation

typedef double RectReal

Definition at line 28 of file rtree.h.

typedef int rt_delete_fn(struct RTree_Rect *, union RTree_Child, struct RTree *)

Definition at line 98 of file rtree.h.

typedef int rt_insert_fn(struct RTree_Rect *, union RTree_Child, int, struct RTree *)

Definition at line 97 of file rtree.h.

typedef int rt_search_fn(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)

Definition at line 95 of file rtree.h.

typedef int rt_valid_child_fn(union RTree_Child *)

Definition at line 99 of file rtree.h.

typedef int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg)

Definition at line 91 of file rtree.h.

Function Documentation

RectReal* RTreeAllocBoundary ( struct RTree t)

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.

Parameters
rThe pointer to rectangle to initialize the boundary coordinates. This is usually a rectangle that was created on the stack or self allocated.
tThe pointer to a RTree struct

Definition at line 84 of file rect.c.

References assert, RTree_Rect::boundary, malloc(), and RTree::rectsize.

Referenced by RTreeAllocNode(), RTreeAllocRect(), and RTreeCreateTree().

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.

Parameters
tThe pointer to a RTree struct
Returns
A new allocated RTree_Rect struct

Definition at line 45 of file rect.c.

References assert, RTree_Rect::boundary, malloc(), r, and RTreeAllocBoundary().

int RTreeContained ( struct RTree_Rect ,
struct RTree_Rect ,
struct RTree  
)

Definition at line 617 of file rect.c.

References RTree_Rect::boundary, FALSE, RTree::ndims, RTree::ndims_alloc, TRUE, and Undefined.

int RTreeContains ( struct RTree_Rect ,
struct RTree_Rect ,
struct RTree  
)

Definition at line 644 of file rect.c.

References RTree_Rect::boundary, FALSE, RTree::ndims, RTree::ndims_alloc, TRUE, and Undefined.

void RTreeCopyNode ( struct RTree_Node ,
struct RTree_Node ,
struct RTree  
)
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.

Parameters
fdfile descriptor to hold data, negative toggles memory mode
rootposoffset in file to root node (past any header info)
ndimsnumber of dimensions for the new tree: min 2, max 20
Returns
pointer to new RTree structure

Definition at line 61 of file vector/rtree/index.c.

References RTree::_recycle::alloc, RTree::_recycle::avail, RTree_Rect::boundary, RTree_Node::branch, RTree::BranchBuf, RTree::branchsize, RTree::c, RTree::center_n, RTree_PartitionVars::cover, RTree::delete_rect, NodeBuffer::dirty, fd, RTree::fd, RTree::free_nodes, RTree::insert_rect, RTree::leafcard, RTree_Node::level, malloc(), MAXCARD, MAXLEVEL, RTree::min_leaf_fill, RTree::min_node_fill, RTree::minfill_leaf_split, RTree::minfill_node_split, NodeBuffer::n, RTree::n_leafs, RTree::n_nodes, RTree::nb, RTree::ndims, RTree::ndims_alloc, NODE_BUFFER_SIZE, RTree::nodecard, RTree::nodesize, RTree::ns, RTree::nsides, RTree::nsides_alloc, NULL, RTree::orect, RTree::overflow, RTree::p, NodeBuffer::pos, RTree::_recycle::pos, RTree_Branch::rect, RTree::rectsize, RTree::root, RTree::rootlevel, RTree::rootpos, RTreeAllocBoundary(), RTreeAllocNode(), RTreeDeleteRectF(), RTreeDeleteRectM(), RTreeFreeNode(), RTreeInsertRectF(), RTreeInsertRectM(), RTreeSearchF(), RTreeSearchM(), RTreeValidChildF(), RTreeValidChildM(), RTreeWriteNode(), RTree::search_rect, RTree::used, and RTree::valid_child.

Referenced by dig_spidx_free_areas(), dig_spidx_free_isles(), dig_spidx_free_lines(), dig_spidx_free_nodes(), dig_spidx_init(), Vect_break_polygons_file(), Vect_line_check_intersection(), Vect_line_intersection(), Vect_snap_line(), and 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.

Parameters
rpointer to rectangle to use for searching
tidid of the data to be deleted, must be > 0
tpointer to RTree structure
Returns
0 on success
1 if data item not found

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_line(), dig_spidx_del_node(), and Vect_spatial_index_del_item().

void RTreeDestroyNode ( struct RTree_Node ,
int   
)
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.

Parameters
tpointer to RTree structure
Returns
nothing

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(), dig_spidx_free_areas(), dig_spidx_free_isles(), dig_spidx_free_lines(), dig_spidx_free_nodes(), Vect_break_polygons_file(), Vect_line_check_intersection(), Vect_line_intersection(), Vect_snap_line(), and Vect_spatial_index_destroy().

void RTreeFlushBuffer ( struct RTree )
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.

Parameters
rThe pointer to the rectangle to delete the boundary from.

Definition at line 101 of file rect.c.

References assert, RTree_Rect::boundary, free(), and NULL.

Referenced by RTreeDestroyTree(), RTreeFreeListBranch(), RTreeFreeNode(), and RTreeFreeRect().

void RTreeFreeNode ( struct RTree_Node )
void RTreeFreeRect ( struct RTree_Rect r)

Delete a rectangle.

This method deletes (free) the allocated memory of a rectangle.

Parameters
rThe pointer to the rectangle to be deleted

Definition at line 66 of file rect.c.

References assert, free(), and RTreeFreeBoundary().

off_t RTreeGetNodePos ( struct RTree )

Definition at line 70 of file io.c.

References RTree::_recycle::avail, RTree::fd, RTree::free_nodes, and RTree::_recycle::pos.

Referenced by RTreeInsertRectF().

void RTreeInitNode ( struct RTree ,
struct RTree_Node ,
int   
)

Definition at line 65 of file node.c.

References RTree_Node::branch, RTree_Node::count, RTree_Node::level, and MAXCARD.

Referenced by RTreeAddBranch(), and RTreeInsertRectF().

int RTreeInsertRect ( struct RTree_Rect r,
int  tid,
struct RTree t 
)

Insert an item into a R*-Tree.

Parameters
rpointer to rectangle to use for searching
tiddata id stored with rectangle, must be > 0
tpointer to RTree structure
Returns
number of qualifying data rectangles

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_line(), dig_spidx_add_node(), Vect_break_polygons_file(), Vect_line_check_intersection(), Vect_line_intersection(), Vect_snap_line(), and Vect_spatial_index_add_item().

int RTreeOverlap ( struct RTree_Rect ,
struct RTree_Rect ,
struct RTree  
)

Definition at line 597 of file rect.c.

References RTree_Rect::boundary, FALSE, RTree::ndims, RTree::ndims_alloc, and TRUE.

Referenced by rtree_search(), RTreeSearchF(), and RTreeSearchM().

void RTreePrintRect ( struct RTree_Rect ,
int  ,
struct RTree  
)

Definition at line 307 of file rect.c.

References assert, RTree_Rect::boundary, RTree::ndims_alloc, and RTreeTabIn().

Referenced by RTreePrintNode().

size_t RTreeReadNode ( struct RTree_Node ,
off_t  ,
struct RTree  
)

Definition at line 93 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.

Parameters
tpointer to RTree structure
rpointer to rectangle to use for searching
shcbSearch Hit CallBack function
cbargcustom pointer used as argument for the shcb fn
Returns
number of qualifying data rectangles

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_line_box(), dig_find_node(), dig_select_areas(), dig_select_isles(), dig_select_lines(), dig_select_nodes(), Vect_break_polygons_file(), Vect_line_check_intersection(), Vect_line_intersection(), Vect_snap_line(), 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.

Parameters
tpointer to RTree structure
overflowbinary flag
Returns
nothing

Definition at line 204 of file vector/rtree/index.c.

References RTree::overflow.

Referenced by Vect_line_check_intersection(), Vect_line_intersection(), and Vect_snap_line().

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.

Parameters
rThe pointer to the rectangle
tThe pointer to the RTree
x_minThe lower x coordinate
x_maxThe higher x coordinate

Definition at line 131 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.

Parameters
rThe pointer to the rectangle
tThe pointer to the RTree
x_minThe lower x coordinate
x_maxThe higher x coordinate
y_minThe lower y coordinate
y_maxThe higher y coordinate

Definition at line 152 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.

Parameters
rThe pointer to the rectangle
tThe pointer to the RTree
x_minThe lower x coordinate
x_maxThe higher x coordinate
y_minThe lower y coordinate
y_maxThe higher y coordinate
z_minThe lower z coordinate
z_maxThe higher z coordinate

Definition at line 177 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.

Parameters
rThe pointer to the rectangle
tThe pointer to the RTree
x_minThe lower x coordinate
x_maxThe higher x coordinate
y_minThe lower y coordinate
y_maxThe higher y coordinate
z_minThe lower z coordinate
z_maxThe higher z coordinate
t_minThe lower t coordinate
t_maxThe higher t coordinate

Definition at line 207 of file rect.c.

References assert, RTree_Rect::boundary, RTree::ndims, RTree::ndims_alloc, and RTreeInitRect().

size_t RTreeWriteNode ( struct RTree_Node ,
struct RTree  
)