Iterating over all (i,j)-elements in a circle

Question

Given two (very simplified) classes:

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;
};

If I want to iterate over all elements in a Rectangle, I can simply do that by:

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

My problem is to implement a smart way of iterating over all elements in Circle. My current solution looks as follows:

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();

However, for radius getting large my current solution is very time-expensive (since I touch many elements which aren't in the Circle and since I always need to evaluate pow). Can you think of a more intelligent and efficient way of iteration over all Circle-elements?

[Polar coordinate system](https://en.wikipedia.org/wiki/Polar_coordinate_system) — Ivan Aksamentov - Drop, Dec 14 '16 at 06:38
So I got a discrete 2D-shape (with i,j-points) where several circles and rectangles lie on. If I use polar coordinates I got the same problem: How should I iterate over the angle \phi? I need sth. like (psuedocode:) `for (double phi=0; phi<360; phi++)` and that is not possible. — Kapa11, Dec 14 '16 at 06:48
@Jarod42: you're right, I already changed this in my code :) Is it true that the compiler internally automatically changes pow(x,2) to x*x (using flag `-O2`)? — Kapa11, Dec 14 '16 at 09:10
@Kapa11: It can (with the as-if rule). You have to check generated code with your compiler (but indeed gcc/clang does [Demo](https://godbolt.org/g/E31uf8)). — Jarod42, Dec 14 '16 at 09:34

score 6 · Accepted Answer · answered Dec 14 '16 at 06:56

6

For every line find the first column that belongs to the circle, and walk from this column to one mirrored relative to the circle center. Pseudo code

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);

answered Dec 14 '16 at 06:56

MBo

77,366
5
53
86

Thanks, I will test that. But I will change ix- and iy-loop for improving cache-locality :) – Kapa11 Dec 14 '16 at 07:09
Emm... In most languages (including c++) 2D arrays are stored "by rows", so usually described order is preferred. Perhaps, you mean some other circumstances though... – MBo Dec 14 '16 at 07:14
But in your code snippet you iterate over each y (j-direction) and then over every x (i-direction). So, for each column you check each row. But as you said, checking each row one after another would be better – Kapa11 Dec 14 '16 at 07:23
1

@Kapa11 Seems our opinions about row/columns slightly differ ;) For every outer cycle run I fix IY (line), find limits along to X-axis, and walk through X-range (changing second array of 2d-array more frequently). Probably your data is organized by another way (X-index first) – MBo Dec 14 '16 at 08:04
1

yeah I think we meant the same in a different context – Kapa11 Dec 14 '16 at 08:05

score -1 · Answer 2 · answered Dec 14 '16 at 07:19

Let the radius of the circle be r. Consider a Square of size (2r+1)*(2r+1) around the circle to be drawn. So equidistant points in square are stored in 2D array .

Now walk through every point inside the square. For every point (x,y), if (x, y) lies inside the circle (or x^2+ y^2 < r^2), then print it. For example, equidistant points form a 10x10 array, and a chosen "center" of the array at (x,y):

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
        }
    }
}

Isn't it exactly the thing I'm doing at the moment and the code I don't feel comfortable with ?!?! — Kapa11, Dec 14 '16 at 07:24

Iterating over all (i,j)-elements in a circle

2 Answers2