Convex Hull of Polygon using Boost.Geometry
Sameer D'Costa —
written Feb 23, 2014 —
source

Rcpp can be used to convert basic R data types to and from
Boost.Geometry models.

In this example, we take a matrix of 2d-points and convert it into a Boost.Geometry polygon.
We then compute the convex hull of this polygon using the Boost.Geometry function
`boost::geometry::convex_hull()`

. The convex hull is then converted back to an R matrix.

The conversions to and from R and Boost.Geometry types are are done using two custom
`as()`

and `wrap()`

convenience converter functions which are implemented below, followed by
a function using them in order to take data from R, call a
Boost.Geometry
function, and return the result to R.

#include <Rcpp.h> using namespace Rcpp ; #include <boost/geometry.hpp> #include <boost/geometry/geometries/polygon.hpp> #include <boost/geometry/geometries/adapted/boost_tuple.hpp> BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS ( cs :: cartesian ) typedef boost :: tuple < double , double > point ; typedef boost :: geometry :: model :: polygon < point , true , true > polygon ; namespace Rcpp { // as<>() converter from R to Boost.Geometry's polygon type template <> polygon as ( SEXP pointsMatrixSEXP ) { // the coordinates are the rows of the (n x 2) matrix NumericMatrix pointsMatrix ( pointsMatrixSEXP ); polygon poly ; for ( int i = 0 ; i < pointsMatrix . nrow (); ++ i ) { double x = pointsMatrix ( i , 0 ); double y = pointsMatrix ( i , 1 ); point p ( x , y ); poly . outer (). push_back ( p ); } return ( poly ); } // wrap() converter from Boost.Geometry's polygon to an R(cpp) matrix // The Rcpp NumericMatrix can be converted to/from a SEXP template <> SEXP wrap ( const polygon & poly ) { const std :: vector < point >& points = poly . outer (); NumericMatrix rmat ( points . size (), 2 ); for ( unsigned int i = 0 ; i < points . size (); ++ i ) { const point & p = points [ i ]; rmat ( i , 0 ) = p . get < 0 > (); rmat ( i , 1 ) = p . get < 1 > (); } return Rcpp :: wrap ( rmat ); } } // [[Rcpp::export]] NumericMatrix convexHullRcpp ( SEXP pointsMatrixSEXP ){ // Conversion of pointsMatrix here to boost::geometry polygon polygon poly = as < polygon > ( pointsMatrixSEXP ); polygon hull ; // Compute the convex hull boost :: geometry :: convex_hull ( poly , hull ); // Convert hull into a NumericMatrixsomething that Rcpp can hand back to R return wrap ( hull ); }

Now we can use R to replicate the `convex_hull`

example
in the Boost.Geometry documentation .

points <- c ( 2.0 , 1.3 , 2.4 , 1.7 , 2.8 , 1.8 , 3.4 , 1.2 , 3.7 , 1.6 , 3.4 , 2.0 , 4.1 , 3.0 , 5.3 , 2.6 , 5.4 , 1.2 , 4.9 , 0.8 , 2.9 , 0.7 , 2.0 , 1.3 ) points.matrix <- matrix ( points , ncol = 2 , byrow = TRUE ) points.matrix

[,1] [,2]
[1,] 2.0 1.3
[2,] 2.4 1.7
[3,] 2.8 1.8
[4,] 3.4 1.2
[5,] 3.7 1.6
[6,] 3.4 2.0
[7,] 4.1 3.0
[8,] 5.3 2.6
[9,] 5.4 1.2
[10,] 4.9 0.8
[11,] 2.9 0.7
[12,] 2.0 1.3
convexHullRcpp ( points.matrix )

[,1] [,2]
[1,] 2.0 1.3
[2,] 2.4 1.7
[3,] 4.1 3.0
[4,] 5.3 2.6
[5,] 5.4 1.2
[6,] 4.9 0.8
[7,] 2.9 0.7
[8,] 2.0 1.3
In fact, because of the interplay because providing `as<>()`

and
`wrap()`

for the compiler, and how `compileAttributes()`

works, we
can write the function more cleanly with the desired new types in
the interface.

// [[Rcpp::export]] polygon convexHullRcpp2 ( polygon pointsMatrixBG ){ polygon hull ; boost :: geometry :: convex_hull ( pointsMatrixBG , hull ); return hull ; }

We can run this second function as well:

convexHullRcpp2 ( points.matrix )

[,1] [,2]
[1,] 2.0 1.3
[2,] 2.4 1.7
[3,] 4.1 3.0
[4,] 5.3 2.6
[5,] 5.4 1.2
[6,] 4.9 0.8
[7,] 2.9 0.7
[8,] 2.0 1.3
tags:
boost

Related Articles