繰り返しインデックスのない円の配列をループする

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：私は、半径が6まで2から始めて、そして彼の円が、それは本当ではないので、必ずしもすべての指数は、得られるインクリメントする必要があるので、私は、中間点サークルを使用することはできません（三角法による）

EDIT： 私が本当に必要とするのは、中心から始まるエッジで完全な円エッジをスキャンすることです。

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

2つのアルゴリズムの考え方がありますここで遊んで：1つは、円をラスタライズしています。そのOPコードは、（a）360度の円全体をサンプリングする必要はなく、円が両方の軸で対称であることを認識している必要があります。 （x、y）、（-x、-y）、および（x、-y）として他の3つの象限に反映させることができる。 （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 
} 

これらの改良点を使用すると、重複するサンプルが生成されることに気付かないことがあります。それでもやっていれば、サークルから独立した2番目のアイデアは、intのペアをハッシュする方法です。そのことに関する良い記事がここにあります：Mapping two integers to one, in a unique and deterministic way一言で言えば

は、私たちは、これは、X、Yの正の値に対してのみ機能

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

当社のxからint型、一意にマッピングし、その後、重複のためにそれをチェックするために保証されます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); 
}