random points in a circle with mbostock and umbrella

random-point-spike.ts

import { renderOnce, clearDOM } from "@thi.ng/hdom";
import * as svg from "@thi.ng/hiccup-svg";
import * as tx from "@thi.ng/transducers";
import * as isec from "@thi.ng/geom-isec";
import { add2, subN2 } from "@thi.ng/vectors";
import { poissonDiscSampler } from "./poisson-disc-sampler";

const width = 600;
const height = 500;

const circleArea = {
  center: [width / 2, height / 2],
  radius: (Math.min(width, height) / 2) * 0.9
};

// reference
// for now: https://programming.guide/random-point-within-circle.html
// http://xdpixel.com/random-points-in-a-circle/
// https://www.jasondavies.com/poisson-disc/
// https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf
// https://bl.ocks.org/mbostock/19168c663618b7f07158
const pointGenerator = poissonDiscSampler(
  circleArea.radius * 2,
  circleArea.radius * 2,
  10
);

const xform = tx.comp(
  tx.map(_ => pointGenerator()),
  tx.takeWhile(x => Boolean(x)),
  tx.map(x => subN2(null, add2([], x, circleArea.center), circleArea.radius)),
  tx.filter(
    x =>
      isec.classifyPointInCircle(x, circleArea.center, circleArea.radius) === 1
  )
);

const randomPoints = [...tx.transduce(xform, tx.push(), tx.range(1500))];

console.log({ randomPoints });

export function sketch() {
  renderOnce([
    "div.ma2.code",
    ["h1", "random point in a circle"],
    [
      "svg",
      { width, height },
      [
        [
          "rect",
          {
            x: 0,
            y: 0,
            width,
            height,
            fill: "transparent",
            stroke: "black"
          }
        ],
        [
          "g",
          [
            svg.svg(
              {},
              svg.circle(circleArea.center, circleArea.radius, {
                fill: "transparent",
                stroke: "black"
              })
            )
          ],
          [
            "g",
            tx.map(point => {
              return svg.svg(
                {},
                svg.circle(point, 2, {
                  fill: "black",
                  stroke: "none"
                })
              );
            }, randomPoints)
          ]
        ]
      ]
    ]
  ]);
}

if (process.env.NODE_ENV !== "production") {
  const hot = (<any>module).hot;
  hot && hot.dispose(() => clearDOM(document.getElementById("app")));
}



export function poissonDiscSampler(
  width: number,
  height: number,
  radius: number
) {
  var k = 30, // maximum number of samples before rejection
    radius2 = radius * radius,
    R = 3 * radius2,
    cellSize = radius * Math.SQRT1_2,
    gridWidth = Math.ceil(width / cellSize),
    gridHeight = Math.ceil(height / cellSize),
    grid = new Array(gridWidth * gridHeight),
    queue: Array<[number, number]> = [],
    queueSize = 0,
    sampleSize = 0;

  return function() {
    if (!sampleSize)
      return sample(Math.random() * width, Math.random() * height);

    // Pick a random existing sample and remove it from the queue.
    while (queueSize) {
      var i = (Math.random() * queueSize) | 0,
        s = queue[i];

      // Make a new candidate between [radius, 2 * radius] from the existing sample.
      for (var j = 0; j < k; ++j) {
        var a = 2 * Math.PI * Math.random(),
          r = Math.sqrt(Math.random() * R + radius2),
          x = s[0] + r * Math.cos(a),
          y = s[1] + r * Math.sin(a);

        // Reject candidates that are outside the allowed extent,
        // or closer than 2 * radius to any existing sample.
        if (0 <= x && x < width && 0 <= y && y < height && far(x, y))
          return sample(x, y);
      }

      queue[i] = queue[--queueSize];
      queue.length = queueSize;
    }
  };

  function far(x: number, y: number) {
    var i = (x / cellSize) | 0,
      j = (y / cellSize) | 0,
      i0 = Math.max(i - 2, 0),
      j0 = Math.max(j - 2, 0),
      i1 = Math.min(i + 3, gridWidth),
      j1 = Math.min(j + 3, gridHeight);

    for (j = j0; j < j1; ++j) {
      var o = j * gridWidth;
      for (i = i0; i < i1; ++i) {
        if ((s = grid[o + i])) {
          var s,
            dx = s[0] - x,
            dy = s[1] - y;
          if (dx * dx + dy * dy < radius2) return false;
        }
      }
    }

    return true;
  }

  function sample(x: number, y: number) {
    const s: [number, number] = [x, y];
    queue.push(s);
    grid[gridWidth * ((y / cellSize) | 0) + ((x / cellSize) | 0)] = s;
    ++sampleSize;
    ++queueSize;
    return s;
  }
}