中点椭圆算法

17 Mar 2025 | 4 分钟阅读

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

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

现在将椭圆曲线从 (0, b) 分成两部分，到 (a, 0) 在点 Q，其中曲线的斜率为 -1。

曲线的斜率由 f(x, y) = 0 定义为中点椭圆算法，其中 fx & fy 是 f(x, y) 相对于 x & y 的偏导数。

我们有 fx = 2b² x, fy=2a² y & 中点椭圆算法因此，我们可以在扫描转换过程中监视斜率值以检测 Q。我们的起始点是 (0, b)

假设进入步骤 i 时，最后一个扫描转换像素的坐标是 (x_i,y_i)。我们将选择 T (x_i+1),y_i) 或 S (x_i+1,y_i-1) 作为下一个像素。 T & S 的中点用于定义以下决策参数。

pi = f(x_i+1),y_i- 中点椭圆算法 )
pi=b² (x_i+1)²+a² (y_i-)²-a² b²

如果 pi<0，中点在曲线内部，我们选择像素 T。

如果 pi>0，中点在曲线外部或曲线上，我们选择像素 S。

下一步的决策参数是

p_i+1=f(x_i+1+1,y_i+1- 中点椭圆算法 )
= b² (x_i+1+1)²+a² (y_i+1-)²-a² b²

由于 x_i+1=xi+1，我们有
p_i+1-pi=b²[((x_i+1+1)²+a² (y_i+1- 中点椭圆算法 )²-(y_i -)²]
p_i+1= pi+2b² x_i+1+b²+a² [(y_i+1-)²-(y_i -)²]

如果选择了像素 T (pi<0)，我们有 y_i+1=yi。

如果选择了像素 S (pi>0)，我们有 y_i+1=yi-1。因此我们可以表达

p_i+1 用 pi 和 (x_i+1,y_i+1): p_i+1= pi+2b² x_i+1+b² if pi<0 = pi+2b² x_i+1+b²-2a² y_i+1 if pi>0

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

p1 = (b²+a² (b- 中点椭圆算法 )²-a² b²
= b²-a² b+a²/4

假设像素 (x_j y_j) 在进入步骤 j 时刚刚被扫描转换。下一个像素是 U (x_j ,y_j-1) 或 V (x_j+1,y_j-1)。连接 U & V 的水平线的中点用于定义决策参数

q_j=f(x_j+ 中点椭圆算法 ,y_j-1)
q_j=b² (x_j+)²+a² (y_j -1)²-a² b²

如果 q_j<0，中点在曲线内部，我们选择像素 V。

如果 q_j≥0，中点在曲线外部，我们选择像素 U。下一步的决策参数是

q_j+1=f(x_j+1+ 中点椭圆算法 ,y_j+1-1)
= b² (x_j+1+)²+ a² (y_j+1-1)²- a² b²

由于 y_j+1=y_j-1，我们有
q_j+1-q_j=b² [(x_j+1+ 中点椭圆算法 )²-(x_j +)² ]+a² (y_j+1-1)²-( y_j+1)² ]
q_j+1=q_j+b² [(x_j+1+)²-(x_j +)²]-2a² y_j+1+a²

如果选择了像素 V (qj<0)，我们有 x_j+1=xj。

如果选择了像素 U (pi>0)，我们有 x_j+1=xj。因此我们可以表达

q_j+1用 q_j 和 (x_j+1,y_j+1 )
q_j+1=q_j+2b² x_j+1-2a² y_j+1+a² if qj < 0
=q_j-2a² y_j+1+a² if qj>0

递归表达式的初始值是使用 qj 的原始定义计算的。以及曲线的第 1 部分选择的最后一个像素的坐标 (x_k y_k)

q1 = f(x_k+ 中点椭圆算法 ,y_k-1)=b² (x_k+)²-a² (y_k-1)²- a² b²

算法

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

输出