热门标签 | HotTags
当前位置:  开发笔记 > 人工智能 > 正文

【寒江雪】中点画圆法

圆的特征每一个圆都拥有一个圆心(x,y)和半径R。一个圆如果位于原点,则有四条对称轴x0.y0.xy,x-y;这样,利用圆上任意一点,可以画出其他7个点。这种性质称为
圆的特征

每一个圆都拥有一个圆心(x,y)和半径R。一个圆如果位于原点,则有四条对称轴x=0.y=0.x=y,x=-y;这样,利用圆上任意一点,可以画出其他7个点。这种性质称为圆的八分性质

 

显示圆弧上八个对称点的算法如下:

Void CirclePoints(int x,int y,int color){

       DrawPixel(x,y,color);DrawPixel(y,x,color);

       DrawPixel(-x,y,color);DrawPixel(-y,x,color);

       DrawPixel(x,-y,color);DrawPixel(y,-x,color);

       DrawPixel(-x,-y,color);DrawPixel(-y,-x,color);

}

 

中心点画圆法

根据圆的函数F(x,y)=x^2+y^2-R^2;得出结论:对于平面内任意一点(x,y),若F(x,y)<0则该点在圆内,若F(x,y)=0,则该点在圆上。若F(x,y)>0,则该点在圆外。

据此,我们可以构造判别式d=F(x+1,y-0.5)。

若d<0, 判别式d=F(x+2,y-0.5)=d+2x+3;.y值不变

若d>=0,判别式f=F(x+2,y-1.5)=d+2(x-y)+5;y值减少1

初始是

起始点为(0,R),d=F(1,R-0.5)=1.25-R;

算法如下

Void MidPointCircle(int r,int color){

       Intx,y;

       Floatd;

       X=0;y=r;d=1.25-r;

       CirclePoints(x,y,color);

       While(x<=y){

              If(d<0)

                     d+=2*x+3;

              else{

                     d+=2*(x-y)+5;

                     y--;

}

x++;

              CirclePoints(x,y,color);

}

}

 

该算法主要思路是使用中点判断是应该取上界还是下界。

我们要绘制的点的横坐标X肯定都是整数。而Y的值肯定是经过四舍五入过后的整数值

但是严格意义上的圆,其纵坐标不可能都为整数。因此,采用中点是不是在圆内的方法来判别当前X坐标对应圆上的点是在中点之上还是在中点之下,进而判断是该舍还是入。

 

现做如下推导

假设当前横坐标为X,为整数

计算得到圆上的点为(X,y),y可能为整数也可能为浮点数

Y为y四舍五入后得到的Y值

算法一开始,y=Y=R,X=0,都为整数。取中点(x+1,ym);ym为Y与Y-1的中值。

若(x+1,ym)在圆内,表明(x+1,y)中Y>y>ym,此时应取Y作为要绘制的点的纵坐标(x+1,Y)

若(x+1,ym)在圆外,表明(x+1,y)中ym>y>Y-1,此时应取Y作为要绘制的点的纵坐标(x+1,Y-1)

同时根据相应的公式,计算下一点的判别式

这样,该算法可以简述为,推测当前点,推导下一点的判别式。依次滚动直到计算完八分之一圆为止。

完善
在上述算法中,使用了浮点数来表示决策变量d。为了简化算法,摆脱浮点数,在算法中全部使用整数,我们使用e=d-1/4代替d。显然,初值d=5/4-r对应于e=1-r。决策变量d<0对应于e<-1/4。算法中其它与d有关的式子可把d直接换成e。又由于e的初值为整数,且在运算过程中的迭代值也是整数,故e始终是整数,所以e<-1/4等价于e<0。因此,可以写出完全用整数实现的中点画圆算法。

推荐阅读
  • Søren Kierkegaard famously stated that life can only be understood in retrospect but must be lived moving forward. This perspective delves into the intricate relationship between our lived experiences and our reflections on them. ... [详细]
  • 计算机网络复习:第五章 网络层控制平面
    本文探讨了网络层的控制平面,包括转发和路由选择的基本原理。转发在数据平面上实现,通过配置路由器中的转发表完成;而路由选择则在控制平面上进行,涉及路由器中路由表的配置与更新。此外,文章还介绍了ICMP协议、两种控制平面的实现方法、路由选择算法及其分类等内容。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 深入理解C++中的KMP算法:高效字符串匹配的利器
    本文详细介绍C++中实现KMP算法的方法,探讨其在字符串匹配问题上的优势。通过对比暴力匹配(BF)算法,展示KMP算法如何利用前缀表优化匹配过程,显著提升效率。 ... [详细]
  • 探讨一个显示数字的故障计算器,它支持两种操作:将当前数字乘以2或减去1。本文将详细介绍如何用最少的操作次数将初始值X转换为目标值Y。 ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • 本文探讨如何设计一个安全的加密和验证算法,确保生成的密码具有高随机性和低重复率,并提供相应的验证机制。 ... [详细]
  • 深入解析:手把手教你构建决策树算法
    本文详细介绍了机器学习中广泛应用的决策树算法,通过天气数据集的实例演示了ID3和CART算法的手动推导过程。文章长度约2000字,建议阅读时间5分钟。 ... [详细]
  • 在金融和会计领域,准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据,还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法,确保数据的标准化和规范化。 ... [详细]
  • 在给定的数组中,除了一个数字外,其他所有数字都是相同的。任务是找到这个唯一的不同数字。例如,findUniq([1, 1, 1, 2, 1, 1]) 返回 2,findUniq([0, 0, 0.55, 0, 0]) 返回 0.55。 ... [详细]
  • 本文探讨了卷积神经网络(CNN)中感受野的概念及其与锚框(anchor box)的关系。感受野定义了特征图上每个像素点对应的输入图像区域大小,而锚框则是在每个像素中心生成的多个不同尺寸和宽高比的边界框。两者在目标检测任务中起到关键作用。 ... [详细]
  • 网络攻防实战:从HTTP到HTTPS的演变
    本文通过一系列日记记录了从发现漏洞到逐步加强安全措施的过程,探讨了如何应对网络攻击并最终实现全面的安全防护。 ... [详细]
  • 本文深入探讨了Linux系统中网卡绑定(bonding)的七种工作模式。网卡绑定技术通过将多个物理网卡组合成一个逻辑网卡,实现网络冗余、带宽聚合和负载均衡,在生产环境中广泛应用。文章详细介绍了每种模式的特点、适用场景及配置方法。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
author-avatar
我是小崔来啦
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有