algorithm - 如何找到二维数组中的最大圆

Question

给定一个二维 n*n 数组，每个元素是 + 或 x，我们如何找到最大圆直径仅由 + 个字符组成。

例如:

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

最大直径为 2，圆原点为圆心。

在所有情况下，圆可能不会在二维数组中居中。

有没有简单的算法可以解决这个问题？我不是在寻找代码只是一种算法。谢谢。

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

将是一个直径为 2 的圆来回答有关边的问题。

Answer 1

解决此问题的一种方法是将空闲单元格 (+) 想象成海洋，将其他单元格 (x) 想象成陆地。该算法在海岸线开始向各个方向流动的水波(直到它碰到另一个波浪或陆地)。被波浪覆盖的最后一片海是半径最大的圆心。

这导致了这个更正式的算法:

1. 设count 为空闲单元格的数量(+ 的数量)。
2. 如果count为零，无结果退出。
3. 创建一个数组 coast，其中包含已占用单元格的单元格坐标(那些带有 x 的单元格)
   • 还向海岸添加位于网格外的虚拟单元格，因为它们也代表“陆地”。
4. 将半径设为1

5. 获取具有此 radius 的圆的相对坐标(好像以单元格 [0, 0] 为中心)。所以对于半径 1 这将是:

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

6. 对于每个 centre = coast 中引用的单元格:

   • 使用此 centre 和 radius 获取圆上的空闲单元格，对于每个单元格:
     • 将其标记为已占用，并减少计数
     • 如果count 为零，那么我们有一个解决方案:这个单元格是要绘制的圆的中心，它的半径应该是radius-1。退出。
   • 如果此圆上的所有单元格均未空闲，则从 coast 中删除 centre(以避免将来进行不必要的检查)

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>