title: Implementing Bresenham's circle drawing algorithm
body: <p>I have written an implementation of Bresenham's circle drawing algorithm. <strong>This algorithms takes advantage of the highly symmetrical properties of a circle</strong> (it only computes points from the 1st octant and draws the other points by taking advantage of symmetry). Therefore I was expecting it to be very fast. The Graphics programming black book, chapter #35 was titled "<strong>Bresenham is fast, and fast is good</strong>", and though it was about the line drawing algorithm, I could reasonably expect the circle drawing algorithm to also be fast (since the principle is the same).</p>
  
  <p>Here is my java, swing implementation</p>
  
  <pre><code>public static void drawBresenhamsCircle(int r, double width, double height, Graphics g) {
      int x,y,d;
      y = r;
      x = 0;
  
      drawPoint(x, y, width, height,g);
      d = (3-2*(int)r);
      while (x &lt;= y) {
          if (d &lt;= 0) {
              d = d + (4*x + 6);
          } else {
              d = d + 4*(x-y) + 10;
              y--;
          }
          x++;
  
          drawPoint(x, y, width, height,g);
  
          drawPoint(-x, y, width, height,g);
          drawPoint(x, -y, width, height,g);
  
          drawPoint(-x, -y, width, height,g);
          drawPoint(y, x, width, height,g);
          drawPoint(-y, x, width, height,g);
          drawPoint(y, -x, width, height,g);
  
          drawPoint(-y, -x, width, height,g);
      }   
  }
  </code></pre>
  
  <p>This method uses the following <code>drawPoint</code>method:</p>
  
  <pre><code>public static void drawPoint(double x, double y,double width,double height, Graphics g) {
      double nativeX = getNativeX(x, width);
      double nativeY = getNativeY(y, height);
      g.fillRect((int)nativeX, (int)nativeY, 1, 1);
  }
  </code></pre>
  
  <p>The two methods getNativeX and getNativeY are used to switch coordinates from originating in the upper left corner of the screen to a system that has it origin in the center of the panel with a more classic axis orientation.</p>
  
  <pre><code>public static double getNativeX(double newX, double width) {
      return newX + (width/2);
  }
  
  public static double getNativeY(double newY, double height) {
      return (height/2) - newY;
  }
  </code></pre>
  
  <p>I have also created an implementation of a circle drawing algorithm based on trigonometrical formulaes (<code>x=R*Math.cos(angle)</code>and <code>y= R*Math.sin(angle)</code>) and a third implementation using a call to the standard drawArc method (available on the Graphics object). These additional implementations are for the sole purpose of comparing Bresenham's algorithm to them.</p>
  
  <p>I then created methods to draw a bunch of circles in order to be able to get good measures of the spent time. Here is the method I use to draw a bunch of circles using Bresenham's algorithm</p>
  
  <pre><code>public static void drawABunchOfBresenhamsCircles(int numOfCircles, double width, double height, Graphics g) {
      double r = 5;
      double step = (300.0-5.0)/numOfCircles;
  
      for (int i = 1; i &lt;= numOfCircles; i++) {
          drawBresenhamsCircle((int)r, width, height, g);
          r += step;
      }
  }
  </code></pre>
  
  <p>Finally I override the paint method of the JPanel I am using, to draw the bunch of circles and to measure the time it took each type to draw. Here is the paint method:</p>
  
  <pre><code>public void paint(Graphics g) {
      Graphics2D g2D = (Graphics2D)g;
  
      g2D.setColor(Color.RED);
  
      long trigoStartTime = System.currentTimeMillis();
      drawABunchOfTrigonometricalCircles(1000, this.getWidth(), this.getHeight(), g);
      long trigoEndTime = System.currentTimeMillis();
      long trigoDelta = trigoEndTime - trigoStartTime;
  
      g2D.setColor(Color.BLUE);
  
      long bresenHamsStartTime = System.currentTimeMillis();
      drawABunchOfBresenhamsCircles(1000, this.getWidth(), this.getHeight(), g);
      long bresenHamsEndTime = System.currentTimeMillis();
      long bresenDelta = bresenHamsEndTime - bresenHamsStartTime;
  
      g2D.setColor(Color.GREEN);
  
      long standardStarTime = System.currentTimeMillis();
      drawABunchOfStandardCircles(1000, this.getWidth(), this.getHeight(),g);
      long standardEndTime = System.currentTimeMillis();
      long standardDelta = standardEndTime - standardStarTime;
  
      System.out.println("Trigo : " + trigoDelta  + " milliseconds");
      System.out.println("Bresenham :" + bresenDelta +  " milliseconds");
      System.out.println("Standard :" + standardDelta +  " milliseconds");
  }
  </code></pre>
  
  <p>Here is the kind of rendering it would generate (drawing 1000 circles of each type)</p>
  
  <p><img src="https://i.stack.imgur.com/yybed.png" alt="Bresenham and other methods"></p>
  
  <p><strong>Unfortunately my Bresenham's implementation is very slow</strong>. I took many comparatives measures, and the Bresenham's implementation is not only slower than the <code>Graphics.drawArc</code>but also slower than the trigonometrical approach. Take a look at the following measures for a various number of circles drawn.</p>
  
  <p>What part of my implementation is more time-consuming? Is there any workaround I could use to improve it? Thanks for helping.</p>
  
  <p><img src="https://i.stack.imgur.com/NXd9v.png" alt="Comparing Bresenham to other implementations"></p>
  
  <p><strong>[EDITION]</strong>: as requested by @higuaro, here is my trigonometrical algorithm for drawing a circle</p>
  
  <pre><code>public static void drawTrigonometricalCircle (double r, double width, double height, Graphics g) {
  
      double x0 = 0;
      double y0 = 0;
      boolean isStart = true;
  
      for (double angle = 0; angle &lt;= 2*Math.PI; angle = angle + Math.PI/36) {
  
          double x = r * Math.cos(angle);
          double y = r * Math.sin(angle);
  
          drawPoint((double)x, y, width, height, g);
  
          if (!isStart) {
              drawLine(x0,  y0, x, y, width, height, g);
          }
  
          isStart = false;
  
          x0 = x;
          y0 = y;
      }
  }
  </code></pre>
  
  <p>And the method used to draw a bunch of trigonometrical circles</p>
  
  <pre><code>public static void drawABunchOfTrigonometricalCircles(int numOfCircles, double width, double height, Graphics g) {
  
      double r = 5;
      double step = (300.0-5.0)/numOfCircles;
  
      for (int i = 1; i &lt;= numOfCircles; i++) {
          drawTrigonometricalCircle(r, width, height, g);
          r += step;
      }
  }
  </code></pre>