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

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 6292|回复: 2

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

[复制链接]

1109

主题

1649

回帖

7万

积分

用户组: 管理员

一只技术宅

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

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

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

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

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

midpoint.gif

    它的推导过程是通过寻找下一个最接近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.     while (x >= y)
  9.     {
  10.         putpixel(x0 + x, y0 + y);
  11.         putpixel(x0 + y, y0 + x);
  12.         putpixel(x0 - y, y0 + x);
  13.         putpixel(x0 - x, y0 + y);
  14.         putpixel(x0 - x, y0 - y);
  15.         putpixel(x0 - y, y0 - x);
  16.         putpixel(x0 + y, y0 - x);
  17.         putpixel(x0 + x, y0 - y);

  18.         if (err <= 0)
  19.         {
  20.             y++;
  21.             err += dy;
  22.             dy += 2;
  23.         }
  24.         
  25.         if (err > 0)
  26.         {
  27.             x--;
  28.             dx += 2;
  29.             err += dx - (radius << 1);
  30.         }
  31.     }
  32. }
复制代码
参考资料:
https://en.wikipedia.org/
wiki
/Midpoint_circle_algorithm

本帖被以下淘专辑推荐:

回复

使用道具 举报

30

主题

207

回帖

2718

积分

用户组: 版主

UID
1821
精华
7
威望
69 点
宅币
2102 个
贡献
206 次
宅之契约
0 份
在线时间
466 小时
注册时间
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

主题

16

回帖

44

积分

用户组: 初·技术宅

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

使用道具 举报

QQ|Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-3-19 14:05 , Processed in 0.041316 second(s), 37 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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