[关闭]
@cxm-2016 2016-11-03T10:38:56.000000Z 字数 4447 阅读 4999

图形算法:圆形生成算法

算法

版本:2
作者:陈小默
声明:禁止商用,禁止转载

发布于:作业部落CSDN博客


圆的定义为所有距离中心位置为定值 的点的集合[1]。在本章内容中,我们将会介绍三种常用的圆形生成算法:勾股定理算法极坐标算法中点圆算法

一、算法导论


1.1 四分法与八分法

由于圆具有对称性,只计算圆上一部分的值,再通过对称性将值变换到其他象限可以极大的减少计算量。

图 1.1-1
假如我们确定了圆在第一象限的位置,则可以通过变换 的符号去生成圆在第二象限的位置。我们再对上述生成的全部位置进行相对于 轴的符号变换就可以得到圆在第三四象限的位置。这就是四分法的基本思路。
图 1.1-2
在同一个象限内,如果按照 进行分割,可以看出其坐标关于这个分割线是对称的。也就是在(0~45)度范围内的值可以通过简单变换映射到其他区域内。这种分割方式被称为圆的八分法。

1.2 勾股定理算法

在笛卡尔坐标系中,对于给定的原点和半径 ,圆上任意一点满足勾股定理

利用这个算法我们可以通过任意 值计算对应的

现在我们通过示例程序演示该算法,仅展示思路,可使用任意语言或图形软件包实现。

  1. void Pythagorean(int x,int y,int r){//使用勾股定理绘制圆
  2. int start = x-r;
  3. int end = r+x;
  4. _IntArray _arr;
  5. int size = 4*(end-start);
  6. _arr = new IntArray(size);
  7. IntArray_ arr = *_arr;
  8. int r2 = r*r;
  9. for(int i=start,j=0;i<end;i++){
  10. int p = sqrt(float(r2-power(x-i)));
  11. arr[j++]=i;
  12. arr[j++]=y+p;
  13. arr[j++]=i;
  14. arr[j++]=y-p;
  15. }
  16. _list->add(_arr);
  17. }

图 1.2-1
通过结果 [图 1.2-1] 我们可以看出直接使用勾股定理会造成像素间距不一致的问题。处理方法有两种:第一种是在斜率的绝对值大于1后,交换来调整间距;第二种方式是使用1.1节中提到的八分法。我们只需要计算八分之一的图形,剩下的操作就是简单映射即可。以下是使用八分法的示例

  1. void Pythagorean(int xc,int yc,int r){//使用勾股定理和八分法绘制圆
  2. int len = int(1+0.5*sqrt(2.0)*r);
  3. int size = 16*len;
  4. _IntArray _arr = new IntArray(size);
  5. IntArray_ arr = *_arr;
  6. int r2 = r*r;
  7. int j=0;
  8. for(int x=0;x<len;x++){
  9. int p = sqrt(float(r2-power(x)));
  10. arr[j++]=x;
  11. arr[j++]=p;
  12. }
  13. int k=j;
  14. for(int i=0;i<k;i+=2){
  15. arr[j++] = arr[i+1];
  16. arr[j++] = arr[i];
  17. }
  18. k = j;
  19. for(int i=0;i<k;i+=2){
  20. arr[j++] = arr[i];
  21. arr[j++] = -arr[i+1];
  22. }
  23. k = j;
  24. for(int i=0;i<k;i+=2){
  25. arr[j++] = -arr[i];
  26. arr[j++] = arr[i+1];
  27. }
  28. for(int i=0;i<j;i+=2){
  29. arr[i]+=xc;
  30. arr[i+1]+=yc;
  31. }
  32. _list->add(_arr);
  33. }

图 1.2-2
在此示例中,我们先将圆计算时的圆心已原点(0,0)计算,在所有操作完成之后在平移到相应位置,这么做方便变换简化计算量。

总结:勾股定理算法简单,即使是使用八分法缩减运算规模,其大量复杂的开平方计算仍然是影响效率的关键因素。接下来,我们将介绍一种能够替换开平方运算的算法。

1.3 极坐标算法

极坐标系是一种常用的坐标系。其中坐标位置由到原点的极半径距离 和距水平轴的角 指定。正的角位移是逆时针的,而负的角位移是逆时针的。利用三角函数的定义,可以从极坐标系转换为笛卡尔坐标系。

通过式(1.3.1)我们可以通过下列方程组表示圆方程

使用上述方式以单位角度为步长,可以在圆周上以等距离的点来绘制圆。

