Third party cookies may be stored when visiting this site. Please see the cookie information.

PenguinTutor YouTube Channel

Computer Science - Beginners Algorithm Design - Circle Algorithm

This is an introduction to algorithm design. This is designed to be a simple explanation for those starting in computer science and watching to understand about why we design algorithms, how to create better algorithms and how to evaluate those algorithms.

This is based around a practical example of drawing circles on a Badger 2040 hackable ID badge, similar to the Raspberry Pi Pico.
This is going to explain about how I came up with 3 different algorithm designs. The first two I created using mathematical principles, the third is based on a real world algorithm which is more efficient.

In the video I also discuss some unique aspects of the Badger 2040 including how to create an interactive game which is usuable despite the refresh mechanism used for e-paper displays. This is based on a pass-and-play implementation of Tic-Tac-Toe.

What is an algorithm?

An algoirithm is a process or set of rules which are followed to perform a calculation or to solve a problem. A useful analogy is with a cooking recipe. Just like a recipe describes the ingredients and how you combine them into something to eat, an algorithm tells you of the variables that you need and how the computer processes them to achieve the desired result. An algorithm can be as simple as saying increase x by 1, which would have something move left to right across the screen, or more complex such as finding the optimal route on a car satellite navigation system.

In this example the aim is to tell a computer how to draw a circle on the screen. This is done by calculating all the pixels that need to be coloured in. As you will see there are different ways that this can be achieved with different performance and correctness.

Creating a circle using trigonometry

The first example is based on basic rules of trigonometry.

Circle with right-angled triangle - trigonometry

The hypotenuse is shown as r, which is the radius of the circle. We need to know the co-ordinates x and y, which are calculated using the cosine and the sine of the angle. By starting the angle at zero and moving around the circle then the position of each of the pixels can be calculated.

An issue with this algorithm is that it involves a lot of processing to calculate all these points. This is known as time complexity.

Creating a circle using straight lines (approximation algorithm)

The next algorithm is an approximation algorithm. The aim is to have an algorithm that creates an approximation of what is desired, or in this case something that looks like a circle, even if it’s not.

This is actually quite a common technique, especially for problems that are NP-hard, effectively those who would need huge amounts of processing to perform a certain task. An example is the classic travelling salesman problem which is about choosing an optimum route between cities. The idea of using an approximation algorithm is that rather than trying to calculate every possible solution to find the shortest (which you can do with a small number of cities) then to have an algorithm which instead works out a route that is approximately the best solution.

We also use approximations in other aspects of computer science. For example JPEG images you capture with a phone use a technique to reduce the size of the files by using a lossey compression algorithm. The aim to have a picture that looks the same to a human as the original, but uses much less storage.

The approximation I used with the circle is to have something that looks like it’s made with curved lines, but is actually made of straight lines. This is particularly useful for use with the Badger 2040 as the library has a function for drawing a straight line, but not one for drawing curved lines.

At it’s most accurate a line could be just 1 pixel long and it would be exactly the same as a true circle (in the case of my 200 pixel circle that’s made up of about 1000 lines), or we could reduce it to only 100 lines (a Hectogon) or 10 lines a Decagon (as shown in the image below).

A circle from straight lines a decagon

This is farly intuitive and easy to understand. It also reduces the number of trigonometry calculations needed. This is the technique I used in the tic-tac-toe game for the Badger 2040. The code for drawing the circle is shown below.

def draw_circle(cx, cy, radius=10):

    degree_step_size = 10

    # build list of points

    points = []

    for i in range (0, 360, degree_step_size):

        irad = math.radians(i)

        this_x = int(cx + radius * math.cos(irad))

        this_y = int(cy + radius * math.sin(irad))

        points.append ((this_x, this_y))

    for i in range(len(points)-1):

        display.line (*points[i], *points[i+1])

    # final back to the start

    display.line(*points[len(points)-1], *points[0])

Mid-point Circle Drawing Algorithm

This is a more mathematically based algorithm which is used in real-world implementations of circle drawing functions.

