Poisson Disc Sampling

poisson-disc-sampling.js

// Poisson Disc Sampling 
// https://www.youtube.com/watch?v=flQgnCUxHlw
 
class PoissonSampling {
    constructor(width, height, r, start, k = 30) {
        this.r = r;
        this.k = k;
        this.w = r / sqrt(2);
        
        let rows = floor(height / this.w);
        let columns = floor(width / this.w);
        
        this.grid = [];
        this.grid.length = floor(height / this.w);
        for(let i = 0; i < this.grid.length; i++) {
            this.grid[i] = [];
            this.grid[i].length = columns;
        }
        
        let pos = start;
        let y = floor(pos.y / this.w);
        let x = floor(pos.x / this.w);
      
        this.grid[y][x] = pos;
        this.active = [pos];
        
        this.history = [];
    }
    
    inRow(y) {
        return y > -1 && y < this.grid.length;
    }
    
    inGrid(x, y) {
        return this.inRow(y) && x  > -1 && x < this.grid[0].length;
    }
    
    noAdjacentNeighbor(sample, x, y) {
        return [
            [x - 1, y - 1], [x, y - 1], [x + 1, y - 1],
            [x - 1, y], [x, y], [x + 1, y],
            [x - 1, y + 1], [x, y + 1], [x + 1, y + 1]
        ].every(nbr => 
            !this.inRow(nbr[1]) || 
            this.grid[nbr[1]][nbr[0]] === undefined ||  
            p5.Vector.dist(sample, this.grid[nbr[1]][nbr[0]]) >= this.r
        );
    }
    
    randomSample(pos) {
        let sample = p5.Vector.random2D();
        sample.setMag(random(this.r, 2 * this.r));
        sample.add(pos);    
        return sample;
    }

    hasActive() {
        return this.active.length > 0;
    }

    kSamples(pos) {
        let samples = [];
        for(let n = 0; n < this.k; n++) {
            let sample = this.randomSample(pos);
            
            let y = floor(sample.y / this.w);
            let x = floor(sample.x / this.w);
    
            if(this.inGrid(x, y) && this.noAdjacentNeighbor(sample, x, y)) {       
                samples.push(sample);   
            }
        }
        return samples;
    }
    
    minDistSample(pos, samples) {
        if(samples.length === 1) {
            return samples[0];
        }
        
        let sample = samples[0];
        let dist = p5.Vector.dist(pos, sample);
        for(let i = 1; i < samples.length; i++) {
            let d = p5.Vector.dist(pos, samples[i]);
            if(dist > d) {
                dist = d;
                sample = samples[i];
            }
        }
        return sample;
    }

    trySampleFromOneActive() {        
        let i = floor(random(this.active.length));
        let pos = this.active[i];
        let samples = this.kSamples(pos);
        
        if(samples.length === 0) { 
            this.active.splice(i, 1);
        }
        else {
            // try to find a minimum distance between cells
            let sample = this.minDistSample(pos, samples);
            let y = floor(sample.y / this.w);
            let x = floor(sample.x / this.w);
            this.grid[y][x] = sample;
            this.active.push(sample);
            this.history.push([pos, sample]);
        }
    }
}

let sampling;
function setup() {
  createCanvas(400, 400);
  background(200);
  
  let r = random(10, 15);
  let k = 30;
  strokeWeight(4);
  sampling = new PoissonSampling(width, height, r, createVector(width / 2, height / 2), k);
}

function draw() {  
  if(sampling.hasActive()) {
      sampling.trySampleFromOneActive();
        
      stroke(255);
      sampling.history.forEach(pts => {
          line(pts[0].x, pts[0].y, pts[1].x, pts[1].y);
      });
      
      stroke(0);
      for(let row of sampling.grid) {
        row.forEach(pos => {
            point(pos.x, pos.y);
        });
      }
  }
  else {
      noLoop();
      console.log('stop');
  }
}