What is a good algorithm to draw circle borders on a square grid?

Keywords´╝Ü algorithm lua geometry drawing


I have a square grid where I can draw only lines. I need to draw a 'rough outline' (blue) of a specified circle (red). Unfortunately I can't come up with a good algorithm.

I tried to separate circle in 4 quarters, do one of them (parts 1 and 2) and just mirror it. But my algorithm fails in the part 2, where x increases too slowly. I feel like I'm doing something wrong and there is a much better and performance-friendly way.

Code in Lua:

-- half refers to the 1/2 side of one square
function drawCircleOutline(half, circleRadius)
    local y = math.floor(circleRadius)
    local prevY = y
    local baseX, baseY = 0, y
    local screenX, screenY = getCoordinatesScreenPosition(0, y) -- gives screen coordinates of the center of a square, we'll need to correct them using 'half'
    local endX = y
    for x = 0, endX do
        -- trying to adjust border Y coordinate
        for z = 1, -10, -1 do
            if length(x, y + z) <= circleRadius then
                y = y + z
        local newScreenX = screenX + (x - baseX) * half * 2
        local newScreenY = screenY + (y - baseY) * half * 2
        drawLine(newScreenX - half, newScreenY - half, newScreenX + half, newScreenY - half)
        if y < prevY then
            drawLine(newScreenX - half, newScreenY - half * ((prevY - y) * 2 + 1), newScreenX - half, newScreenY - half)
        prevY = y



Similar questions

Programmatically creating a unique schedule for a given number of teams in multiple divisions

Scheduling interview algorithm to minimize number of applicants in an interview

Why Big-O is a misused term

k length combination of n length string where no repeated character is present

Program to find whether an edge exists between two given vertices of a graph

Improve the time complexity of my implementation of Counting Sort (C)

What's the most efficient way to extract min, max & median from a vector

parse a number represented as string and return array of numbers satisfying fibonacci relation

What's a formula to hash a string if your only goal is even distribution of output characters with N length?

Custom JavaScript sorting algorithm not sorting correctly

How to calculate time complexity of given algorithm ( ridge regression)?

Is there a simple algorithm to fit rectangles of differing sizes into a larger rectangular-container through one side

how to represent non-binary trees with 1D-arrays?

How to fix a directed graph on undirected?

How to use python to test if a line can cross a certain point?

Find offset between two matrices

What is the time complexity of the algorithm to check if a number is prime?

returning possible decodes of a sequence of numbers

Is there an equivalent (or faster) version of numpy.binCount in R for summing values based on multiple bins?

Algorithm: Fastest possible route from n nodes, where each node must be visited in one of m time intervals