Procedural generation of evenly distributed random points (2d)

Question

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 :(

Answer 1

I guess what you're looking for is what's called "Worley's Noise".

An In Depth Cell Noise Tutorial (archived)

It's very similar to what you're already doing. But instead of placing the points at the corners of the grid and moving them around, you place one (or more) points within each cell at random. When you want to find the closest point to a point P, you find which cell the point P lies in, and then start from that cell outwards. There will be a moment where all other cells are further away from the closest point you already have, and then you stop. If there's always one (or more) points within each cell, you'll never need to search in more than 9 cells (assuming this is in 2D)