temporal_rtree.c File Reference

In-memory RTree index for MEOS bounding boxes, i.e., for Span, TBox, and STBox. More...

#include <stdlib.h>
#include <math.h>
#include <meos.h>
#include <meos_geo.h>
#include <meos_internal.h>
#include <meos_internal_geo.h>
#include "temporal/temporal.h"
#include "temporal/temporal_rtree.h"

Functions
static void	add_answer (const int id, int **ids, int *count)
	Adds an ID to the dynamically allocated array with the answer of a query. More...
static bool	bbox_contains_span (const void *box1, const void *box2)
	Return true if the first span contains the second one, false otherwise. More...
static bool	bbox_contains_stbox (const void *box1, const void *box2)
	Return true if the first spatiotemporal box contains the second one, false otherwise. More...
static bool	bbox_contains_tbox (const void *box1, const void *box2)
	Return true if the first temporal box contains the second one, false otherwise. More...
static void	bbox_expand_span (const void *box1, void *box2)
	Expand the second span with the first one. More...
static void	bbox_expand_stbox (const void *box1, void *box2)
	Expand the second spatiotemporal box with the first one. More...
static void	bbox_expand_tbox (const void *box1, void *box2)
	Expand the second temporal box with the first one. More...
static bool	bbox_overlaps_span (const void *box1, const void *box2)
	Return true if the two spans overlap, false otherwise. More...
static bool	bbox_overlaps_stbox (const void *box1, const void *box2)
	Return true if the two spatiotemporal boxes overlap, false otherwise. More...
static bool	bbox_overlaps_tbox (const void *box1, const void *box2)
	Return true if the two temporal boxes overlap, false otherwise. More...
static double	box_area (const RTree *rtree, const void *box)
	Return the length, area, or volume of a bounding box. More...
static int	box_largest_axis (const RTree *rtree, const void *box)
	Return the axis with the largest length in a bounding box. More...
static double	get_axis_length (const RTree *rtree, const void *box, int axis)
	Return the length of a bounding box along a given axis as a double. More...
static double	get_axis_span (const void *box, int axis UNUSED, bool upper)
	Return the lower or upper bound from a span as a double. More...
static double	get_axis_stbox (const void *box, int axis, bool upper)
	Return the lower or upper bound of a given axis from a spatiotemporal box as a double. More...
static double	get_axis_tbox (const void *box, int axis, bool upper)
	Return the lower or upper bound of a given axis from a temporal box as a double. More...
static bool	is_power_of_two (const int n)
	Returns true if a number greater than 0 is a power of two, false otherwise. More...
static void	node_box_calculate (const RTree *rtree, const RTreeNode *node, void *box)
	Return the bounding box that encloses all bounding boxes in an RTree node. More...
static int	node_choose (const RTree *rtree, const void *box, const RTreeNode *node)
	Returns the best child node for inserting a new bounding box in an RTree. More...
static int	node_choose_least_enlargement (const RTree *rtree, const RTreeNode *node, const void *box)
	Return the child node that requires the least enlargement to accommodate a new bounding box. More...
static void	node_free (RTreeNode *node)
	Frees the memory allocated for an RTree node. More...
static void	node_insert (RTree *rtree, void *node_bounding_box, RTreeNode *node, void *new_box, int id, bool *split)
	Inserts a new bounding box into an RTree node and handles node splitting if necessary. More...
static RTreeNode *	node_make (RTreeNodeType node_type, size_t bboxsize)
	Creates a new RTree node. More...
static void	node_move_box_at_index_into (RTreeNode *from, int index, RTreeNode *into)
	Moves a bounding box from one RTree node to another. More...
static void	node_qsort (const RTree *rtree, RTreeNode *node, int index, bool upper, int s, int e)
	Sort the bounding boxes within an RTree node using the QuickSort algorithm. More...
void	node_search (const RTree *rtree, const RTreeNode *node, const void *query, int **ids, int *count)
	Searches recursively a node looking for hits with a query. More...
static void	node_sort_axis (const RTree *rtree, RTreeNode *node, int index, bool upper)
	Sort the bounding boxes in an RTree node along a given axis using QuickSort. More...
static void	node_split (RTree *rtree, RTreeNode *node, void *box, RTreeNode **right_out)
	Splits an RTree node and redistributes its bounding boxes between two nodes. More...
static void	node_swap (const RTree *rtree, RTreeNode *node, int i, int j)
	Swaps two bounding boxes and their associated data within an RTree node. More...
RTree *	rtree_create (meosType bboxtype)
	Creates an RTree index. More...
RTree *	rtree_create_bigintspan ()
	Creates an RTree index for big integer spans. More...
RTree *	rtree_create_datespan ()
	Creates an RTree index for temporal boxes. More...
RTree *	rtree_create_floatspan ()
	Creates an RTree index for float spans. More...
RTree *	rtree_create_intspan ()
	Creates an RTree index for integer spans. More...
RTree *	rtree_create_stbox ()
	Creates an RTree index for spatiotemporal boxes. More...
RTree *	rtree_create_tbox ()
	Creates an RTree index for temporal boxes. More...
RTree *	rtree_create_tstzspan ()
	Creates an RTree index for temporal boxes. More...
void	rtree_free (RTree *rtree)
	Frees an RTree. More...
void	rtree_insert (RTree *rtree, void *box, int64 id)
	Insert a bounding box into the RTree index. More...
int *	rtree_search (const RTree *rtree, const void *query, int *count)
	Queries an RTree with a bounding box. More...
static double	unioned_area (const RTree *rtree, const void *box1, const void *box2)
	Return the length, area, or volume of the union of two bounding boxes. More...

Detailed Description

In-memory RTree index for MEOS bounding boxes, i.e., for Span, TBox, and STBox.