How to find the maximum circle in a 2D array

Question

Given a 2D n*n array with each element being either a + or a x, how can we find the maximum circle diameter made of only + chars.

For example:

xxxxx  
x++++
x+++x
x+++x
xxxxx

Would have a maximum diameter of 2 and the circle origin is the center.

The circle may not be centred in the 2D array in all cases.

Is there an easy algorithm to solve this? I'm not looking for code just an algorithm. Thanks.

xxxxx
xx+xx
x+++x
xx+xx
xxxxx

Would be a circle of diameter 2 to answer the question about edges.

Answer 1

A way to tackle this problem, is to imagine the free cells (+) as sea, and the other cells (x) as land. The algorithm starts a water-wave at the coast line(s) that flows in all directions (until it hits another wave or land). The last piece of sea that gets covered by a wave is a centre of a circle with greatest radius.

This leads to this more formal algorithm:

1. Let count be the number of free cells (number of +).
2. If count is zero, exit without result.
3. Create an array coast with cell-coordinates of occupied cells (those with x)
   • Add also to the coast the virtual cells that lie just outside the grid, as they also represent "land".
4. Set radius to 1

5. Get the relative coordinates of a circle with this radius (as if centred on cell [0, 0]). So for radius 1 this would be:

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

6. For each centre = cell referenced in coast:

   • Get the free cells on the circle with this centre and radius, and for each:
     • mark it as occupied, and decrease count
     • if count is zero, then we have a solution: this cell is the centre of the circle to draw, and it should have a radius of radius-1. Exit.
   • If none of the cells on this circle was free, remove centre from coast (to avoid unnecessary checks in the future)

  7. Increase radius and repeat from step 5.

When the algorithm exits with a result (a centre and a radius), it is straightforward to overlay the given grid with the actual disk.

Here is an implementation in JavaScript (without using any of the newer syntax, so it should be straightforward to read), which you can run here:

"use strict";
function circleCoordinates(radius) {
    var cells = [];
    var r2 = (radius+0.41)*(radius+0.41); // constant determines margin
    var i = 0;
    var j = radius;
    while (i <= j) {
        cells.push([ i,  j]);
        cells.push([ i, -j]);
        if (i < j) {
            cells.push([ j,  i]);
            cells.push([-j,  i]);
        }
        if (i) {
            cells.push([-i,  j]);
            cells.push([-i, -j]);
            if (i < j) {
                cells.push([j,  -i]);
                cells.push([-j, -i]);
            }
        }
        i++;
        if (i*i + j*j > r2) {
            j--; 
            // Decrementing i here is not standard, but needed to make 
            // sure we cover the surface added compared to a disk with 
            // a radius of one unit one less.            
            i--;
        }
    }
    return cells;
}

function solve(a) {
    var i, j, k, l, m, n, count, coast, circle, reduced, radius, b;

    function get(b, i, j) {
        if (i < 0 || j < 0 || i >= b.length || j >= b[i].length)
            return 1;
        return b[i][j];
    }

    // Copy input, count free cells, and collect the others in "coast"
    count = 0;
    coast = [];
    b = [];
    for (i = 0; i < a.length; i++) {
        b[i] = [];
        for (j = 0; j < a[i].length; j++) {
            b[i].push(a[i][j]); // copy array element
            count += !b[i][j]; // count free cells
            if (b[i][j]) coast.push([i,j]); // push occupied cells
        }
    }
    if (!count) return; // no solution
    // To bound the area, add virtual border cells in 'coast':
    for (i = 0; i < b.length; i++) {
        coast.push([i, -1], [i, b[i].length]);
    }
    for (j = 0; j < b[0].length; j++) {
        coast.push([-1, j], [b.length, j]);
    }
    // Keep reducing free space by drawing circles from the coast
    // until one free cell is left over.
    radius = 0;
    while (count) {
        radius++;
        circle = circleCoordinates(radius);
        for (k = coast.length - 1; (k >= 0) && count; k--) {
            reduced = false;
            for (l = 0; (l < circle.length) && count; l++) {
                m = coast[k][0] + circle[l][0];
                n = coast[k][1] + circle[l][1];
                if (!get(b, m, n)) {
                    b[m][n] = radius+1;
                    count--;
                    reduced = true;
                }
            }
            // Save some time by removing the cell in the coast
            // list that had no reducing effect anymore:
            if (!reduced) coast.splice(k, 1);
        }
    }
    // Greatest circle has a radius that is one smaller:
    radius--;
    // Restore array to original
    for (i = 0; i < b.length; i++) {
        for (j = 0; j < b[i].length; j++) {
            b[i][j] = a[i][j];
        }
    }
    // Draw a disc centered at i, j
    circle = circleCoordinates(radius);
    for (l = 0; l < circle.length; l++) {
        for (k = m + circle[l][0]; k <= m - circle[l][0]; k++) {
            b[k][n+circle[l][1]] = 2;
        }
    }
    // Return the array with the marked disc
    return b;
}

// String handling

function cleanText(txt) {
    return txt.trim().replace(/[ \r\t]/g, '').replace(/[^x\n]/g, '+');
}

function textToArray(txt) {
    var lines, a, i, j;
    // Clean text and split into lines
    lines = cleanText(txt).split('\n');
    // convert to 2D array of 0 or 1:
    a = [];
    for (i = 0; i < lines.length; i++) {
        a[i] = [];
        for (j = 0; j < lines[i].length; j++) {
            a[i][j] = +(lines[i][j] !== '+'); // '+' => 0, 'x' => 1
        }
    }
    return a;
}

function arrayToText(a) {
    // Convert 2D array back to text. 2-values will be translated to '#'
    var lines, i, j;
    lines = [];
    for (i = 0; i < a.length; i++) {
        lines[i] = [];
        for (j = 0; j < a[i].length; j++) {
            lines[i][j] = '+x#'[a[i][j]]; // mark disc with '#'
        }
        lines[i] = lines[i].join('');
    }
    return lines.join('\n');
}

// I/O handling for snippet:

var inp = document.querySelector('textarea');
var solveBtn = document.querySelector('#solve');
var clearBtn = document.querySelector('#clear');

solveBtn.onclick = function() {
    // Convert input to 2D array of 0 and 1 values:
    var a = textToArray(inp.value);
    // Draw greatest disk by replacing 0-values with 2-values:
    a = solve(a);
    // Convert 2D array back to text. 2-values will be translated to '#'
    inp.value = arrayToText(a);
};

clearBtn.onclick = function() {
    inp.value = cleanText(inp.value);
};

<button id="solve">Show Greatest Disc</button>
<button id="clear">Remove Disc</button><br>
<textarea rows=10>
xxxxxxxxxxxxxxxxxx
xxxxx++++++x++++++
+++x+++++++x+++++x
++++x+++++++++++x+
++++x+++++x++++x++
+++x+++++++x+++x+x
x+++++xx+++++x++++
xx+++++x+++++x+++x
++++++xxxx++xxxx++
xxx++xxxxxxxxxxxx+
++xxxxxxxxx+xxxxxx</textarea>
<pre></pre>