计算机图形学:中点画圆算法

2024-08-26 13:58

本文主要是介绍计算机图形学:中点画圆算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在平面解析几何中,圆的方程可以描述为(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)= x+ y– 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

 

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

26 void MP_Circle(int xc , int yc , int r)

27 {

28     int x, y;

29     double d;

30 

31     x = 0;

32     y = r;

33     d = 1.25 - r;

34     CirclePlot(xc , yc , x , y);

35     while(< y)

36     {

37         if(< 0)

38         {

39             d = d + 2 * x + 3;

40         }

41         else

42         {

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

44             y--;

45         }

46         x++;

47         CirclePlot(xc , yc , x , y);

48     }

49 }

 参数xc和yc是圆心坐标,r是半径,CirclePlot()函数是参照圆的八分对称性完成八个点的位置计算的辅助函数。

2  改进的中点画圆法-Bresenham算法

        中点画圆法中,计算判别式d使用了浮点运算,影响了圆的生成效率。如果能将判别式规约到整数运算,则可以简化计算,提高效率。于是人们针对中点画圆法进行了多种改进,其中一种方式是将d的初始值由1.25 – R改成1 – R,考虑到圆的半径R总是大于2,因此这个修改不会响d的初始值的符号,同时可以避免浮点运算。还有一种方法是将d的计算放大两倍,同时将初始值改成3 – 2R,这样避免了浮点运算,乘二运算也可以用移位快速代替,采用3 – 2R为初始值的改进算法,又称为Bresenham算法:

52 void Bresenham_Circle(int xc , int yc , int r)

53 {

54     int x, y, d;

55 

56     x = 0;

57     y = r;

58     d = 3 - 2 * r;

59     CirclePlot(xc , yc , x , y);

60     while(< y)

61     {

62         if(< 0)

63         {

64             d = d + 4 * x + 6;

65         }

66         else

67         {

68             d = d + 4 * ( x - y ) + 10;

69             y--;

70         }

71         x++;

72         CirclePlot(xc , yc , x , y);

73     }

74 }

3、  正负判定画圆法

        除了中点画圆算法,还有一种画圆算法也是利用当前点产生的圆函数进行符号判别,利用负反馈调整以决定下一个点的产生来直接生成圆弧,就是正负法,下面就介绍一下正负法的算法实现。

        正负法根据圆函数:F(x, y)= x+ y– R2的值,将平面区域分成圆内和圆外,如图(3)所示:

图(3)正负法判定示意图

假设圆弧的生成方向是从A到B方向,当某个点Pi被确定以后,Pi的下一个点Pi+1的取值就根据F(xi, yi)的值进行判定,判定的原则是:

 

1、当F(xi, yi)≤ 0时:取xi+1 = xi+1,yi+1 = yi。即向右走一步,从圆内走向圆外。对应图(3-a)中的从Pi到Pi+1

2、当F(xi, yi)> 0时:取xi+1 = xi,yi+1 = yi - 1。即向下走一步,从圆外走向圆内。对应图(3-b)中的从Pi到Pi+1

 

由于下一个点的取向到底是向圆内走还是向圆外走取决于F(xi, yi)的正负,因此称为正负法。对于判别式F(xi, yi)的递推公式,也要分两种情况分别推算:

 

1、当F(xi, yi)≤ 0时,Pi的下一个点Pi+1取xi+1 = xi+1,yi+1 = yi,判别式F(xi+1, yi+1)的推算过程是:

F(xi+1, yi+1)= F(xi+1,yi) = (xi+1)2+yi2-R= (xi2+yi2-R2)+2xi+1 = F(xi,yi)+2xi+1

 

2、当F(xi, yi)> 0时,Pi的下一个点Pi+1取xi+1 = xi,yi+1 = yi - 1,判别式F(xi+1, yi+1)的推算过程是:

F(xi+1, yi+1)= F(xi,yi-1) = xi2+(yi-1)- R= (xi2+yi2-R2) - 2y+ 1 = F(xi,yi) - 2yi+1

 

设画圆的初始点是(0,R),判定式的初始值是0,正负法生成圆的算法如下:

105 void Pnar_Circle(int xc, int yc, int r)

