Drawing Circles using Bresenham's Circle Algorithm
update dec 2006
bresenham arc, line drawing, and scan conversion working
now! Thanks to Andy McFadden and Nick Westgate...
here is dsk image:
zipped disk image
I posted to Comp.sys.apple2.programmer newsgroup,
asking how to quickly compute an arc + area of
circle.
Andy McFadden replied with : this post , which pointed to:
this page, and this page.
I had been doing the the following
to compute circles:
*********************************************
10 gosub 1000: rem draw screen
20 END
1010 REM draw screen
1020 GR: COLOR = 7
1050 color = 3:plot 19,19 : rem center
1060 color = 4
1070 CX = 19:CY = 19 : rem center coordinates of circle
1100 r1=19 : rem radius of circle
1110 for a = 0 to 360:rem angle
1120 gosub 8000: rem compute x,y offset
1130 plot CX + x1 , CY + y1 : rem plot point
1140 next a
1150 return
8000 rem calc pt in circle
8010 ar = a * (3.14/180)
8020 x1 = r1 * cos (AR)
8030 y1=-r1 * sin (ar)
8040 return
*********************************************
This took 30 seconds in an emulator, running at
"real machine" speed.
Using the information contained in the articles
that Andy gave me links to, I was able to speed
this up to about 1 second execution time! :
*********************************************
500 radius = 19
510 CX = 19: cy = 19 : REM center coordinates
1000 D = 3 - (2*radius)
1010 X = 0
1020 Y = radius :rem (when x=0, Y = radius!)
2000"loop":
2010 if d < 0 then d = d + ( 4 * x ) + 6
:goto 3000: rem "D isn't < 0"
2020 if d > = 0 then d = d + 4 * ( x - y ) + 10
: y = y - 1
3000 rem "D isn't <0"
3010 gosub 4000: rem "plot"
3020 if x=y then GOTO 3500
3030 x=x+1:goto 2000 : rem "loop"
3040 END
3500 rem done with circle
3510 print "done"
3520 END
4000 rem "plot"
4010 plot cx+x, cy+y
4020 plot cx+x, cy-y
4030 plot cx-x,cy+y
4040 plot cx-x,cy-y
4050 plot cx+y,cy+x
4060 plot cx+y,cy-x
4070 plot cx-y,cy+x
4080 plot cx-y,cy-x
4090 return
*********************************************
this graphic shows the order that the points
are plotted in. Point 1 refers to line 4010
plot. point 2 refers to line 4020 plot, etc:
___________________
| number | line |
|_________|________|
| pt1: | 4010 |
| pt2: | 4020 |
| pt3: | 4030 |
| pt4: | 4040 |
| pt5: | 4050 |
| pt6: | 4060 |
| pt7: | 4070 |
| pt8: | 4080 |
|_________|________|
The graphic above shows what I want to figure
out next. I want to calculate a 45 degree
slice of the circle, and fill this area
(I actually want coordinates of all the points,
but if I can fill it, I know the points!)
The 45 degree slice that I want to compute
coordinates for can be *any* 45 degree slice.
As INPUT to the routine, I have the angle
of a line running through the center of
the 45 degree slice:
In the above example, the slice is centered
on 42 degree line. In my program I want
the 42 degrees to be variable, but always
compute a 45 degree segment of the circle.
more progress
the above graphic shows which plots
(in the code) refer to which angle
in the circle.
0 degrees on the circle is "up", or
"north". 180 is "down" or "south"
________________________
|number | degrees |
|_________|_____________|
1 | # 2 | 0 - 45 |
2 | # 6 | 45 - 90 |
3 | # 5 | 90 - 135 |
4 | # 1 | 135 - 180 |
5 | # 3 | 180 - 225 |
6 | # 7 | 225 - 270 |
7 | # 8 | 270 - 315 |
8 | # 4 | 315 - 0 |
-------------------------
Since I only want a 45 degree
segment of the circle, I will only
be using 2 of the lines in the PLOT
routine each time I do a calculation.
I need to determine WHICH of these
plots to use based on the input
angle of the routine.
I also have to skip drawing points
that are out of range.
DSK image of what I have so far
