绘制圆没有浮点计算

Question

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

问题很简单:

圆方程为:x ^ 2 + y ^ 2 = R ^ 2.给定R,尽可能最好地绘制0,0居中的圆而不使用任何浮点(没有trigo,平方根等,只有整数)

Answer 1

类似Bresenham的算法可能是预期的答案,并且可以在没有"复杂理论"的情况下得出.从(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--

Answer 2

老实说,中点圈算法不够吗？只需在所有象限中镜像它.并且绝不是 - 除非你试图找到一个窗口应用测试人员的工作,Bresenham的线算法并不是复杂的理论.

Answer 3

从此页面上的第二种方法：

对于每个像素，求值x ² + y ²，看它是否在R ² -R + 1到R ² + R（含）范围内。如果是这样，请为屏幕上的像素着色，否则请不要。

前述页面上提供了更多详细信息和说明，但关键是要查找距原点R-0.5和R + 0.5之间的距离的像素，因此距离的平方是x ² + y ²和阈值距离R ² -R + 0.25和R ² + R + 0.25 平方。

对于其他方法，Google“仅使用整数算术绘制圆”。