106 {

107     int x, y, f;

108 

109     x = 0;

110     y = r;

111     f = 0;

112     while(<= y)

113     {

114         CirclePlot(xc, yc, x, y);

115         if(<= 0)

116         {

117             f = f + 2 * x + 1;

118             x++;

119         }

120         else

121         {

122             f = f - 2 * y + 1;

123             y--;

124         }

125     }

126 }

        改进的中点划线算法和正负法虽然都避免了浮点运算,并且计算判别式时用到的乘法都是乘2运算,可以用移位代替,但是实际效率缺有很大差别。因为正负法并不是严格按照x方向步进的,因此就会出现在某个点的下一个点在两个位置上重复画点的问题,增加了不必要的计算。此外,从生成圆的质量看,中点画圆法和改进的中点画圆法都比正负法效果好。

4、  快速画圆法

        除了中点画圆法和正负法,本文再介绍一种圆的光栅扫描算法,就是快速画圆法。快速画圆法的生成效果和中点画圆法差不多,但是判别式的计算只用了加减法,没有用任何乘法,因此被成为快速画圆法。我找不到快速画圆法的理论依据,只是把算法的实现写出来,供有兴趣的读者参考。以下就是快速画圆法的实现算法:

128 void Fast_Circle(int xc , int yc , int r)

129 {

130     int x, y, d;

131 

132     x = 0;

133     y = r;

134     d = -/ 2;

135     CirclePlot(xc , yc , x , y);

136     if(% 2 == 0)

137     {

138         while(< y)

139         {

140             x++;

141             if(< 0)

142                 d += x;

143             else

144             {

145                 y--;

146                 d += x - y;

147             }

148 

149             CirclePlot(xc , yc , x , y);

150         }

151     }

152     else

153     {

154         while(< y)

155         {

156             x++;

157             if(< 0)

158               d += x + 1;

159             else

160             {

161               y--;

162               d += x - y + 1;

163             }

164 

165             CirclePlot(xc , yc , x , y);

166         }

167     }

168 }

        圆的光栅扫描转换算法有很多种,本文介绍的几个都是简单易懂的算法,除了本文介绍的几种方法外,还有很多种圆光栅转换算法,比如多边形逼近算法等等,有兴趣的读者可以参考计算机图形学方面的资料自己研究算法的实现。

 

 

 

 

 

参考资料:

 

【1】计算几何:算法设计与分析 周培德  清华大学出版社 2005年

【2】计算几何:算法与应用 德贝尔赫(邓俊辉译)  清华大学出版社 2005年

【3】计算机图形学 孙家广、杨常贵 清华大学出版社 1995年


中点画圆opengl实现:

#include<windows.h>
#include<GL/glut.h>void init(int argc,char** argv)
{glutInit(&argc,argv);glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);glutInitWindowPosition(50,100);glutInitWindowSize(400,400);glutCreateWindow("Bresenham");glClearColor(1.0,1.0,1.0,0);glMatrixMode(GL_PROJECTION);gluOrtho2D(0,400,0,400);
}
void Bresenham_Circle(int xc,int yc,int r)
{int x, y, d;x = 0;y = r;d = 3 - 2 * r;glVertex2i(x+xc,y+yc);while(x < y){if(d < 0){d = d + 4 * x + 6;}else{d = d + 4 * ( x - y ) + 10;y--;}x++;glVertex2i(x+xc,y+yc);glVertex2i(y+xc,x+yc);glVertex2i(y+xc,-x+yc);glVertex2i(x+xc,-y+yc);glVertex2i(-x+xc,-y+yc);glVertex2i(-y+xc,-x+yc);glVertex2i(-x+xc,y+yc);glVertex2i(-y+xc,x+yc);}
}
void myDisplay(void)
{glClear(GL_COLOR_BUFFER_BIT);glColor3f(0.0,0.4,0.2);glPointSize(2);glBegin(GL_POINTS);Bresenham_Circle(200,200,50);glEnd();glFlush();
}
int main(int argc,char** argv)
{init(argc,argv);glutDisplayFunc(myDisplay);glutMainLoop();return 0;
}


这篇关于计算机图形学:中点画圆算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1108762

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯: