Java - Loop through all pixels in a 2D circle with center x,y and radius?

Question

I have a BufferedImage that I want to loop through. I want to loop through all pixels inside a circle with radius radius which has a center x and y at x,y.

I do not want to loop through it in a square fashion. It would also be nice if I could do this and cut O complexity in the process, but this is not needed. Since area of a circle is pi * r^2 and square would be 4 * r^2 that would mean I could get 4 / pi better O complexity if I looped in a perfect circle. If the circle at x,y with a radius of radius would happen to be larger than the dimensions of the BufferedImage, then prevent going out of bounds (this can be done with an if statement I believe to prevent going out of bounds at each check).

Examples: O means a recorded pixel while X means it was not looped over.

Radius 1

X   O   X
O   O   O
X   O   X

Radius 2

X   X   O   X   X
X   O   O   O   X
O   O   O   O   O
X   O   O   O   X
X   X   O   X   X

I think the proper way to do this is with trigonometric functions but I can't quite get it in my head. I know one easy part is that all Pixels up, left, right, and down in radius from the origin are added. Would like some advice incase anyone has any.

private LinkedList<Integer> getPixelColorsInCircle(final int x, final int y, final int radius)
{
    final BufferedImage img; // Obtained somewhere else in the program via function call.
    final LinkedList<Integer> ll = new Linkedlist<>();

    for (...)
        for (...)
        {
            int x = ...;
            int y = ...;

            ll.add(img.getRGB(x, y));   // Add the pixel    
        }
}

Answer 1

Having the center of the circle O(x,y) and the radius r the following coordinates (j,i) will cover the circle.

for (int i = y-r; i < y+r; i++) {
    for (int j = x; (j-x)^2 + (i-y)^2 <= r^2; j--) {
        //in the circle
    }
    for (int j = x+1; (j-x)*(j-x) + (i-y)*(i-y) <= r*r; j++) {
        //in the circle
    }
}

Description of the approach:

1. Go from the top to the bottom perpendicularly through the line which goes through the circle center.
2. Move horizontally till you reach the coordinate outside the circle, so you only hit two pixels which are outside of the circle in each row.
3. Move till the lowest row.

As it's only the approximation of a circle, prepare for it might look like a square for small rs

Ah, and in terms of Big-O, making 4 times less operations doesn't change complexity.

Big-O =/= complexity

Answer 2

While xentero's answer works, I wanted to check its actual performance (inCircle1) against the algorithm that OP thinks is too complex (inCircle2):

public static ArrayList<Point> inCircle1(Point c, int r) {
    ArrayList<Point> points = new ArrayList<>(r*r); // pre-allocate
    int r2 = r*r;
    // iterate through all x-coordinates
    for (int i = c.y-r; i <= c.y+r; i++) {
        // test upper half of circle, stopping when top reached
        for (int j = c.x; (j-c.x)*(j-c.x) + (i-c.y)*(i-c.y) <= r2; j--) {
            points.add(new Point(j, i));
        }
        // test bottom half of circle, stopping when bottom reached
        for (int j = c.x+1; (j-c.x)*(j-c.x) + (i-c.y)*(i-c.y) <= r2; j++) {
            points.add(new Point(j, i));
        }
    }
    return points;
}

public static ArrayList<Point> inCircle2(Point c, int r) {
    ArrayList<Point> points = new ArrayList<>(r*r); // pre-allocate
    int r2 = r*r;
    // iterate through all x-coordinates
    for (int i = c.y-r; i <= c.y+r; i++) {
        int di2 = (i-c.y)*(i-c.y);
        // iterate through all y-coordinates
        for (int j = c.x-r; j <= c.x+r; j++) {
            // test if in-circle
            if ((j-c.x)*(j-c.x) + di2 <= r2) {
                points.add(new Point(j, i));
            }
        }
    }
    return points;
}

public static <R extends Collection> R timing(Supplier<R> operation) {
    long start = System.nanoTime();
    R result  = operation.get();
    System.out.printf("%d points found in %dns\n", result.size(),
            TimeUnit.NANOSECONDS.toNanos(System.nanoTime() - start));
    return result;
}

public static void testCircles(int r, int x, int y) {
    Point center = new Point(x, y);
    ArrayList<Point> in1 = timing(() -> inCircle1(center, r));
    ArrayList<Point> in2 = timing(() -> inCircle2(center, r));
    HashSet<Point> all = new HashSet<>(in1);
    assert(all.size() == in1.size()); // no duplicates
    assert(in1.size() == in2.size()); // both are same size
    all.removeAll(in2);
    assert(all.isEmpty());            // both are equal
}

public static void main(String ... args) {
    for (int i=100; i<200; i++) {
        int x = i/2, y = i+1;
        System.out.println("r = " + i + " c = [" + x + ", " + y + "]");
        testCircles(i, x, y);
    }
}

While this is by no means a precise benchmark (not much warm-up, machine doing other things, not smoothing outliers via n-fold repetition), the results on my machine are as follows:

[snip]
119433 points found in 785873ns
119433 points found in 609290ns
r = 196 c = [98, 197]
120649 points found in 612985ns
120649 points found in 584814ns
r = 197 c = [98, 198]
121905 points found in 619738ns
121905 points found in 572035ns
r = 198 c = [99, 199]
123121 points found in 664703ns
123121 points found in 778216ns
r = 199 c = [99, 200]
124381 points found in 617287ns
124381 points found in 572154ns

That is, there is no significant difference between both, and the "complex" one is often faster. My explanation is that integer operations are really, really fast - and examining a few extra points on the corners of a square that do not fall into the circle is really fast, compared to the cost of processing all those points that do fall into the circle (= the expensive part is calling points.add, and it is called the exact same number of times in both variants).

In the words of Knuth:

programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming

Then again, if you really need an optimal way of iterating the points of a circle, may I suggest using Bresenham's Circle Drawing Algorithm, which can provide all points of a circumference with minimal operations. It will again be premature optimization if you are actually going do anything with the O(n^2) points inside the circle, though.