Last active
April 12, 2025 22:40
-
-
Save bazzargh/b802a1d8a3d387bac665cea19f72864a to your computer and use it in GitHub Desktop.
"place specimens on the grid at randomly selected points until no more can be placed: "no more" because each specimen has a neighborhood radius r_i such that no other specimens may be placed within that radius."
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function initialiseGrid(w, h) { | |
// first get all the initial max radii | |
let temp = [] | |
for (let x = 0; x < w; x++) { | |
for (let y = 0; y < h; y++) { | |
let k = JSON.stringify([x, y]) | |
temp.push([k, Math.min(x, y, w-x, h-y)]) | |
} | |
} | |
// now shuffle, so that we do not need to filter | |
// and shuffle later to find a random point. If | |
// we don't do this, the points will be in insertion order. | |
let i = temp.length; | |
while (--i > 0) { | |
let randIndex = Math.floor(Math.random() * (i + 1)); | |
[temp[randIndex], temp[i]] = [temp[i], temp[randIndex]]; | |
} | |
// now store these in grid. | |
return Object.fromEntries(temp) | |
} | |
function pickCircle(r) { | |
// because of the way we constructed the grid above, | |
// the keys are returned in a random order, and we | |
// can just peel off the first matching point. | |
let p = Object.keys(grid).find(k => grid[k] >= r); | |
if (!p) { | |
return null | |
} | |
return JSON.parse(p) | |
} | |
function addCircle(x, y, r) { | |
let seen = {} | |
let q = [[x, y]] | |
let k = JSON.stringify(x, y) | |
seen[k] = 1 | |
let rr = r * r | |
while (q.length > 0) { | |
[x1, y1] = q.pop() | |
// stringifying would not be necessary in python. | |
let k = JSON.stringify([x1, y1]) | |
if (!Object.hasOwn(grid, k)) { | |
// can occur if point was removed | |
continue | |
} | |
let r1 = sqrt((x1 - x)*(x1 - x) + (y1 - y)*(y1 - y)) | |
let rmax = Math.max(r1 - r, 0) | |
if (grid[k] > rmax) { | |
if (rmax == 0) { | |
delete grid[k] | |
} else { | |
//fill(max(255, 10*(20-rmax))) | |
//point(x1, y1) | |
grid[k] = rmax | |
} | |
for (let i = -1; i <= 1; i++) { | |
for (let j = -1; j <= 1; j++) { | |
if (i ==0 && j==0) { | |
continue | |
} | |
let k2 = JSON.stringify([x1 + i, y1 + j]) | |
if (Object.hasOwn(grid, k2) && !Object.hasOwn(seen, k2)) { | |
seen[k2] = 1 | |
q.push([x1 + i, y1 + j]) | |
} | |
} | |
} | |
} | |
} | |
} | |
let grid = {} | |
let done = false | |
function setup() { | |
createCanvas(400, 400); | |
grid = initialiseGrid(400, 400) | |
} | |
function draw() { | |
if (done) { | |
return | |
} | |
// allowing r to reach the max radius (200), this stops | |
// quite quickly as the chance of picking a circle | |
// you can't place is high. | |
let r = Math.random() * 20; | |
let p = pickCircle(r) | |
if (!p) { | |
console.log("Cannot place circle radius", r) | |
done = true | |
return | |
} | |
let [x, y] = p; | |
addCircle(x, y, r) | |
fill(255) | |
circle(x, y, 2*r) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This is an alternative implementation using spatial hashing, which is just a fancy way of saying, divide into a grid and only test nearby cells for collisions