【2D图形】中点画圆算法
画圆有很多种算法，最典型的就是用三角函数画一圈点。但这种方法依赖昂贵的三角函数算法，sin和cos，不仅很慢而且不适合嵌入式开发。除此以外，对于不依赖三角函数的画圆算法，还有一个是用勾股定理来找出距离值最接近圆半径的像素点。但这种算法需要遍历大量的像素，对它的坐标做x*x+y*y的计算。随着圆的面积的增加，需要遍历的像素数量就会呈指数增加。这种画圆算法只适用于GPU着色器。中点画圆算法，可以用于解决这种问题。它使用非常简单的算法，通过一个初始坐标开始推算下一个像素的位置，每推算一次只需要少量的加减法和移位，以及条件判断就可以了。然后只需要推算出八分之一个圆的像素量，再进行各种对称翻转、镜像等就可以画出一整个圆。
它的推导过程是通过寻找下一个最接近x² + y² = r²的点，来决定应该画哪几个像素来组成圆。下例C代码中，它就是一边统计误差值，一边向下寻找y正方向的相邻像素，如果误差值到达判断条件，它就向左移动一格。这样一边向下移动一边向左移动并计算误差值的方式，就可以移动出一个八分之一圆的轨迹了。void drawcircle(int x0, int y0, int radius)
{
int x = radius-1;
int y = 0;
int dx = 1;
int dy = 1;
int err = dx - (radius << 1);
while (x >= y)
{
putpixel(x0 + x, y0 + y);
putpixel(x0 + y, y0 + x);
putpixel(x0 - y, y0 + x);
putpixel(x0 - x, y0 + y);
putpixel(x0 - x, y0 - y);
putpixel(x0 - y, y0 - x);
putpixel(x0 + y, y0 - x);
putpixel(x0 + x, y0 - y);
if (err <= 0)
{
y++;
err += dy;
dy += 2;
}
if (err > 0)
{
x--;
dx += 2;
err += dx - (radius << 1);
}
}
}参考资料：
https://en.wikipedia.org/wiki/Midpoint_circle_algorithm 本帖最后由 Ayala 于 2018-11-6 12:21 编辑
这种有实用性的算法去做推导算式还有价值，如果是没通用性的就真得不偿失了 比如这个算法3的不等式证明
https://www.0xaa55.com/forum.php?mod=redirect&goto=findpost&ptid=2193&pid=8152&fromuid=1821 牛逼牛逼
页:
[1]