RTree Module

Module contents

template<typename value_type, typename rtree_algorithm_type = bgi::quadratic<16>>
class RTree

This is a wrapper for the Boost rtree implementation in boost::geometry::index.

Its purpose is to insulate you, the user, from having to care about all the complexity (and power) involved in boost::geometry::index::rtree. You supply a value type (which can be a point, a pair or a tuple) and we do the rest.

The disadvantage is that you’re restricted from using some of the more powerful query capabilities, including user-defined predicates and query combination.

Quick Start:

typedef tracktable::RTree<my_point_type> rtree_type;

rtree_type my_tree;

for (int i = 0; i < my_points.size(); ++i) my_tree.insert(my_points[i]);

std::vector<my_point_type> results;

my_tree.find_points_inside_box(min_corner, max_corner, std::back_inserter(results));

(your results vector now contains all the points inside the box)

You can populate this R-tree with any point type known to Tracktable / boost::geometry. This includes base_point_type and trajectory_point_type from all the domains as well as any other point that you have registered with boost::geometry.

You can also populate the R-tree with std::pair<>s and boost::tuple<>s where the first element of the pair / tuple is one of the point types listed above. Note that when you query the r-tree, only the geometry will be used in the query: the auxiliary information is preserved but never compared.

When querying the r-tree, you must use the same geometric point type that you used to populate it. Like the values stored in the tree, you can specify the search point(s) as a point type, a std::pair<> or a boost::tuple<> whose first element is the geometry. This is just for convenience: the only part that will be used for the search is the geometry.

You may only modify the contents of the R-tree with insert(), remove() and clear(). There is no way to get a reference to an internal element and modify it directly as you can do with std::vector, std::map and friends. Doing so would break the search structure.

Public Types

typedef bgi::rtree<value_type, rtree_algorithm_type> rtree_type

typedef rtree_type::const_query_iterator query_result_iterator_type

typedef std::pair<query_result_iterator_type, query_result_iterator_type> query_result_range_type

typedef rtree_type::size_type size_type

Public Functions

RTree()

~RTree()

RTree(RTree const &other)

RTree &operator=(RTree const &other)

bool operator==(RTree const &other) const

bool operator!=(RTree const &other) const

template<typename value_iterator_type>
RTree(value_iterator_type range_begin, value_iterator_type range_end)

Create and populate an RTree from a range of elements.

If you have a container of points you can use this constructor to create and populate the tree in one swell foop instead of adding elements one at a time.

Parameters

• [in] range_begin: Iterator pointing to beginning of input points

• [in] range_end: Iterator pointing past end of input points

void insert(value_type const &value)

Insert a single element into an RTree.

Parameters

• [in] value: Element to insert (will be copied)

size_type remove(value_type const &value)

Remove a single element from the RTree.

Return

1 if the element was removed, 0 otherwise

Parameters

• [in] value: Element to remove

template<typename value_iterator_type>
size_type remove(value_iterator_type range_begin, value_iterator_type range_end)

Remove many elements from the RTree.

Return

Number of removed values

Parameters

• [in] range_begin: First element to remove

• [in] range_end: Past last element to remove

std::size_t size() const

Return number of elements in RTree.

Return

Non-negative integer (number of elements)

bool empty() const

Check whether an rtree is empty.

Return

Boolean explaining whether or not size() == 0

void clear()

Empty out an rtree.

This function will completely reset an rtree to its un-populated state.

template<typename corner_type, typename insert_iter_type>
void find_points_inside_box(corner_type const &min_corner, corner_type const &max_corner, insert_iter_type result_sink) const

Find points inside a search box (output sink version)

This function finds points inside a box specified as two corners. You must provide an InsertIterator as the third argument. This iterator will be used to save the results. For example:

my_point min_corner, max_corner; std::vector<my_point> results;

my_tree.find_points_inside_box(min_corner, max_corner, std::back_inserter(results));

Note that this function will return points that are exactly on the boundary of the search box as well as those in the interior. If you want only the points in the interior, use ‘find_points_strictly_inside_box’.

As with all the other RTree functions, you can use a point type, a std::pair<point_type, X> or a boost::tuple<point, type, [other stuff]> for your searches. In the case of a std::pair or boost::tuple, your geometry type must be the first element.

Parameters

• [in] min_corner: Corner at minimum end of search box

• [in] max_corner: Corner at maximum end of search box

• [in] result_sink: InsertIterator where results will be stored

