如何在一个二维数组中找到最大的圆形

Question

给定一个 n*n 的二维数组，每个元素要么是 +， 要么是 x。如何找到只由 + 组成的最大圆直径。

例如：

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

这个圆的直径最大为2，圆心位于中心。

在某些情况下，这个圆可能不在二维数组的中心。

有没有一种简单的算法来解决这个问题？我不需要代码，只需要一个算法。谢谢。

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

如果要回答关于边缘的问题，直径为2的圆将是一个好的选择。

- JVDM92

---

在这个问题中，圆的定义是什么？只有两条垂直且长度相同的直径吗？我的意思是，在你的例子中，你有一个3x3的+正方形。如果边缘是x，它会被认为是一个圆吗？另外，为什么你的例子直径是2而不是3？ - Santiago Gil

如果边缘是x，则被视为一个圆。 - JVDM92

你需要明确定义“圆”的意思。那么，哪些数组元素属于某个半径的圆呢？显然不是被圆所交叉的元素集合，正如你的第二个例子所示。 - Nico Schertler

我猜你指的是出租车度量中的磁盘（而不是圆形）。但是，我宁愿不猜测，而是希望你能解释一下。 - John Coleman

“出租车距离圆”是菱形的。我怀疑你的意思不是这个？你是指像这样的圆吗：“中点圆算法”？ - trincot

Answer 1

一种解决这个问题的方法是将空单元格（+）想象为海洋，而其他单元格（x）则为陆地。该算法从海岸线处开始产生水波，水波在所有方向上流动（直到遇到另一波或陆地）。被水波覆盖的最后一个海洋区域是具有最大半径的圆的中心。

这导致了以下更正式的算法：

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. 增加 radius 并从第5步重复。

当算法输出结果（圆心和半径）时，可以直接将给定的网格与实际的圆盘叠加。

以下是JavaScript的实现（不使用任何新语法，因此应该很容易阅读），您可以在这里运行：

"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>

- trincot