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

inline RTree()

Instantiate an empty RTree

inline ~RTree()

Destructor.

inline RTree(RTree const &other)

Copy contructor, create an RTree with a copy of another

Parameters:

other – [in] RTree to copy from

inline RTree &operator=(RTree const &other)

Assign a RTree to the value of another.

Parameters:

other – [in] RTree to assign value of

Returns:

RTree with the new assigned value

inline bool operator==(RTree const &other) const

Check whether one RTree is equal to another.

Parameters:

other – [in] RTree for comparison

Returns:

Boolean indicating equivalency

inline bool operator!=(RTree const &other) const

Check whether two RTrees are unequal.

Parameters:

other – [in] RTree for comparison

Returns:

Boolean indicating equivalency

template<typename value_iterator_type>
inline 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:

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

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

inline void insert(value_type const &value)

Insert a single element into an RTree

Parameters:

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

template<typename value_iterator_type>
inline void insert(value_iterator_type range_begin, value_iterator_type range_end)

Insert multiple elements into an RTRee

Parameters:

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

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

inline size_type remove(value_type const &value)

Remove a single element from the RTree

Parameters:

value – [in] Element to remove

Returns:

1 if the element was removed, 0 otherwise

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

Remove many elements from the RTree

Parameters:

  • range_begin – [in] First element to remove

  • range_end – [in] Past last element to remove

Returns:

Number of removed values

inline std::size_t size() const

Return number of elements in RTree

Returns:

Non-negative integer (number of elements)

inline bool empty() const

Check whether an rtree is empty

Returns:

Boolean explaining whether or not size() == 0

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

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:

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

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

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

template<typename corner_type, typename T2, typename insert_iter_type>
inline 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

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename corner_type, typename insert_iter_type, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9>
inline 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

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename corner_type>
inline 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).

Example:

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.

Parameters:

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

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

Returns:

Pair of iterators pointing to query result range

template<typename corner_type, typename T2>
inline 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

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename corner_type, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9, typename T10>
inline 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)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename corner_type, typename insert_iter_type>
inline 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.

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:

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

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

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

template<typename corner_type, typename T2, typename insert_iter_type>
inline 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

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

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>
inline 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

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename corner_type>
inline 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).

Example:

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.

Parameters:

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

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

Returns:

Pair of iterators pointing to query result range

template<typename corner_type, typename T2>
inline 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

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename corner_type, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9, typename T10>
inline 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)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename corner_type, typename insert_iter_type>
inline void intersects(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/objects that are not disjoint from the box You must provide an InsertIterator as the third argument. This iterator will be used to save the results.

Example:

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

my_tree.intersects(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:

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

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

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

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

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename corner_type, typename insert_iter_type, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9>
inline void intersects(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

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename corner_type>
inline query_result_range_type intersects(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).

Example:

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

Parameters:

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

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

Returns:

Pair of iterators pointing to query result range

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

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename corner_type, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9, typename T10>
inline query_result_range_type intersects(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)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename search_point_type, typename insert_iter_type>
inline 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.

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:

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

  • num_neighbors – [in] How many neighbors to find

  • result_sink – [in] Where to write the results

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

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

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

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);
Parameters:

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

  • num_neighbors – [in] How many neighbors to find

Returns:

Pair of iterators pointing to neighboring points

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

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename search_point_type, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9, typename T10>
inline 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)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Private Functions

template<typename box_type, typename insert_iter_type>
inline void _find_points_inside_box(box_type const &search_box, insert_iter_type result_sink) const
template<typename box_type>
inline query_result_range_type _find_points_inside_box(box_type const &search_box) const
template<typename box_type, typename insert_iter_type>
inline void _intersects(box_type const &search_box, insert_iter_type result_sink) const
template<typename box_type>
inline query_result_range_type _intersects(box_type const &search_box) const
template<typename box_type, typename insert_iter_type>
inline void _find_points_strictly_inside_box(box_type const &search_box, insert_iter_type output_sink) const
template<typename box_type>
inline query_result_range_type _find_points_strictly_inside_box(box_type const &search_box) const
template<typename search_point_type, typename insert_iter_type>
inline 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>
inline 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>
inline void _copy_range_to_output(iterator_range_type range, output_iterator_type output_sink) const

Private Members

rtree_type _RTree