⭕ 中点画圆算法
Midpoint Circle Algorithm (Bresenham Circle Algorithm) - 利用八对称性的高效圆形绘制
🎯 当前计算点的八对称性
一个点 (x, y) 可以通过对称性生成其他7个点：
(x, y)
(y, x)
(-x, y)
(-y, x)
(x, -y)
(y, -x)
(-x, -y)
(-y, -x)
💡 中点画圆算法原理
🔑 核心思想：
- 利用圆的八对称性，只需计算第一象限的45°圆弧（1/8圆）
- 使用决策参数判断下一个像素位置
- 全程只用整数运算（加减法），无需浮点数和乘除法
算法步骤：
- 初始化：
x = 0, y = r (从圆的最上方开始)
p = 1 - r (初始决策参数)
- 循环直到 x > y：
绘制8个对称点: (±x, ±y) 和 (±y, ±x)
x = x + 1
如果 p < 0:
p = p + 2*x + 1 (选择正右方的点)
否则:
y = y - 1
p = p + 2*(x - y) + 1 (选择右下方的点)
为什么这样做？
- 决策参数 p：表示中点到圆的距离，用于判断下一个像素应该选哪个
- p < 0：中点在圆内部，选择正右方的像素 (x+1, y)
- p ≥ 0：中点在圆外部，选择右下方的像素 (x+1, y-1)
- 八对称性：一次计算就能得到8个像素，效率提升8倍！
⚡ 为什么快？
✓ 没有浮点运算
✓ 没有乘除法
✓ 没有平方根
✓ 只有整数加减法
✓ 利用对称性减少计算量
圆的方程：
x² + y² = r²
对于圆上的点：F(x,y) = x² + y² - r² = 0
点在圆内：F(x,y) < 0
点在圆外：F(x,y) > 0
🎓 算法特点对比
| 特性 |
中点画圆算法 |
传统方法 |
| 运算类型 |
只用整数加减法 |
需要sin/cos或平方根 |
| 速度 |
极快 ⚡ |
较慢 |
| 对称性 |
利用八对称 (1/8计算) |
全圆计算 |
| 应用 |
图形硬件、游戏引擎 |
理论教学 |