title: Python to Draw a Filled "Circle" on a Grid
body: <p>Can you provide an efficient algorithm for drawing a circle(ish) shape in a grid of arbitrary position and radius?</p>
  
  <pre><code>. . . . . . . . . . . . . . . . . . . . . . . . . . . .
  . . . . . o O o . . . . . . . . . . . . . . . . . . . .
  . . . . O O O O O . . . . . . . . . . . . . . . . . . .
  . . . o O O O O O o . . . . . . . . . . . . . . . . . .
  . . . O O O O O O O . . . . . . . . . . o O o . . . . .
  . . . o O O O O O o . . . . . . . . . o O O O o . . . .
  . . . . O O O O O . . . . . . . . . . O O O O O . . . .
  . . . . . o O o . . . . . . . . . . . o O O O o . . . .
  . . . . . . . . . . . . . . . . . . . . o O o . . . . .
  . . . . . . . . . . . . . . . . . . . . . . . . . . . .
  </code></pre>
  
  <p>I'm using this for pathfinding. It is a lower-res abstraction of a more finely-resolved graphic field. These shapes serve as blocks to avoid.</p>
  
  <p>Keep in mind that I want to be able to use this to quickly index a 2d array of where the blocks are located.</p>
  
  <pre><code>score = self.map[x][y]
  </code></pre>
  
  <p>So "drawing" the circle will be akin to setting values as blocked:</p>
  
  <pre><code>self.map[x][y] = PATH_COST_PROX1
  </code></pre>
  
  <p>Drawing the field looks like this:</p>
  
  <pre><code>def printme(self):
      """ Print the map to stdout in ASCII."""
      for y in reversed(range(self.ymax)):
          for x in range(self.xmax):
              if self.map[x][y] &gt;= PATH_COST_PROX0:
                  print 'O',
              elif self.map[x][y] &gt;= PATH_COST_PROX1:
                  print 'o',
              else:
                  print '.',
          print ''
  </code></pre>
  
  <p>EDIT: Here was my original (shameful) attempt. I made circles by hand on a grid and just jotted down the points that were added by each increase in radius. It isn't a terrible idea, but the accepted answer is much more elegant.</p>
  
  <pre><code>COVER_MAP = [
      [(0,0)],
      [(0,1),(1,0),(0,-1),(-1,0)],
      [(1,1),(1,-1),(-1,-1),(-1,1)],
      [(0,2),(2,0),(0,-2),(-2,0)],
      [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)],
      [(0,3),(2,2),(3,0),(2,-2),(0,-3),(-2,-2),(-3,0),(-2,2)],
      [(1,3),(3,1),(3,-1),(1,-3),(-1,-3),(-3,-1),(-3,1),(-1,3)]
  ]
  
  def set_blocked(self, p, radius):
      """
      Set the blocked state of a coordinate. Takes an integer value that
      represents the cost of the block
      """
      #radius = radius * 2
      if radius &gt; len(COVER_MAP)-1:
          radius=len(COVER_MAP)-1
      #print "point:",p," radius:",radius
      (cx,cy) = p
      for i in range(len(COVER_MAP)):
          for j in range(len(COVER_MAP[i])):
              (rx,ry) = COVER_MAP[i][j]
              x = cx + rx
              y = cy + ry
              if x &gt;= 0 and x &lt; self.xmax and y &gt;= 0 and y &lt; self.ymax:
                  if i &lt; radius:
                      self.map[x][y] = PATH_COST_PROX0
                  elif i == radius:
                      self.map[x][y] = PATH_COST_PROX1
                  elif i == radius + 1:
                      self.map[x][y] = PATH_COST_PROX2
                  elif i == radius + 2:
                      self.map[x][y] = PATH_COST_PROX3
                  elif i == radius + 3:
                      self.map[x][y] = PATH_COST_PROX4
  </code></pre>
  
  <p>Mine does have the advantage of being able to make a fuzzy ring of lessened cost around the original circle, something that the memorization algorithm below doesn't have but could be adapted to provide.</p>