Computing circles without Sin() or Cos()

May 22, 2019
493
255
63
So I was thinking about how I'd draw a circle, but without using the SIN and COS functions in the software. Instead, I'm using the Pythagorean theorem.

So what do we know about circles? A circle is the graph of all points that are equidistant from the center point. In other words, all of the points on a circle are the same distance from the center.

In graphics, any time we talk "distance", we might invoke Pythagoras. Anyone who has taken high school geometry probably remembers the formula:
a²+b²=c²
Re-written for a 2D graphics plane, we can say
x²+y²=d²
where d is the distance from the starting point, and x and y are the horizontal and vertical distance between the start and end points.

Normally, we solve this for d, getting the distance to a point, but what if we wanted to solve this for the x component? So I transformed the formula into...
d² = x² + y²
d² - y² = x² + y² - y²
d² - y² = x²
x² = d² - y²
x = √(d²-y²)
finally, we convert this to program code:
x = sqrt(d*d - y*y)

What this actually gives us is an arc...., like this:
1573067716732.png


So how to turn that into a circle? We just plot the same point by negating the x offset, then repeat with the y offset negated:

x = sqrt(d*d - y*y)
x = -sqrt(d*d - y*y)
x = sqrt(d*d - -y*-y)
x = -sqrt(d*d - -y*-y)

and some BASIC code:
1573067970048.png

This creates a filled circle, by drawing from the X axis out to the edge. If we want a filled circle, we should instead draw a line from the previous point to the next one. This prevents the broken arc we saw in the first image:

1573068386324.png


Here's the program listing:
Code:
10 SCREEN $80
20 RECT 0,0,319,199,12
30 X=160:Y=100:R=75:C=2
100 FOR YO=0 TO R
110 XO = SQR(R*R - YO*YO)
130 LINE X-XO,Y+YO,X+XO,Y+YO,C
140 LINE X+XO,Y-YO,X-XO,Y-YO,C
170 LX=XO:LY=YO
190 NEXT
200 C=5
210 LX=R:LY=Y
220 FOR YO=0 TO R
230 XO = SQR(R*R - YO*YO)
240 LINE X+LX,Y+YO,X+XO,Y+YO,C
250 LINE X-LX,Y+YO,X-XO,Y+YO,C
260 LINE X+LX,Y-YO,X+XO,Y-YO,C
270 LINE X-LX,Y-YO,X-XO,Y-YO,C
280 LX=XO:LY=YO
290 NEXT
300 C=1
310 PSET X,Y,C
And, for fun, here is an animated GIF showing the whole sequence:

circle.gif
 
Last edited:
  • Like
Reactions: mobluse
May 22, 2019
493
255
63
So I wanted to look closer at the broken arc in my first figure. Let's take another look at that:



What's going on here is that once we pass the 45° mark, the X offset is changing by more than 1 unit per row. This is entirely expected, as 45° is the point at which the X and Y offsets match.

In my first example, I saved the last point and drew a line from that to the next one, to guarantee contiguous lines. There is another method, one that uses more lines of code, but is a little faster.

So in the first example, we draw 4 pixels for each calculation by negating the X and Y offsets, in turn:

x = sqrt(d*d - y*y)
x = -sqrt(d*d - y*y)
x = sqrt(d*d - -y*-y)
x = -sqrt(d*d - -y*-y)

Of course, there's no rule saying we can't also solve this equation for Y. So what happens if we solve for Y, instead of X?

y = sqrt(d*d - x*x)


We get the same broken circle, but turned 90°
1573074311132.png


So can we take advantage of this?

As it turns out, we can... we can draw half of the arc by solving for X, then draw half of the arc solving for Y. But the trick is to figure out where the 45° mark actually is.... it's not at 50% down. It's actually at 71% down, or more precisely, 0.707.

Here's a graphic illustration of the 45° point:
1573075070179.png

What this means is we need to draw 71% of the way down solving for X, then draw 71% of the way across solving for Y.

That results in two loops, which look something like this:
Code:
R1=R * 0.707
FOR YO=0 TO R1
  XO = SQR(R*R - YO*YO)
  PSET X+XO,Y+YO,C
NEXT
FOR XO=0 TO R1
  YO = SQR(R*R - XO*XO)
  PSET X+XO,Y+YO,C
NEXT
That, indeed draws a full 90° arc.
1573075401515.png

But the two loop approach is a little ugly... so let's combine the two loops into one block of code

Code:
R1=R * 0.707
FOR YO=0 TO R1
  XO = SQR(R*R - YO*YO)
  PSET X+XO,Y+YO,C
  PSET X+=YO,Y+XO,C
NEXT
And when we then draw all four quadrants using this method, we get the program below

Code:
10 SCREEN $80
20 RECT 0,0,319,199,15
30 X=160:Y=100
40 R=75:R1=R*0.71
300 C=0
305 T1=TI
310 FOR YO=0 TO R1
320 XO = SQR(R*R - YO*YO)
330 PSET X+XO,Y+YO,C
340 PSET X-XO,Y+YO,C
350 PSET X-XO,Y-YO,C
360 PSET X+XO,Y-YO,C
370 PSET X+YO,Y+XO,C
380 PSET X-YO,Y+XO,C
390 PSET X-YO,Y-XO,C
400 PSET X+YO,Y-XO,C
410 NEXT
420 T2=TI
430 PRINTT2-T1
500 C=1
510 PSET X,Y,C
 

Schol-R-LEA

New Member
Sep 20, 2019
17
10
3
Perhaps you aren't aware (I am guessing that you are and are just using the opening paragraph as a framing device) that generally speaking, no one has been using trig functions in drawing complete 2D circles since the early 1970s (partial arcs are another matter, and even then they are only used for the endpoints).

The algorithm you are describing is similar to the Midpoint Circle Algorithm (explained somewhat less abstractly on Geeks4Geeks and given in several languages on Rosetta Code), except that the MPC manages to avoid the need for the square roots as well, and the most commonly used version even works with integer-only math.

I can try to get a version of MPC (and the more general Bresenham's ellipse algorithm) written RSN, if you like.
 
May 22, 2019
493
255
63
At this point, I’m just experimenting with trig and geometry. As it turns out, a 32 point ellipse with SIN() and COS() is still faster to plot than even using Bresenham.

I was really mostly just interested in the trigonometry, and solving for a and b grew out of that. I’ve actually written several implementations of the circle algorithm, but those are moot, since the intent was to demonstrate some algebra, rather than MPC or Bresenham. The thing I don’t like about those algorithms is they kind of divorce the math from the underlying geometry, which is fine when you’re optimizing programs for speed, but not when you’re explaining math and basic computing science.

I guess this is really an answer to a question asked elsewhere... why do I need to know algebra (and other maths) to write computer software? This is one application. This is a super simple use of algebra, but it’s an important one.
 
Last edited:

JoshuaScholar

New Member
Nov 6, 2019
4
0
1
I vaguely remember there was a trick that would draw almost circles, probably without any multiplies. They were SLIGHTLY elliptical diagonally.
 
May 22, 2019
493
255
63
Try searching for Bresenham circles, they can be done with integer math

Yes, I tried Bresenham, too, but while it's roughly 2x as fast as using the Pythagorean method, it's not very useful to demonstrate algebra, trigonometry, or geometry, which is more what I was going for.

Regardless, the SIN/COS method is still faster than any other method I've tried, depending on how many vertices I plot. (I usually go with 32.)