椭圆中点Bresenham算法

1、.专业整理 .目录一、设计题目 2二、设计要求 2三、设计方案 2四、程序流程图6五、程序 清单 7六、程序运行结果分析 15七、系统不足及改进方案 15八、设计总结16. 学习帮手 .专业整理 .一、设计题目 ：椭圆中点 Bresenham算法二、设计要求 ：1、要求有两种输入方式 ：（1）输入椭圆的长短轴来生成椭圆；（2）根据输入点来生成椭圆并输出椭圆的长短轴；2、椭圆的颜色为红色 ；三、设计方案 ：1、椭圆对称性质 ：椭圆分别关于 X 轴、Y 轴对称 。因此在计算椭圆生成的时候，只需要计算 1/4 个椭圆，经过对称原理就可以实现其他3/4 个椭圆的生成了，即：计算出目标点 （x,y）的坐

2、标，必然存在 （x,-y）、（ -x,y ）（-x,-y ）。此方案中采用计算第一象限中椭圆的生成，即：计算 x=0 到 y=0的 1/4 的椭圆 。先通过平移的方法将假设椭圆中心在坐标原点，然后计算 ，最后再平移到真实中心位置。2、对于第一象限的椭圆 ，斜率 k=- （ b*b ）*x/（a*a ）*y，当 x< 时，斜率. 学习帮手 .专业整理 .k 的绝对值小于1，计算时在 x 方向上取单位量 ；当 x>y 时，斜率 k 的绝对值大于 1，计算时在 y 方向上取单位量 。记：x<y 的区域为第一区域 ，x>y 的区域为第二区域 。3、输入方式一 ：输入椭圆的长短轴

3、来生成椭圆。已知：长短半轴分别为a、 b，计算的初始位置为 （ 0,b）。x2y2椭圆的方程为 ： a2b21 。令 F（x,y） =b*b*x*x+a*a*y*y- a*a* b*b=0（ 1）对于第一区域 ，如图 1 所示， P 点坐标为 （ xP , yP ）、 P1（ xP +1, yP ）为 P 点正右边的点 、 P2（ xP +1, yP -1 ）为 P 点右下方的点 ， M （ xP +1, yP -0.5 ）为 P1、 P2 的中点 。P P1 MP2图1 第一区域示意图. 学习帮手 .专业整理 .令 d=F （ M ）=F （ xP +1, yP -0.5 ）=b*b+a*a

4、* （ b-0.5 ）*（b-0.5 ）-a*a*b*b当 xP =0 、 yP =b 时， d 的初始值为 ： d= b*b-a*a*b+1/4a*a1 d>=0 时，应取 P2 作为下一个像素点 ，则其正右方的点的坐标为（ xP +2, yP -1 ），右下方的点的坐标为 （ xP +2, yP -2 ），中点坐标为（ xP +2, yP -1.5 ）。此时，d=F （M ） =F（ xP +2, yP -1.5 ）=d+b*b* （ 2* xP +3 ） -2a*a* （ yP -1 ）2 d<0 时，应取 P1 作为下一个像素点 ，则其正右方的点的坐标为（ xP +2, y

5、P ），右下方的点的坐标为 （ xP +2, yP -1 ），中点坐标为（ xP +2, yP -0.5 ）。此时，d=F （M ） =F（ xP +2, yP -0.5 ）=d+2* b*b*xP +3* b*b（ 2）对于第二区域 ，如图 2 所示， P 点坐标为 （ xP , yP ）， P1（ xP , yP -1 ）为 P 点正下方的点 、 P2（ xP +1, yP -1 ）为 P 点右下方的点 ， M （ xP +0.5, yP -1 ）为 P1、 P2 的中点 。. 学习帮手 .专业整理 .PP1MP2图2 第二区域示意图令 d=F （ M ）=F （ xP +0.5, yP

