#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:

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.

int	RTreeInsertRect (struct RTree_Rect , int, struct RTree )
	Insert an item into a R*-Tree.

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.

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.

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.

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.

int	RTreeDeleteRect (struct RTree_Rect , int, struct RTree )
	Delete an item from a R*-Tree.

void	RTreePrintRect (struct RTree_Rect , int, struct RTree )

struct RTree *	RTreeCreateTree (int, off_t, int)
	Create new empty R*-Tree.

void	RTreeSetOverflow (struct RTree *, char)
	Enable/disable R*-tree forced reinsertion (overflow)

void	RTreeDestroyTree (struct RTree *)
	Destroy an R*-Tree.

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.

void	RTreeFreeRect (struct RTree_Rect *r)
	Delete a rectangle.

RectReal *	RTreeAllocBoundary (struct RTree *t)
	Allocate the boundary array of a rectangle for a given tree.

void	RTreeFreeBoundary (struct RTree_Rect *r)
	Delete the boundary of a rectangle.

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

◆ FALSE

#define FALSE 0

Definition at line 36 of file rtree.h.

◆ LEAFCARD

#define LEAFCARD MAXCARD

Definition at line 46 of file rtree.h.

◆ MAXCARD

#define MAXCARD 9

Definition at line 44 of file rtree.h.

◆ MAXLEVEL

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

Definition at line 49 of file rtree.h.

◆ NODE_BUFFER_SIZE

#define NODE_BUFFER_SIZE 32

Definition at line 52 of file rtree.h.

◆ NODECARD

#define NODECARD MAXCARD

Definition at line 45 of file rtree.h.

◆ TRUE

#define TRUE 1

Definition at line 33 of file rtree.h.

Typedef Documentation

◆ RectReal

typedef double RectReal

Definition at line 26 of file rtree.h.

◆ rt_delete_fn

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

Definition at line 94 of file rtree.h.

◆ rt_insert_fn

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

Definition at line 92 of file rtree.h.

◆ rt_search_fn

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

Definition at line 90 of file rtree.h.

◆ rt_valid_child_fn

typedef int rt_valid_child_fn(union RTree_Child *)

Definition at line 96 of file rtree.h.

◆ SearchHitCallback

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

Definition at line 86 of file rtree.h.

Function Documentation

◆ RTreeAllocBoundary()

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

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 81 of file rect.c.

References assert, RTree_Rect::boundary, malloc(), and t.

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

◆ RTreeAllocNode()

struct RTree_Node * RTreeAllocNode	(	struct RTree *	t,
		int	level
	)

Definition at line 74 of file node.c.

References assert, RTree_Node::branch, RTree_Node::count, RTree_Node::level, malloc(), MAXCARD, NODETYPE, RTreeAllocBoundary(), and t.

Referenced by RTreeAddBranch(), RTreeCreateTree(), RTreeInsertRectF(), and RTreeInsertRectM().

◆ RTreeAllocRect()

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

t	The pointer to a RTree struct

Returns: A new allocated RTree_Rect struct

Definition at line 42 of file rect.c.

References assert, malloc(), r, RTreeAllocBoundary(), and t.

◆ RTreeContained()

int RTreeContained	(	struct RTree_Rect *	r,
		struct RTree_Rect *	s,
		struct RTree *	t
	)

Definition at line 609 of file rect.c.

References RTree_Rect::boundary, FALSE, r, t, TRUE, and Undefined.

◆ RTreeContains()

int RTreeContains	(	struct RTree_Rect *	r,
		struct RTree_Rect *	s,
		struct RTree *	t
	)

Definition at line 634 of file rect.c.

References RTree_Rect::boundary, FALSE, r, t, TRUE, and Undefined.

◆ RTreeCopyNode()

void RTreeCopyNode	(	struct RTree_Node *	n1,
		struct RTree_Node *	n2,
		struct RTree *	t
	)

Definition at line 109 of file node.c.

References assert, RTree_Node::branch, RTree_Node::count, RTree_Node::level, MAXCARD, RTreeCopyBranch(), and t.

◆ RTreeCreateTree()

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

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

Returns: pointer to new RTree structure

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

◆ RTreeDeleteRect()

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

r	pointer to rectangle to use for searching
tid	id of the data to be deleted, must be > 0
t	pointer to RTree structure

Returns: 0 on success; 1 if data item not found

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

◆ RTreeDestroyNode()

void RTreeDestroyNode	(	struct RTree_Node *	n,
		int	nodes
	)

Definition at line 290 of file node.c.

References RTree_Node::branch, RTree_Node::level, RTreeDestroyNode(), and RTreeFreeNode().

Referenced by RTreeDestroyNode(), and RTreeDestroyTree().

◆ 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.

Parameters

t	pointer to RTree structure

Returns: nothing

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

◆ RTreeFlushBuffer()

void RTreeFlushBuffer ( struct RTree * t )

Definition at line 244 of file io.c.

References NODE_BUFFER_SIZE, RTreeRewriteNode(), and t.

Referenced by dig_dump_spidx().

