Draw a circle


  • 0
    N

    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.


  • 0

    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.


  • 0
    N

    @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.


  • 0
    J
    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;
    }
    

  • 0

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

    For more information, please see here for instructions.


  • 0
    J

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


  • 0

    @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.


  • 0

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


  • 0

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


  • 0

    @1337c0d3r yeah, you are right


  • 0

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


  • 0

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


  • 0

    @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.


  • 0
    S

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


  • 0
    M

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


  • 1
    L

    @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.


  • 1
    L

    @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) {
                            list.add(new int[]{0, 0});
                        } else if (i == 0) {
                            list.add(new int[]{i, j});
                            list.add(new int[]{i, -j});
                        } else if (j == 0) {
                            list.add(new int[]{i, j});
                            list.add(new int[]{-i, j});
                        } else {
                            list.add(new int[]{i, j});
                            list.add(new int[]{i, -j});
                            list.add(new int[]{-i, j});
                            list.add(new int[]{-i, -j});
                        }
                    }
                }
            }
            return list;
        }
    

  • 0
    P

    @nixed I dont understand how the points (0,0), (0,1)(0,-1) or any the points which are x^2 + y^2 < r^2 should be in the answer? Can you please explain why there is '<' Since the circle equation should be x^2 + y^2 = r^2


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.