Is there anybody having a code snippet for using the Bresenham circle algo
and modifiying it in a way so that it actually draws arcs with specified
start and end angle instead of complete circles?

A Bresenham algo for a complete circle in Python would be like this:

``````import PIL.Image, PIL.ImageDraw

"Bresenham complete circle algorithm in Python"
# init vars
switch = 3 - (2 * radius)
points = set()
x = 0
# first quarter/octant starts clockwise at 12 o'clock
while x <= y:
# first quarter first octant
# first quarter 2nd octant
# second quarter 3rd octant
# second quarter 4.octant
# third quarter 5.octant
# third quarter 6.octant
# fourth quarter 7.octant
# fourth quarter 8.octant
if switch < 0:
switch = switch + (4 * x) + 6
else:
switch = switch + (4 * (x - y)) + 10
y = y - 1
x = x + 1
return points

size = 100
circle_graph = PIL.Image.new("RGB", (size, size), (0,0,0))
draw = PIL.ImageDraw.Draw(circle_graph)
# print the point coords
print p
for point in p:
draw.point((size/2+point,size/2+point),(255,255,255))
circle_graph.show()``````

Reason for this request?

Have you tested that normal 'turtle' trigonometric approach is not fast enough?

I only know to do archs with turtle graphics like this:

``````from turtle import *
def toarch(stepsize, turn, totalturn):
for count in xrange(totalturn//turn+1):
forward(stepsize)
right(turn)

def toarrow(stepsize, turn, totalturn):
pd()
toarch(stepsize, turn, totalturn)
width_of_arrow = 60
left(180- width_of_arrow//2)
forward(20)
pu()
backward(20)
left(width_of_arrow)
pd()
forward(20)
backward(20)
pu()
left(180- …``````

## All 9 Replies

Reason for this request?

Reason for this request?

I am trying to program an arrow algorithm for bent arrows
in PIL. I know there is something like matplotlib existing
but it is pretty slow and try to get a fast routine for
which the Bresenham routine is apprpriate. The arrows shall
have a start and end angle and so I ask for the Bresenham
arc routine.

Have you tested that normal 'turtle' trigonometric approach is not fast enough?

Have you tested that normal 'turtle' trigonometric approach is not fast enough?

I don´t know the normal "turtle" trigonometric approach. Do you have any hints/links to this one?

I only know to do archs with turtle graphics like this:

``````from turtle import *
def toarch(stepsize, turn, totalturn):
for count in xrange(totalturn//turn+1):
forward(stepsize)
right(turn)

def toarrow(stepsize, turn, totalturn):
pd()
toarch(stepsize, turn, totalturn)
width_of_arrow = 60
left(180- width_of_arrow//2)
forward(20)
pu()
backward(20)
left(width_of_arrow)
pd()
forward(20)
backward(20)
pu()
left(180- width_of_arrow//2)

def initialize():
clearscreen()
delay(0)
ht()
color('black','white')

initialize()
width(4)

pu()
forward(40)
write('Start', font=('Arial', 22, 'bold'))
forward(60)

toarrow(5,2, 180)

pu()
forward(60)
write('End', font=('Arial', 22, 'bold'))

forward(20)
toarrow(5,2, 180)

mainloop()``````

This differential geometry of going forward and turns are using trigonometric functions see the source of turtle.py (IDLE open module)

``````def rotate(self, angle):
"""rotate self counterclockwise by angle
"""
perp = Vec2D(-self, self)
angle = angle * math.pi / 180.0
c, s = math.cos(angle), math.sin(angle)
return Vec2D(self*c+perp*s, self*c+perp*s)``````

Hi Tonyjv,

thank you very much for your suggestions. Unfortunately the turtle module seems to be too slow for what I am aiming at.
So I went through hours of programming and complicated case differentations on the original Bresenham circle algorithm and here is my result, the Bresenham-Bunkus algo which even has the possibility not to only draw arcs but even draw pie shaped forms with the algorithm. No warranty that it does work in every case but I did test in many cases and it seems to work fine in all cases I tested. If you find any cases which do not produce the desired results let me know or even better try to find the bug in the code.

So here is the circle arc pie algorithm based on Bresenham by Bunkus:

``````import PIL.Image, PIL.ImageDraw, math, time

"Python implementation of the original Bresenham algorithm for complete circles"
# init vars
switch = 3 - (2 * radius)
points = set()
x = 0
# first quarter/octant starts clockwise at 12 o'clock
while x <= y:
# first quarter first octant
# first quarter 2nd octant
# second quarter 3rd octant
# second quarter 4.octant
# third quarter 5.octant
# third quarter 6.octant
# fourth quarter 7.octant
# fourth quarter 8.octant
if switch < 0:
switch = switch + (4 * x) + 6
else:
switch = switch + (4 * (x - y)) + 10
y = y - 1
x = x + 1
return points

"""Python implementation of the modified Bresenham algorithm
for complete circles, arcs and pies
start and end are angles in radians
function will return a list of points (tuple coordinates)
and the coordinates of the start and end point in a list xy
"""
if start>=math.pi*2:
if end>=math.pi*2:
# always clockwise drawing, if anti-clockwise drawing desired
# exchange start and end
if not clockwise:
s = start
start = end
end = s
# determination which quarters and octants are necessary
# init vars
xy = [[0,0], [0,0]] # to locate actual start and end point for pies
# the x/y border value for drawing the points
q_x = []
q_y = []
# first q element in list q is quarter of start angle
# second q element is quarter of end angle
# now determine the quarters to compute
q = []
# 0 - 90 degrees = 12 o clock to 3 o clock = 0.0 - math.pi/2 --> q==1
# 90 - 180 degrees = math.pi/2 - math.pi --> q==2
# 180 - 270 degrees = math.pi - math.pi/2*3 --> q==3
# 270 - 360 degrees = math.pi/2*3 - math.pi*2 --> q==4
j = 0
for i in [start, end]:
angle = i
if angle<math.pi/2:
q.append(1)
# compute the minimum x and y-axis value for plotting
if j==1 and angle==0:
xy = [0,-radius] # 90 degrees
elif angle>=math.pi/2 and angle<math.pi:
q.append(2)
# compute the minimum x and y-axis value for plotting
if j==1 and angle==math.pi/2:
xy = [radius,0] # 90 degrees
elif angle>=math.pi and angle<math.pi/2*3:
q.append(3)
# compute the minimum x and y-axis value for plotting
if j==1 and angle==math.pi:
else:
q.append(4)
# compute the minimum x and y-axis value for plotting
if j==1 and angle==math.pi/2*3:
j = j + 1
# print "q", q, "q_x", q_x, "q_y", q_y
quarters = []
sq = q
while 1:
quarters.append(sq)
if q == sq and start<end or q == sq and start>end and q!=q:
break # we reach the final end quarter
elif q == sq and start>end:
quarters.extend([(sq+1)%5, (sq+2)%5, (sq+3)%5, (sq+4)%5])
break
else:
sq = sq + 1
if sq>4:
sq = 1
# print "quarters", quarters
switch = 3 - (2 * radius)
points = []
points1 = set()
points2 = set()
points3 = set()
points4 = set()
#
x = 0
# first quarter/octant starts clockwise at 12 o'clock
while x <= y:
if 1 in quarters:
if not (1 in q):
# add all points of the quarter completely
# first quarter first octant
# first quarter 2nd octant
else:
# start or end point in this quarter?
if q == 1:
# start point
if q_x<=x and q_y>=abs(-y) and len(quarters)>1 or q_x<=x and q_x>=x:
# first quarter first octant
if -y<xy:
xy = [x,-y]
elif -y==xy:
if x<xy:
xy = [x,-y]
if q_x<=y and q_y>=abs(-x) and len(quarters)>1 or q_x<=y and q_x>=y and q_y>=abs(-x) and q_y<=abs(-x):
# first quarter 2nd octant
if -x<xy:
xy = [y,-x]
elif -x==xy:
if y<xy:
xy = [y,-x]
if q == 1:
# end point
if q_x>=x and len(quarters)>1 or q_x<=x and q_x>=x:
# first quarter first octant
if x>xy:
xy = [x,-y]
elif x==xy:
if -y>xy:
xy = [x,-y]
if q_x>=y and q_y<=abs(-x) and len(quarters)>1 or q_x<=y and q_x>=y and q_y>=abs(-x) and q_y<=abs(-x):
# first quarter 2nd octant
if y>xy:
xy = [y,-x]
elif y==xy:
if -x>xy:
xy = [y,-x]
if 2 in quarters:
if not (2 in q):
# add all points of the quarter completely
# second quarter 3rd octant
# second quarter 4.octant
else:
# start or end point in this quarter?
if q == 2:
# start point
if q_x>=y and q_y<=x and len(quarters)>1 or q_x>=y and q_x<=y and q_y<=x and q_y>=x:
# second quarter 3rd octant
if y>xy:
xy = [y,x]
elif y==xy:
if x<xy:
xy = [y,x]
if q_x>=x and q_y<=y and len(quarters)>1 or q_x>=x and q_x<=x:
# second quarter 4.octant
if x>xy:
xy = [x,y]
elif x==xy:
if y<xy:
xy = [x,y]
if q == 2:
# end point
if q_x<=y and q_y>=x and len(quarters)>1 or q_x>=y and q_x<=y and q_y<=x and q_y>=x:
# second quarter 3rd octant
if x>xy:
xy = [y,x]
elif x==xy:
if y<xy:
xy = [y,x]
if q_x<=x and q_y>=y and len(quarters)>1 or q_x>=x and q_x<=x:
# second quarter 4.octant
if y>xy:
xy = [x,y]
elif x==xy:
if x<xy:
xy = [x,y]
if 3 in quarters:
if not (3 in q):
# add all points of the quarter completely
# third quarter 5.octant
# third quarter 6.octant
else:
# start or end point in this quarter?
if q == 3:
# start point
if q_x<=x and q_y>=abs(y) and len(quarters)>1 or q_x<=x and q_x>=x:
# third quarter 5.octant
if y>xy:
xy = [-x,y]
elif y==xy:
if -x>xy:
xy = [-x,y]
if q_x<=y and q_y>=abs(x) and len(quarters)>1 or q_x<=y and q_x>=y and q_y>=x and q_y<=x:
# third quarter 6.octant
if x>xy:
xy = [-y,x]
elif x==xy:
if -y>xy:
xy = [-y,x]
if q == 3:
# end point
if q_x>=x and len(quarters)>1 or q_x<=x and q_x>=x:
# third quarter 5.octant
if -x<xy:
xy = [-x,y]
elif -x==xy:
if y<xy:
xy = [-x,y]
if q_x>=y and q_y<=abs(x) and len(quarters)>1 or q_x<=y and q_x>=y and q_y>=x and q_y<=x:
# third quarter 6.octant
if -y<xy:
xy = [-y,x]
elif -y==xy:
if x<xy:
xy = [-y,x]
if 4 in quarters:
if not (4 in q):
# add all points of the quarter completely
# fourth quarter 7.octant
# fourth quarter 8.octant
else:
# start or end point in this quarter?
if q == 4:
# start point
if q_x>=y and q_y<=abs(-x) and len(quarters)>1 or q_x>=y and q_x<=y and q_y<=x and q_y>=x:
# fourth quarter 7.octant
if -y<xy:
xy = [-y,-x]
elif -y==xy:
if -x>xy:
xy = [-y,-x]
if q_x>=x and q_y<=abs(-y) and len(quarters)>1 or q_x>=x and q_x<=x:
# fourth quarter 8.octant
if -x<xy:
xy = [-x,-y]
elif -x==xy:
if -y>xy:
xy = [-x,-y]
if q == 4:
# end point
if q_x<=y and q_y>=x and len(quarters)>1 or q_x>=y and q_x<=y  and q_y<=x and q_y>=x:
# fourth quarter 7.octant
if -x<xy:
xy = [-y,-x]
elif -x==xy:
if -y>xy:
xy = [-y,-x]
if q_x<=x and q_y>=abs(-y) and len(quarters)>1 or q_x>=x and q_x<=x:
# fourth quarter 8.octant
if -y<xy:
xy = [-x,-y]
elif -y==xy:
if -x>xy:
xy = [-x,-y]
if switch < 0:
switch = switch + (4 * x) + 6
else:
switch = switch + (4 * (x - y)) + 10
y = y - 1
x = x + 1

if 1 in quarters:
points1_s = list(points1)
# points1_s.sort() # if your some reason you need them sorted
points.extend(points1_s)
if 2 in quarters:
points2_s = list(points2)
# points2_s.sort() # if your some reason you need them sorted
# points2_s.reverse() # # if your some reason you need in right order
points.extend(points2_s)
if 3 in quarters:
points3_s = list(points3)
# points3_s.sort()
# points3_s.reverse()
points.extend(points3_s)
if 4 in quarters:
points4_s = list(points4)
# points4_s.sort()
points.extend(points4_s)
return points, xy

def draw_circle_arc(size, background, color, radius, start, end):
circle_graph = PIL.Image.new("RGB", (size, size), background)
draw = PIL.ImageDraw.Draw(circle_graph)
p, xy = circle_arc(radius, start, end)
# draw the arc points
for point in p:
draw.point((size/2+point,size/2+point),color)
# draw the pie lines
draw.line((size/2,size/2, size/2+xy, size/2+xy),color)
draw.line((size/2,size/2, size/2+xy, size/2+xy),color)
return circle_graph, xy

circle_graph = PIL.Image.new("RGB", (size, size), background)
draw = PIL.ImageDraw.Draw(circle_graph)
lista = []
for i in range(10):
lista.append(18+i*36)
for i in range(0,len(lista),2):
p, xy = circle_arc(r, start, end)
for point in p:
draw.point((size/2+point,size/2+point),color)
draw.line((size/2,size/2, size/2+xy, size/2+xy),color)
draw.line((size/2,size/2, size/2+xy, size/2+xy),color)
return circle_graph

size = 400 # of current image
background = (0,0,0) # background color
color = (255,255,255) # line color
print time.time() # just for benchmarking
start = math.radians(5) # give the start angle in degrees (0-359)
end = math.radians(268) # give the end angle in degrees (0-359)
circlearc_drawing,xy = draw_circle_arc(size, background, color, radius, start, end)
print time.time()
circlearc_drawing.show()
# these are the point ccordinates of the edges of the arc for pie drawing
print xy
print time.time()
circlearcs_drawing = draw_circle_arcs(size, background, color, radius)
print time.time()
circlearcs_drawing.show()``````

Here is an update of some corrections of the original routine,
some bugs and minor errors have been corrected. Hope this is the final
version of circle_arc Breesenham-Bunkus:

``````def circle_arc(radius, start, end, clockwise=True):
"""Python implementation of the modified Bresenham algorithm
for complete circles, arcs and pies
start and end are angles in radians
function will return a list of points (tuple coordinates)
and the coordinates of the start and end point in a list xy
"""
# round it to avoid rounding errors and wrong drawn pie slices
if start>=math.pi*2:
if end>=math.pi*2:
# always clockwise drawing, if anti-clockwise drawing desired
# exchange start and end
if not clockwise:
s = start
start = end
end = s
# determination which quarters and octants are necessary
# init vars
xy = [[0,0], [0,0]] # to locate actual start and end point for pies
# the x/y border value for drawing the points
q_x = []
q_y = []
# first q element in list q is quarter of start angle
# second q element is quarter of end angle
# now determine the quarters to compute
q = []
# 0 - 90 degrees = 12 o clock to 3 o clock = 0.0 - math.pi/2 --> q==1
# 90 - 180 degrees = math.pi/2 - math.pi --> q==2
# 180 - 270 degrees = math.pi - math.pi/2*3 --> q==3
# 270 - 360 degrees = math.pi/2*3 - math.pi*2 --> q==4
j = 0
for i in [start, end]:
angle = i
if angle<math.pi/2:
q.append(1)
# compute the minimum x and y-axis value for plotting
if j==1 and angle==0:
xy = [0,-radius] # 90 degrees
elif angle>=math.pi/2 and angle<math.pi:
q.append(2)
# compute the minimum x and y-axis value for plotting
if j==1 and angle==math.pi/2:
xy = [radius,0] # 90 degrees
elif angle>=math.pi and angle<math.pi/2*3:
q.append(3)
# compute the minimum x and y-axis value for plotting
if j==1 and angle==math.pi:
else:
q.append(4)
# compute the minimum x and y-axis value for plotting
if j==1 and angle==math.pi/2*3:
j = j + 1
# print "q", q, "q_x", q_x, "q_y", q_y
quarters = []
sq = q
while 1:
quarters.append(sq)
if q == sq and start<end or q == sq and start>end and q!=q:
break # we reach the final end quarter
elif q == sq and start>end:
quarters.extend([(sq+1)%5, (sq+2)%5, (sq+3)%5, (sq+4)%5])
break
else:
sq = sq + 1
if sq>4:
sq = 1
# print "quarters", quarters
switch = 3 - (2 * radius)
points = []
points1 = set()
points2 = set()
points3 = set()
points4 = set()
#
x = 0
# first quarter/octant starts clockwise at 12 o'clock
while x <= y:
if 1 in quarters:
if not (1 in q):
# add all points of the quarter completely
# first quarter first octant
# first quarter 2nd octant
else:
# start or end point in this quarter?
if q == 1:
# start point
if q_x<=x and q_y>=abs(-y) and len(quarters)>1 or q_x<=x and q_x>=x:
# first quarter first octant
if -y<xy:
xy = [x,-y]
elif -y==xy:
if x<xy:
xy = [x,-y]
if q_x<=y and q_y>=x and len(quarters)>1 or q_x<=y and q_x>=y and q_y>=abs(-x) and q_y<=abs(-x):
# first quarter 2nd octant
if -x<xy:
xy = [y,-x]
elif -x==xy:
if y<xy:
xy = [y,-x]
if q == 1:
# end point
if q_x>=x and len(quarters)>1 or q_x<=x and q_x>=x:
# first quarter first octant
if x>xy:
xy = [x,-y]
elif x==xy:
if -y>xy:
xy = [x,-y]
if q_x>=y and q_y<=x and len(quarters)>1 or q_x<=y and q_x>=y and q_y>=abs(-x) and q_y<=abs(-x):
# first quarter 2nd octant
if y>xy:
xy = [y,-x]
elif y==xy:
if -x>xy:
xy = [y,-x]
if 2 in quarters:
if not (2 in q):
# add all points of the quarter completely
# second quarter 3rd octant
# second quarter 4.octant
else:
# start or end point in this quarter?
if q == 2:
# start point
if q_x>=y and q_y<=x and len(quarters)>1 or q_x>=y and q_x<=y and q_y<=x and q_y>=x:
# second quarter 3rd octant
if y>xy:
xy = [y,x]
elif y==xy:
if x<xy:
xy = [y,x]
if q_x>=x and q_y<=y and len(quarters)>1 or q_x>=x and q_x<=x and q_y<=y and q_y>=y:
# second quarter 4.octant
if x>xy:
xy = [x,y]
elif x==xy:
if y<xy:
xy = [x,y]
if q == 2:
# end point
if q_x<=y and q_y>=x and len(quarters)>1 or q_x>=y and q_x<=y and q_y<=x and q_y>=x:
# second quarter 3rd octant
if x>xy:
xy = [y,x]
elif x==xy:
if y<xy:
xy = [y,x]
if q_x<=x and q_y>=y and len(quarters)>1 or q_x>=x and q_x<=x and q_y<=y and q_y>=y:
# second quarter 4.octant
if y>xy:
xy = [x,y]
elif x==xy:
if x<xy:
xy = [x,y]
if 3 in quarters:
if not (3 in q):
# add all points of the quarter completely
# third quarter 5.octant
# third quarter 6.octant
else:
# start or end point in this quarter?
if q == 3:
# start point
if q_x<=x and q_y>=abs(y) and len(quarters)>1 or q_x<=x and q_x>=x:
# third quarter 5.octant
if y>xy:
xy = [-x,y]
elif y==xy:
if -x>xy:
xy = [-x,y]
if q_x<=y and q_y>=x and len(quarters)>1 or q_x<=y and q_x>=y and q_y>=x and q_y<=x:
# third quarter 6.octant
if x>xy:
xy = [-y,x]
elif x==xy:
if -y>xy:
xy = [-y,x]
if q == 3:
# end point
if q_x>=x and len(quarters)>1 or q_x<=x and q_x>=x:
# third quarter 5.octant
if -x<xy:
xy = [-x,y]
elif -x==xy:
if y<xy:
xy = [-x,y]
if q_x>=y and q_y<=x and len(quarters)>1 or q_x<=y and q_x>=y and q_y>=x and q_y<=x:
# third quarter 6.octant
if -y<xy:
xy = [-y,x]
elif -y==xy:
if x<xy:
xy = [-y,x]
if 4 in quarters:
if not (4 in q):
# add all points of the quarter completely
# fourth quarter 7.octant
# fourth quarter 8.octant
else:
# start or end point in this quarter?
if q == 4:
# start point
if q_x>=y and q_y<=x and len(quarters)>1 or q_x>=y and q_x<=y and q_y<=x and q_y>=x:
# fourth quarter 7.octant
if -y<xy:
xy = [-y,-x]
elif -y==xy:
if -x>xy:
xy = [-y,-x]
if q_x>=x and q_y<=abs(-y) and len(quarters)>1 or q_x>=x and q_x<=x and q_y<=y and q_y>=y:
# fourth quarter 8.octant
if -x<xy:
xy = [-x,-y]
elif -x==xy:
if -y>xy:
xy = [-x,-y]
if q == 4:
# end point
if q_x<=y and q_y>=x and len(quarters)>1 or q_x>=y and q_x<=y  and q_y<=x and q_y>=x:
# fourth quarter 7.octant
if -x<xy:
xy = [-y,-x]
elif -x==xy:
if -y>xy:
xy = [-y,-x]
if q_x<=x and q_y>=abs(-y) and len(quarters)>1 or q_x>=x and q_x<=x and q_y<=y and q_y>=y:
# fourth quarter 8.octant
if -y<xy:
xy = [-x,-y]
elif -y==xy:
if -x>xy:
xy = [-x,-y]
if switch < 0:
switch = switch + (4 * x) + 6
else:
switch = switch + (4 * (x - y)) + 10
y = y - 1
x = x + 1

if 1 in quarters:
points1_s = list(points1)
# points1_s.sort() # if for some reason you need them sorted
points.extend(points1_s)
if 2 in quarters:
points2_s = list(points2)
# points2_s.sort() # if for some reason you need them sorted
# points2_s.reverse() # # if for some reason you need in right order
points.extend(points2_s)
if 3 in quarters:
points3_s = list(points3)
# points3_s.sort()
# points3_s.reverse()
points.extend(points3_s)
if 4 in quarters:
points4_s = list(points4)
# points4_s.sort()
points.extend(points4_s)
return points, xy``````

This is a greate example for getting all the points from an arc. But How can I use the same thing in java? Can you please provide this code in java?

Thank you.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.