template<typename corner_type, typename T2, typename insert_iter_type>
void find_points_inside_box(std::pair<corner_type, T2> const &min_corner, std::pair<corner_type, T2> const &max_corner, insert_iter_type result_sink) const

template<typename corner_type, typename insert_iter_type, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9>
void find_points_inside_box(boost::tuple<corner_type, T2, T3, T4, T5, T6, T7, T8, T9> const &min_corner, boost::tuple<corner_type, T2, T3, T4, T5, T6, T7, T8, T9> const &max_corner, insert_iter_type result_sink) const

template<typename corner_type>
query_result_range_type find_points_inside_box(corner_type const &min_corner, corner_type const &max_corner) const

Find points inside a search box (iterator range version)

This function finds points inside a box specified as a tracktable::Box (also known as a tracktable::RTree<point_type>::box_type).

typedef typename tracktable::RTree<my_point>::query_result_range_type query_result_type; my_point min_corner, max_corner;

query_result_type result_range = my_tree.find_points_inside_box(min_corner, max_corner);

std::vector<my_point> results(result_range.first, result_range.second);

Note that this function will return points that are exactly on the boundary of the search box as well as those in the interior. If you want only the points in the interior, use ‘find_points_strictly_inside_box’.

As with all the other RTree functions, you can use a point type, a std::pair<point_type, X> or a boost::tuple<point, type, [other stuff]> for your searches. In the case of a std::pair or boost::tuple, your geometry type must be the first element.

** Warning **: This function is sensitive to numerical imprecision issues when points are (allegedly) right on the border of the search box. This is especially problematic in the terrestrial domain (longitude/latitude points) since we have to do trigonometry to compute point-in-polygon results.

Return

Pair of iterators pointing to query result range

Parameters

• [in] min_corner: Corner at minimum end of search box

• [in] max_corner: Corner at maximum end of search box

template<typename corner_type, typename T2>
query_result_range_type find_points_inside_box(std::pair<corner_type, T2> const &min_corner, std::pair<corner_type, T2> const &max_corner) const

template<typename corner_type, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9, typename T10>
query_result_range_type find_points_inside_box(boost::tuple<corner_type, T2, T3, T4, T5, T6, T7, T8, T9, T10> const &min_corner, boost::tuple<corner_type, T2, T3, T4, T5, T6, T7, T8, T9, T10> const &max_corner)

template<typename corner_type, typename insert_iter_type>
void find_points_strictly_inside_box(corner_type const &min_corner, corner_type const &max_corner, insert_iter_type result_sink) const

Find points strictly inside a search box.

This function finds points inside a box specified as two corners. You must provide an InsertIterator as the third argument. This iterator will be used to save the results. For example:

my_point min_corner, max_corner; std::vector<my_point> results;

my_tree.find_points_strictly_inside_box(min_corner, max_corner, std::back_inserter(results));

Note that this function will return points that are strictly within the box. Points on the border will not be returned. If you want points on the border, use ‘find_points_inside_box’.

As with all the other RTree functions, you can use a point type, a std::pair<point_type, X> or a boost::tuple<point, type, [other stuff]> for your searches. In the case of a std::pair or boost::tuple, your geometry type must be the first element.

Parameters

• [in] min_corner: Corner at minimum end of search box

• [in] max_corner: Corner at maximum end of search box

• [in] result_sink: InsertIterator where results will be stored

template<typename corner_type, typename T2, typename insert_iter_type>
void find_points_strictly_inside_box(std::pair<corner_type, T2> const &min_corner, std::pair<corner_type, T2> const &max_corner, insert_iter_type result_sink) const

template<typename corner_type, typename insert_iter_type, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9, typename T10>
void find_points_strictly_inside_box(boost::tuple<corner_type, T2, T3, T4, T5, T6, T7, T8, T9, T10> const &min_corner, boost::tuple<corner_type, T2, T3, T4, T5, T6, T7, T8, T9, T10> const &max_corner, insert_iter_type result_sink) const

template<typename corner_type>
query_result_range_type find_points_strictly_inside_box(corner_type const &min_corner, corner_type const &max_corner) const

Find points inside a search box (iterator range version)

This function finds points inside a box specified as a tracktable::Box (also known as a tracktable::RTree<point_type>::box_type).

typedef typename tracktable::RTree<my_point>::query_result_range_type query_result_type; my_point min_corner, max_corner;

query_result_type result_range = my_tree.find_points_strictly_inside_box(min_corner, max_corner);

std::vector<my_point> results(result_range.first, result_range.second);

