title: Midpoint circle algorithm for filled circles
body: <p>The <a href="http://en.wikipedia.org/wiki/Midpoint_circle_algorithm" rel="noreferrer">Midpoint circle algorithm</a> can be used rasterize the border of a circle. However, I want the circle to be filled, without drawing pixels multiple times (this is very important).</p>
  
  <p>This answer provides a modification of the algorithm that yields a filled circle, but some pixels are visited several times:
  <a href="https://stackoverflow.com/questions/1201200/fast-algorithm-for-drawing-filled-circles">fast algorithm for drawing filled circles?</a></p>
  
  <p><strong>Q:</strong> How can I rasterize a circle without drawing pixels multiple times? Note that RAM is very limited!</p>
  
  <p><strong>Update:</strong></p>
  
  <pre><code>using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  
  namespace CircleTest
  {
      class Program
      {
          static void Main(string[] args)
          {
              byte[,] buffer = new byte[50, 50];
              circle(buffer, 25, 25, 20);
  
              for (int y = 0; y &lt; 50; ++y)
              {
                  for (int x = 0; x &lt; 50; ++x)
                      Console.Write(buffer[y, x].ToString());
  
                  Console.WriteLine();
              }
          }
  
          // 'cx' and 'cy' denote the offset of the circle center from the origin.
          static void circle(byte[,] buffer, int cx, int cy, int radius)
          {
              int error = -radius;
              int x = radius;
              int y = 0;
  
              // The following while loop may altered to 'while (x &gt; y)' for a
              // performance benefit, as long as a call to 'plot4points' follows
              // the body of the loop. This allows for the elimination of the
              // '(x != y)' test in 'plot8points', providing a further benefit.
              //
              // For the sake of clarity, this is not shown here.
              while (x &gt;= y)
              {
                  plot8points(buffer, cx, cy, x, y);
  
                  error += y;
                  ++y;
                  error += y;
  
                  // The following test may be implemented in assembly language in
                  // most machines by testing the carry flag after adding 'y' to
                  // the value of 'error' in the previous step, since 'error'
                  // nominally has a negative value.
                  if (error &gt;= 0)
                  {
                      error -= x;
                      --x;
                      error -= x;
                  }
              }
          }
  
          static void plot8points(byte[,] buffer, int cx, int cy, int x, int y)
          {
              plot4points(buffer, cx, cy, x, y);
              if (x != y) plot4points(buffer, cx, cy, y, x);
          }
  
          // The '(x != 0 &amp;&amp; y != 0)' test in the last line of this function
          // may be omitted for a performance benefit if the radius of the
          // circle is known to be non-zero.
          static void plot4points(byte[,] buffer, int cx, int cy, int x, int y)
          {
  #if false // Outlined circle are indeed plotted correctly!
              setPixel(buffer, cx + x, cy + y);
              if (x != 0) setPixel(buffer, cx - x, cy + y);
              if (y != 0) setPixel(buffer, cx + x, cy - y);
              if (x != 0 &amp;&amp; y != 0) setPixel(buffer, cx - x, cy - y);
  #else // But the filled version plots some pixels multiple times...
              horizontalLine(buffer, cx - x, cy + y, cx + x);
              //if (x != 0) setPixel(buffer, cx - x, cy + y);
              //if (y != 0) setPixel(buffer, cx + x, cy - y);
              //if (x != 0 &amp;&amp; y != 0) setPixel(buffer, cx - x, cy - y);
  #endif
          }
  
          static void setPixel(byte[,] buffer, int x, int y)
          {
              buffer[y, x]++;
          }
  
          static void horizontalLine(byte[,] buffer, int x0, int y0, int x1)
          {
              for (int x = x0; x &lt;= x1; ++x)
                  setPixel(buffer, x, y0);
          }
      }
  }
  </code></pre>
  
  <p>Here's the relevant result:</p>
  
  <pre><code>00000111111111111111111111111111111111111111110000
  00000111111111111111111111111111111111111111110000
  00000111111111111111111111111111111111111111110000
  00000111111111111111111111111111111111111111110000
  00000111111111111111111111111111111111111111110000
  00000011111111111111111111111111111111111111100000
  00000011111111111111111111111111111111111111100000
  00000011111111111111111111111111111111111111100000
  00000001111111111111111111111111111111111111000000
  00000001111111111111111111111111111111111111000000
  00000000111111111111111111111111111111111110000000
  00000000111111111111111111111111111111111110000000
  00000000011111111111111111111111111111111100000000
  00000000001111111111111111111111111111111000000000
  00000000000111111111111111111111111111110000000000
  00000000000011111111111111111111111111100000000000
  00000000000001111111111111111111111111000000000000
  00000000000000122222222222222222222210000000000000
  00000000000000001222222222222222221000000000000000
  00000000000000000012333333333332100000000000000000
  00000000000000000000012345432100000000000000000000
  00000000000000000000000000000000000000000000000000
  00000000000000000000000000000000000000000000000000
  00000000000000000000000000000000000000000000000000
  00000000000000000000000000000000000000000000000000
  </code></pre>
  
  <p>The bottom pixels are plotted too many times. What am I missing here?</p>
  
  <p><strong>Update #2: This solution works:</strong></p>
  
  <pre><code>static void circle(byte[,] buffer, int cx, int cy, int radius)
  {
      int error = -radius;
      int x = radius;
      int y = 0;
  
      while (x &gt;= y)
      {
          int lastY = y;
  
          error += y;
          ++y;
          error += y;
  
          plot4points(buffer, cx, cy, x, lastY);
  
          if (error &gt;= 0)
          {
              if (x != lastY)
                  plot4points(buffer, cx, cy, lastY, x);
  
              error -= x;
              --x;
              error -= x;
          }
      }
  }
  
  static void plot4points(byte[,] buffer, int cx, int cy, int x, int y)
  {
      horizontalLine(buffer, cx - x, cy + y, cx + x);
      if (y != 0)
          horizontalLine(buffer, cx - x, cy - y, cx + x);
  }    
  </code></pre>