Python Bresenham Circle Arc Algorithm

[bunkus]

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

def circle(radius):
    "Bresenham complete circle algorithm in Python"
    # init vars
    switch = 3 - (2 * radius)
    points = set()
    x = 0
    y = radius
    # first quarter/octant starts clockwise at 12 o'clock
    while x <= y:
        # first quarter first octant
        points.add((x,-y))
        # first quarter 2nd octant
        points.add((y,-x))
        # second quarter 3rd octant
        points.add((y,x))
        # second quarter 4.octant
        points.add((x,y))
        # third quarter 5.octant
        points.add((-x,y))        
        # third quarter 6.octant
        points.add((-y,x))
        # fourth quarter 7.octant
        points.add((-y,-x))
        # fourth quarter 8.octant
        points.add((-x,-y))
        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
radius = 40
circle_graph = PIL.Image.new("RGB", (size, size), (0,0,0))
draw = PIL.ImageDraw.Draw(circle_graph)
p = circle(radius)
# print the point coords
print p
for point in p:
    draw.point((size/2+point[0],size/2+point[1]),(255,255,255))
circle_graph.show()

[TrustyTony]

Reason for this request?

[bunkus]

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.

[TrustyTony]

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

[bunkus]

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?

[TrustyTony]

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[1], self[0])
        angle = angle * math.pi / 180.0
        c, s = math.cos(angle), math.sin(angle)
        return Vec2D(self[0]*c+perp[0]*s, self[1]*c+perp[1]*s)

[bunkus]

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

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