Note that this function will return points that are strictly within the box. Points on the border will not be returned. If you want points on the border, use ‘find_points_inside_box’.

As with all the other RTree functions, you can use a point type, a std::pair<point_type, X> or a boost::tuple<point, type, [other stuff]> for your searches. In the case of a std::pair or boost::tuple, your geometry type must be the first element.

Return

Pair of iterators pointing to query result range

Parameters

• [in] min_corner: Corner at minimum end of search box

• [in] max_corner: Corner at maximum end of search box

template<typename corner_type, typename T2>
query_result_range_type find_points_strictly_inside_box(std::pair<corner_type, T2> const &min_corner, std::pair<corner_type, T2> const &max_corner) const

template<typename corner_type, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9, typename T10>
query_result_range_type find_points_strictly_inside_box(boost::tuple<corner_type, T2, T3, T4, T5, T6, T7, T8, T9, T10> const &min_corner, boost::tuple<corner_type, T2, T3, T4, T5, T6, T7, T8, T9, T10> const &max_corner)

template<typename search_point_type, typename insert_iter_type>
void find_nearest_neighbors(search_point_type const &search_point, unsigned int num_neighbors, insert_iter_type result_sink) const

Find points near a search point (output iterator version)

This function finds the K nearest neighbors to a search point. Note that if the search point is already present in the R-tree then it will be one of the results returned.

You must provide an output iterator as a place to store the results. For example:

tracktable::RTree<my_point> tree; my_point search_point; std::vector<my_point> neighbors;

tree.find_nearest_neighbors(search_point, 10, std::back_inserter(neighbors));

Parameters

• [in] search_point: Point whose neighbors you want to find

• [in] num_neighbors: How many neighbors to find

• [in] result_sink: Where to write the results

template<typename search_point_type, typename T2, typename insert_iter_type>
void find_nearest_neighbors(std::pair<search_point_type, T2> const &search_point, unsigned int num_neighbors, insert_iter_type result_sink) const

template<typename search_point_type, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9, typename T10, typename insert_iter_type>
void find_nearest_neighbors(boost::tuple<search_point_type, T2, T3, T4, T5, T6, T7, T8, T9, T10> const &search_point, unsigned int num_neighbors, insert_iter_type result_sink) const

template<typename search_point_type>
query_result_range_type find_nearest_neighbors(search_point_type const &search_point, unsigned int num_neighbors) const

Find points near a search point (iterator range version)

This function finds the K nearest neighbors to a search point. Note that if the search point is already present in the R-tree then it will be one of the results returned.

The result is returned as a pair of iterators. For example:

typedef typename tracktable::RTree<my_point>::query_result_range_type query_result_type; tracktable::RTree<my_point> tree; my_point search_point; std::vector<my_point> neighbors;

query_result_type result_range = my_tree.find_nearest_neighbors(search_point, 10);

neighbors.assign(result_range.first, result_range.second);

Return

Pair of iterators pointing to neighboring points

Parameters

• [in] search_point: Point whose neighbors you want to find

• [in] num_neighbors: How many neighbors to find

template<typename search_point_type, typename T2>
query_result_range_type find_nearest_neighbors(std::pair<search_point_type, T2> const &search_point, unsigned int num_neighbors) const

template<typename search_point_type, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9, typename T10>
query_result_range_type find_nearest_neighbors(boost::tuple<search_point_type, T2, T3, T4, T5, T6, T7, T8, T9, T10> const &search_point, unsigned int num_neighbors)

Private Functions

template<typename box_type, typename insert_iter_type>
void _find_points_inside_box(box_type const &search_box, insert_iter_type result_sink) const

template<typename box_type>
query_result_range_type _find_points_inside_box(box_type const &search_box) const

template<typename box_type, typename insert_iter_type>
void _find_points_strictly_inside_box(box_type const &search_box, insert_iter_type output_sink) const

template<typename box_type>
query_result_range_type _find_points_strictly_inside_box(box_type const &search_box) const

template<typename search_point_type, typename insert_iter_type>
void _find_nearest_neighbors(search_point_type const &search_point, unsigned int num_neighbors, insert_iter_type output_sink) const

template<typename search_point_type>
query_result_range_type _find_nearest_neighbors(search_point_type const &search_point, unsigned int num_neighbors) const

template<typename iterator_range_type, typename output_iterator_type>
void _copy_range_to_output(iterator_range_type range, output_iterator_type output_sink) const

Private Members

rtree_type _RTree