mio::geo::RTree Class Reference

R-tree for spatial queries of geographical locations on the sphere. More...

#include <rtree.h>

Public Member Functions
std::vector< size_t >	in_range_indices (const IsSphericalLocation auto &location, Distance radius) const
	Return the indices of the points within a given radius. More...
std::vector< size_t >	in_range_indices_approximate (const IsSphericalLocation auto &location, Distance radius) const
	Return the indices of the points within a given radius (in kilometers) where the circle is approximated by a polygon. More...
std::vector< std::vector< size_t > >	in_range_indices_query (const IsSphericalLocation auto &location, const std::vector< Distance > &radii) const
	Return the indices of the points within each given radius for multiple radii at the same time. More...
std::vector< size_t >	nearest_neighbor_indices (const IsSphericalLocation auto &location, size_t number) const
	Return the indices of the k nearest neighbors (i.e. More...
	RTree ()=default
	Construct a new RTree object without data. More...
template<IsSphericalLocation Location>
	RTree (const std::vector< Location > &locations)
	Construct a new RTree object with data given in a vector. More...
auto	size () const
	Return the number of data points stored in the RTree. More...

Private Types
using	MultiPolygon = boost::geometry::model::multi_polygon< boost::geometry::model::polygon< Point > >
	MultiPolygon type for circle approximation. More...
using	Node = std::pair< Point, size_t >
	Node stores a point and its associated index. More...
using	Point = boost::geometry::model::point< double, 2, boost::geometry::cs::geographic< boost::geometry::degree > >
	Point stores longitude and latitude in this order. More...

Private Member Functions
MultiPolygon	create_circle_approximation (const IsSphericalLocation auto &location, Distance radius, size_t approximation_points=36) const
	Create a circle approximation object. More...

Private Attributes
boost::geometry::index::rtree< Node, boost::geometry::index::rstar< m_max_number_of_elements_per_tree_node > >	m_rtree

Static Private Attributes
constexpr static size_t	m_max_number_of_elements_per_tree_node = 16

Detailed Description

R-tree for spatial queries of geographical locations on the sphere.

Data structure to store spatial indices and allow for efficient in-range and nearest neighbour queries. Wraps the Boost::geometry::index::rtree. Can be initialized with a vector of geographical location data or a range. The provided location data needs to provide get_latitude() and get_longitude(). The tree is initialised with a maximum number of elements per tree node of 16, which can be changed for different use cases.

Member Typedef Documentation

MultiPolygon

using mio::geo::RTree::MultiPolygon = boost::geometry::model::multi_polygon<boost::geometry::model::polygon<Point> >

private

MultiPolygon type for circle approximation.

Node

using mio::geo::RTree::Node = std::pair<Point, size_t>

private

Node stores a point and its associated index.

Point

using mio::geo::RTree::Point = boost::geometry::model::point<double, 2, boost::geometry::cs::geographic<boost::geometry::degree> >

private

Point stores longitude and latitude in this order.

Constructor & Destructor Documentation

RTree() [1/2]

mio::geo::RTree::RTree ( )

default

Construct a new RTree object without data.

RTree() [2/2]

template<IsSphericalLocation Location>

mio::geo::RTree::RTree ( const std::vector< Location > &  locations )

inline

Construct a new RTree object with data given in a vector.

Parameters

locations

A vector of geographical locations, they need to provide get_latitude() and get_longitude().

Member Function Documentation

create_circle_approximation()

MultiPolygon mio::geo::RTree::create_circle_approximation ( const IsSphericalLocation auto &  location, Distance  radius, size_t  approximation_points = 36  ) const

inlineprivate

Create a circle approximation object.

Parameters

location	Midpoint, needs to provide get_latitude() and get_longitude().
radius
approximation_points	Number of points used to approximate the circle. Default is 36, i.e. we build a 36-gon.

Returns

multi_polygon.

in_range_indices()

std::vector<size_t> mio::geo::RTree::in_range_indices ( const IsSphericalLocation auto &  location, Distance  radius  ) const

inline

Return the indices of the points within a given radius.

Parameters

location	Midpoint for the query, provides get_latitude() and get_longitude().
radius	The radius of the query.

Returns

Vector with indices of the points found.

Basically the same as in_range_indices_approximate, but filters the result to make sure the points are within the radius.

in_range_indices_approximate()

std::vector<size_t> mio::geo::RTree::in_range_indices_approximate ( const IsSphericalLocation auto &  location, Distance  radius  ) const

inline

Return the indices of the points within a given radius (in kilometers) where the circle is approximated by a polygon.

Parameters

location	Midpoint for the query, provides get_latitude() and get_longitude().
radius	The radius of the query.

Returns

Vector with indices of the points found.

in_range_indices_query()

std::vector<std::vector<size_t> > mio::geo::RTree::in_range_indices_query ( const IsSphericalLocation auto &  location, const std::vector< Distance > &  radii  ) const

inline

Return the indices of the points within each given radius for multiple radii at the same time.

Parameters

location	Midpoint for the query, provides get_latitude() and get_longitude().
radii	Vector containing the radii of the query.

Returns

Vector of vectors with indices of the points found.

nearest_neighbor_indices()

std::vector<size_t> mio::geo::RTree::nearest_neighbor_indices ( const IsSphericalLocation auto &  location, size_t  number  ) const

inline

Return the indices of the k nearest neighbors (i.e.

nodes with the least distance) of a given location.

Parameters

location	Midpoint for the query, provides get_latitude() and get_longitude().
number	The number of nearest neighbours to find.

Returns

Vector with indices of the nearest neighbours.

size()

auto mio::geo::RTree::size ( ) const

inline

Return the number of data points stored in the RTree.

Returns

size of the tree.

Member Data Documentation

m_max_number_of_elements_per_tree_node

constexpr static size_t mio::geo::RTree::m_max_number_of_elements_per_tree_node = 16

staticconstexprprivate

m_rtree

boost::geometry::index::rtree<Node, boost::geometry::index::rstar<m_max_number_of_elements_per_tree_node> > mio::geo::RTree::m_rtree

private