admin管理员组

文章数量:1320882

I want an array looking like this:

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

My first approach was to get the circumference

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

and with the resulting coords i could have juggled around to get the circular area. but i doubt that would be performant.

So my second approach would be to check every entry of the array whether it has a certain distance (i.e. radius) to the center of my circle. but for huge maps that wouldnt be performant either. perhaps checking only in a reasonable frame would be wiser.

but im certain there is a better approach for this problem. im needing this for a fog of war implementation.

I want an array looking like this:

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

My first approach was to get the circumference

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

and with the resulting coords i could have juggled around to get the circular area. but i doubt that would be performant.

So my second approach would be to check every entry of the array whether it has a certain distance (i.e. radius) to the center of my circle. but for huge maps that wouldnt be performant either. perhaps checking only in a reasonable frame would be wiser.

but im certain there is a better approach for this problem. im needing this for a fog of war implementation.

• javascript
• arrays
• geometry

Share Improve this question Follow edited Jun 2, 2015 at 7:06 InsOp asked Jun 1, 2015 at 23:05 InsOpInsOp 2,69955 gold badges3131 silver badges4545 bronze badges 5

• Is your 2d array of a known size or are there a fixed number of known sizes? – bhspencer Commented Jun 1, 2015 at 23:07
• 1 Seems to me the array will always be square and the values symmetric around a centre. You should only need to generate the pattern for 1/4, then flip to fill the adjacent quarter to get half, then flip that to get the rest. You can probably calculate the matrix for specific diameters and store them so you only have to do them once. – RobG Commented Jun 1, 2015 at 23:11
• 1 You can just pute one octant and then flip it around 7 times. The octant is very quick to pute with the Bresenham circle algorithm. To make things easier you may want to draw a whole quadrant. From circumference to filled circle is an easy step, just fill all that is left of the puted coordinate. – pid Commented Jun 1, 2015 at 23:16
• Are you sure that your second approach is unacceptable? If you pare the distance squared to the radius squared you don't even need a square root. The calculation will probably be insignificant pared to all the other operations you do on the element (rendering etc). Is the small increase in speed really worth the extra code plexity? – samgak Commented Jun 2, 2015 at 1:34
• the array could be of any size. @samgak as it turns out the second approach isnt that inacceptable. but its definitely worth having a more plex code, since the rendering happens on clientside, while fog of war calculation happens on serverside – InsOp Commented Jun 2, 2015 at 7:00

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 5

Your second suggested approach of testing each point in the array will be simple to implement, and can be optimized to just one subtract, one multiply and one test per element in the inner loop.

The basic test is ((x - centerX) * (x - centerX)) + ((y - centerY) * (y - centerY)) > radiusSq, but since ((y - centerY) * (y - centerY)) will be constant for a given row you can move that outside the loop.

Given that you have to visit each element in the array and set it anyway (meaning your algorithm will always be O(n²) on the circle radius), the test is a negligible cost:

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

I would use the mid-point circle algorithm and see the array as a bitmap.

I did this JavaScript implementation a while back, modified here to use an array as target source for the "pixel". Just note that a circle will produce odd widths and heights as the distance is always from a single center point and we can only use integer values in this case.

Tip: For speed improvements you could use typed array instead of a regular one (shown below).

Example

Make sure to use integer values as input, the code will clip values outside the "bitmap"/array -

var width = 7, height = 7,
    array = new Uint8Array(width * height);

// "draw" circle into array
circle(3, 3, 3);
renderDOM();

// circle example 2
width = height = 17;
array = new Uint8Array(width * height);

circle(8, 8, 8);
renderDOM();

function circle(xc, yc, r) {
  if (r < 1) return;

  var x = r, y = 0,  // for Bresenham / mid-point circle
      cd = 0,
      xoff = 0,
      yoff = r,
      b = -r,
      p0, p1, w0, w1;

  while (xoff <= yoff) {
    p0 = xc - xoff;
    p1 = xc - yoff;
    w0 = xoff + xoff;
    w1 = yoff + yoff;

    hl(p0, yc - yoff, yc + yoff, w0);  // fill a "line"
    hl(p1, yc - xoff, yc + xoff, w1);

    if ((b += xoff+++xoff) >= 0) {
      b -= --yoff + yoff;
    }
  }

  // for fill
  function hl(x, y1, y2, w) {
    w++;
    var xw = 0;
    while (w--) {
      xw = x + w;
      setPixel(xw, y1);
      setPixel(xw, y2);
    }
  }

  function setPixel(x, y) {
	if (x < width && y < height && x >= 0 && y >= 0)
		array[y * width + x] = 1;
  }
}

function renderDOM() {
  for(var i = 0, str = ""; i < array.length; i++) {
    if (i > 0 && !(i % width)) str += "<br>";
    str += array[i];
  }
  document.body.innerHTML += str + "<br><br>";
}

body {font:18px monospace}

For an odd-sized array (2r+1 x 2r+1),

for (row= 0; row < 2 * r + 1; row++)
{
  f= (row + 1) * (row - 2 * r - 1) + r * r + r;
  for (col= 0; col < 2 * r + 1; f+= 2 * (col - r) + 1; col++)
  {
    array[row][col]= f >= 0;
  }
}

本文标签： javascriptFill a 2d Array with circular areaStack Overflow