For this to work you need to consider the circle split into 8 segments. The algorithm shown will calculate the values for the (x,y) segment and then you will need to apply the various translations to calculate for all 8 segments. This algorithm is based on calculating a single arc in the (x, y) segment.

Circle in 8 segments for computer science understanding of mid-point drawing algorithm

To implement this then you start at x = radius and y = 0
The next pixel is either (x, y+1) or (x-1, y+1).
To determine which then find the mid-point p of the two possible values (x-0.5, y+1) and if p is inside or on the perimeter then plot (x, y+1) otherwise plot (x-1, y+1).

To determine if p is inside or outside the circle use:
F(p) = x2 + y2 - r2

F(p) < 0 : inside the cricle
F(p) = 0 : on the perimeter
F(p) > 0 : outside the circle

The source code for the calculation of x, y and p is shown below.

Mid-point circle drawing algorithm

This has performance improvements compared to both the above and meets the correctness criteria.

Tic-Tac-Toe Game

This has been used to create a game which you can play on the Badger 2040. It's a pass-and-play version of tic-tac-toe.

Tic-Tac-Toe game on Badger 2040 (based on Raspberry Pi Pico)

This is the source code from the tic-tac-toe game. This uses the algorithrm that creates a circle using straight lines and the E-ink refresh settings.

import time, math

import badger2040

import badger_os

# Global Constants

WIDTH = badger2040.WIDTH

HEIGHT = badger2040.HEIGHT

# Tic-Tac-Toe / Noughts and Crosses game

# Grid is x,y

#     x is 0 to 2 (left to right)

#     y is 0 to 2 (top to bottom)

def draw():



    # Show grid



    display.line(103, 49, 193, 49)

    display.line(103, 79, 193, 79)

    display.line(133, 19, 133, 109)

    display.line(163, 19, 163, 109)


    # draw any played positions

    for gy in range (0, 3):

        for gx in range (0, 3):

            if (grid[gx][gy] == 0):

                # draw a cross

                draw_cross(gx, gy)

            elif (grid[gx][gy] == 1):

                # draw a nought

                draw_nought(gx, gy)



    # Only show player and cursor if in game

    if state == "play":

        # Show current player

        display.text("Player", 20, 20, 0.5)

        if (player == 0):

            draw_x (40, 50)

        elif (player == 1):

            draw_circle (40, 50)




    if state == "gameover":

        display.text ("Game Over", 10, 20, 0.5)

        # If there is a winner show the line

        winner = is_won()

        if winner >= 0:

            # Draw line 


            display.text ("Winner", 10, 40, 0.5)

            if winner == 0:

                draw_x (40, 70)

            if winner == 1:

                draw_circle (40, 70)

        # It's a draw


            display.text ("Draw", 10, 40, 0.5)



# Draw the noughts and crosses

# Top level - draw nought on grid

def draw_nought(gridx, gridy):

    # Approximation of a circle using lines

    # get centre of circle

    (cx, cy) = grid_to_coord(gridx, gridy)

    draw_circle (cx, cy)


# Lower level needs co-ords - useful for player scores etc.

def draw_circle(cx, cy, radius=10):

    degree_step_size = 10

    # build list of points

    points = []

    for i in range (0, 360, degree_step_size):

        irad = math.radians(i)

        this_x = int(cx + radius * math.cos(irad))

        this_y = int(cy + radius * math.sin(irad))

        points.append ((this_x, this_y))

    for i in range(len(points)-1):

        display.line (*points[i], *points[i+1])

    # final back to the start

    display.line(*points[len(points)-1], *points[0])


# High level - draw cross on grid

def draw_cross(gridx, gridy):

    # get centre of cross

    (cx, cy) = grid_to_coord(gridx, gridy)

    draw_x (cx, cy)


# Lower level needs co-ords - useful for player scores etc.

def draw_x (cx, cy):

    display.line (cx -10, cy -10, cx + 10, cy + 10)

    display.line (cx +10, cy -10, cx - 10, cy + 10) 

