Перебор всех (I, J) -элементов в круге

Question

Учитывая две (очень упрощенным) классов:

class Rectangle { 
    public: 
    int iL,jL; // lower left point of rectangle 
    int width, length; // width: in i-direction, length: in j-direction 
}; 

class Circle { 
    public: 
    int iC,jC; // center-point of circle 
    int radius; 
}; 

Если я хочу, чтобы перебрать все элементы в Rectangle, я могу просто сделать это:

for (int i = iL; i < iL-width; i--) 
    for (int j = jL; j < jL+length; j++) 
    doSomething(); 

Моя проблема заключается в реализации смарт способ перебора всех элементов в Circle. Мое текущее решение выглядит следующим образом:

for (int i = iC-radius; i <= iC+radius; i++) 
    for (int j = jC-radius; j <= jC+radius; j++) 
    if (sqrt(pow(i-iC,2)+pow(j-jC,2)) <= r) // checking if (i,j) lies within the circle (or its boundary) 
     doSomething(); 

Однако для получения radius большой мое текущее решение является очень дорогим по времени (так как я прикасаюсь много элементов, которые не находятся в Circle и так как я всегда нужно оценивать pow) , Можете ли вы подумать о более интеллектуальном и эффективном способе итерации по всем Circle -элементам?

Answer 1

Для каждой строки найдите первый столбец, принадлежащий кругу, и перейдите от этого столбца к одному зеркальному относительно центра круга. Псевдокод

for (int iy = - radius to radius; iy++) 
    dx = (int) sqrt(radius * radius - iy * iy) 
    for (int ix = - dx to dx; ix++) 
     doSomething(CX + ix, CY + iy); 

Answer 2

Пусть радиус круга равен r. Рассмотрим квадрат размера (2r + 1) * (2r + 1) вокруг круга, который нужно нарисовать. Таким образом, эквидистантные точки в квадрате сохраняются в 2D-массиве.

Теперь пройдите через каждую точку внутри квадрата. Для каждой точки (x, y), если (x, y) лежит внутри круга (или x^2 + y^2 < r^2), напечатайте ее. Например, равноудаленные друг от друга точек образуют массив 10x10, и выбранный «центр» массива в точке (х, у):

for i from 0 to 9 { 
    for j from 0 to 9 { 
     a = i - x 
     b = j - y 
     if a*a + b*b <= r*r { 
      // Do something here 
     } 
    } 
}