# Procedural generation of evenly distributed random points (2d)

I am coming here because I've have a performance problem with my current implementation of an algorithm. I am the idea of Voronoi diagrams to distribute patches on an infinte 2d layer.

For a Voronoi pattern you need to have a set of points which is in my case procedural generated to allow an infinite generation of the Voronoi pattern.

And there is the problem. I have an algorithm which requires uses a grid of interval for the distance between each point on the grid. But I don't want a perfect square pattern so I add a randomization to each point on the grid with amplitude as possible randomization on X and Y axis. Here you can see how the points are shifted by adding the randomiation. (The randomization depends on the coordinates of the point on the grid to allow procedural generation. They are generatied by a noise map, but let's assume they are just a seed for a RNG)

And now we come to the performance problem. I have a point (x,y) which I need to find the nearest point. So what I do is I take all points within the maximum randomization amplitude and apply the randomization to get the points in my layer.

Now I take the random point with the shortest distance to my point (x,y) and return it. The performance of the code is exploding very quickly though.

n = amplitude / interval
runtime = (2n + 1)^2


A basic shape of the code is here, in the actual code I already use caching to avoid costly randomization of one point multiple times.

Vector2d currentlyBest = null;
double bestDistance = Double.POSITIVE_INFINITY;

double gridX = round(x / interval) * interval;
double gridY = round(y / interval) * interval;
for (double ix = 0; ix <= interval + amplitude; ix += interval) {
for (int loopX = -1; loopX < 2; loopX += 2) {
double dx = gridX + ix * loopX;
for (double iy = 0; iy <= interval + amplitude; iy += interval) {
for (int loopY = -1; loopY < 2; loopY += 2) {
double dy = gridY + iy * loopY;
Vector2d point = new Vector2d(dx, dy);
randomizePoint(point);

double px = point.x - x;
double py = point.y - y;
double disSq = px * px + py * py;
// save point if disSq is smaller than before
}
}
}
}


Thanks for reading so far! My question now is, if anyone knows a way to improve that or if you know a better way to produce evenly distributed randomized points on a 2d layer.

Thank you very much!

PS: I am not allowed to post more images so I can't give you more images, sadly :(

• Are you attached to this particular way of arranging the points in the first place? If you change the randomization so that [at most] one point is scattered randomly in each grid cell, then you only ever need to check a maximum of 9 cells for the closest point to any arbitrary location (if there is exactly one point in every cell, or 21 if using a suitable Poisson-disc-like distribution) – DMGregory Apr 26 '16 at 3:56
• Watch Rune Skovbo Johansen's video on the topic. – Engineer Apr 26 '16 at 5:13
• Thanks for the hint DMGregory, I already thought about limiting the user input, which would indeed make it a lot easier to check, I guess I can optimize the code for amplitude / interval <= 1. Thanks for the video Arcane Engineer, seems to be very useful and well thought. Very informative. – Slikey Apr 26 '16 at 8:24
• In case you end up succeeding, consider posting you did it. I am fairly interested in seeing different ways to optimize that problem (although my first guess would also be with a modification of Worley's Noise, as in Gato's answer) – MAnd Apr 26 '16 at 8:48
• Oh, yes of course I will, I am working on this now and I'll run the benchmarks later after checking code compatibility. – Slikey Apr 26 '16 at 10:12