我需要一种算法来给我坐标到距离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来创建它,但它可以是任何东西。
你的目标不明确。你想要一个所有网格点的列表(或生成器),使它们距离给定点越来越远吗?在上市过程中,距离是否必须增加或稍微减少?从给定点开始采用“螺旋”模式有什么问题,点是在垂直和水平段中进行的,但基本模式离给定点更远? (这最后会很容易编程,似乎足以应付大多数搜索。) –
我认为https://stackoverflow.com/questions/3706219/algorithm-for-iterating-over-an-outward-spiral-on- a-discrete-2d-grid-from-the-or-或者你正在寻找的东西。 – barrycarter