首页 > 搜索 > 生成圆弧算法,圆弧生成算法

生成圆弧算法,圆弧生成算法

互联网 2020-10-29 04:16:49
在线算命,八字测算命理

        在平面解析几何中,圆的方程可以描述为(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),这种性质称为八分对称性。因此只要能画出八分之一的圆弧,就可以利用对称性的原理得到整个圆。

有几种较容易的方法可以得到圆的扫描转换,首先介绍一下直角坐标法。已知圆方程:x2 + y2 = R2,若取x作为自变量,解出y,得到:

 

y =

 

在生成圆时先扫描转换四分之一的圆周,让自变量x从0到R以单位步长增加,在每一步时可解出y,然后调用画点函数即可逐点画出圆。但这样做,由于有乘方和平方根运算,并且都是浮点运算,算法效率不高。而且当x接近R值时(圆心在原点),在圆周上的点(R,0)附近,由于圆的斜率趋于无穷大,因浮点数取整需要四舍五入的缘故,使得圆周上有较大的间隙。接下来介绍一下极坐标法,假设直角坐标系上圆弧上一点P(x,y)与x轴的夹角是θ,则圆的极坐标方程为:

 

x = Rcosθ

y = Rsinθ

 

生成圆是利用圆的八分对称性,使自变量θ的取值范围为(0,45°)就可以画出整圆。这个方法涉及三角函数计算和乘法运算,计算量较大。直角坐标法和极坐标法都是效率不高的算法,因此只是作为理论方法存在,在计算机图形学中基本不使用这两种方法生成圆。下面就介绍几种在计算机图形学中比较实用的圆的生成算法。

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

 

根据上面的分析,可以写出中点画圆法的算法。考虑到圆心不在原点的情况,需要对计算出来的坐标进行了平移,下面就是通用的中点画圆法的源代码:

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多