Create an R-tree data structure using Rcpp and Boost::Geometry
Nagi Teramo and Dirk Eddelbuettel —
written Dec 27, 2014 —
The purpose of this post is to show how to use
which was introduced
Rcpp. Especially, we focus on
R-tree data structure
for searching objects in space because only one spatial index is
implemented - R-tree Currently in this library.
Boost.Geometry which is part of the Boost C++ Libraries gives us algorithms
for solving geometry problems. In this library, the Boost.Geometry.Index
which is one of components is intended to gather data structures called
spatial indexes which are often used to searching for objects in space
quickly. Generally speaking, spatial indexes stores geometric objects’
representations and allows searching for objects occupying some space or
close to some point in space.
R-tree is a tree data structure used for spatial searching, i.e., for
indexing multi-dimensional information such as geographical coordinates,
rectangles or polygons. R-tree was proposed by Antonin Guttman in 1984 as an
expansion of B-tree for multi-dimensional data and plays significant role in
both theoretical and applied contexts. It is only one spatial index
implemented in Boost::Geometry.
As a real application of this, It is often used to store spatial objects such
as restaurant locations or the polygons which typical maps are made of:
streets, buildings, outlines of lakes, coastlines, etc in order to perform a
spatial query like “Find all stations within 1 km of my current location”,
“Let me know all road segments in 2 km of my location” or “find the nearest
gas station” which we often ask google seach by your voice recenlty. In this
way, the R-tree can be used (nearest neighbor) search for some places.
You can find more explanations about R-tree in
Write a wrapper class of rtree in Boost::Geometry using Rcpp
Now, we write a simple C++ wrapper class of rtree class in
Boost::Geometry::Index that we can use in R.
The most important feature to mention here is the use of Rcpp module to
expose your own class to R. Although almost all classes in Boost library have
a lot of functions, , you do not use all in many cases. In that case, you
should write your wrapper class for making your code simple.
R code using RTreeCpp
First, we create a sample data set of spatial data.
One can use the RTreeCpp class as follows:
 1 0
 2 1 0
Note the re-creation of the RTreeCpp object is of course
inefficient, but the Rcpp Gallery imposes some constraints on how we
present code. For actual application a stateful and persistent
object would be created. This could be done via Rcpp Modules as
well a number of different ways. Here, however, we need to
recreate the object for each call as knitr (which is used behind
the scenes) cannot persist objects between code chunks. This is
simply a technical limitation of the Rcpp Gallery—but not of Rcpp