Poisson disc sampling.
ActivePublic
Actions

Authored by lyv on Sep 14 2018, 8:12 PM.

Tags

None

Referenced Files

	F645327: Poisson disc sampling.
	Sep 14 2018, 8:12 PM

Subscribers

elexis

FeXoR

nani

	Index: binaries/data/mods/public/maps/random/rmgen/math.js
	===================================================================
	--- binaries/data/mods/public/maps/random/rmgen/math.js (revision 21862)
	+++ binaries/data/mods/public/maps/random/rmgen/math.js (working copy)
	@@ -173,3 +173,58 @@

	return order;
	}
	+
	+function poissondiskSamples(width, height, r, k = 30)
	+{
	+ let cellSize = r / Math.sqrt(2); // sqrt of the dimension of the grid.
	+ let gridWidth = Math.ceil(width / cellSize);
	+ let gridHeight = Math.ceil(height / cellSize);
	+ let grid = new Array(gridWidth * gridHeight);
	+
	+ let point = new Vector2D(width * Math.random(), height * Math.random());
	+ let queue = [point];
	+ let gridX = Math.floor(point.x / cellSize);
	+ let gridY = Math.floor(point.y / cellSize);
	+
	+ grid[gridX + gridY * gridWidth] = point;
	+
	+ let ret = [];
	+ ret.push(point);
	+
	+ while (queue.length)
	+ {
	+ let randPoint = pickRandom(queue);
	+ queue.splice(0, 1);
	+
	+ for (let i = 0; i < k; ++i)
	+ {
	+ let randAngle = randomAngle();
	+ let randDist = r * Math.sqrt(3 * Math.random() + 1);
	+
	+ let newPoint = new Vector2D(randPoint.x + randDist * Math.cos(randAngle), randPoint.y + randDist * Math.sin(randAngle));
	+ if (newPoint.x < 0 \|\| newPoint.x > width \|\| newPoint.y < 0 \|\| newPoint.y > height)
	+ continue;
	+
	+ let [gridx, gridy] = [Math.floor(newPoint.x / cellSize), Math.floor(newPoint.y / cellSize)];
	+ let gridPoints = [];
	+
	+ for (let x = Math.max(gridx - 2, 0); x < Math.min(gridx + 3, gridWidth); ++x)
	+ for (let y = Math.max(gridy - 2, 0); y < Math.min(gridy + 3, gridHeight); ++y)
	+ {
	+ let gridPoint = grid[x + y * gridWidth]
	+ if (!gridPoint)
	+ continue;
	+ gridPoints.push(gridPoint);
	+ }
	+
	+ if (gridPoints.every(point => point.distanceTo(newPoint) > r))
	+ {
	+ queue.push(newPoint);
	+ grid[gridx + gridy * gridWidth] = newPoint;
	+ ret.push(newPoint);
	+ }
	+ }
	+ }
	+
	+ return ret;
	+}

Event Timeline

An interesting thing which can be useful. Used for distributing points uniformly (with slight random variations) in a given area.

nani added a subscriber: nani.Sep 15 2018, 12:37 AM

@FeXoR @elexis , is this worth having?

While this might be useful IMO this implementation is a bit over the top in terms of line numbers, resource use and complexity since a difference to other distributions like linear drop with distance or squarerooting (and at some point cutting) the radial parameter of a random roll will likely go unnoticed ;p

So I don't really see a need for this but if it's used in a map I'm OK to add it.

OFC I'm always happy to be educated (e.g. that it makes a notable difference) ;)

elexis changed the visibility from "All Users" to "Public (No Login Required)".Mar 20 2019, 4:17 PM

Poisson disc sampling.ActivePublicActions

Event Timeline

Poisson disc sampling.
ActivePublic
Actions