下面将使用程序展示极坐标算法的计算过程

  1. void Polar(int xc,int yc,int r){//使用极坐标系绘制圆
  2. int point = 2;//每一度绘制两个点
  3. double angle = 1.0/point;//每两个点之间的角度
  4. int size = point*45*8*2;//使用八分法,
  5. _IntArray _arr = new IntArray(size);
  6. IntArray_ arr = *_arr;
  7. int j=0;
  8. for(int i=0;i<45;i++){
  9. for(int m=0;m<point;m++){
  10. arr[j++] = int(r*cos(((i+angle*m)*(PI/180))));//使用c库中的三角函数需要将角度转换为弧度
  11. arr[j++] = int(r*sin(((i+angle*m)*(PI/180))));
  12. }
  13. }
  14. int k=j;
  15. for(int i=0;i<k;i+=2){
  16. arr[j++] = arr[i+1];
  17. arr[j++] = arr[i];
  18. }
  19. k = j;
  20. for(int i=0;i<k;i+=2){
  21. arr[j++] = arr[i];
  22. arr[j++] = -arr[i+1];
  23. }
  24. k = j;
  25. for(int i=0;i<k;i+=2){
  26. arr[j++] = -arr[i];
  27. arr[j++] = arr[i+1];
  28. }
  29. for(int i=0;i<j;i+=2){
  30. arr[i]+=xc;
  31. arr[i+1]+=yc;
  32. }
  33. _list->add(_arr);
  34. }

图 1.3-1

总结:我们可以从图中看出其边缘有毛刺状突起,这是因为极坐标系运算以角度为步长而不是任何一个轴,这就导致其结果取整后不仅仅只会在一个方向上浮动。从效率的角度上说,虽然极坐标系统提供了等距离点,但是其三角函数计算仍然十分耗时。

1.4 中点圆算法

我们可以参照直线算法中的Bresenham算法,以决策参数的增量运算为基础,将圆的计算过程转换为简单的整数加减运算。

如同画线算法,我们在每一步中以单位间隔取样并确定离圆最近的像素位置。对于给定半径 和屏幕中心 ,可以现将圆的圆心放在坐标原点运算,在运算完成之后,再将圆移动到相应的位置。

为了应用中点圆算法,我们先定义一个圆函数

任意一点 均满足

我们需要使用(1.4.2)对每一个取样步上对接近圆周的两个像素的中点进行测试。因此,在中点算法中,圆函数(1.4.1)是决策参数。

图 1.4-1

[1.4-1] 给出了取样位置 上的中点,我们可以取出中点的坐标 也就是点 ,接下来,我们只需要将中点位置代入方程(1.4.1)就可以算出决策参数

如果,那么这个圆的轨迹在中点的上方,所以我们选择扫描 这个像素,否则,我们扫描这个像素。

接下来我们要寻找决策增量之间的关系。这使用了我们中学所学的数学归纳法。通过任意相邻两点之间的关系递推整个决策的关系。

通过式(1.4.4)我们可以求出下一个决策参数

我们可以找出相邻的两个决策参数之间的关系

其中 或者是 具体取值取决于 的符号。

我们已经计算出了决策增量的关系,接下来只需要计算出决策增量的初始值即可,对于圆心在坐标原点,半径为 的圆来说,假设第一点从处起笔

如果为了简化运算,我们可以将决策参数近似为整数,而不用浮点数,其中 也是整数

接下来我们将使用一段代码来解释其流程:

  1. void Bresenham(int xc,int yc,int r){//使用中点圆算法
  2. int j = 0;
  3. int p = 1-r;//这里计算出的p0使用近似的整型来简化运算
  4. int x = 0;
  5. int y = r;
  6. int size = 16*int(1+0.5*sqrt(2.0)*r);//整个运算过程会产生size/2个点
  7. _IntArray _arr = new IntArray(size);
  8. IntArray_ arr = *_arr;
  9. for(int i=x;i<y;i++){
  10. arr[j++] = x++;
  11. if(p<0){//决策参数小于0说明中点在圆内,所以点要绘制在上方
  12. arr[j++] = y;
  13. p+=2*x+1;
  14. }else{
  15. arr[j++] = y--;
  16. p+=2*x+1-2*y;
  17. }
  18. }
  19. int k=j;
  20. for(int i=0;i<k;i+=2){
  21. arr[j++] = arr[i+1];
  22. arr[j++] = arr[i];
  23. }
  24. k = j;
  25. for(int i=0;i<k;i+=2){
  26. arr[j++] = arr[i];
  27. arr[j++] = -arr[i+1];
  28. }
  29. k = j;
  30. for(int i=0;i<k;i+=2){
  31. arr[j++] = -arr[i];
  32. arr[j++] = arr[i+1];
  33. }
  34. for(int i=0;i<j;i+=2){
  35. arr[i]+=xc;
  36. arr[i+1]+=yc;
  37. }
  38. _list->add(_arr);
  39. }

图 1.4-2

图中示例分别为勾股定理(左),极坐标系(中)和中点算法(右)


[1] 计算机图形学第四版.电子工业出版社.109~114
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注