6、-1 ）=b*b* （ xP +0.5 ）*（ xP +0.5 ）+a*a*（ yP -1 ）*（ yP -1 ）-a*a*b*b设 P 坐标的初始值为 xP = x0 ， yP = y0 ， x0 = y0d 的初始值为 ：d= F （ x0 +0.5,y0 -1 ） = b*b* （ x0 +0.5 ）*（ x0 +0.5 ） +a*a* （ y0 -1 ）*（ y0 -1 ） -a*a*b*b1 d>=0 时，应取 P1 作为下一个像素点 ，则其正下方的点的坐标为（ xP , yP -2 ），右下方的点的坐标为 （ xP +1, yP -2 ），中点坐标为（ xP +0.5, yP

7、 -2 ）。此时，d=F （M ） =F（ xP +0.5, yP -2 ）=d+ a*a* （3-2 * yP ）. 学习帮手 .专业整理 .2 d<0 时，应取 P2 作为下一个像素点 ，则其正下方的点的坐标为（ xP +1, yP -2 ），右下方的点的坐标为 （ xP +2, yP -2 ），中点坐标为（ xP +1.5, yP -2 ）。此时，d=F （M ） =F（xP+1.5,yP-2 ）=d+2*b*b*（x0+1）+ a*a* （ 3-2*yP）（ 3）根据对称性原理计算其他3 个象限的坐标 。输入方式二 ：根据输入点来生成椭圆并输出椭圆的长短轴。已知：两点坐标 （ x

8、1 , y1 ）、（ x2 , y2 ）x2y2设椭圆的方程为 ： a2b21将两点坐标 （ x1 , y1 ）、（ x2 , y2 ）代人椭圆方程中，得出 a、b 的值分别为 ：a2 = （ x2 2 * y12 - x12 * y2 2 ）/ （ y12 - y2 2 ）b2 =( x12 * y22 - x2 2 * y12 )/( x12 - x2 2 )然后按照方式一生成所求椭圆。四、程序流程图输入方式一的流程图如图3 所示：. 学习帮手 .专业整理 .输入方式二的流程图如图4 所示：输入椭圆长短半轴 a、bd+=a*a* （3-2 *y ）YNd=b*b*(x+0.5)*(x+0.

9、5)+0<x<ya*a* (y-1)*(y-1)-a*a*b*b>=0YNd= b*b-a*a*b+1/4a*a>=0NYd+=2* b*b*x +3* b*bd+=b*b* （2*x+3 ）d+=2*b*b* （ x+1）+ a*a* （ 3-2*y ）-2a*a* （y-1）计算第一象限椭圆上各个坐标的值根据对称原理计算其它三个象限的各点坐标图3 输入方式一流程图输入两点的坐标值通过两点坐标计算a、 b的值，并输出转向方式一计算椭圆的各点坐标. 学习帮手 .图 4 输入方式二流程图.专业整理 .五、程序清单/ zhongdiansuanfa.cpp : Define

10、s the entry point for the console application.#include "stdafx.h"#include <stdlib.h>#include <vector>#include <GL/glut.h>#include <math.h>int a;. 学习帮手 .专业整理 .int b;/* 定义长短半轴分别为a、 b*/void GetValue()int input=0;int x1,x2,y1,y2;printf(" 请输入中点算法产生的方式：n");print

11、f("1. 输入椭圆长短半径 n");printf("2. 输入椭圆坐标 n");/* 输出两种输入方式 */scanf("%d",&input);if(input=1)printf(" 请输入 a 的值： n");scanf("%d",&a);. 学习帮手 .专业整理 .printf(" 请输入 b 的值：n");scanf("%d",&b);if(input=2)printf(" 请输入第一个坐标的值 ：n"

12、);scanf("%d,%d",&x1,&y1);printf(" 请输入第二个坐标的值 ：n");scanf("%d,%d",&x2,&y2);a=sqrt (y1*y1*x2*x2-x1*x1*y2*y2)/(y1*y1-y2*y2);b=sqrt (x1*x1*y2*y2-x2*x2*y1*y1)/(x1*x1-x2*x2);/* 根据输入的两个坐标计算椭圆长短半轴a、b 的值 */printf("a=%d",a);printf("b=%d",b);. 学习

13、帮手 .专业整理 ./* 输出长短半轴a、 b 的值 */void PointsEllipse(int x,int y)glColor3f (1.0f, 0.0f, 0.0f);/* 生成的椭圆的颜色为红色*/glPointSize(1);glBegin (GL_POINTS);glVertex2i(x+200,y+200);glVertex2i(-x+200,y+200);glVertex2i(x+200,-y+200);glVertex2i(-x+200,-y+200);/* 根据对称原理求出椭圆上各个点的坐标*/glEnd ();. 学习帮手 .专业整理 .void myDisplay(

14、)glClear(GL_COLOR_BUFFER_BIT);glColor3f (1.0f, 0.0f, 0.0f);glBegin (GL_POINTS);/int a=200,b=100;float x,y,d1,d2;x=0;y=b;/* 第一区域的起始坐标 */d1=b*b+a*a*(-b+0.25);. 学习帮手 .专业整理 .PointsEllipse(x,y);/* 计算第一区域椭圆上各个点的坐标*/while(b*b*(x+1)<a*a*(y-0.5)if (d1<0)d1+=b*b*(2*x+3);x+;elsed1+=b*b*(2*x+3)+a*a*(-2*y+

15、2);x+;y-;. 学习帮手 .专业整理 .PointsEllipse(x,y);/* 计算第二区域椭圆上各个点的坐标*/d2=b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b;/* 第二区域的起始点处的d 值*/while(y>0)if (d2<0)d2+=2*b*b*(x+1)-a*a*(2*y-3);x+;y-;else. 学习帮手 .专业整理 .d2+=a*a*(-2*y+3);y-;PointsEllipse(x,y);glEnd ();glFlush();/* 保证前面的 OpenGL 命令立即执行 */void Init()Ge

16、tValue();glClearColor(0.0, 0.0, 0.0, 0.0);/* 定义清空颜色设计为黑色*/glShadeModel(GL_FLAT);. 学习帮手 .专业整理 .void Reshape(int w, int h)glViewport(0, 0, (GLsizei) w,(GLsizei) h);glMatrixMode(GL_PROJECTION);glLoadIdentity();gluOrtho2D(0.0, (GLdouble) w, 0.0, (GLdouble) h);int main(int argc, char *argv)glutInit(&

17、argc, argv);glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);glutInitWindowPosition(100, 100);/* 定义窗口在屏幕中的位置*/. 学习帮手 .专业整理 .glutInitWindowSize(600, 600);/* 定义窗口的大小 */glutCreateWindow("zhongdiansuanfa!");/* 根据前述设置的信息创建窗口*/Init();glutDisplayFunc(myDisplay);glutReshapeFunc(Reshape);glutMainLoop();

18、return 0;六、程序运行结果分析运行该程序 ，窗口中显示 ：请输入中点算法产生的方式：1、输入椭圆长短半径 。2、输入椭圆坐标 。. 学习帮手 .专业整理 .输入 1，并单击回车 ，显示请输入 a 的值，输入 a 的值，并单击回车 ，将显示请输入 b 的值，输入 b 的值，并单击回车 ，屏幕上将显示一个以a、b 为长短半轴的红色椭圆 ；输入 2，并单击回车 ，将显示请输入第一个坐标的值，输入第一个坐标的值 ，并单击回车 ，将显示请输入第二个坐标的值，输入第二个坐标的值 ，并单击回车，屏幕上将显示一个以原点为中心，经过两个坐标的红色椭圆。七、系统不足及改进方案该算法生成的椭圆以原点为中心，如果要想实现椭圆的中心可放在任何位置，则在上述算法中通过平移的方法将假设圆心在坐标原点，然后计算 ，最后再平移到真实的中心位置。假设椭圆的中心坐标为 （ x-center ，y-center ），则100010x'