用圆形区域填充二维数组

Question

我想要一个看起来像这样的数组：

[
[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],
]

我的第一个方法是获取周长

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]);
    }
}

有了最终的坐标，我就可以巧妙地得到圆形区域。但我怀疑这是否有效。

所以我的第二种方法是检查数组的每个条目是否到我的圆心有一定的距离（即半径）。但对于巨大的地图来说，性能也不佳。也许只在合理的框架内进行检查会更明智。

但我确信有更好的方法来解决这个问题。我需要这个来实施战争迷雾。

Answer 1

您建议的第二种测试数组中每个点的方法将很容易实现，并且可以优化为仅对内循环中的每个元素进行一次减法、一次乘法和一次测试。

基本测试是((x - centerX) * (x - centerX)) + ((y - centerY) * (y - centerY)) > radiusSq，但由于((y - centerY) * (y - centerY))对于给定行来说是恒定的，因此您可以将其移到循环之外。

鉴于您必须访问数组中的每个元素并无论如何设置它（意味着您的算法在圆半径上始终为 O(n ² )），因此测试的成本可以忽略不计：

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