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.
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.
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>