function* poissonDiscSampler(x0, y0, x1, y1, r, k = 30) {
if (!(x1 >= x0) || !(y1 >= y0) || !(r > 0)) throw new Error;
const width = x1 - x0;
const height = y1 - y0;
const r2 = r * r;
const r2_3 = 3 * r2;
const cellSize = r * Math.SQRT1_2;
const gridWidth = Math.ceil(width / cellSize);
const gridHeight = Math.ceil(height / cellSize);
const grid = new Array(gridWidth * gridHeight);
const queue = [];
function far(x, y) {
const i = x / cellSize | 0;
const j = y / cellSize | 0;
const i0 = Math.max(i - 2, 0);
const j0 = Math.max(j - 2, 0);
const i1 = Math.min(i + 3, gridWidth);
const j1 = Math.min(j + 3, gridHeight);
for (let j = j0; j < j1; ++j) {
const o = j * gridWidth;
for (let i = i0; i < i1; ++i) {
const s = grid[o + i];
if (s) {
const dx = s[0] - x;
const dy = s[1] - y;
if (dx * dx + dy * dy < r2) return false;
}
}
}
return true;
}
function sample(x, y) {
queue.push(grid[gridWidth * (y / cellSize | 0) + (x / cellSize | 0)] = [x, y]);
return [x + x0, y + y0];
}
yield sample(width / 2, height / 2);
pick: while (queue.length) {
const i = Math.random() * queue.length | 0;
const parent = queue[i];
for (let j = 0; j < k; ++j) {
const a = 2 * Math.PI * Math.random();
const r = Math.sqrt(Math.random() * r2_3 + r2);
const x = parent[0] + r * Math.cos(a);
const y = parent[1] + r * Math.sin(a);
if (0 <= x && x < width && 0 <= y && y < height && far(x, y)) {
yield sample(x, y);
continue pick;
}
}
const r = queue.pop();
if (i < queue.length) queue[i] = r;
}
}