Filling a circle. | Hello World
You are given a point at Cartesian coordinate x, y, and a positive number r. implement a function to fill the circle, you can assume that you have a fillPixel(int x, int y) method that fills a pixel at coordinate x, y in constant time.
The brute force idea is to search all the coordinates in the range x – r to x + r and y – r and y + r, test if they are in the circle or not, and fill the coordinates if they fit. This, however, requires testing all the coordinates in the square range, and note that even though fillPixel is fast, testing if the coordinate takes a long time (square).
So the problem become how we can minimized the number of checks by using the symmetric property of the circle, you only need to check one forth of the cycle to fill out the whole circle because the all the rest of the three forth can be filled symmetrically.
The other optimization we have is only search for the edge, since we search from bottom up, we can stop when we find the edge, then fill everything until you hit the edge of the 1 forth of the circle.
However, there is one more optimization that you can go further to push it to the limit. Instead of going from bottom up to find the edge, you find out that since going from right to left, the circle is always increasing (assuming we are looking at the bottom left part of the circle. So instead of searching y from bottom, we start from the y position of the cycle that we found in the previous iteration.
Read full article from Filling a circle. | Hello World
