Bresenham 的圆绘制算法，其圆在增加半径时使用所有坐标

Question

我想绘制的圆不会留下任何不包含在任何圆中的坐标。问题是，目前，当您绘制所有圆圈时，例如半径 1 到 4 表示某些坐标不包含在任何圆中，例如 (2,2)。

缺失的坐标可以包含在较大或较小的圆圈中。

这是我当前的代码

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()

缺失的坐标似乎遵循某种模式，但我无法推断出这是什么模式。我认为还应该可以将当前半径的圆与半径 - 1 的圆进行比较，并推断出将跳过哪些坐标并将它们添加到当前圆中，但由于我有限的技能，没有成功。

Answer 1

使用圆方程为每个半径（通常为 1 或 2 个像素）绘制小线段会更简单。

如果您必须使用 Bresenham 方程 - 请记住上一轮的 x 位置并在当前运行中使用它们

而不是

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

制作

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