中点画圆算法

       如同光栅画线算法，我们在每一个步中以单位间隔取样并确定离指定圆近期的像素位置。对于给定半径r和屏幕中心(x_c,y_c)，能够先使用算法计算圆心在坐标原点(0,
0)的圆的像素位置，然后通过将x_c加到x且y_c加到y。从而把计算出的每一个位置(x,y)移动到其适当的屏幕位置。在第一象限中，圆弧段从x
= 0到x = y，曲线的斜率从0变化到-1.0。

因此，能够在该八分圆上的正x方向取单位步长。并使用决策參数来确定每一步两个可能的y位置中，哪一个更接近于圆的位置。然后，其它七个八分圆中的位置可由对称性得到。

为了应用中点画圆算法。我们定义一个圆函数:

半径为r的圆边界上不论什么一点(x, y)满足方程f_circ(x,y) = 0。假设点在圆的内部，则圆函数为负值;如果点在圆的外部，则圆函数为正值。总之。不论什么点(x, y)的相对位置可由圆函数的符号来决定:

(3.30)式中的圆函数在每一个取样步上对接近圆周的两个像素的中点进行測试。

因此，在中点算法中圆函数是决策參数，而且能够类似画线算法为这个函数设置增量运算。

图3.19给出了取样位置x_k+1上两个候选像素间的中点。

如果刚在(x_k,y_k)绘制了一个像素，下一步须要确定是像素位置(x_k+1,y_k)

还是(x_k+1,y_k-1)更接近于圆。

我们的决策參数是圆函数方程(3.29 )在这两个像素的中点求值而得到的:

　

假如p_k < 0。那么这个中点位于圆内。扫描线yk上的像素接近于圆周边界。否则，中点位于圆外或在圆周边界上。我们选择扫描线y_k-1的像素。

兴许的决策參数能够使用增量运算得到。我们对取样位置x_k+1= x_k+2处的圆函数求值。能够得到下一个决策參数的循环表达式:

或

当中。y_k+1是y_k或是y_k-1，取决于p_k的符号。

为了得到p_k+1增量可能是2x_k+1+1(假设p_k为负)或是2x_k+1+1-2y_k+1。

和2y_k+1的求值也能够通过增量的方式进行，即

在起始位置(0, r)处。这两个项的值分别为0和2r 。

2x_k+1项的每一个兴许值能够通过对前一值加2或是对2y_k+1的前一值减2而得到。

对圆函数在起始位置(x₀,y₀) = (0,r)处求值，就能够得到初始决策參数:

或

假如将半径r指定为整数，就能够对p₀进行简单的取整:

由于全部的增量都是整数。

如果以整数屏幕坐标指定圆參数，那么如同Bresenham画线算法中一样。中点方法使用整数加减来计算沿圆周的像素位置。我们可将中点画圆算法的步骤概括例如以下:

中点画圆算法的步骤

1.输入圆半径r和圆心(x_c,y_c)，并得到圆周(圆心在原点)上的第一个点:

2.计算决策參数的初始值：

3.在每一个x_k位置，从k = 0開始，完毕下列測试:假如p_k
< 0。圆心在(0, 0)的圆的下一个点为(x_k+1,y_k)而且

否则，圆的下一个点是(x_k+1,y_k-1)。而且

当中2x_k+1= 2x_k+2且2y_k+1= 2y_k-2。

4.确定在其它七个八分圆中的对称点。

5.将每一个计算出的像素位置移动到圆心在（x_c,y_c）的圆路径上，并画坐标值:

6.反复步骤3到步骤5，直至x >= y。





例3.2使用中点画圆算法绘图

给定圆半径r = 10，我们将演示中点画圆算法。确定在第一象限从x = 0到x = y沿八分圆的像素位置。决策參数的初始值为

