Fill a 2d Array with circular area

Question

I want an array looking like this:

[
[0,0,1,1,1,0,0],
[0,1,1,1,1,1,0],
[1,1,1,1,1,1,1],
[1,1,1,1,1,1,1],
[1,1,1,1,1,1,1],
[0,1,1,1,1,1,0],
[0,0,1,1,1,0,0],
]

My first approach was to get the circumference

var steps = 100;
var coord = [];
var x,y;
for (var i = 0; i < steps; i++) {
    var phase = 2 * Math.PI * i / steps;
    x = Math.round(cenx + range * Math.cos(phase));
    y = Math.round(ceny + range * Math.sin(phase))

    if(x>=0 && y >=0){
        coord.push([x,y]);
    }
}

and with the resulting coords i could have juggled around to get the circular area. but i doubt that would be performant.

So my second approach would be to check every entry of the array whether it has a certain distance (i.e. radius) to the center of my circle. but for huge maps that wouldnt be performant either. perhaps checking only in a reasonable frame would be wiser.

but im certain there is a better approach for this problem. im needing this for a fog of war implementation.

Answer 1

Your second suggested approach of testing each point in the array will be simple to implement, and can be optimized to just one subtract, one multiply and one test per element in the inner loop.

The basic test is ((x - centerX) * (x - centerX)) + ((y - centerY) * (y - centerY)) > radiusSq, but since ((y - centerY) * (y - centerY)) will be constant for a given row you can move that outside the loop.

Given that you have to visit each element in the array and set it anyway (meaning your algorithm will always be O(n²) on the circle radius), the test is a negligible cost:

    // circle generation code:
    function makeCircle(centerX, centerY, radius, a, arrayWidth, arrayHeight)
    {
        var x, y, d, yDiff, threshold, radiusSq;
        radius = (radius * 2) + 1;
        radiusSq = (radius * radius) / 4;
        for(y = 0; y < arrayHeight; y++)
        {
            yDiff = y - centerY;
            threshold = radiusSq - (yDiff * yDiff);
            for(x = 0; x < arrayWidth; x++)
            {
                d = x - centerX;
                a[y][x] = ((d * d) > threshold) ? 0 : 1;
            }
        }
    }
    
    // test code:
    var width = 7;
    var dim = (width * 2) + 1;
    var array = new Array(dim);
    for(row = 0; row < dim; row++)
        array[row] = new Array(dim);
    
    makeCircle(width, width, width, array, dim, dim);
    
    for(var y = 0, s = ""; y < dim; y++)
    {
        for(var x = 0; x < dim; x++)
        {
            s += array[y][x];
        }
        s += "<br>";
    }
    document.body.innerHTML += s + "<br>";