Examples Database
Share
Poisson disk sampling using a single curve
Poisson disk sampling using a single curve
This is an example how to program a JSXGraph extension. It uses a single curve to host the points which makes it much faster.
Have also a look at the examples
Web references
// Define the id of your board in BOARDID
// ----------------------------------------------------------
// Start external file
//
// Poisson disk sampling.
// Pure JavaScript, no JSXGraph at this point.
//
/**
* 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 to JSXGraph
JXG.extend(JXG.Options, {
poissonpointcurve: { // Lower case
highlight: false,
strokeWidth: 5,
withLabel: false,
}
});
// Create constructor function and register the element
JXG.createPoissonSampleCurve = function (board, parents, attributes) {
var box = parents[0],
r = parents[1],
attr, 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.");
}
attr = JXG.copyAttributes(attributes, board.options, 'poissonpointcurve');
// attr = JXG.copyAttributes(attr, board.options, 'curve')
el = board.create('curve', [[], []], attr); // Curve attributes are merged here
el.box = box;
el.radius = r;
el.poissonDiskSampling = poissonDiskSampling;
el.poissonPoints = null;
el.updateDataArray = function () {
var le = this.poissonPoints.length,
i;
this.dataX = [];
this.dataY = [];
for (i = 0; i < le; i++) {
this.dataX.push(this.poissonPoints[i].x, this.poissonPoints[i].x, NaN);
this.dataY.push(this.poissonPoints[i].y, this.poissonPoints[i].y, NaN);
}
};
el.sample = function () {
var w = this.box[2] - this.box[0],
h = this.box[1] - this.box[3],
w2 = w / 2,
h2 = h / 2;
this.poissonPoints = this.poissonDiskSampling(w, h, JXG.evaluate(this.radius));
// console.log(this.poissonPoints.length)
for (let i = 0; i < this.poissonPoints.length; i++) {
this.poissonPoints[i].x -= w2;
this.poissonPoints[i].y -= h2;
}
};
el.resample = function () {
// console.time('samplecurve')
el.sample();
this.updateDataArray();
// console.timeEnd('samplecurve')
}
el.resample();
return el;
};
JXG.registerElement('poissonsamplecurve', JXG.createPoissonSampleCurve);
// End external file
// ----------------------------------------------------------
// Use the new element
const board = JXG.board(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 pointscurve = board.create('poissonsamplecurve', [[-4, 4, 4, -4], 0.05], {
strokeWidth: 2, color: 'red'
});
// setInterval(() => { pointscurve.resample(); board.update(); }, 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.