Barycentric interpolation: fast interpolation on arbitrary grids

[This article was first published on dahtah » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Barycentric interpolation generalises linear interpolation to arbitrary dimensions. It is very fast although suboptimal if the function is smooth. You might now it as algorithm 21.7.1 in Numerical Recipes (Two-dimensional Interpolation on an Irregular Grid). Using package geometry it can be implemented in a few lines of code in R.

Here’s a quick explanation of what the algorithm is doing: when interpolating to approximate the value of a function at {f(\mathbf{x})}, you want to see what the value of {f} is at neighbouring grid points and return some kind of weighted average of these values (with higher weights given to closer grid points). We start with random grid points:

X <- cbind(rnorm(n),rnorm(n))


Barycentric interpolation on the plane uses just three near-neighbours to interpolate. As a first step a triangulation is built: usually but not necessarily the Delaunay triangulation. This divides the convex hull of the grid into triangular tiles:

dn <- delaunayn(X)


The function delaunayn returns the index of the three points that make up each triangle. The tiles define which neighbours to use in the interpolation: for example if we interpolate anywhere within the blue tile we will be using the measured value of {f} at the three highlighted points.


The only thing that we still need to define is the relative weights of the three points in the interpolated value. This is where barycentric coordinates come in: given a point {\mathbf{x}} in the interior of a triangle formed by {\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3}}, we can express {\mathbf{x}} as a weighted average (convex combination) of {\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3}}:

\displaystyle \mathbf{x}=\sum_{i=1}^{3}\alpha_{i}\mathbf{x}_{i}


\displaystyle f\left(\mathbf{x}\right)\approx\sum_{i=1}^{3}\alpha_{i}f\left(\mathbf{x}_{i}\right)

For a linear function {f(\mathbf{x})=\mathbf{w}^{t}\mathbf{x}+\mathbf{r}} this interpolation is exact, so barycentric interpolation makes sense for functions that are roughly piecewise linear on the triangulation.

The function tsearch will assign each interpolated location to its Delaunay tile, and return its barycentric coordinates. To avoid slow R loops I use a sparse matrix trick to compute the interpolation. The whole thing is essentially five lines of code:

#2D barycentric interpolation at points Xi for a function with values f measured at locations X
#For N-D interpolation simply replace tsearch with tsearchn and modify the sparse matrix definition to have non-zero values in the right spots.
interp.barycentric <- function(X,f,Xi)
dn <- delaunayn(X)
tri <- tsearch(X[,1],X[,2],dn,Xi[,1],Xi[,2],bary=T)
#For each line in Xi, defines which points in X contribute to the interpolation
active <- dn[tri$idx,]
#Define the interpolation as a sparse matrix operation. Faster than using apply, probably slower than a C implementation
M <- sparseMatrix(i=rep(1:nrow(Xi),each=3),j=as.numeric(t(active)),x=as.numeric(t(tri$p)),dims=c(nrow(Xi),length(f)))



To leave a comment for the author, please follow the link and comment on their blog: dahtah » R. offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)