3
\$\begingroup\$

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. Grid Pattern without randomization

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. Image with last stage of algorithm

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – DMGregory Apr 26 '16 at 3:56
  • \$\begingroup\$ Watch Rune Skovbo Johansen's video on the topic. \$\endgroup\$ – Engineer Apr 26 '16 at 5:13
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Slikey Apr 26 '16 at 8:24
  • \$\begingroup\$ 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) \$\endgroup\$ – MAnd Apr 26 '16 at 8:48
  • \$\begingroup\$ Oh, yes of course I will, I am working on this now and I'll run the benchmarks later after checking code compatibility. \$\endgroup\$ – Slikey Apr 26 '16 at 10:12
4
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Yeah, I've looked at worley's noise earlier and didn't think it suits my needs, but I might be able to extract the idea and use it for my needs, now that you added that extra-thought to it. Thank you! \$\endgroup\$ – Slikey Apr 26 '16 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.