algorithm - 没有浮点计算的画圆

Question

这是一个常见的面试问题(根据一些面试网站)，但我在互联网上找不到正常的答案 - 有些是错误的，有些指向复杂的理论，我希望在面试中不需要(比如 Bresenham 算法) ).

问题很简单:

The circle equation is: x² + y² = R². Given R, draw 0,0-centered circle as best as possible without using any floating point (no trig, square roots, and so on, only integers)

Answer 1

Bresenham-like 算法可能是预期的答案，并且可以在没有“复杂理论”的情况下推导出来。从圆上的一点 (x,y) 开始:(R,0) 并保持值 d=x^2+y^2-R ^2，初始为0。D为当前点到圆的距离的平方。我们根据需要递增 Y 并递减 X 以保持 D 最小:

// Discretize 1/8 circle:
x = R ; y = 0 ; d = 0
while x >= y
  print (x,y)
  // increment Y, D must be updated by (Y+1)^2 - Y^2 = 2*Y+1
  d += (2*y+1) ; y++
  // now if we decrement X, D will be updated by -2*X+1
  // do it only if it keeps D closer to 0
  if d >= 0
    d += (-2*x+1) ; x--