中点圆算法

17 Mar 2025 | 阅读 2 分钟

它基于以下函数，用于测试任意点 (x, y) 与以原点为中心的半径为 r 的圆的空间关系

现在，考虑点位于像素 T 和像素 S 之间一半的坐标

这被称为中点 (x_i+1,y_i- MidPoint Circle Algorithm ) ，我们用它来定义一个决策参数

P_i=f (x_i+1,y_i- MidPoint Circle Algorithm ) = (x_i+1)²+(y_i-)²-r² ...............公式 2

如果 P_i 为 -ve ⟹中点在圆内，我们选择像素 T

如果 P_i 为+ve ⟹中点在圆外（或在圆上），我们选择像素 S。

下一步的决策参数是

P_i+1=(x_i+1+1)²+(y_i+1- MidPoint Circle Algorithm )²- r²............公式 3

由于 x_i+1=x_i+1，我们有

如果选择像素 T ⟹P_i<0

我们有 y_i+1=y_i

如果选择像素 S ⟹P_i≥0

我们有 y_i+1=y_i-1

我们可以继续简化为 n 个 (x_i,y_i) 项，得到

现在，P_i 的初始值 (0,r) 来自公式 2

我们可以将 MidPoint Circle Algorithm ≅1
∴r 是一个整数
所以，P₁=1-r

算法

步骤 1： 在公式 2 中，将 x =0，y =r
我们有 p=1-r

步骤 2： 只要 x ≤ y，就重复步骤
绘制 (x, y)
如果 (p<0)
然后设置 p = p + 2x + 3
否则
p = p + 2(x-y)+5
y =y - 1 (结束如果)
x =x+1 (结束循环)

步骤 3： 结束

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

#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;
	public:
	void get ();
	void cal ();
};
	void main ()
    {
	bresen b;
	b.get ();
	b.cal ();
	getch ();
   }
	Void bresen :: get ()
   {
	cout<<"ENTER CENTER AND RADIUS";
	 cout<< "ENTER (a, b)";
	cin>>a>>b;
	cout<<"ENTER r";
	cin>>r;
}
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=r;
	putpixel (a, b+r, RED);
	putpixel (a, b-r, RED);
	putpixel (a-r, b, RED);
	putpixel (a+r, b, RED);
	p=5/4)-r;
	while (x<=y)
	{
		If (p<0)
		p+= (4*x)+6;
		else
		{
			p+=(2*(x-y))+5;
			y--;
		}
		x++;
		putpixel (a+x, b+y, RED);
		putpixel (a-x, b+y, RED);
		putpixel (a+x, b-y, RED);
		putpixel (a+x, b-y, RED);
		putpixel (a+x, b+y, RED);
		putpixel (a+x, b-y, RED);
		putpixel (a-x, b+y, RED);
		putpixel (a-x, b-y, RED);
	}
}

输出