"Heat spot" image generation I wrote a function that generates an image like:



The function is as follows:

    /** Draws a texture wherein are spots of "heat" where a pixel's spotColor is of highest alpha, fading as distance from heat
     * spots increases.
     * @param width
     * @param height
     * @param spotColor The color of the spots, ignores alpha.
     * @param density
     * @return */
    public static Texture drawHeatSpots (int width, int height, Color spotColor, Magnitude density) {
        Pixmap p = new Pixmap(width, height, Format.RGBA8888);

        int spotCount;
        if (density == Magnitude.high)
            spotCount = width * height / 5000;
        else if (density == Magnitude.medium)
            spotCount = width * height / 6500;
        else if (density == Magnitude.low)
            spotCount = width * height / 8000;
        else
            throw new IllegalArgumentException(density.name() + " is an invalide Magnitude");

        Array&lt;Vector2&gt; spots = new Array&lt;&gt;();
        boolean next;

        for (int i = 0; i &lt; spotCount; i++) {
            next = false;
            while (!next) {
                Vector2 v = new Vector2(MathUtils.random(width), MathUtils.random(height));
                if (!spots.contains(v, false)) {
                    spots.add(v);
                    next = true;
                }
            }
        }

        Vector2 v = new Vector2();
        Color c = new Color(spotColor);

        for (int x = 0; x &lt; width; x++) {
            for (int y = 0; y &lt; height; y++) {
                v.set(x, y);
                if (spots.contains(v, false)) {
                    c.a = 1;
                    p.drawPixel(x, y, Color.rgba8888(c));
                    continue;
                }
                c.a = calcAlpha(v, spots);
                p.drawPixel(x, y, Color.rgba8888(c));
            }
        }

        return new Texture(p);
    }

    private static float calcAlpha (Vector2 pos, Array&lt;Vector2&gt; spots) {
        float a = 0;
        for (Vector2 v : spots) {
            a += 1f / Math.sqrt(Math.pow(pos.x - v.x, 2) + Math.pow(pos.y - v.y, 2));
        }
        if (a &gt; 1) a = 1;
        if (a &lt; 0) a = 0;

        return a;
    }
}


In the picture, the magnitude is at high and it takes roughly 3 seconds to generate the image. At low, it takes about 2 seconds. Preferably, I would like the generation to take less than 1 second on high (without decreasing the number of spots).

Is there any way I can speed up the generation of this image? Or is this the best and fastest way to get an image similar to the one?
Time Complexity

Although you should always profile when concerned with performance. I'll go out on a limb here and make an educated guess.

    for (int x = 0; x &lt; width; x++) {
        for (int y = 0; y &lt; height; y++) {
            v.set(x, y);
            if (spots.contains(v, false)) {
                c.a = 1;
                p.drawPixel(x, y, Color.rgba8888(c));
                continue;
            }
            c.a = calcAlpha(v, spots);
            p.drawPixel(x, y, Color.rgba8888(c));
        }
    }


Here spots.contains and calcAlpha are both \$\mathcal{O}(n)\$ where \$n\$ is the number of spots. This means that for example the inner most loop of calcAlpha:

    for (Vector2 v : spots) {
        a += 1f / Math.sqrt(Math.pow(pos.x - v.x, 2) + Math.pow(pos.y - v.y, 2));
    }


is executed \$w \cdot h \cdot \frac{w\cdot h}{5000} = \frac{(w\cdot h)^2}{5000} = 169869312\$ times for 1280x720 (which I gather from your screenshot). Notice the square on \$w\cdot h\$? That's your problem. 

How to solve it? Well you can use a HashSet for spots, this reduces spot.contains to \$\mathcal{O}(1)\$ amortized. But you're still left with calcAlpha.

You need to come up with a smarter algorithm that doesn't have to iterate over all the spots for all pixels.

Cache Efficiency

The CPU has a little thing called a "pre-fetcher". Simply put when you ask for memory address x it will also make sure that x+1 and x-1 are in the CPU cache. This means that linear access of memory is much faster than any other way of addressing memory. Particularly, "randomly" accessing memory is bound to give you a metric f-ton of cache misses and your performance will be a proper charlie-foxtrot.

I am not aware of any graphics library or hardware that stores images in column-major mode. This means that you should always process images, row-by-row. Meaning that the x coordinate should always be the inner most loop.

I.e. this:

for (int x = 0; x &lt; width; x++) {
    for (int y = 0; y &lt; height; y++) {


should be:

for (int y = 0; y &lt; height; y++) {
    for (int x = 0; x &lt; width; x++) {


for maximal performance (note the swapped order of x and y).

Improved Algorithm

The key idea to note for improving the algorithm is that each of the spots has the same influence on it's neighbourhood. I.e. all the distance calculations for each dot are the same, just with a different offset. This means that we can pre-calculate the results once and just blit.

Define radius as the radius in pixels from a spot where you cut off it's influence on the image.

Below is pseudocode to show the idea. It may contain bugs, and there is definitely some assembly required. Like checking image bounds and using a 1D dense array instead of a 2D nested array (which is done for clarity):

// Prepare alpha-map.
// Time: O(radius^2)
float[][] alphaMap = new float[2*radius+1][2*radius+1];
for(int y = 0; y &lt; 2*radius + 1; ++y){
    for(int x = 0; x &lt; 2*radius +1; ++x){
        int dx = x - radius;
        int dy = y - radius;
        int hypot2 = dx*dx + dy*dy;
        if(dx == 0 &amp;&amp; dy == 0){
            alphaMap[y][x] = 1.0f;
        }else if (hypot2 &lt; radius*radius){
            alphaMap[y][x] = 1.0f / Math.sqrt(hypot2); 
        }
    }
}

// Calculate alpha values for entire image at once
// Time: O((w*h)*radius^2)
float[][] alphaBuffer = new float[height][width];
for(spot : spots){
    int xMin = spot.x - radius;
    int xMax = spot.x + radius +1;
    int yMin = spot.y - radius;
    int yMax = spot.y + radius +1;
    for(int y = yMin; y &lt; yMax; ++y){
        int dy = y - spot.y;
        for(int x = xMin; x &lt; xMax; ++x){
            int dx = x - spot.x;
            alphaBuffer[y][x] += alphaMap[radius + dy][radius + dx];
        }
    }
}


Note that this has the same asymptotic time complexity as OP's own answer \$\mathcal{O}(whr^2)\$. But this computes the reciprocal of the hypotenuse only \$\pi r^2\$ times while OPs answer does it \$\frac{wh}{5000}\pi r^2\$ times. The calculation of the reciprocal of the hypotenuse is the most time consuming part in this algorithm and should dominate the execution time.

Note: The observant reader will have noticed that the alphaMap grid is symmetrical in all quadrants. This means you can reduce the number of calculations of the reciprocal of the hypotenuse to \$\frac{\pi r^2}{4}\$ but that's left as an exercise to the reader.