javascript - 用圆形区域填充二维数组

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

根据生成的坐标，我可以四处寻找圆形区域。但我怀疑这是否有效。

所以我的第二种方法是检查数组的每个条目是否与我的圆心有一定的距离(即半径)。但是对于性能也不佳的巨大 map 。也许只在合理的范围内检查会更明智。

但我确定有更好的方法来解决这个问题。我需要这个来实现 war 迷雾。

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