algorithm - 二维圆形搜索模式

Question

我需要一种算法来为我提供二维网格中距离另一个单元格最近的单元格(按距离顺序)的坐标。它用于搜索算法，然后检查这些坐标是否适合各种事物。无论如何，到目前为止我想出了这个:

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

但如您所知，它有点废话，因为它跳过了一些单元格。我在那里做了一些假设:

1. 某个半径的圆的周长对应于该圆路径上的单元数。我不认为这会是一个太大的问题，因为半径中的实际单元格数量应该低于导致重复的圆周(少量是可以的)但不是排除(不可以)。

2. 指定第 n 个索引的圆的半径将略大于 Math.floor(Math.sqrt(idx/Math.PI))，因为半径每增加 1 对应于 2 * Math.PI 被添加到圆的周长。同样，应该会导致轻微重复但不会排除。

除此之外，我不知道它可能有什么问题，我的数学比这更复杂，所以可能与此有关。

也许已经有另一种类似的算法了？一个不跳过单元格的？语言并不重要，我正在使用 js 来制作原型(prototype)，但它可以是任何东西。

Answer 1

与其考虑完整的圆，不如考虑一个象限。稍后将其适应整个循环应该相当容易。为方便起见，使用 (0,0) 作为圆心。因此，您想按照非递减 x² + y² 的顺序列出具有 x,y ≥ 0 的网格单元。

一个有用的数据结构是优先级队列。它可用于跟踪每个 x 值的下一个 y 值，并且您可以提取具有最小 x² + < em>y² 很容易。

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)

因此对于大小为 n 的 Canvas ，这将枚举所有 n² 点，但优先级队列将仅包含 n 个元素最多。整个循环在 O(n² log(n)) 内运行。而且，如果您因为找到了要查找的内容而立即中止循环，与简单地对所有点进行排序相比，它仍然会变得更便宜。另一个好处是您可以专门使用整数运算，因此数字错误不会成为问题。一个缺点是 JavaScript 没有开箱即用的优先级队列，但我相信你可以找到一个你可以重用的实现，例如tiniqueue .

当做整圈时，你会生成 (−x,y) 除非 x=0，同样对于 (x,−y) 和 (−x,−y)。您可以通过仅在圆的 ⅛ 上循环来更多地利用对称性，即如果 xx,y+1) >=y，然后还生成 (y,x) 作为一个单独的点，除非 x=是的。对于许多用例而言，性能差异应该是微不足道的。

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