【2D图形】中点画圆算法

0xAA55

    画圆有很多种算法，最典型的就是用三角函数画一圈点。但这种方法依赖昂贵的三角函数算法，sin和cos，不仅很慢而且不适合嵌入式开发。除此以外，对于不依赖三角函数的画圆算法，还有一个是用勾股定理来找出距离值最接近圆半径的像素点。但这种算法需要遍历大量的像素，对它的坐标做x*x+y*y的计算。随着圆的面积的增加，需要遍历的像素数量就会呈指数增加。这种画圆算法只适用于GPU着色器。

    中点画圆算法，可以用于解决这种问题。它使用非常简单的算法，通过一个初始坐标开始推算下一个像素的位置，每推算一次只需要少量的加减法和移位，以及条件判断就可以了。然后只需要推算出八分之一个圆的像素量，再进行各种对称翻转、镜像等就可以画出一整个圆。



    它的推导过程是通过寻找下一个最接近x² + y² = r²的点，来决定应该画哪几个像素来组成圆。下例C代码中，它就是一边统计误差值，一边向下寻找y正方向的相邻像素，如果误差值到达判断条件，它就向左移动一格。这样一边向下移动一边向左移动并计算误差值的方式，就可以移动出一个八分之一圆的轨迹了。

1. void drawcircle(int x0, int y0, int radius)
   
2. {
   
3.     int x = radius-1;
   
4.     int y = 0;
   
5.     int dx = 1;
   
6.     int dy = 1;
   
7.     int err = dx - (radius << 1);
   
8. 
   
9.     while (x >= y)
   
10.     {
    
11.         putpixel(x0 + x, y0 + y);
    
12.         putpixel(x0 + y, y0 + x);
    
13.         putpixel(x0 - y, y0 + x);
    
14.         putpixel(x0 - x, y0 + y);
    
15.         putpixel(x0 - x, y0 - y);
    
16.         putpixel(x0 - y, y0 - x);
    
17.         putpixel(x0 + y, y0 - x);
    
18.         putpixel(x0 + x, y0 - y);
    
19. 
    
20.         if (err <= 0)
    
21.         {
    
22.             y++;
    
23.             err += dy;
    
24.             dy += 2;
    
25.         }
    
26.         
    
27.         if (err > 0)
    
28.         {
    
29.             x--;
    
30.             dx += 2;
    
31.             err += dx - (radius << 1);
    
32.         }
    
33.     }
    
34. }

复制代码

参考资料：
https://en.wikipedia.org/

wiki

/Midpoint_circle_algorithm

Ayala

这种有实用性的算法去做推导算式还有价值，如果是没通用性的就真得不偿失了 比如这个算法3的不等式证明
https://www.0xaa55.com/forum.php ... 52&fromuid=1821

Si515

牛逼牛逼