# Bresenham's circle algorithm (Python)

**This program is a code dump.**

Code dumps are articles with little or no documentation or rearrangement of code. Please help to

**turn it into a literate program**. Also make sure that the source of this code does consent to release it under the CC0 license.

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:

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

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

fromTkinterimport*classBresenhamCanvas(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.ifx != 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 pointforyinrange(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 circlewhileyout > x:ifdin < 0: # Moving E din = din + deltaEin deltaEin = deltaEin + 2 deltaSEin = deltaSEin + 2else: # Moving SE din = din + deltaSEin deltaEin = deltaEin + 2 deltaSEin = deltaSEin + 4 yin = yin - 1ifdout < 0: # Moving E dout = dout + deltaEout deltaEout = deltaEout + 2 deltaSEout = deltaSEout + 2else: # Moving SE dout = dout + deltaSEout deltaEout = deltaEout + 2 deltaSEout = deltaSEout + 4 yout = yout - 1 x = x + 1foryinrange(yin,yout): self.draw_circle_points(x, y, center_x, center_y, color)defrun():importmath 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_circlesforiinrange(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()

## [edit] References

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

Download code |