def circle_arc(radius, start, end, clockwise=True):
    """Python implementation of the modified Bresenham algorithm 
    for complete circles, arcs and pies
    radius: radius of the circle in pixels
    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:
        start = math.radians(math.degrees(start)%360)
    if end>=math.pi*2:
        end = math.radians(math.degrees(end)%360)
    # 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
            q_x.append(int(round(math.sin(angle)*radius)))
            q_y.append(int(round(math.cos(angle)*radius)))
            if j==1 and angle==0:
                xy[1] = [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
            q_x.append(int(round(math.cos(angle-math.pi/2)*radius)))
            q_y.append(int(round(math.sin(angle-math.pi/2)*radius)))
            if j==1 and angle==math.pi/2:
                xy[1] = [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
            q_x.append(int(round(math.sin(angle-math.pi)*radius)))
            q_y.append(int(round(math.cos(angle-math.pi)*radius)))
            if j==1 and angle==math.pi:
                xy[1] = [0, radius]
        else:
            q.append(4)
            # compute the minimum x and y-axis value for plotting
            q_x.append(int(round(math.cos(angle-math.pi/2*3)*radius)))
            q_y.append(int(round(math.sin(angle-math.pi/2*3)*radius)))
            if j==1 and angle==math.pi/2*3:
                xy[1] = [-radius, 0]
        j = j + 1
    # print "q", q, "q_x", q_x, "q_y", q_y
    quarters = []
    sq = q[0]
    while 1:
        quarters.append(sq)
        if q[1] == sq and start<end or q[1] == sq and start>end and q[0]!=q[1]:
            break # we reach the final end quarter
        elif q[1] == 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
    y = radius
    # 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
                points1.add((x,-y))
                # first quarter 2nd octant
                points1.add((y,-x))
            else:
                # start or end point in this quarter?
                if q[0] == 1: 
                    # start point
                    if q_x[0]<=x and q_y[0]>=abs(-y) and len(quarters)>1 or q_x[0]<=x and q_x[1]>=x:
                        # first quarter first octant
                        points1.add((x,-y))
                        if -y<xy[0][1]:
                            xy[0] = [x,-y]
                        elif -y==xy[0][1]:
                            if x<xy[0][0]:
                                xy[0] = [x,-y]
                    if q_x[0]<=y and q_y[0]>=abs(-x) and len(quarters)>1 or q_x[0]<=y and q_x[1]>=y and q_y[0]>=abs(-x) and q_y[1]<=abs(-x):
                        # first quarter 2nd octant
                        points1.add((y,-x))
                        if -x<xy[0][1]:
                            xy[0] = [y,-x]
                        elif -x==xy[0][1]:
                            if y<xy[0][0]:
                                xy[0] = [y,-x]
                if q[1] == 1:
                    # end point
                    if q_x[1]>=x and len(quarters)>1 or q_x[0]<=x and q_x[1]>=x:
                        # first quarter first octant
                        points1.add((x,-y))
                        if x>xy[1][0]:
                            xy[1] = [x,-y]
                        elif x==xy[1][0]:
                            if -y>xy[1][1]:
                                xy[1] = [x,-y]
                    if q_x[1]>=y and q_y[1]<=abs(-x) and len(quarters)>1 or q_x[0]<=y and q_x[1]>=y and q_y[0]>=abs(-x) and q_y[1]<=abs(-x):
                        # first quarter 2nd octant
                        points1.add((y,-x))
                        if y>xy[1][0]:
                            xy[1] = [y,-x]
                        elif y==xy[1][0]:
                            if -x>xy[1][1]:
                                xy[1] = [y,-x]
        if 2 in quarters:
            if not (2 in q):
                # add all points of the quarter completely
                # second quarter 3rd octant
                points2.add((y,x))
                # second quarter 4.octant
                points2.add((x,y))
            else:
                # start or end point in this quarter?
                if q[0] == 2: 
                    # start point
                    if q_x[0]>=y and q_y[0]<=x and len(quarters)>1 or q_x[0]>=y and q_x[1]<=y and q_y[0]<=x and q_y[1]>=x:
                        # second quarter 3rd octant
                        points2.add((y,x))
                        if y>xy[0][0]:
                            xy[0] = [y,x]
                        elif y==xy[0][0]:
                            if x<xy[0][1]:
                                xy[0] = [y,x]
                    if q_x[0]>=x and q_y[0]<=y and len(quarters)>1 or q_x[0]>=x and q_x[1]<=x:
                        # second quarter 4.octant
                        points2.add((x,y))
                        if x>xy[0][0]:
                            xy[0] = [x,y]
                        elif x==xy[0][0]:
                            if y<xy[0][1]:
                                xy[0] = [x,y]                        
                if q[1] == 2:
                    # end point
                    if q_x[1]<=y and q_y[1]>=x and len(quarters)>1 or q_x[0]>=y and q_x[1]<=y and q_y[0]<=x and q_y[1]>=x:
                        # second quarter 3rd octant
                        points2.add((y,x))
                        if x>xy[1][1]:
                            xy[1] = [y,x]
                        elif x==xy[1][1]:
                            if y<xy[1][0]:
                                xy[1] = [y,x]
                    if q_x[1]<=x and q_y[1]>=y and len(quarters)>1 or q_x[0]>=x and q_x[1]<=x:
                        # second quarter 4.octant
                        points2.add((x,y))
                        if y>xy[1][1]:
                            xy[1] = [x,y]
                        elif x==xy[1][1]:
                            if x<xy[1][0]:
                                xy[1] = [x,y]
        if 3 in quarters:    
            if not (3 in q):
                # add all points of the quarter completely
                # third quarter 5.octant
                points3.add((-x,y))        
                # third quarter 6.octant
                points3.add((-y,x))
            else:
                # start or end point in this quarter?
                if q[0] == 3:
                    # start point
                    if q_x[0]<=x and q_y[0]>=abs(y) and len(quarters)>1 or q_x[0]<=x and q_x[1]>=x:
                        # third quarter 5.octant
                        points3.add((-x,y))
                        if y>xy[0][1]:
                            xy[0] = [-x,y]
                        elif y==xy[0][1]:
                            if -x>xy[0][0]:
                                xy[0] = [-x,y]                        
                    if q_x[0]<=y and q_y[0]>=abs(x) and len(quarters)>1 or q_x[0]<=y and q_x[1]>=y and q_y[0]>=x and q_y[1]<=x:
                        # third quarter 6.octant
                        points3.add((-y,x))
                        if x>xy[0][1]:
                            xy[0] = [-y,x]
                        elif x==xy[0][1]:
                            if -y>xy[0][0]:
                                xy[0] = [-y,x]                                                
                if q[1] == 3:
                    # end point
                    if q_x[1]>=x and len(quarters)>1 or q_x[0]<=x and q_x[1]>=x:
                        # third quarter 5.octant
                        points3.add((-x,y))
                        if -x<xy[1][0]:
                            xy[1] = [-x,y]
                        elif -x==xy[1][0]:
                            if y<xy[1][1]:
                                xy[1] = [-x,y]
                    if q_x[1]>=y and q_y[1]<=abs(x) and len(quarters)>1 or q_x[0]<=y and q_x[1]>=y and q_y[0]>=x and q_y[1]<=x:
                        # third quarter 6.octant
                        points3.add((-y,x))
                        if -y<xy[1][0]:
                            xy[1] = [-y,x]
                        elif -y==xy[1][0]:
                            if x<xy[1][1]:
                                xy[1] = [-y,x]                        
        if 4 in quarters:
            if not (4 in q):
                # add all points of the quarter completely
                # fourth quarter 7.octant
                points4.add((-y,-x))
                # fourth quarter 8.octant
                points4.add((-x,-y))
            else:
                # start or end point in this quarter?
                if q[0] == 4: 
                    # start point
                    if q_x[0]>=y and q_y[0]<=abs(-x) and len(quarters)>1 or q_x[0]>=y and q_x[1]<=y and q_y[0]<=x and q_y[1]>=x:
                        # fourth quarter 7.octant
                        points4.add((-y,-x))
                        if -y<xy[0][0]:
                            xy[0] = [-y,-x]
                        elif -y==xy[0][0]:
                            if -x>xy[0][1]:
                                xy[0] = [-y,-x]
                    if q_x[0]>=x and q_y[0]<=abs(-y) and len(quarters)>1 or q_x[0]>=x and q_x[1]<=x:
                        # fourth quarter 8.octant
                        points4.add((-x,-y))
                        if -x<xy[0][0]:
                            xy[0] = [-x,-y]
                        elif -x==xy[0][0]:
                            if -y>xy[0][1]:
                                xy[0] = [-x,-y]                                                
                if q[1] == 4:
                    # end point
                    if q_x[1]<=y and q_y[1]>=x and len(quarters)>1 or q_x[0]>=y and q_x[1]<=y  and q_y[0]<=x and q_y[1]>=x:
                        # fourth quarter 7.octant
                        points4.add((-y,-x))
                        if -x<xy[1][1]:
                            xy[1] = [-y,-x]
                        elif -x==xy[1][1]:
                            if -y>xy[1][0]:
                                xy[1] = [-y,-x]
                    if q_x[1]<=x and q_y[1]>=abs(-y) and len(quarters)>1 or q_x[0]>=x and q_x[1]<=x:
                        # fourth quarter 8.octant
                        points4.add((-x,-y))
                        if -y<xy[1][1]:
                            xy[1] = [-x,-y]
                        elif -y==xy[1][1]:
                            if -x>xy[1][0]:
                                xy[1] = [-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[0],size/2+point[1]),color)
    # draw the pie lines
    draw.line((size/2,size/2, size/2+xy[0][0], size/2+xy[0][1]),color)
    draw.line((size/2,size/2, size/2+xy[1][0], size/2+xy[1][1]),color)
    return circle_graph, xy

def draw_circle_arcs(size, background, color, radius):
    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 r in [radius-10, radius]:
        for i in range(0,len(lista),2):
            start = math.radians(lista[i])
            end = math.radians(lista[i+1])
            p, xy = circle_arc(r, start, end)
            for point in p:
                draw.point((size/2+point[0],size/2+point[1]),color)
            draw.line((size/2,size/2, size/2+xy[0][0], size/2+xy[0][1]),color)
            draw.line((size/2,size/2, size/2+xy[1][0], size/2+xy[1][1]),color)
    return circle_graph

size = 400 # of current image
background = (0,0,0) # background color
color = (255,255,255) # line color
radius = 175 # radius of circle arc
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()

[bunkus]

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
    radius: radius of the circle in pixels
    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
    start = math.radians(round(math.degrees(start)))    
    end = math.radians(round(math.degrees(end)))
    if start>=math.pi*2:
        start = math.radians(math.degrees(start)%360)
    if end>=math.pi*2:
        end = math.radians(math.degrees(end)%360)
    # 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
            q_x.append(int(round(math.sin(angle)*radius)))
            q_y.append(int(round(math.cos(angle)*radius)))
            if j==1 and angle==0:
                xy[1] = [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
            q_x.append(int(round(math.cos(angle-math.pi/2)*radius)))
            q_y.append(int(round(math.sin(angle-math.pi/2)*radius)))
            if j==1 and angle==math.pi/2:
                xy[1] = [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
            q_x.append(int(round(math.sin(angle-math.pi)*radius)))
            q_y.append(int(round(math.cos(angle-math.pi)*radius)))
            if j==1 and angle==math.pi:
                xy[1] = [0, radius]
        else:
            q.append(4)
            # compute the minimum x and y-axis value for plotting
            q_x.append(int(round(math.cos(angle-math.pi/2*3)*radius)))
            q_y.append(int(round(math.sin(angle-math.pi/2*3)*radius)))
            if j==1 and angle==math.pi/2*3:
                xy[1] = [-radius, 0]
        j = j + 1
    # print "q", q, "q_x", q_x, "q_y", q_y
    quarters = []
    sq = q[0]
    while 1:
        quarters.append(sq)
        if q[1] == sq and start<end or q[1] == sq and start>end and q[0]!=q[1]:
            break # we reach the final end quarter
        elif q[1] == 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
    y = int(round(radius))
    # 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
                points1.add((x,-y))
                # first quarter 2nd octant
                points1.add((y,-x))
            else:
                # start or end point in this quarter?
                if q[0] == 1: 
                    # start point
                    if q_x[0]<=x and q_y[0]>=abs(-y) and len(quarters)>1 or q_x[0]<=x and q_x[1]>=x:
                        # first quarter first octant
                        points1.add((x,-y))
                        if -y<xy[0][1]:
                            xy[0] = [x,-y]
                        elif -y==xy[0][1]:
                            if x<xy[0][0]:
                                xy[0] = [x,-y]
                    if q_x[0]<=y and q_y[0]>=x and len(quarters)>1 or q_x[0]<=y and q_x[1]>=y and q_y[0]>=abs(-x) and q_y[1]<=abs(-x):
                        # first quarter 2nd octant
                        points1.add((y,-x))
                        if -x<xy[0][1]:
                            xy[0] = [y,-x]
                        elif -x==xy[0][1]:
                            if y<xy[0][0]:
                                xy[0] = [y,-x]
                if q[1] == 1:
                    # end point
                    if q_x[1]>=x and len(quarters)>1 or q_x[0]<=x and q_x[1]>=x:
                        # first quarter first octant
                        points1.add((x,-y))
                        if x>xy[1][0]:
                            xy[1] = [x,-y]
                        elif x==xy[1][0]:
                            if -y>xy[1][1]:
                                xy[1] = [x,-y]
                    if q_x[1]>=y and q_y[1]<=x and len(quarters)>1 or q_x[0]<=y and q_x[1]>=y and q_y[0]>=abs(-x) and q_y[1]<=abs(-x):
                        # first quarter 2nd octant
                        points1.add((y,-x))
                        if y>xy[1][0]:
                            xy[1] = [y,-x]
                        elif y==xy[1][0]:
                            if -x>xy[1][1]:
                                xy[1] = [y,-x]
        if 2 in quarters:
            if not (2 in q):
                # add all points of the quarter completely
                # second quarter 3rd octant
                points2.add((y,x))
                # second quarter 4.octant
                points2.add((x,y))
            else:
                # start or end point in this quarter?
                if q[0] == 2: 
                    # start point
                    if q_x[0]>=y and q_y[0]<=x and len(quarters)>1 or q_x[0]>=y and q_x[1]<=y and q_y[0]<=x and q_y[1]>=x:
                        # second quarter 3rd octant
                        points2.add((y,x))
                        if y>xy[0][0]:
                            xy[0] = [y,x]
                        elif y==xy[0][0]:
                            if x<xy[0][1]:
                                xy[0] = [y,x]
                    if q_x[0]>=x and q_y[0]<=y and len(quarters)>1 or q_x[0]>=x and q_x[1]<=x and q_y[0]<=y and q_y[1]>=y:
                        # second quarter 4.octant
                        points2.add((x,y))
                        if x>xy[0][0]:
                            xy[0] = [x,y]
                        elif x==xy[0][0]:
                            if y<xy[0][1]:
                                xy[0] = [x,y]                        
                if q[1] == 2:
                    # end point
                    if q_x[1]<=y and q_y[1]>=x and len(quarters)>1 or q_x[0]>=y and q_x[1]<=y and q_y[0]<=x and q_y[1]>=x:
                        # second quarter 3rd octant
                        points2.add((y,x))
                        if x>xy[1][1]:
                            xy[1] = [y,x]
                        elif x==xy[1][1]:
                            if y<xy[1][0]:
                                xy[1] = [y,x]
                    if q_x[1]<=x and q_y[1]>=y and len(quarters)>1 or q_x[0]>=x and q_x[1]<=x and q_y[0]<=y and q_y[1]>=y:
                        # second quarter 4.octant
                        points2.add((x,y))
                        if y>xy[1][1]:
                            xy[1] = [x,y]
                        elif x==xy[1][1]:
                            if x<xy[1][0]:
                                xy[1] = [x,y]
        if 3 in quarters:    
            if not (3 in q):
                # add all points of the quarter completely
                # third quarter 5.octant
                points3.add((-x,y))        
                # third quarter 6.octant
                points3.add((-y,x))
            else:
                # start or end point in this quarter?
                if q[0] == 3:
                    # start point
                    if q_x[0]<=x and q_y[0]>=abs(y) and len(quarters)>1 or q_x[0]<=x and q_x[1]>=x:
                        # third quarter 5.octant
                        points3.add((-x,y))
                        if y>xy[0][1]:
                            xy[0] = [-x,y]
                        elif y==xy[0][1]:
                            if -x>xy[0][0]:
                                xy[0] = [-x,y]                        
                    if q_x[0]<=y and q_y[0]>=x and len(quarters)>1 or q_x[0]<=y and q_x[1]>=y and q_y[0]>=x and q_y[1]<=x:
                        # third quarter 6.octant
                        points3.add((-y,x))
                        if x>xy[0][1]:
                            xy[0] = [-y,x]
                        elif x==xy[0][1]:
                            if -y>xy[0][0]:
                                xy[0] = [-y,x]                                                
                if q[1] == 3:
                    # end point
                    if q_x[1]>=x and len(quarters)>1 or q_x[0]<=x and q_x[1]>=x:
                        # third quarter 5.octant
                        points3.add((-x,y))
                        if -x<xy[1][0]:
                            xy[1] = [-x,y]
                        elif -x==xy[1][0]:
                            if y<xy[1][1]:
                                xy[1] = [-x,y]
                    if q_x[1]>=y and q_y[1]<=x and len(quarters)>1 or q_x[0]<=y and q_x[1]>=y and q_y[0]>=x and q_y[1]<=x:
                        # third quarter 6.octant
                        points3.add((-y,x))
                        if -y<xy[1][0]:
                            xy[1] = [-y,x]
                        elif -y==xy[1][0]:
                            if x<xy[1][1]:
                                xy[1] = [-y,x]                        
        if 4 in quarters:
            if not (4 in q):
                # add all points of the quarter completely
                # fourth quarter 7.octant
                points4.add((-y,-x))
                # fourth quarter 8.octant
                points4.add((-x,-y))
            else:
                # start or end point in this quarter?
                if q[0] == 4: 
                    # start point
                    if q_x[0]>=y and q_y[0]<=x and len(quarters)>1 or q_x[0]>=y and q_x[1]<=y and q_y[0]<=x and q_y[1]>=x:
                        # fourth quarter 7.octant
                        points4.add((-y,-x))
                        if -y<xy[0][0]:
                            xy[0] = [-y,-x]
                        elif -y==xy[0][0]:
                            if -x>xy[0][1]:
                                xy[0] = [-y,-x]
                    if q_x[0]>=x and q_y[0]<=abs(-y) and len(quarters)>1 or q_x[0]>=x and q_x[1]<=x and q_y[0]<=y and q_y[1]>=y:
                        # fourth quarter 8.octant
                        points4.add((-x,-y))
                        if -x<xy[0][0]:
                            xy[0] = [-x,-y]
                        elif -x==xy[0][0]:
                            if -y>xy[0][1]:
                                xy[0] = [-x,-y]
                if q[1] == 4:
                    # end point
                    if q_x[1]<=y and q_y[1]>=x and len(quarters)>1 or q_x[0]>=y and q_x[1]<=y  and q_y[0]<=x and q_y[1]>=x:
                        # fourth quarter 7.octant
                        points4.add((-y,-x))
                        if -x<xy[1][1]:
                            xy[1] = [-y,-x]
                        elif -x==xy[1][1]:
                            if -y>xy[1][0]:
                                xy[1] = [-y,-x]
                    if q_x[1]<=x and q_y[1]>=abs(-y) and len(quarters)>1 or q_x[0]>=x and q_x[1]<=x and q_y[0]<=y and q_y[1]>=y:
                        # fourth quarter 8.octant
                        points4.add((-x,-y))
                        if -y<xy[1][1]:
                            xy[1] = [-x,-y]
                        elif -y==xy[1][1]:
                            if -x>xy[1][0]:
                                xy[1] = [-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

[Shiladittya]

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.

[vegaseat]

Start with:
http://rosettacode.org/wiki/Bitmap/Midpoint_circle_algorithm#Java