Hatefiend Hatefiend - 16 days ago 6
Java Question

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

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

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