Bresenham's circle drawing algorithm whose circle uses all coordinates when increasing the radius

Question

I want to draw circles that will not leave any coordinates not included in any circle. The problem is that currently, when you plot all circles for e.g. radii 1 to 4 that some coordinates are not included in any circle, for example (2,2). current circle with skipped coordinates

Missing coordinates can be included in either the larger or smaller circle.

This is my current code

import matplotlib.pyplot as plt


def bresenham_circle(x0, y0, radius):
  x = radius
  y = 0
  err = 0

  points = []

  while x >= y:
    points.append((x0 + x, y0 + y))
    points.append((x0 + y, y0 + x))
    points.append((x0 - y, y0 + x))
    points.append((x0 - x, y0 + y))
    points.append((x0 - x, y0 - y))
    points.append((x0 - y, y0 - x))
    points.append((x0 + y, y0 - x))
    points.append((x0 + x, y0 - y))

    y += 1
    err += 1 + 2*y
    if 2*(err-x) + 1 > 0:
      x -= 1
      err += 1 - 2*x

  return list(set(points))


coords_included_in_circles = []
for i in (1,2,3,4):
    coords_included_in_circles += bresenham_circle(0, 0, i)


# Scatter plot to visualize gaps
plt.scatter([x for x, y in coords_included_in_circles], [y for x, y in coords_included_in_circles])
plt.show()

The missing coordinates seem to follow a pattern but I am unable to deduce what pattern this is. I think it should also be possible to compare the circle of the current radius to the circle of radius - 1 and deduce what coordinates would be skipped and add these to the current circle, but wasn't successful with my limited skills.

Answer 1

You can achieve that if you are willing to only update either the x coordinate or the y coordinate, but not both in the same iteration. This is easy to accomplish, by just putting the y update in an else block.

Secondly, I think you have applied the update to err at the wrong moment. It should use the x value (y value) before it is updated. This will produce a bit more "accurate" circles.

Finally, with this altered method, the if condition should compare the difference between options that are now different, so the formula for comparison changes a bit.

So replace this piece of code:

    y += 1
    err += 1 + 2*y
    if 2*(err-x) + 1 > 0:
      x -= 1
      err += 1 - 2*x

with this:

    if err + y + 1 > x:  # altered expression
      err += 1 - 2*x  # do this before updating x
      x -= 1
    else:  # only update one coordinate at a time
      err += 1 + 2*y  # do this before updating y
      y += 1

Now you will have "full coverage" if you increase the radius by 1 in each step.

Demo

Just to demo it with a runnable snippet, here is the same function in JavaScript. It draws the cells in an HTML table and pauses briefly between each (larger) circle:

function bresenham_circle(x0, y0, radius) {
  let x = radius
  let y = 0
  let err = 0

  let points = []

  while (x >= y) {
    points.push([x0 + x, y0 + y])
    points.push([x0 + y, y0 + x])
    points.push([x0 - y, y0 + x])
    points.push([x0 - x, y0 + y])
    points.push([x0 - x, y0 - y])
    points.push([x0 - y, y0 - x])
    points.push([x0 + y, y0 - x])
    points.push([x0 + x, y0 - y])

    if (err + y + 1 > x) {
      err += 1 - 2*x
      x -= 1
    } else {
      err += 1 + 2*y
      y += 1
    }
  }
  return points
}

// I/O initialisation
const MAX = 20;

const drawPoint = (function createGrid() {
    const table = document.querySelector("table");
    for (let i = -MAX; i <= MAX; i++) {
        const row = table.insertRow();
        for (let j = -MAX; j <= MAX; j++) row.insertCell();
    }
    
    return ([x, y]) => table.rows[x].cells[y].style.backgroundColor = "black";
})();

const delay = ms => new Promise(resolve => (setTimeout(resolve, ms)));

(async function main() {
    // Run the algorithm with a delays between each circle
    for (let rad = 0; rad <= MAX; rad++) {
        bresenham_circle(MAX, MAX, rad).forEach(drawPoint);
        await delay(500);
    }
})();

table { border-collapse: collapse }
td { border: 1px solid; width: 2px; height: 2px; line-height: 0 }
body { margin: 0; padding: 0 }

<table></table>

Answer 2

It is simpler to draw small line segments for every radius - usually 1 or 2 pixels - using circle equation.

If you are obliged to use Bresenham equation - remember x-positions for the last round and use them in the current run

instead of

 points.append((x0 + x, y0 + y))

make

 for dx in range(lastx[y]+1, x+1):
    points.append((x0 + dx, y0 + y))
 lastx[y] = x