Quick start

Let’s go through a very simple example to demonstrate how to use rtree. First, you need to specify a concrete type by specifying the key type and value type to use:

#include <mdds/rtree.hpp>

#include <string>
#include <iostream>

// key values are of type double, and we are storing std::string as a
// value for each spatial object.  By default, tree becomes 2-dimensional
// object store unless otherwise specified.
using rt_type = mdds::rtree<double, std::string>;

You’ll only need to specify the types of key and value here unless you want to customize other properties of rtree including the number of dimensions. By default, rtree sets the number of dimensions to 2.

rt_type tree;

Instantiating an rtree instance should be no brainer as it requires no input parameters. Now, let’s insert some data:

tree.insert({{0.0, 0.0}, {15.0, 20.0}}, "first rectangle data");

This inserts a string value associated with a bounding rectangle of (0, 0) - (15, 20). Note that in the above code we are passing the bounding rectangle parameter to rtree’s insert() method as a nested initializer list, which implicitly gets converted to extent_type. You can also use the underlying type directly as follows:

rt_type::extent_type bounds({-2.0, -1.0}, {1.0, 2.0});
std::cout << "inserting value for " << bounds.to_string() << std::endl;
tree.insert(bounds, "second rectangle data");

which inserts a string value associated with a bounding rectangle of (-2, -1) to (1, 2). You may have noticed that this code also uses extent_type’s to_string() method which returns a string representation of the bounding rectangle. This may come in handy when debugging your code. This method should work as long as the key type used in your rtree class overloads std::ostream’s << operator function.

Running this code will generate the following output:

inserting value for (-2, -1) - (1, 2)

As extent_type consists of two members called start and end both of which are of type point_type, which in turn contains an array of keys called d whose size equals the number of dimensions, you can modify the extent directly:

bounds.start.d[0] = -1.0; // Change the first dimension value of the start rectangle point.
bounds.end.d[1] += 1.0; // Increment the second dimension value of the end rectangle point.
std::cout << "inserting value for " << bounds.to_string() << std::endl;
tree.insert(bounds, "third rectangle data");

This code will insert a string value associated with a rectangle of (-1, -1) to (1, 3), and will generate the following output:

inserting value for (-1, -1) - (1, 3)

So far we have only inserted data associated with rectangle shapes, but rtree also allows data associated with points to co-exist in the same tree. The following code inserts a string value associated with a point (5, 6):

tree.insert({5.0, 6.0}, "first point data");

Like the very first rectangle data we inserted, we are passing the point data as an initializer list of two elements (for 2-dimensional data storage), which will implicitly get converted to point_type before it enters into the call.

Now that some data have been inserted, it’s time to run some queries. Let’s query all objects that overlap with a certain rectangular region either partially or fully. The following code will do just that:

// Search for all objects that overlap with a (4, 4) - (7, 7) rectangle.
auto results = tree.search({{4.0, 4.0}, {7.0, 7.0}}, rt_type::search_type::overlap);

for (const std::string& v : results)
    std::cout << "value: " << v << std::endl;

In this query, we are specifying the search region to be (4, 4) to (7, 7) which should overlap with the first rectangle data and the first point data. Indeed, when you execute this code, you will see the following output:

value: first rectangle data
value: first point data

indicating that the query region does overlap with two of the stored values.

Note that the search() method takes exactly two arguments; the first one specifies the search region while the second two specifies the type of search to be performed. In the above call we passed search_type’s overlap enum value which picks up all values whose bounding rectangles overlap with the search region either partially or fully.

Sometimes, however, you may need to find a value whose bounding rectangle matches exactly the search region you specify in your query. You can achieve that by setting the search type to match.

Here is an example:

// Search for all objects whose bounding rectangles are exactly (4, 4) - (7, 7).
auto results = tree.search({{4.0, 4.0}, {7.0, 7.0}}, rt_type::search_type::match);
std::cout << "number of results: " << std::distance(results.begin(), results.end()) << std::endl;

The search region is identical to that of the previous example, but the search type is set to match instead. Then the next line will count the number of results and print it out. The output you will see is as follows:

number of results: 0

indicating that the results are empty. That is expected since none of the objects stored in the tree have an exact bounding rectangle of (4, 4) - (7, 7). When you change the search region to (0, 0) - (15, 20), however, you’ll get one object back. Here is the actual code:

// Search for all objects whose bounding rectangles are exactly (0, 0) - (15, 20).
auto results = tree.search({{0.0, 0.0}, {15.0, 20.0}}, rt_type::search_type::match);
std::cout << "number of results: " << std::distance(results.begin(), results.end()) << std::endl;

which is identical to the previous one except for the search region. This is its output:

number of results: 1

indicating that it has found exactly one object whose bounding rectangle exactly matches the search region.

It’s worth mentioning that rtree supports storage of multiple objects with identical bounding rectangle. As such, searching with the search type of match can return more than one result.

As you may have noticed in these example codes, the search_results object does provide begin() and end() methods that return standard iterators which you can plug into various iterator algorithms from the STL. Dereferencing the iterator will return a reference to the stored value i.e. this line:

std::cout << "value: " << *results.begin() << std::endl;

which immediately follows the previous code block will output:

value: first rectangle data

In addition to accessing the value that the iterator references, you can also query from the same iterator object the bounding rectangle associated with the value as well as its depth in the tree by calling its extent() and depth() methods, respectively:

auto it = results.begin();
std::cout << "value: " << *it << std::endl;
std::cout << "extent: " << it.extent().to_string() << std::endl;
std::cout << "depth: " << it.depth() << std::endl;

Running this code will produce the following output:

value: first rectangle data
extent: (0, 0) - (15, 20)
depth: 1

This depth value represents the distance of the node that stores the value from the root node of the tree, and is technically 0-based. However, you will never see a depth of 0 in the search results since the root node of a R-tree is always a directory node, and a directory node only stores other child nodes and never stores a value, hence it never appears in the search results.