def draw_cursor(gridx, gridy):

    # draw square

    (cx, cy) = grid_to_coord(gridx, gridy)

    display.rectangle (cx -4, cy -4, 8, 8)

# ------------------------------

#        Helper methods

# ------------------------------

# Convert x,y position to centre of square

def grid_to_coord (gridx, gridy):

    x = 118 + 30 * gridx

    y = 34 + 30 * gridy


    return (x, y)

# Checks for possible wins

def is_won ():

    global willing_line

    # start with first square on a possible line, check that has a player assigned

    # then check rest of that line matches - if so then return the first square value

    # which will equal the player number. If not return -1

    # Check vertical lines

    for col in range (0, 3):

        if grid[col][0] != -1 and grid[col][0] == grid[col][1] and grid[col][1] == grid[col][2]:

            winning_line[0] = 118 + col * 30

            winning_line[1] = 19

            winning_line[2] = 118 + col * 30

            winning_line[3] = 109

            return grid[col][0]


    # Check horizontal lines

    for line in range (0, 3):

        if grid[0][line] != -1 and grid[0][line] == grid[1][line] and grid[1][line] == grid[2][line]:

            winning_line[0] = 103

            winning_line[1] = 34 + line * 30

            winning_line[2] = 193

            winning_line[3] = 34 + line * 30

            return grid[0][line]


    # check 2 diagnals

    if grid[0][0] != -1 and grid[0][0] == grid[1][1] and grid[1][1] == grid[2][2]:

        winning_line[0] = 103

        winning_line[1] = 19

        winning_line[2] = 193

        winning_line[3] = 109

        return grid[0][0]

    if grid[2][0] != -1 and grid[2][0] == grid[1][1] and grid[1][1] == grid[0][2]:

        winning_line[0] = 193

        winning_line[1] = 19

        winning_line[2] = 103

        winning_line[3] = 109

        return grid[2][0]


    # reach here no match

    return -1

# ------------------------------

#        Program setup

# ------------------------------

# Create a new Badger and set it to update NORMAL

display = badger2040.Badger2040()



# ------------------------------

#       Main program

# ------------------------------

state = "play"

# Player 0 = crosses (goes first on first game)

# Player 1 = noughts

player = 0

cursor = [0,0]

# number of goes played - when reach 9 know that grid is full

played = 0

# Grid is x y (cols then rows) - so array does not look the same

# -1 = none

# 0 = player 0

# 1 = player 1

grid = [

    [-1,-1, -1],



# winning_line used as a global to determine where to draw line when someone wins

winning_line = [0,0,0,0]

# Display initial screen



while (1):

    # wait for action (uses loop)

    while (1):

        if state == "play":


            if display.pressed(badger2040.BUTTON_A):

                if cursor[0] > 0:

                    cursor[0] -= 1


            if display.pressed(badger2040.BUTTON_C):

                if cursor[0] < 2:

                    cursor[0] += 1


            if display.pressed(badger2040.BUTTON_UP):

                if cursor[1] > 0:

                    cursor[1] -= 1


            if display.pressed(badger2040.BUTTON_DOWN):

                if cursor[1] < 2:

                    cursor[1] += 1


            if display.pressed(badger2040.BUTTON_B):


                # If empty then place the mark

                # If not empty then ignore button press

                if (grid[cursor[0]][cursor[1]] == -1):

                    grid[cursor[0]][cursor[1]] = player

                    played += 1

                    # Swap player and reset cursor

                    if player == 0:

                        player = 1


                        player = 0

                    # return cursor to top left

                    cursor[0] = 0

                    cursor[1] = 0


            # Otherwise press B to start game


                if display.pressed(badger2040.BUTTON_B):

                    state == "play"

    if is_won() >= 0 or played >= 9:

        state = "gameover"




More information

More information about the Badger 2040 badge.

See my other programming guides at:

Blog links and videos on programming

Previous Introduction to programming for teachers and parents
Introduction to programming for teachers and parents
Next Introduction to API
Introduction to API