2D圓形搜索模式

Question

我需要一種算法來給我座標到距離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 
 
});

但正如你所知道的，它有點廢話，因爲它會跳過一些細胞。我在這裏做了一些假設：

1. 某個半徑的圓的周長對應於該圓的路徑上的單元數。我並不認爲這會有太大的問題，因爲半徑中的實際細胞數應該低於導致重複的周長（少量是可以的），但不排除（不好）。

2. 由於指定的第n個索引的圓的半徑略大於Math.floor（Math.sqrt（idx/Math.PI）），因爲每個增加1到半徑對應於2 * Math.PI被添加到圓的圓周。再次，應該導致輕微的重複，但不排除。

除此之外，我不知道什麼可能是錯的，我的數學考不及格，這所以大概是與任何更復雜。

也許有這樣的另一種算法已經出現在那裏？一個不跳過細胞？語言並不重要，我使用js來創建它，但它可以是任何東西。

Answer 1

不要考慮整個圓，而應考慮一個象限。稍後將其適用於整個圓周應該相當容易。爲方便起見，使用（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>