◆ RTreeFreeBoundary()

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

r	The pointer to the rectangle to delete the boundary from.

Definition at line 98 of file rect.c.

References assert, free(), NULL, and r.

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

◆ RTreeFreeNode()

void RTreeFreeNode ( struct RTree_Node * n )

Definition at line 95 of file node.c.

References assert, RTree_Node::branch, free(), MAXCARD, and RTreeFreeBoundary().

Referenced by RTreeCreateTree(), RTreeDeleteRectF(), RTreeDeleteRectM(), and RTreeDestroyNode().

◆ RTreeFreeRect()

void RTreeFreeRect ( struct RTree_Rect * r )

Delete a rectangle.

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

Parameters

r	The pointer to the rectangle to be deleted

Definition at line 63 of file rect.c.

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

◆ RTreeGetNodePos()

off_t RTreeGetNodePos ( struct RTree * t )

Definition at line 74 of file io.c.

References t.

Referenced by RTreeInsertRectF().

◆ RTreeInitNode()

void RTreeInitNode	(	struct RTree *	t,
		struct RTree_Node *	n,
		int	type
	)

Definition at line 62 of file node.c.

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

Referenced by RTreeAddBranch(), and RTreeInsertRectF().

◆ RTreeInsertRect()

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

Insert an item into a R*-Tree.

Parameters

r	pointer to rectangle to use for searching
tid	data id stored with rectangle, must be > 0
t	pointer to RTree structure

Returns: number of qualifying data rectangles

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

References assert, r, and t.

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

◆ RTreeOverlap()

int RTreeOverlap	(	struct RTree_Rect *	r,
		struct RTree_Rect *	s,
		struct RTree *	t
	)

Definition at line 590 of file rect.c.

References RTree_Rect::boundary, FALSE, r, t, and TRUE.

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

◆ RTreePrintRect()

void RTreePrintRect	(	struct RTree_Rect *	R,
		int	depth,
		struct RTree *	t
	)

Definition at line 304 of file rect.c.

References assert, r, RTreeTabIn(), and t.

Referenced by RTreePrintNode().

◆ RTreeReadNode()

size_t RTreeReadNode	(	struct RTree_Node *	n,
		off_t	nodepos,
		struct RTree *	t
	)

Definition at line 97 of file io.c.

References _, RTree_Node::branch, RTree_Node::count, err(), G_fatal_error(), RTree_Node::level, MAXCARD, read, RTreeReadBranch(), and t.

Referenced by RTreeGetNode().

◆ RTreeSearch()

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.

Parameters

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

Returns: number of qualifying data rectangles

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

References assert, r, and t.

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

◆ RTreeSetOverflow()

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

t	pointer to RTree structure
overflow	binary flag

Returns: nothing

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

References t.

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

◆ RTreeSetRect1D()

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

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 128 of file rect.c.

References r, RTreeInitRect(), and t.

◆ RTreeSetRect2D()

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

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 149 of file rect.c.

References r, RTreeInitRect(), and t.

◆ RTreeSetRect3D()

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

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 174 of file rect.c.

References r, RTreeInitRect(), and t.

◆ RTreeSetRect4D()

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

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 204 of file rect.c.

References assert, r, RTreeInitRect(), and t.

◆ RTreeWriteNode()

size_t RTreeWriteNode	(	struct RTree_Node *	n,
		struct RTree *	t
	)

Definition at line 177 of file io.c.

References RTree_Node::branch, RTree_Node::count, G_fatal_error(), RTree_Node::level, MAXCARD, RTreeWriteBranch(), t, and write.

Referenced by RTreeCreateTree(), RTreeInsertRectF(), and RTreeRewriteNode().

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ FALSE

◆ LEAFCARD

◆ MAXCARD

◆ MAXLEVEL

◆ NODE_BUFFER_SIZE

◆ NODECARD

◆ TRUE

Typedef Documentation

◆ RectReal

◆ rt_delete_fn

◆ rt_insert_fn

◆ rt_search_fn

◆ rt_valid_child_fn

◆ SearchHitCallback

Function Documentation

◆ RTreeAllocBoundary()

◆ RTreeAllocNode()

◆ RTreeAllocRect()

◆ RTreeContained()

◆ RTreeContains()

◆ RTreeCopyNode()

◆ RTreeCreateTree()

◆ RTreeDeleteRect()

◆ RTreeDestroyNode()

◆ RTreeDestroyTree()

◆ RTreeFlushBuffer()

◆ RTreeFreeBoundary()

◆ RTreeFreeNode()

◆ RTreeFreeRect()

◆ RTreeGetNodePos()

◆ RTreeInitNode()

◆ RTreeInsertRect()

◆ RTreeOverlap()

◆ RTreePrintRect()

◆ RTreeReadNode()

◆ RTreeSearch()

◆ RTreeSetOverflow()

◆ RTreeSetRect1D()

◆ RTreeSetRect2D()

◆ RTreeSetRect3D()

◆ RTreeSetRect4D()

◆ RTreeWriteNode()