# Draw a circle

• Implement a method to draw a circle. You are not allowed to use math library functions such as `sqrt`, `sin`, or `cos`.

For example, given r = 2 (radius), return the following points to plot:

``````(0,0), (0,1),(0,2), (1,0), (1,1), (2,0), (0,-1), (0,-2), (-1,0), (-1,1), (1,-1), (-1,-1),(-2,0)
``````

Note that all points satisfy the equation: `x^2 + y^2 <= r^2`.

• Thanks for posting! Could you please include an example? Also how do you define "drawing a circle"? Is it drawing a circle by plotting pixels on a computer screen? It would be great if you can define the input/output of the function.

• @1337c0d3r Yes, you draw the circle by plotting pixels on the screen. I have included the example. There are few ways you can do this, pass in a 2d grid of points and modify it by plotting the points, or returning a set of plotted points. Either way should be fine.

• ``````function test(\$r){
\$res = array();
for(\$x=-\$r;\$x<=\$r;\$x++){
for (\$y=-\$r; \$y<=\$r ; \$y++) {
if(\$x*\$x+\$y*\$y<=\$r*\$r){
\$res[] = "({\$x},{\$y})";
}
}
}
return \$res;
}
``````

• @justhacker Hi, welcome! You can wrap your code around three backquotes sign to format your code.

• @1337c0d3r ok, Discuss should remind user add （To format your code, surround your code block with 3 backquote signs:）when someone reply question!!!

• @justhacker
We can only consider a quarter of the space: x in [0, r] and y in [0, r]. Because the points can be mirrored by the axis.

• There are mutliple computer graphics algorithm to draw a circle without sqrt, sic and cos.

• @xidui This can further improve to just calculating one-eight of the space. The circle is symmetry along `y=x` and `y=-x`.

• @1337c0d3r yeah, you are right

• yes, most of the algorithm used this property, I think they were Bresenham,Mid point and so on

• It is not specified where is the center of the circle. Only radius is mentioned.

• @elmirap
I think we can assume that center is at (0,0). After that we can move all the points according to the desired center.

• This is a typical computer graphic problem. Search for `computer graphics draw circle` and you will get the answer.

• How come (1, 0) and (2, 0) both are returned for a point on circle of radius 2 ?

• @nixed said in Draw a circle:

(0,0), (0,1),(0,2), (1,0), (1,1), (2,0), (0,-1), (0,-2), (-1,0), (-1,1), (1,-1), (-1,-1),(-2,0)

A basic solution will be :

``````  private static List<int[]> drawCircle(int r)
{
List<int[]> list = new ArrayList<>();
int l = -r;
int u = r;
for (int i = l; i <= u; i++)
{
for (int j = u; j >= l; j--)
{
if (i * i + j * j <= r * r)
{
list.add(new int[] { i, j });
}
}
}
return list;
}
``````

If someone knows how to optimize it further, please suggest.

• @labs Here is my implementation. It reduced the runtime from 4n^2 to n^2. Is there anyone can continue reduce it to 1/4 n^2. I believe 1/4 n^2 is doable due to i and j can be exchanged.

``````public List<int[]> drawCycle(int n) {
if (n <= 0) {
return new ArrayList<>();
}

List<int[]> list = new ArrayList<>();
int r = n * n;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (i * i + j * j <= r) {
if (i == 0 && j == 0) {
} else if (i == 0) {
} else if (j == 0) {
} else {