对于中心在坐标原点的圆，初始点(x₀,y₀） = (0,10)，计算决策參数的初始增量项:

使用中点画圆算法计算的后继决策參数值和沿圆路径的位置为

下列程序段给出了用于实现中点画圆算法的过程。半径值和圆心坐标传递给过程circleMidpoint。

然后计算第一个八分圆上的一个像素位置并传递给过程circlePlotPoints。该过程通过重复调用setPixel函数在帧缓存中该像素及与其对称的全部像素位置来设定圆的颜色，setPixel由OpenGL画点函数实现。

#include "stdafx.h"

#include "GL/glut.h"

#include "stdlib.h"

#include "math.h"

#include "iostream"

using namespace std;

const GLdouble twoPi = 6.283185;

GLsizei winWidth = 400, winHeight = 300; // 屏幕显示宽高.

class screenPt {

public:

	screenPt(){

		x = y = 0;

	}

	GLint x, y;

	void setCoords(GLint xCoordValue, GLint yCorrdValue){

		x = xCoordValue;

		y = yCorrdValue;

	}

	GLint getx() const{

		return x;

	}

	GLint gety() const{

		return y;

	}

	void incrementx(){

		x++;

	}

	void incrementy(){

		y--;

	}

};

void init( )

{

	glClearColor(1.0, 1.0, 1.0, 1.0);

	glMatrixMode(GL_PROJECTION);

	gluOrtho2D(0.0, 200.0, 0.0, 150.0);

}

void setPixel(GLint xCoord, GLint yCoord){

	glBegin(GL_POINTS);

	glVertex2i(xCoord, yCoord);

	glEnd();

}

void circleMidpoint(GLint xc, GLint yc, GLint radius){

	screenPt circPt;

	GLint p = 1 - radius;//中点參数初值

	circPt.setCoords(0, radius);//Set coords for top point of circle

	void circlePlotPoints(GLint, GLint, screenPt);

	/*Plot the initial point in each circle quadrant*/

	circlePlotPoints(xc, yc, circPt);

	/*Calculate next point and plot in each octant*/

	while (circPt.getx() < circPt.gety()){

		circPt.incrementx();

		if (p < 0)

			p += 2 * circPt.getx() + 1;

		else{

			circPt.incrementy();

			p += 2 * (circPt.getx() - circPt.gety()) + 1;

		}

		circlePlotPoints(xc, yc, circPt);

	}

}

void circlePlotPoints(GLint xc, GLint yc, screenPt circPt)

{

	setPixel(xc + circPt.getx(), yc + circPt.gety());

	setPixel(xc - circPt.getx(), yc + circPt.gety());

	setPixel(xc + circPt.getx(), yc - circPt.gety());

	setPixel(xc - circPt.getx(), yc - circPt.gety());

	setPixel(xc + circPt.gety(), yc + circPt.getx());

	setPixel(xc - circPt.gety(), yc + circPt.getx());

	setPixel(xc + circPt.gety(), yc - circPt.getx());

	setPixel(xc - circPt.gety(), yc - circPt.getx());

}

void pieChart( )

{

	screenPt circCtr, piePt;

	GLint radius = winWidth / 4;         // Circle radius.

	circCtr.x = winWidth / 2;            // Circle center position.

	circCtr.y = winHeight / 2;

	circleMidpoint(circCtr.x, circCtr.y, radius);    // 调用中点画圆方法

}

void displayFcn( )

{

	glClear(GL_COLOR_BUFFER_BIT);         // Clear display window.

	glColor3f(0.0, 0.0, 1.0);             // Set circle color to blue.

	pieChart();

	glFlush();

}

void winReshpeFcn(GLint newWidth, GLint newHeight)

{

	glMatrixMode(GL_PROJECTION);

	glLoadIdentity();

	gluOrtho2D(0.0, GLdouble(newWidth), 0.0, GLdouble(newHeight));

	glClear(GL_COLOR_BUFFER_BIT);

	/* Reset display-window size parameters. */

	winWidth = newWidth;

	winHeight = newHeight;

}

int _tmain(int argc, char** argv)

{

	glutInit(&argc, argv);

	glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);

	glutInitWindowPosition(100, 100);

	glutInitWindowSize(winWidth, winHeight);

	glutCreateWindow("Pie Chart");

	init();

	glutDisplayFunc(displayFcn);

	glutReshapeFunc(winReshpeFcn);

	glutMainLoop();

}