Bresenham's circle algorithm (Python)

From LiteratePrograms

Bresenham's circle algorithm (also known as a midpoint circle algorithm) is an algorithm for determining the points needed for drawing a circle with a given radius and origin for the circle.

Scan converts a circle of a specified radius, centered at the specified location. Scan conversion is performed using a Bresenham-style midpoint decision approach to compute pixels in one octant of the circle (from x = 0 to x = y = R/sqrt(2). Points in other octants are drawn via symmetry.

At each step of the iteration, we:

1. Determine whether to move east (E) or south-east (SE) based on the sign of the decision variable 'd'.

• d < 0 ==> move E (i.e. x' = x+1, y' = y)
• d >= 0 ==> move SE (i.e. x' = x+1, y' = y-1)

1. Update the decision variable with a delta-value that depends on the direction selected
2. Update the delta-values based on the move direction
3. Draw a pixel at x', y'

from Tkinter import *
class BresenhamCanvas(Canvas):
    def draw_point(self, x, y, color="red"):
        self.create_line(x, y, x+1, y+1, fill=color)
    def draw_circle_points(self, x, y, center_x, center_y, color="red"):
        '''Draw 8 points on a circle centered
           at center_x, center_y, by symmetry.'''
        self.draw_point(center_x + x, center_y + y, color)
        self.draw_point(center_x - x, center_y - y, color)  
        self.draw_point(center_x + x, center_y - y, color)
        self.draw_point(center_x - x, center_y + y, color)
        # If x == y then these points will simply duplicate
        # points already drawn above. No need to repeat them then.
        if x != y:
            self.draw_point(center_x + y, center_y + x, color)
            self.draw_point(center_x - y, center_y - x, color)
            self.draw_point(center_x + y, center_y - x, color)
            self.draw_point(center_x - y, center_y + x, color) 
    def draw_circle(self, center_x, center_y, radius, line_thickness, color="red"):

        # Start at the top of the circle
        x = 0
        yin = radius - int(line_thickness/2)
        yout = radius + int(line_thickness/2)
        din = 1 - radius - int(line_thickness/2) # midpoint decision variable
        deltaEin = 3     # initial delta for move E
        deltaSEin = -2*(radius - int(line_thickness/2)) + 5 # initial delta for move SE
        dout = 1 - radius + int(line_thickness/2) # midpoint decision variable
        deltaEout = 3     # initial delta for move E
        deltaSEout = -2*(radius + int(line_thickness/2)) + 5 # initial delta for move SE
        # First point
        for y in range(yin,yout):
            self.draw_circle_points(x, y, center_x, center_y, color)
        # Stop when we cross the line y == x, which is the edge
        # of the first octant of the circle
        while yout > x:
            if din < 0:
                # Moving E
                din = din + deltaEin
                deltaEin = deltaEin + 2
                deltaSEin = deltaSEin + 2
            else:
                # Moving SE
                din = din + deltaSEin
                deltaEin = deltaEin + 2
                deltaSEin = deltaSEin + 4
                yin = yin - 1
            if dout < 0:
                # Moving E
                dout = dout + deltaEout
                deltaEout = deltaEout + 2
                deltaSEout = deltaSEout + 2
            else:
                # Moving SE
                dout = dout + deltaSEout
                deltaEout = deltaEout + 2
                deltaSEout = deltaSEout + 4
                yout = yout - 1
            x = x + 1
            for y in range(yin,yout):
                self.draw_circle_points(x, y, center_x, center_y, color)
def run():
    import math
    CANVAS_SIZE = 600
    root = Tk()
    canvas = BresenhamCanvas(root, width=CANVAS_SIZE, height=CANVAS_SIZE)
    canvas.pack()
    margin = CANVAS_SIZE / 10
    origin_x = int(CANVAS_SIZE / 2)
    origin_y = int(CANVAS_SIZE / 2)
    center_dist = ((CANVAS_SIZE / 2) - 2*margin)
    radius = margin*2
    n_circles = 10
    angle_step = (2 * math.pi) / n_circles
    for i in range(n_circles):
        theta = angle_step * i
        center_x = int(center_dist * math.cos(theta)) + origin_x
        center_y = int(center_dist * math.sin(theta)) + origin_y
        canvas.draw_circle(center_x, center_y, radius, 10, color="blue")
    root.mainloop()
if __name__ == "__main__":
    run()

References

• Foley, Van Dam, Feiner, and Hughes, Computer Graphics: Principles and Practice, 2nd Ed. Addison-Wesley, 1996.