## Sunday, June 12, 2016

### Draw a Circle

Question:
Given a parameter r2, where the equation x^2 + y^2 = r2 holds. Return a list of points that
1. x and y are both integers
2. fits the circle equations.

Drawing a circle on the screen is a little complex than drawing a line. There are two popular algorithms for generating a circle − Bresenham’s Algorithm and Midpoint Circle Algorithm. These algorithms are based on the idea of determining the subsequent points required to draw the circle. Let us discuss the algorithms in detail −
The equation of circle is ${X}^{2}+{Y}^{2}={r}^{2},$ where r is radius.

Method 1: Bresenham’s Algorithm
We cannot display a continuous arc on the raster display. Instead, we have to choose the nearest pixel position to complete the arc.

From the following illustration, you can see that we have put the pixel at (X, Y) location and now need to decide where to put the next pixel − at N (X+1, Y) or at S (X+1, Y-1).

This can be decided by the decision parameter d. -- If d <= 0, then N(X+1, Y) is to be chosen as next pixel. -- If d > 0, then S(X+1, Y-1) is to be chosen as the next pixel.

### Algorithm

Step 1 − Get the coordinates of the center of the circle and radius, and store them in x, y, and R respectively. Set P=0 and Q=R.
Step 2 − Set decision parameter D = 3 – 2R.
Step 3 − Repeat through step-8 while X < Y.
Step 4 − Call Draw Circle (X, Y, P, Q).
Step 5 − Increment the value of P.
Step 6 − If D < 0 then D = D + 4x + 6.
Step 7 − Else Set Y = Y + 1, D = D + 4(X-Y) + 10.
Step 8 − Call Draw Circle (X, Y, P, Q).
Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
public static void drawCircle(int centerX, int centerY, int radius) {
int d = 3 - 2 * radius;
int x = 0;

do {
setPixel(centerX + x, centerY + y);
setPixel(centerX + x, centerY - y);
setPixel(centerX - x, centerY + y);
setPixel(centerX - x, centerY - y);
setPixel(centerX + y, centerY + x);
setPixel(centerX + y, centerY - x);
setPixel(centerX - y, centerY + x);
setPixel(centerX - y, centerY - x);

if (d <= 0) {
d += 4 * x + 6;
} else {
d += 4 * (x - y) + 10;
y--;
}
x++;
} while (x <= y);
}

private static void setPixel(int x, int y) {
System.out.println(x + ", " + y);
}

public static void main(String[] args) {
drawCircle(0, 0, 100);
}
}

Method 2: Mid-point algorithm:

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {

public static void drawCircleMidPoint(int centerX, int centerY, int radius) {
int d = 1 - radius; // Or d = (5 - radius * 4) / 4
int x = 0;

do {
setPixel(centerX + x, centerY + y);
setPixel(centerX + x, centerY - y);
setPixel(centerX - x, centerY + y);
setPixel(centerX - x, centerY - y);
setPixel(centerX + y, centerY + x);
setPixel(centerX + y, centerY - x);
setPixel(centerX - y, centerY + x);
setPixel(centerX - y, centerY - x);

if (d <= 0) {
d += 2 * x + 3;
} else {
d += 2 * (x - y) + 5;
y--;
}
x++;
} while (x <= y);
}

private static void setPixel(int x, int y) {
System.out.println(x + ", " + y);
}

public static void main(String[] args) {
drawCircleBresenham(0, 0, 10);

System.out.println("");

drawCircleMidPoint(0, 0, 10);

}
}