中点画圆算法
2021/6/17 14:25:51
本文主要是介绍中点画圆算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
在平面解析几何中,圆的方程可以描述为(x – x0)2 + (y – y0)2 = R2,其中(x0, y0)是圆心坐标,R是圆的半径,特别的,当(x0, y0)就是坐标中心点时,圆方程可以简化为x2 + y2 = R2。在计算机图形学中,圆和直线一样,也存在在点阵输出设备上显示或输出的问题,因此也需要一套光栅扫描转换算法。为了简化,我们先考虑圆心在原点的圆的生成,对于中心不是原点的圆,可以通过坐标的平移变换获得相应位置的圆。
在进行扫描转换之前,需要了解一个圆的特性,就是圆的八分对成性。如图(1)所示:
图(1)圆的八分对称性
圆心位于原点的圆有四条对称轴x = 0、y = 0、x = y和x = -y,若已知圆弧上一点P(x,y),就可以得到其关于四条对称轴的七个对称点:(x, -y)、(-x, y)、(-x, -y)、(y, x)、(y, -x)、(-y, x)、(-y, -x),这种性质称为八分对称性。因此只要能画出八分之一的圆弧,就可以利用对称性的原理得到整个圆。
1、 中点画圆法
考虑圆心在原点,半径为R的圆在第一象限内的八分之一圆弧,从点(0, R)到点(R' , R' )顺时针方向确定这段圆弧。假定某点Pi(xi, yi)已经是该圆弧上最接近实际圆弧的点,那么Pi的下一个点只可能是正右方的P1或右下方的P2两者之一,如图(2)所示:
图(2)中点划线法示例
构造判别函数:
F(x, y)= x2 + y2 – R2
当F(x, y)= 0,表示点在圆上,当F(x, y)> 0,表示点在圆外,当F(x, y)< 0,表示点在圆内。如果M是P1和P2的中点,则M的坐标是(xi + 1, yi – 0.5),当F(xi + 1, yi – 0.5)< 0时,M点在圆内,说明P1点离实际圆弧更近,应该取P1作为圆的下一个点。同理分析,当F(xi + 1, yi – 0.5)> 0时,P2离实际圆弧更近,应取P2作为下一个点。当F(xi + 1, yi – 0.5)= 0时,P1和P2都可以作为圆的下一个点,算法约定取P2作为下一个点。
现在将M点坐标(xi + 1, yi – 0.5)带入判别函数F(x, y),得到判别式d:
d = F(xi + 1, yi – 0.5)= (xi + 1)2 + (yi – 0.5)2 – R2
若d < 0,则取P1为下一个点,此时P1的下一个点的判别式为:
d’ = F(xi + 2, yi – 0.5)= (xi + 2)2 + (yi – 0.5)2 – R2
展开后将d带入可得到判别式的递推关系:
d’ = d + 2xi + 3
若d > 0,则取P2为下一个点,此时P2的下一个点的判别式为:
d’ = F(xi + 2, yi – 1.5)= (xi + 2)2 + (yi – 1.5)2 – R2
展开后将d带入可得到判别式的递推关系:
d’ = d + 2(xi - yi) + 5
特别的,在第一个象限的第一个点(0, R)时,可以推倒出判别式d的初始值d0:
d0 = F(1, R – 0.5) = 1 – (R – 0.5)2 – R2 = 1.25 - R
根据上面的分析,可以写出中点画圆法的算法。考虑到圆心不在原点的情况,需要对计算出来的坐标进行了平移,下面就是通用的中点画圆法的源代码:
void MP_Circle(int xc , int yc , int r) { int x, y; double d; x = 0; y = r; d = 1.25 - r; CirclePlot(xc , yc , x , y); while(x < y) { if(d < 0) { d = d + 2 * x + 3; } else { d = d + 2 * ( x - y ) + 5; y--; } x++; CirclePlot(xc , yc , x , y); } }
参数xc和yc是圆心坐标,r是半径,CirclePlot()函数是参照圆的八分对称性完成八个点的位置计算的辅助函数。
通过EasyX实现画一个同心圆环:
#include <graphics.h> #include <conio.h> // 中点画圆法 void Circle_Midpoint(int x, int y, int r, int color) { int tx = 0, ty = r, d = 1.25 - r; while (tx <= ty) { // 利用圆的八分对称性画点 putpixel(x + tx, y + ty, color); putpixel(x + tx, y - ty, color); putpixel(x - tx, y + ty, color); putpixel(x - tx, y - ty, color); putpixel(x + ty, y + tx, color); putpixel(x + ty, y - tx, color); putpixel(x - ty, y + tx, color); putpixel(x - ty, y - tx, color); if (d < 0) d += 2 * tx + 3; else d += 2 * (tx - ty) + 5, ty--; tx++; } } // 主函数 int main() { initgraph(640, 480); // 测试画圆 Circle_Midpoint(320, 240, 200, RED); Circle_Midpoint(320, 240, 101, RED); // 按任意键退出 _getch(); closegraph(); return 0; }
结果如下:
参考链接:
https://blog.csdn.net/MMogega/article/details/53055625?depth_1-utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-1&utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-1
https://codebus.cn/yangw/a/midpoint-circle-algorithm
这篇关于中点画圆算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)