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

Keywords： algorithm lua geometry drawing Question:

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
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
break
end
end
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)
end
prevY = y
end
end
``````  Answers: