2D Circular search pattern

Question

I need an algorithm to give me coordinates to the nearest cells (in order of distance) to another cell in a 2D grid. Its for a search algorithm that then checks those coordinates for all sorts of things for suitability. Anyways, so far I came up with this:

function testy(cx, cy, idx) {
 var radius = Math.floor(Math.sqrt(idx / Math.PI));
 var segment = Math.round(idx - (radius * Math.PI));
 var angle = segment / radius;
 var x = Math.round(cx + radius * Math.cos(angle));
 var y = Math.round(cy + radius * Math.sin(angle));
 return [x, y];
}

addEventListener("load", function() {
 var canv = document.createElement("canvas");
 document.body.appendChild(canv);
 canv.width = 800;
 canv.height = 600;
 var ctx = canv.getContext("2d");
 
 var scale = 5;
 var idx = 0;
 var idx_end = 10000;
 
 var func = function() {
  var xy = testy(0,0,idx++);
  var x = xy[0] * scale + canv.width / 2;
  var y = xy[1] * scale + canv.height / 2;
  ctx.rect(x, y, scale, scale);
  ctx.fill();
  
  if (idx < idx_end) setTimeout(func, 0);
 }
 
 func();
 
});

but as you can tell, its kinda crap because it skips some cells. There's a few assumptions I'm making there:

1. That the circumference of a circle of a certain radius corresponds to the number of cells on the path of that circle. I didn't think that would be too great of a problem though since the actual number of cells in a radius should be lower than the circumference leading to duplication(which in small amounts is ok) but not exclusion(not ok).

2. That the radius of a circle by the n-th index specified would be slightly more than Math.floor(Math.sqrt(idx / Math.PI)) because each increase of 1 to the radius corresponds to 2 * Math.PI being added to the circumference of the circle. Again, should lead to slight duplication but no exclusion.

Other than that I have no idea what could be wrong with it, I fail at math any more complex than this so probably something to do with that.

Perhaps there is another algorithm like this already out there though? One that doesn't skip cells? Language doesn't really matter, I'm using js to prototype it but it can be whatever.

Answer 1

Instead of thinking about the full circle, think about a quadrant. Adapting that to the full circle later should be fairly easy. Use (0,0) as the center of the circle for convenience. So you want to list grid cells with x,y ≥ 0 in order of non-decreasing x² + y².

One useful data structure is a priority queue. It can be used to keep track of the next y value for every x value, and you can extract the one with minimal x² + y² easily.

q = empty priority queue, for easy access to element with minimal x²+y²
Insert (0,0) into queue
while queue is not empty:
  remove minimal element from queue and call it (x,y)
  insert (x,y+1) into queue unless y+1 is off canvas
  if y = 0:
    insert (x+1,0) into queue unless x+1 is off canvas
  do whatever you want to do with (x,y)

So for a canvas of size n this will enumerate all the n² points, but the priority queue will only contain n elements at most. The whole loop runs in O(n² log(n)). And if you abort the loop eraly because you found what you were looking for, it gets cheaper still, in contrast to simply sorting all the points. Another benefit is that you can use integer arithmetic exclusively, so numeric errors won't be an issue. One drawback is that JavaScript does not come with a priority queue out of the box, but I'm sure you can find an implementation you can reuse, e.g. tiniqueue.

When doing full circle, you'd generate (−x,y) unless x=0, and likewise for (x,−y) and (−x,−y). You could exploit symmetry a bit more by only having the loop over ⅛ of the circle, i.e. not inserting (x,y+1) if x=y, and then also generating (y,x) as a separate point unless x=y. Difference in performance should be marginal for many use cases.

"use strict";

function distCompare(a, b) {
  const a2 = a.x*a.x + a.y*a.y;
  const b2 = b.x*b.x + b.y*b.y;
  return a2 < b2 ? -1 : a2 > b2 ? 1 : 0;
}

// Yields points in the range -w <= x <= w and -h <= y <= h
function* aroundOrigin(w,h) {
  const q = TinyQueue([{x:0, y:0}], distCompare);
  while (q.length) {
    const p = q.pop();
    yield p;
    if (p.x) yield {x:-p.x, y:p.y};
    if (p.y) yield {x:p.x, y:-p.y};
    if (p.x && p.y) yield {x:-p.x, y:-p.y};
    if (p.y < h) q.push({x:p.x, y:p.y+1});
    if (p.y == 0 && p.x < w) q.push({x:p.x + 1, y:0});
  }
}

// Yields points around (cx,cy) in range 0 <= x < w and 0 <= y < h
function* withOffset(cx, cy, w, h) {
  const delegate = aroundOrigin(
    Math.max(cx, w - cx - 1), Math.max(cy, h - cy - 1));
  for(let p of delegate) {
    p = {x: p.x + cx, y: p.y + cy};
    if (p.x >= 0 && p.x < w && p.y >= 0 && p.y < h) yield p;
  }
}

addEventListener("load", function() {
 const canv = document.createElement("canvas");
 document.body.appendChild(canv);
  const cw = 800, ch = 600;
 canv.width = cw;
 canv.height = ch;
 const ctx = canv.getContext("2d");
 
 const scale = 5;
  const w = Math.ceil(cw / scale);
  const h = Math.ceil(ch / scale);
  const cx = w >> 1, cy = h >> 1;
  const pointgen = withOffset(cx, cy, w, h);
  let cntr = 0;

 var func = function() {
  const {value, done} = pointgen.next();
    if (done) return;
    if (cntr++ % 16 === 0) {
      // lighten older parts so that recent activity is more visible
      ctx.fillStyle = "rgba(255,255,255,0.01)";
    ctx.fillRect(0, 0, cw, ch);
     ctx.fillStyle = "rgb(0,0,0)";
    }
  ctx.fillRect(value.x * scale, value.y*scale, scale, scale);
    setTimeout(func, 0);
 }
 
 func();
 
});

<script type="text/javascript">module={};</script>
<script src="https://cdn.rawgit.com/mourner/tinyqueue/54dc3eb1/index.js"></script>