计算机图形：中点椭圆算法

这是一种增量方法, 用于扫描转换以标准位置为原点的椭圆, 即长轴和短轴平行于坐标系轴。它与中点圆算法非常相似。由于四向对称性, 我们需要考虑第一象限中的整个椭圆曲线。

首先, 我们重写椭圆方程, 并定义函数f, 该函数可用于确定两个候选像素之间的中点是在椭圆的内部还是外部：

现在将椭圆曲线从（0, b）到（a, 0）在点Q处分成两部分, 曲线的斜率是-1。

曲线的斜率由f（x, y）= 0定义, 其中fx＆fy是f（x, y）相对于x＆y的偏导数。

我们有fx = 2b2 x, fy = 2a2 y＆因此我们可以在扫描转换过程中监视斜率值以检测Q。我们的起点是（0, b）

假设在进入步骤i时最后扫描转换​​像素的坐标为（xi, yi）。我们将选择T（xi + 1）, yi）或S（xi + 1, yi-1）作为下一个像素。 T＆S的中点用于定义以下决策参数。

pi = f(xi+1), yi-) pi=b2 (xi+1)2+a2 (yi-)2-a2 b2

如果pi <0, 则中点位于曲线内, 我们选择像素T。

如果pi> 0, 则中点位于曲线的外部或曲线上, 我们选择像素S。

下一步的决策参数是：

pi+1=f(xi+1+1, yi+1-) = b2 (xi+1+1)2+a2 (yi+1-)2-a2 b2

Since xi+1=xi+1, we have pi+1-pi=b2[((xi+1+1)2+a2 (yi+1-)2-(yi -)2] pi+1= pi+2b2 xi+1+b2+a2 [(yi+1-)2-(yi -)2]

如果选择T为像素（pi <0）, 则yi + 1 = yi。

如果选择S为像素（pi> 0）, 则yi + 1 = yi-1。这样我们可以表达

pi+1in terms of pi and (xi+1, yi+1): pi+1= pi+2b2 xi+1+b2 if pi<0 = pi+2b2 xi+1+b2-2a2 yi+1 if pi>0

可以通过使用（0, b）评估pi的原始定义来获得递归表达式的初始值：

p1 =（b2 + a2（b-）2-a2 b2 = b2-a2 b + a2 / 4

假设像素（xj yj）在进入步骤j时刚刚进行了扫描转换。下一个像素是U（xj, yj-1）或V（xj + 1, yj-1）。连接U＆V的水平线的中点用于定义决策参数：

qj = f（xj +, yj-1）qj = b2（xj +）2 + a2（yj -1）2-a2 b2

如果qj <0, 则中点在曲线内, 我们选择像素V。

如果qj≥0, 则中点在曲线外, 我们选择像素U.下一步的决策参数为：

qj + 1 = f（xj + 1 +, yj + 1-1）= b2（xj + 1 +）2+ a2（yj + 1-1）2- a2 b2

由于yj + 1 = yj-1, 我们有qj + 1-qj = b2 [（xj + 1 +）2-（xj +）2] + a2（yj + 1-1）2-（yj + 1）2 ] qj + 1 = qj + b2 [（xj + 1 +）2-（xj +）2] -2a2 yj + 1 + a2

如果选择V作为像素（qj <0）, 则xj + 1 = xj。

如果选择U作为像素（pi> 0）, 则xj + 1 = xj。这样我们可以表达

用qj和（xj + 1, yj + 1）表示qj + 1：qj + 1 = qj + 2b2 xj + 1-2a2 yj + 1 + a2如果qj <0 = qj-2a2 yj + 1 + a2如果qj> 0

使用qj的原始定义计算递归表达式的初始值。为曲线的第1部分选择的最后一个像素的（xk yk）坐标：

q1 = f（xk +, yk-1）= b2（xk +）2-a2（yk-1）2- a2 b2

算法

int x=0, y=b; [starting point]
int fx=0, fy=2a2 b [initial partial derivatives]
int p = b2-a2 b+a2/4
while (fx2;
	if (p<0)
	p = p + fx +b2;
	else
	{
		y--;
		fy=fy-2a2
		p = p + fx +b2-fy;
	}
}
Setpixel (x, y);
p=b2(x+0.5)2+ a2 (y-1)2- a2 b2
while (y>0)
{
	y--;
	fy=fy-2a2;
	if (p>=0)
	p=p-fy+a2
           else
	{
		x++;
		fx=fx+2b2
		p=p+fx-fy+a2;
	}
	Setpixel (x, y);
}

使用中点椭圆算法绘制椭圆的程序：

#include <graphics.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include <conio.h>
#include <iostream.h>

class bresen
{
	float x, y, a, b, r, p, h, k, p1, p2;
	public:
	void get ();
	void cal ();
};
	void main ()
    {
	bresen b;
	b.get ();
	b.cal ();
	getch ();
   }
	void bresen :: get ()
   {
	cout<<"\n ENTER CENTER OF ELLIPSE";
	cout<<"\n ENTER (h, k) ";	
           cin>>h>>k;
	cout<<"\n ENTER LENGTH OF MAJOR AND MINOR AXIS";
	cin>>a>>b;
  }
void bresen ::cal ()
{
	/* request auto detection */
	int gdriver = DETECT, gmode, errorcode;
	int midx, midy, i;
	/* initialize graphics and local variables */
	initgraph (&gdriver, &gmode, " ");
	/* read result of initialization */
	errorcode = graphresult ();
	if (errorcode ! = grOK)    /*an error occurred */
	{
 		printf("Graphics error: %s \n", grapherrormsg (errorcode);
		printf ("Press any key to halt:");
		getch ();
		exit (1); /* terminate with an error code */
	}
	x=0;
	y=b;
	// REGION 1
	p1 =(b * b)-(a * a * b) + (a * a)/4);
	{
		putpixel (x+h, y+k, RED);
		putpixel (-x+h, -y+k, RED);
		putpixel (x+h, -y+k, RED);
		putpixel (-x+h, y+k, RED);
		if (p1 < 0)
			p1 += ((2 *b * b) *(x+1))-((2 * a * a)*(y-1)) + (b * b);
		else
		{
			p1+= ((2 *b * b) *(x+1))-((2 * a * a)*(y-1))-(b * b);
			y--;		
		}
		x++;
	}
	//REGION 2
	p2 =((b * b)* (x + 0.5))+((a * a)*(y-1) * (y-1))-(a * a *b * b);
	while (y>=0)
	{
		If (p2>0)
		p2=p2-((2 * a * a)* (y-1))+(a *a);
		else
		{
		p2=p2-((2 * a * a)* (y-1))+((2 * b * b)*(x+1))+(a * a);
		x++;
		}
		y--;
		putpixel (x+h, y+k, RED);
		putpixel (-x+h, -y+k, RED);
		putpixel (x+h, -y+k, RED);
		putpixel (-x+h, y+k, RED);
	}
	getch();
}

输出：