技术宅的结界

 找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 143|回复: 2
收起左侧

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

[复制链接]

1010

主题

2246

帖子

5万

积分

用户组: 管理员

一只技术宅

UID
1
精华
200
威望
265 点
宅币
16897 个
贡献
33725 次
宅之契约
0 份
在线时间
1608 小时
注册时间
2014-1-26
发表于 2018-11-6 00:47:47 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有帐号?立即注册→加入我们

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

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

midpoint.gif

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

25

主题

91

帖子

1207

积分

用户组: 版主

UID
1821
精华
6
威望
57 点
宅币
936 个
贡献
36 次
宅之契约
0 份
在线时间
210 小时
注册时间
2016-7-12
发表于 2018-11-6 12:18:07 | 显示全部楼层
本帖最后由 Ayala 于 2018-11-6 12:21 编辑

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

1

主题

17

帖子

44

积分

用户组: 初·技术宅

UID
4492
精华
0
威望
2 点
宅币
23 个
贡献
0 次
宅之契约
0 份
在线时间
0 小时
注册时间
2018-11-20
发表于 2018-11-20 18:14:57 | 显示全部楼层
牛逼牛逼
回复

使用道具 举报

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|技术宅的结界 ( 滇ICP备16008837号|网站地图

GMT+8, 2018-12-15 11:03 , Processed in 0.105289 second(s), 41 queries , Gzip On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表