GRASS GIS 7 Programmer's Manual  7.5.svn(2017)-r71769
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
vector/rtree/index.c File Reference

R-Tree library - Multidimensional index. More...

#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <assert.h>
#include <grass/gis.h>
#include "index.h"
Include dependency graph for vector/rtree/index.c:

Go to the source code of this file.

Functions

struct RTreeRTreeCreateTree (int fd, off_t rootpos, int ndims)
 Create new empty R*-Tree. More...
 
void RTreeSetOverflow (struct RTree *t, char overflow)
 Enable/disable R*-tree forced reinsertion (overflow) More...
 
void RTreeDestroyTree (struct RTree *t)
 Destroy an R*-Tree. More...
 
int RTreeSearch (struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
 Search an R*-Tree. More...
 
int RTreeInsertRect (struct RTree_Rect *r, int tid, struct RTree *t)
 Insert an item into a R*-Tree. More...
 
int RTreeDeleteRect (struct RTree_Rect *r, int tid, struct RTree *t)
 Delete an item from a R*-Tree. More...
 
struct RTree_ListNodeRTreeNewListNode (void)
 
void RTreeFreeListNode (struct RTree_ListNode *p)
 
void RTreeReInsertNode (struct RTree_Node *n, struct RTree_ListNode **ee)
 
void RTreeFreeListBranch (struct RTree_ListBranch *p)
 

Detailed Description

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.

Author
Antonin Guttman - original code
Daniel Green (green.nosp@m.@sup.nosp@m.erlim.nosp@m.inal.nosp@m..com) - major clean-up and implementation of bounding spheres
Markus Metz - file-based and memory-based R*-tree

Definition in file vector/rtree/index.c.

Function Documentation

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 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 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, 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 RTreeFreeListBranch ( struct RTree_ListBranch p)
void RTreeFreeListNode ( struct RTree_ListNode p)

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

References free().

Referenced by RTreeDeleteRectF(), and RTreeDeleteRectM().

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 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().

struct RTree_ListNode* RTreeNewListNode ( void  )

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

References malloc().

Referenced by RTreeReInsertNode().

void RTreeReInsertNode ( struct RTree_Node n,
struct RTree_ListNode **  ee 
)
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 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().