2D圆形搜索模式
我需要一种算法来给我坐标到距离2D网格中另一个单元格最近的单元格（按距离顺序）。它的搜索算法，然后检查这些坐标适合各种事情。不管怎么说，到目前为止，我想出了这个：2D圆形搜索模式
function testy(cx, cy, idx) {
\t var radius = Math.floor(Math.sqrt(idx/Math.PI));
\t var segment = Math.round(idx - (radius * Math.PI));
\t var angle = segment/radius;
\t var x = Math.round(cx + radius * Math.cos(angle));
\t var y = Math.round(cy + radius * Math.sin(angle));
\t return [x, y];
}
addEventListener("load", function() {
\t var canv = document.createElement("canvas");
\t document.body.appendChild(canv);
\t canv.width = 800;
\t canv.height = 600;
\t var ctx = canv.getContext("2d");
\t
\t var scale = 5;
\t var idx = 0;
\t var idx_end = 10000;
\t
\t var func = function() {
\t \t var xy = testy(0,0,idx++);
\t \t var x = xy[0] * scale + canv.width/2;
\t \t var y = xy[1] * scale + canv.height/2;
\t \t ctx.rect(x, y, scale, scale);
\t \t ctx.fill();
\t \t
\t \t if (idx < idx_end) setTimeout(func, 0);
\t }
\t
\t func();
\t
});但正如你所知道的，它有点废话，因为它会跳过一些细胞。我在这里做了一些假设：
某个半径的圆的周长对应于该圆的路径上的单元数。我并不认为这会有太大的问题，因为半径中的实际细胞数应该低于导致重复的周长（少量是可以的），但不排除（不好）。
由于指定的第n个索引的圆的半径略大于Math.floor（Math.sqrt（idx/Math.PI）），因为每个增加1到半径对应于2 * Math.PI被添加到圆的圆周。再次，应该导致轻微的重复，但不排除。
除此之外，我不知道什么可能是错的，我的数学考不及格，这所以大概是与任何更复杂。
也许有这样的另一种算法已经出现在那里？一个不跳过细胞？语言并不重要，我使用js来创建它，但它可以是任何东西。
不要考虑整个圆，而应考虑一个象限。稍后将其适用于整个圆周应该相当容易。为方便起见，使用（0,0）作为圆心。所以你想列出的网格单元格为x，y≥0的顺序是非递减的x 2 + y²。
一个有用的数据结构是优先级队列。它可以用来保存每一个X值的下一个Ÿ价值的轨道，并且可以提取一个以最小X²+ Ÿ²容易。因此，对于大小ň的帆布
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)
这将枚举所有ñ²点，但优先级队列将只包含最多ñ元素。整个循环运行在O（n 2 log（n））。如果你因为找到了你想要的东西而中断了时间循环，那么与简单分类所有点相比，它仍然更便宜。另一个好处是你可以完全使用整数运算，所以数字错误不会成为问题。其中一个缺点是JavaScript没有提供开箱即用的优先级队列，但我相信您可以找到一个可以重复使用的实现，例如， tiniqueue。
在做了一圈，你会产生（ - X，ÿ）除非X = 0，同样的（X， - ÿ）和（ - X， - 和）。你可以通过仅将具有循环超过圆的⅛，即不插入（X，ÿ 1）如果X = ÿ，然后也产生（ý利用对称多一点， x）作为单独的点，除非x = y。在很多使用情况下，性能差异应该是微乎其微的。
"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() {
\t const canv = document.createElement("canvas");
\t document.body.appendChild(canv);
const cw = 800, ch = 600;
\t canv.width = cw;
\t canv.height = ch;
\t const ctx = canv.getContext("2d");
\t
\t 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;
\t var func = function() {
\t \t 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)";
\t \t ctx.fillRect(0, 0, cw, ch);
\t ctx.fillStyle = "rgb(0,0,0)";
}
\t \t ctx.fillRect(value.x * scale, value.y*scale, scale, scale);
setTimeout(func, 0);
\t }
\t
\t func();
\t
});<script type="text/javascript">module={};</script>
<script src="https://cdn.rawgit.com/mourner/tinyqueue/54dc3eb1/index.js"></script>
你的目标不明确。你想要一个所有网格点的列表（或生成器），使它们距离给定点越来越远吗？在上市过程中，距离是否必须增加或稍微减少？从给定点开始采用“螺旋”模式有什么问题，点是在垂直和水平段中进行的，但基本模式离给定点更远？ （这最后会很容易编程，似乎足以应付大多数搜索。） –
我认为https://stackoverflow.com/questions/3706219/algorithm-for-iterating-over-an-outward-spiral-on- a-discrete-2d-grid-from-the-or-或者你正在寻找的东西。 – barrycarter