Петля через массив в форме круга без повторных индексов

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, а не каждый индекс получается, потому что его окружение это не реально (согласно тригонометрии)

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 круг или другие шаги алгоритма пропуска (недостающие координаты):

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.

В двух словах, мы вычисляем Int из наших х, у пары, которая гарантирована карта однозначно, а затем проверить, что для дубликатов ...

cantor(x, y) = 1/2(x + y)(x + y + 1) + 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); 
}