an implementation of poisson disc sampling in Typescript

poisson_disc_sampling.ts

import { Vec2, RadialVec2 } from "./utils";
import Random = require("random-js");
import _ = require("underscore");

const ATTEMPTS_PER_POINT = 8;
const DEFAULT_RADIUS = 100;

export enum SamplingStrategy {
  Random = "random",
  First = "first",
  Last = "last"
}

const DEFAULT_SAMPLING_STRATEGY = SamplingStrategy.Random;

export function generatePoints(
  rnd: Random,
  topLeft: Vec2,
  bottomRight: Vec2,
  densityAtPoint: (p: Vec2) => number = () => DEFAULT_RADIUS,
  samplingStrategy: SamplingStrategy = DEFAULT_SAMPLING_STRATEGY
) {
  if (!rnd) {
    rnd = new Random(Random.engines.mt19937().autoSeed());
  }

  let firstPoint = Vec2.rnd(rnd, topLeft, bottomRight);

  let allPoints: Vec2[] = [firstPoint];
  let activePoints: Vec2[] = [firstPoint];

  let maxCount = 1000000;
  while (activePoints.length > 0 && allPoints.length < maxCount) {
    let currentPoint: Vec2;
    switch (samplingStrategy) {
      case SamplingStrategy.Random:
        currentPoint = rnd.pick(activePoints, 0, 1);
        break;
      case SamplingStrategy.First:
        currentPoint = activePoints[0];
        break;
      case SamplingStrategy.Last:
        currentPoint = activePoints[activePoints.length - 1];
        break;
    }

    let r = Math.max(0.1, Math.abs(densityAtPoint(currentPoint)));

    let placed = false;

    for (let i = 0; i < ATTEMPTS_PER_POINT; i++) {
      let offset = RadialVec2.of(rnd.real(0, Math.PI * 2), rnd.real(r, r * 2)).asVec2();
      let newPoint: Vec2 = currentPoint.add(offset);

      let tooClose = !newPoint.within(topLeft, bottomRight);

      if (!tooClose) {
        let r2 = r * r;
        tooClose = allPoints.some(p => p.sqrDistance(newPoint) < r2);
      }

      if (!tooClose) {
        if (rnd.die(30) == 1)
          console.log(`adding ${JSON.stringify(newPoint)} : offset ${JSON.stringify(offset)}, r ${r}`);
        allPoints.push(newPoint);
        activePoints.push(newPoint);
        placed = true;
        break;
      }
    }
    if (!placed) {
      activePoints = _.without(activePoints, currentPoint);
    }
  }

  return allPoints;
}