Examples Database
Share
Poisson disk sampling with many points
This is an example how to program a *JSXGraph extension*. It uses the class [`JXG.composition`](https://jsxgraph.org/docs/JXG.Composition.html) to manage the points.
// Define the id of your board in BOARDID
// ----------------------------------------------------------
// Start external file
//
// Poisson disk sampling.
// Pure JavaScript, no JSXGraph, yet.
//
/**
* Poisson Disk Sampling (Bridson Algorithm)
* Generates points with a minimum distance between each other.
*
* @param {number} width - area width
* @param {number} height - area height
* @param {number} radius - Minimum distance between points
* @returns {Array<{x: number, y: number}>} Array of sampled points
*/
var poissonDiskSampling = function (width, height, radius) {
const k = 30; // max attempts per point before rejection
const cellSize = radius / Math.sqrt(2);
const cols = Math.ceil(width / cellSize);
const rows = Math.ceil(height / cellSize);
// Grid to track occupied cells (flat array for performance)
const grid = new Int32Array(cols * rows).fill(-1);
// Helper: map (x, y) to grid cell index
function cellIndex(x, y) {
const col = Math.floor(x / cellSize);
const row = Math.floor(y / cellSize);
if (col < 0 || col >= cols || row < 0 || row >= rows) return -1;
return row * cols + col;
}
// Result points
const points = [];
// Active list (indices into `points`)
const active = [];
// Seed the first point
points.push({ x: Math.random() * width, y: Math.random() * height });
active.push(0);
grid[cellIndex(points[0].x, points[0].y)] = 0;
while (active.length > 0) {
// Pick a random active point
const idx = Math.floor(Math.random() * active.length);
const point = points[active[idx]];
// Try k random points in the annulus around it
let found = false;
for (let attempt = 0; attempt < k; attempt++) {
// Random angle + random radius in [radius, 2*radius]
const angle = Math.random() * 2 * Math.PI;
const r = radius * (1 + Math.random()); // uniform in annulus
const x = point.x + r * Math.cos(angle);
const y = point.y + r * Math.sin(angle);
// Check bounds
if (x < 0 || x >= width || y < 0 || y >= height) continue;
// Check nearby cells in the grid
const col = Math.floor(x / cellSize);
const row = Math.floor(y / cellSize);
let tooClose = false;
// Search the 5x5 neighborhood of cells
for (let dr = -2; dr <= 2; dr++) {
for (let dc = -2; dc <= 2; dc++) {
const nc = col + dc;
const nr = row + dr;
if (nc < 0 || nc >= cols || nr < 0 || nr >= rows) continue;
const neighborIdx = grid[nr * cols + nc];
if (neighborIdx === -1) continue;
const dx = points[neighborIdx].x - x;
const dy = points[neighborIdx].y - y;
if (dx * dx + dy * dy < radius * radius) {
tooClose = true;
break;
}
}
if (tooClose) break;
}
if (tooClose) continue;
// Valid point found
const newIdx = points.length;
points.push({ x, y });
active.push(newIdx);
grid[cellIndex(x, y)] = newIdx;
found = true;
break;
}
// If no valid point found after k attempts, remove from active
if (!found) {
active[idx] = active[active.length - 1];
active.pop();
}
}
return points;
};
// Add new defaults and new attributes
JXG.extend(JXG.Options, {
poissonsample: { // Lower case
name: '',
highlight: false,
size: 1,
strokeWidth: 0,
color: JXG.palette.blue,
withLabel: false,
withCircle: false,
circle: {
strokeWidth: 0.5,
strokeColor: 'red',
strokeOpacity: 0.5,
highlight: false
}
}
});
// Create constructor and register element
// Create new JSXGraph composition element poissonsample
// Add two methods: sample() and resample()
JXG.createPoissonSample = function (board, parents, attributes) {
var box = parents[0],
r = parents[1],
el;
if (!JXG.isArray(box) || box.length != 4 || !JXG.isNumber(r)) {
throw new Error("JSXGraph: Can't create Poisson sample with these parameters. Supply bounding box array and number radius.");
}
el = new JXG.Composition();
el.box = box;
el.radius = r;
el.poissonDiskSampling = poissonDiskSampling;
el.poissonpoints = null;
el.sample = function () {
var w = this.box[2] - this.box[0],
h = this.box[1] - this.box[3],
w2 = w / 2,
h2 = h / 2,
withCircle,
attr, points;
attr = JXG.copyAttributes(attributes, board.options, 'poissonsample');
this.poissonpoints = this.poissonDiskSampling(w, h, JXG.evaluate(this.radius));
// console.log(this.points.length)
withCircle = attr.withcircle;
// console.time('sample');
let pp = this.poissonpoints;
for (let i = 0; i < pp.length; i++) {
let p = board.create('point', [pp[i].x - w2, pp[i].y - h2], attr);
el.add(i, p);
if (withCircle) {
el.add( i + '_c', board.create('circle', [p, this.radius], attr.circle) );
}
}
// console.timeEnd('sample');
};
el.resample = function () {
var le = this.poissonpoints.length, i;
// Remove all points
board.removeObject(this.objectsList, false);
for (i = 0; i < le; i++) {
this.remove(i);
this.remove(i + '_c');
}
// Sample again
this.sample();
};
el.sample();
return el;
};
JXG.registerElement('poissonsample', JXG.createPoissonSample);
// End external file
// ----------------------------------------------------------
// Use the new element
const board = JXG.JSXGraph.initBoard(BOARDID, {
boundingbox: [-5, 5, 5, -5],
axis: true,
pan: { enabled: true }, // Disable pan for 3D view
zoom: { enabled: true } // Disable zoom for 3D view
});
var points = board.create('poissonsample', [[-4, 4, 4, -4], 1], {
size: 3,
withCircle: true,
circle: {
dash: 1
}
});
// points[10].setAttribute({color: 'red', size: 10});
//setInterval(() => { points.resample(); }, 1000);
This example is licensed under a
Creative Commons Attribution ShareAlike 4.0 International License.
Please note you have to mention
The Center of Mobile Learning with Digital Technology
in the credits.