Reimplementation of @ijeamaka_a randomized circle packing R code with Rcpp

pack_circles.cpp

#include <Rcpp.h>
using namespace Rcpp;

// [[Rcpp::export]]
double distance(double x1, double x2, double y1, double y2){
  double dist = sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
  return dist;
}

// [[Rcpp::export]]
NumericMatrix pack_circles_cpp(NumericVector circs, NumericVector panel, int max_attempts) {
  
  double r_temp;
  double x_temp;
  double y_temp;
  double dist;
  int attempts = 0;
  int overlap = 1;
  
  int n = circs.length();
  NumericMatrix xy(n,3);
  
  
  for(int i=0;i<n;++i){

    attempts = 0;
    overlap = 1; 
    
    while(overlap == 1){
      
      overlap = 0;  
      r_temp = circs[i];
      x_temp = R::runif(r_temp + panel[0], panel[1] - r_temp);
      y_temp = R::runif(r_temp + panel[2], panel[3] - r_temp);
      
      if(i>0){
        //check collision with previous nodes      
        for(int j=0; j<i; j++){
          dist = distance(x_temp,xy(j,0),y_temp,xy(j,1));
          if(dist < (r_temp + xy(j,2))){
            overlap = 1;
            break;
          }
        }
        if(overlap==0){
          xy(i,0) = x_temp;
          xy(i,1) = y_temp;
          xy(i,2) = r_temp;          
        } else{
          attempts += 1;
          if(attempts > max_attempts){
            xy(i,0) = x_temp;
            xy(i,1) = y_temp;
            xy(i,2) = r_temp;
            overlap = 0;
          }
        }
        
      } else{
        xy(i,0) = x_temp;
        xy(i,1) = y_temp;
        xy(i,2) = r_temp;
      }

    }
  }
  
  return xy;
}

The original code is from @ijeamaka_a (which is an implementation of Tyler Hobbs randomized approach to circle packing )

usage:

library(tidyverse)
library(ggforce)

Rcpp::sourceCpp("pack_circles.cpp")

circs <- rev(rep(1.25, 1),rep(0.75, 5),rep(0.25, 20),rep(0.1, 100)) 

res <- pack_circles_cpp(circs,c(0,8,0,5),25)
circle_coords <- as_tibble(res) %>% rename(x=1,y=2,r=3)

ggplot(data = circle_coords) +
  geom_circle(aes(x0 = x,
                  y0 = y,
                  r = r),
              fill = "black",
              color = "white") +
  coord_equal() +
  theme_void() +
  theme(panel.background = element_rect(fill = "black",
                                        color = "black"))

The benefit of implementing it with Rcpp is a significant speedup

tictoc::tic()
res <- pack_circles_cpp(circs,c(0,8,0,5),25)
tictoc::toc()
#> 0.003 sec elapsed