4

Looping through a square section of a 2d array is easy but how do you loop through a circular section?

2
  • Circular section of a 2d array? Can you explain a bit more as I have no idea what that could possibly mean?
    – sberry
    Jan 4, 2011 at 5:45
  • probable what Daniel has written, just that I understand it that it's a filled circle Jan 4, 2011 at 6:58

3 Answers 3

9

The way I've done this is to do a double for-loop like you would for looping through the 2d array normally. Inside this loop, however, do a check to see if the array element in question is within a circle of radius r using the distance formula.

For example, given 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
        }
    }
}

(Code is just pseudocode, not any particular language).

1
  • 1
    Nice pseudocode; remove the braces and that's valid LiveScript (:
    – Farzher
    Feb 18, 2014 at 2:36
3

You can do much better than using trig functions (which are expensive) or using the equation of a circle, which will ultimately require the taking of an expensive square root.

There is a page devoted to the subject here:

http://www.cs.unc.edu/~mcmillan/comp136/Lecture7/circle.html

In essence the answer is that you want to figure out what the start and end points of the circle are on each row of your array. To do this compute an "offset" from the previous row, i.e. a "difference" from the starting point of the previous row (and similarly for the ending point).

This difference can be computed mathematically using the derivative. A refinement is to compute the difference between successive differences using the double derivative.

Anyhow, this abstract mathematical idea leads to the Midpoint Circle Algorithm, sometimes called Bresenehan's circle algorithm. See wikipedia for more detail on the algorithm itself:

http://en.wikipedia.org/wiki/Midpoint_circle_algorithm

1

I'm gussing you have something like this in mind

[ ][ ][x][0][ ][ ]
[ ][x][ ][ ][1][ ]
[9][ ][ ][ ][ ][2]
[8][ ][ ][ ][ ][3]
[ ][7][ ][ ][4][ ]
[ ][ ][6][5][ ][ ]

if that is so, you might have to use some basic trigonometry. I would use the trig to advance the angle until you get the next value and add them to another array(or add the [i,j] coordinates to a new array), because the steps in angles wouldn't correspond to even steps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.