Python to Draw a Filled "Circle" on a Grid

Question

Can you provide an efficient algorithm for drawing a circle(ish) shape in a grid of arbitrary position and radius?

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

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.

Keep in mind that I want to be able to use this to quickly index a 2d array of where the blocks are located.

score = self.map[x][y]

So "drawing" the circle will be akin to setting values as blocked:

self.map[x][y] = PATH_COST_PROX1

Drawing the field looks like this:

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] >= PATH_COST_PROX0:
                print 'O',
            elif self.map[x][y] >= PATH_COST_PROX1:
                print 'o',
            else:
                print '.',
        print ''

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.

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 > 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 >= 0 and x < self.xmax and y >= 0 and y < self.ymax:
                if i < 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

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.

Answer 1

I suspect the fastest way to do this uses memoization (not to be confused with "memorization"). Here is an example of generating discs up to a radius of 20 pixels. If you want circles or hollow discs instead of filled discs, you need to specify a width for them and include x_sq + y_sq >= (k_r_sq - width) in the if statement.

According to time.time() (you can use time.perf_counter() if you have python 3.3 or higher), it takes me 3 microseconds to load each disc's coordinate set, but that doesn't take into account whatever calculation you may want to do on that disc.

Hope this helps.

import time
max_radius = 20    

i0 = time.time()
class DiscTemplate:
    def __init__(self, max_r):
        self.memos = []
        for k_r in range(1, max_r + 1):
            k_r_sq = k_r ** 2
            self.memos.append([])
            for x in range(-max_r, max_r + 1):
                x_sq = x ** 2
                for y in range(-max_r, max_r + 1):
                    y_sq = y ** 2
                    if x_sq + y_sq <= k_r_sq:
                        self.memos[k_r - 1].append((x,y))

        self.max_r = max_r

    def get_disc(self, r):
        return self.memos[r - 1]
test = DiscTemplate(20)
i1 = time.time()

print("time to make class:", i1 - i0)

t0 = time.time()
disc = test.get_disc(2)
t1 = time.time()

print("time to produce disc:", t1 - t0)
print("Disc coordinates: \n", disc)

Answer 2

I would try something like this :

1. Find the enclosing rectangle of the circle you want to draw :

   top_left = (cx + radius*cos(3*pi/4), cy + radius*sin(3*pi/4)) # (cx, cy) center of the circle
   width, height = 2*radius, 2*radius
   

2. For each point of this rectangle test the distance to the center and set the corresponding char if this distance is less than the radius

Edit : numpy

The following code will give you the points in a circle. Here you don't have any loop in Python, so efficiency will be maximal.

import numpy as np

#precomputed (depends on the dimensions of your grid)
x = np.arange(50) # x values
y = np.arange(50) # y values
xx, yy = np.meshgrid(x, y) # combine both vectors

# for this particular circle
cx, cy, r = 10, 10, 5

condition = (xx-cx)**2 + (yy-cy)**2 <= r**2
points = xx[condition] + 1j*yy[condition] # list of points in the circle (stored as complex)