Wednesday, April 29, 2015

Circle packing in R (again)

Back in 2010 I posted some R code for circle packing. Now, just five years later, I've ported the code to Rcpp and created a little package which you can find at GitHub.

The main function is circleLayout which takes a set of overlapping circles and tries to find a non-overlapping arrangement for them. Here's an example:


And here's the code:

# Create some random circles, positioned within the central portion
# of a bounding square, with smaller circles being more common than
# larger ones.

ncircles <- 200
limits <- c(-50, 50)
inset <- diff(limits) / 3
rmax <- 20

xyr <- data.frame(
  x = runif(ncircles, min(limits) + inset, max(limits) - inset),
  y = runif(ncircles, min(limits) + inset, max(limits) - inset),
  r = rbeta(ncircles, 1, 10) * rmax)

# Next, we use the `circleLayout` function to try to find a non-overlapping
# arrangement, allowing the circles to occupy any part of the bounding square.
# The returned value is a list with elements for the layout and the number
# of iterations performed.

library(packcircles)

res <- circleLayout(xyr, limits, limits, maxiter = 1000)
cat(res$niter, "iterations performed")

# Now draw the before and after layouts with ggplot

library(ggplot2)
library(gridExtra)

## plot data for the `before` layout
dat.before <- circlePlotData(xyr)

## plot dta for the `after` layout returned by circleLayout
dat.after <- circlePlotData(res$layout)

doPlot <- function(dat, title)
  ggplot(dat) + 
  geom_polygon(aes(x, y, group=id), colour="brown", fill="burlywood", alpha=0.3) +
  coord_equal(xlim=limits, ylim=limits) +
  theme_bw() +
  theme(axis.text=element_blank(),
        axis.ticks=element_blank(),
        axis.title=element_blank()) +
  labs(title=title)

grid.arrange(
  doPlot(dat.before, "before"),
  doPlot(dat.after, "after"),
  nrow=1)

5 comments:

  1. Wow! It's magic. Thank you for posting this.

    This is an interesting problem to solve in code. Very cool.

    ReplyDelete
    Replies
    1. You're welcome Phillip. If you try it out let me know it goes.

      Delete
  2. I'm having issues compiling the package:

    * installing *source* package 'packcircles' ...
    ** libs
    Warning: running command 'make -f "C:/PROGRA~1/R/R-31~1.3/etc/x64/Makeconf" -f "C:/PROGRA~1/R/R-31~1.3/share/make/winshlib.mk" SHLIB_LDFLAGS='$(SHLIB_CXXLDFLAGS)' SHLIB_LD='$(SHLIB_CXXLD)' SHLIB="packcircles.dll" WIN=64 TCLBIN=64 OBJECTS="RcppExports.o packcircles.o"' had status 127
    ERROR: compilation failed for package 'packcircles'

    ReplyDelete
    Replies
    1. Hi Jim,
      Was that the entire error trace ? I'm building on a windows 7 box with Rtools 3.1.0.1942 and devtools 1.7.0.

      In case I'd missed including something essential in the repo, I just tried cloning it into a new folder, opening the project in RStudio and building it from there. There were no errors.

      If you can't get it to work I could send you a zip file of the built package to install.

      Delete
    2. I also just tried doing `devtools::install_github("mbedward/packcircles")` which also worked. For the moment I'm guessing the problem has to do with your local setup.

      Delete