更新题目 Draw Circle：不用浮点画圆
题目 everpure-draw-circle · 修改（rev 11） · · 2026-10-27 12:09
body
@@ -44,4 +44,6 @@ | 用什么语言？ | 原帖没写。192327 的发帖人说做存储的公司，不会 C/C++ 很难通过 | 本页用 Python。C 里要注意整数溢出，见 Follow-up 3 | +> [!say] Before I start: the center is at the origin, r is a non-negative integer, plot takes integer pixel coordinates, and I only draw the outline. Is it okay if a pixel is not exactly on the circle, as long as it's the nearest one? + ## 面经里怎么考的 @@ -72,4 +74,6 @@ r = 3 时 9 只能拆成 0 + 9（1 + 8、4 + 5 都不是两个平方数的和），所以只有 $(0, \pm 3)$、$(\pm 3, 0)$ 四个点。r = 5 好一些，因为 $25 = 9 + 16$，多出 $(\pm 3, \pm 4)$、$(\pm 4, \pm 3)$，一共 12 个点，但圆周上还是大片空白。整点有几个，取决于 $r^2$ 能拆成几种平方和，和圆周有多长不成比例：r = 7 时也只有 4 个。所以这不是画圆的办法。follow-up「r 很小时多画几个点」就是让你放弃「恰好在圆上」，改成「离圆最近」。 + +> [!say] Plotting only exact lattice points gives four lonely pixels for r equals three, so instead I take, for every column, the pixel closest to the true circle. ### 2. 第二版：每一列取离圆最近的整数 @@ -141,4 +145,6 @@ r = 3 时这一段是 (0, 3)、(1, 3)、(2, 2)，镜像出 4 + 8 + 4 = 16 个点，就是题目一节的图，比第二版多出第二版漏掉的 $(\pm 3, \pm 1)$ 四个点。 +> [!say] I only compute one octant, from the top of the circle down to the line y equals x, and mirror every pixel eight ways. In that octant the true height drops by less than one per column, so when x goes up by one, y either stays or drops by one, and the outline has no gaps. + #### 终止条件 @@ -177,4 +183,6 @@ 这一版没有开方了，但每一列还要算 $x \cdot x$ 和 $(2y - 1)^2$ 两次乘法（$4r^2$ 可以在循环外算好）。 +> [!say] To avoid the square root, I look at the midpoint between the two candidates. If the midpoint is inside the circle, the circle passes above it, so I keep y. Otherwise I decrement y. + ### 5. 第五版：判别式递推，循环里只剩加减法 @@ -211,4 +219,6 @@ 第 4 步之后 x = 4 > y = 3，循环结束。(4, 3) 不属于这一段，它是 (3, 4) 关于对角线的镜像，已经画过了。核对一下：$Y(1) = \sqrt{24} \approx 4.90$，$Y(2) = \sqrt{21} \approx 4.58$，$Y(3) = 4$，取整都和表里一致。每一步的 d 也都等于 $f(x + 1, y - \tfrac{1}{2}) - \tfrac{1}{4}$，比如第 3 步 $f(3, 4.5) = 9 + 20.25 - 25 = 4.25$，减 $\tfrac{1}{4}$ 是 4。完整代码见代码一节。 + +> [!say] The decision value can be updated incrementally: add two x plus three when y stays, or two times x minus y, plus five, when y drops. The loop has only additions and comparisons, no multiplication and no square root. #### r 不是整数时 @@ -341,14 +351,2 @@ - 第一到第三版要算 $r \cdot r$，r = 46341 时 $r^2 = 2147488281$，已经溢出。第四版要算 $4r^2$，r = 23171 时就溢出。 - 第五版只存 d、x、y，不算 $r^2$。d 有多大可以这样估计。先把当前像素 $(x, y)$ 代入圆方程，$e = x^2 + y^2 - r^2 = (y - Y(x)) \cdot (y + Y(x))$：y 是离 $Y(x)$ 最近的整数，第一个因子的绝对值小于 $\tfrac{1}{2}$。y 和 $Y(x)$ 都不超过 r，第二个因子不超过 2r，所以 $|e| < r$。判断用的 $P = f(x + 1, y - \tfrac{1}{2})$ 展开是 $e + (2x - y) + \tfrac{5}{4}$，而 $0 \le x \le y \le r$，所以 $|2x - y| \le r$。合起来 $|P| < 2r + \tfrac{5}{4}$，$d = P - \tfrac{1}{4}$ 是整数，所以 $|d| \le 2r + 1$。循环最后那次更新以后 d 不再使用，它只多加了一个绝对值不超过 $2r + 3$ 的增量，所以 d 存过的所有值都在 $4r + 4$ 以内。r 不超过 5 亿时，$4r + 4 \approx$ 20 亿，32 位整数装得下。实测见测试用例。 - -## 英文讲法 - -> [!say] Before I start: the center is at the origin, r is a non-negative integer, plot takes integer pixel coordinates, and I only draw the outline. Is it okay if a pixel is not exactly on the circle, as long as it's the nearest one? - -> [!say] Plotting only exact lattice points gives four lonely pixels for r equals three, so instead I take, for every column, the pixel closest to the true circle. - -> [!say] I only compute one octant, from the top of the circle down to the line y equals x, and mirror every pixel eight ways. In that octant the true height drops by less than one per column, so when x goes up by one, y either stays or drops by one, and the outline has no gaps. - -> [!say] To avoid the square root, I look at the midpoint between the two candidates. If the midpoint is inside the circle, the circle passes above it, so I keep y. Otherwise I decrement y. - -> [!say] The decision value can be updated incrementally: add two x plus three when y stays, or two times x minus y, plus five, when y drops. The loop has only additions and comparisons, no multiplication and no square root.