循環遍歷一個沒有重複索引的圓形數組

Question

我需要循環遍歷一個小圓弧的圓弧形數組（像像素繪製一個圓圈一樣），但是我試過的所有算法都檢查數組的重複索引（它有幾次相同的x和y）。 我有一個半徑爲3的圓形28個元素（未填充），但算法重複360次。我可以在我做某件事之前檢查x或y是否改變，但這是跛腳。

我現在代碼：

for (int radius = 1; radius < 6; radius++) 
{ 
    for (double i = 0; i < 360; i += 1) 
    { 
     double angle = i * System.Math.PI/180; 
     int x = (int)(radius * System.Math.Cos(angle)) + centerX; 
     int y = (int)(radius * System.Math.Sin(angle)) + centerY; 

     // do something 
     // if (array[x, y]) .... 
    } 
}  

PS：我不能使用中點畫圓，因爲我需要增加半徑從2至6，得到不是每個指標，因爲他的圈子裏是不是真的（根據三角）

編輯： 我真正需要的是從中心開始掃描一個完整的圓形邊緣。

360步（這是獲取所有座標）：

Full scan

for (int radius = 2; radius <= 7; radius++) 
{ 
    for (double i = 0; i <= 360; i += 1) 
    { 
     double angle = i * System.Math.PI/180; 
     int x = (int)(radius * System.Math.Cos(angle)); 
     int y = (int)(radius * System.Math.Sin(angle)); 
     print(x, y, "X"); 
    } 
} 

使用中點畫圓或其它算法跳過步驟（缺少的座標）：

Midpoint Circle Algorithm

for (int radius = 2; radius <= 7; radius++) 
{ 
    int x = radius; 
    int y = 0; 
    int err = 0; 
    while (x >= y) 
    { 
     print(x, y, "X"); 
     print(y, x, "X"); 
     print(-y, x, "X"); 
     print(-y, x, "X"); 
     print(-x, y, "X"); 
     print(-x, -y, "X"); 
     print(-y, -x, "X"); 
     print(y, -x, "X"); 
     print(x, -y, "X"); 

     y += 1; 
     err += 1 + 2 * y; 
     if (2 * (err - x) + 1 > 0) 
     { 
      x -= 1; 
      err += 1 - 2 * x; 
     } 
    } 
} 

Answer 1

有兩種算法思想在這裏玩：一個是光柵化一個圓圈。 OP代碼在這方面提供了一些改進機會：（a）不需要對整個360度圓進行採樣，就可以認識到一個圓在兩個軸上是對稱的。 （x，y）可以在其他三個象限中反映爲（-x，y），（-x，-y）和（x，-y）。 （b）環路上的臺階應與曲率有關。一個簡單的啓發式就是使用半徑作爲步驟。所以...

let step = MIN(radius, 90) 
for (double i=0; i<90; i += step) { 
    add (x,y) to results 
    reflect into quadrants 2,3,4 and add to results 
} 

有了這些改進，您可能不再關心重複生成的樣本。如果你仍然這麼做，那麼獨立於圓圈的第二個想法是如何散列一對整數。這裏有一篇很好的文章：Mapping two integers to one, in a unique and deterministic way。

簡而言之，我們計算從我們的X一個int，y對有保證唯一映射，然後檢查爲重複...

cantor(x, y) = 1/2(x + y)(x + y + 1) + y 

這僅適用於X，Y的正值，這正是你需要的，因爲我們只是在第一象限中進行計算（然後反射）。對於每一對，請檢查它們是否唯一

let s = an empty set 
int step = MIN(radius, 90) 
for (double i=0; i<90; i += step) { 
    generate (x,y) 
    let c = cantor(x,y) 
    if (not(s contains c)) { 
     add (x,y) to results 
     reflect into quadrants 2,3,4 and add to results 
     add c to s 
    } 
} 

Answer 2

知道了！

這不是美麗的，但爲我工作。

int maxRadius = 7; 

for (int radius = 1; radius <= maxRadius; radius++) 
{ 
    x = position.X - radius; 
    y = position.Y - radius; 
    x2 = position.X + radius; 
    y2 = position.Y + radius; 
    for (int i = 0; i <= radius * 2; i++) 
    { 
     if (InCircle(position.X, position.Y, x + i, y, maxRadius)) // Top X 
      myArray[position, x + i, y]; // check array 

     if (InCircle(position.X, position.Y, x + i, y2, maxRadius)) // Bottom X 
      myArray[position, x + i, y2]; // check array 

     if (i > 0 && i < radius * 2) 
     { 
      if (InCircle(position.X, position.Y, x, y + i, maxRadius)) // Left Y 
       myArray[position, x, y + i]; // check array 

      if (InCircle(position.X, position.Y, x2, y + i, maxRadius)) // Right Y 
       myArray[position, x2, y + i]; // check array 
     } 
    } 
} 


public static bool InCircle(int originX, int originY, int x, int y, int radius) 
{ 
    int dx = Math.Abs(x - originX); 
    if (dx > radius) return false; 
    int dy = Math.Abs(y - originY); 
    if (dy > radius) return false; 
    if (dx + dy <= radius) return true; 
    return (dx * dx + dy * dy <= radius * radius); 
}