1.中点画圆算法
（1）P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）
或P2（Xp +1，Yp +1)。
（2）构造函数：F（X，Y）=X2 + Y2 - R2 ；则
F（X，Y）= 0 （X，Y）在圆上；
F（X，Y）< 0 （X，Y）在圆内；
F（X，Y）> 0 （X，Y）在圆外。
设M为P1、P2间的中点，M=(Xp+1,Yp-0.5)
有如下结论：
F（M）< 0 ->M在圆内-> 取P1
F（M）>= 0 ->M在圆外-> 取P2
（3）构造判别式
d = F(M) = F(xp + 1, yp - 0.5)
= (xp + 1)2 + (yp - 0.5) 2 - R2
若d<0, 则P1 为下一个象素，那么再下一个象素的判别式为：
d1 = F(xp + 2, yp - 0.5) = (xp + 2)2 + (yp - 0.5) 2 - R2
= d + 2xp +3
即d 的增量为 2xp +3.
若d>=0, 则P2 为下一个象素，那么再下一个象素的判别式为：
d1 = F(xp + 2, yp - 1.5)= (xp + 2)2 + (yp - 1.5) 2 - R2
= d + （2xp + 3）+（-2 yp + 2）
即d 的增量为 2 (xp - yp) +5.
d的初值:d0 = F(1, R-0.5)= 1 + (R-0.5)2 - R2= 1.25 - R
#include "easyx.h"
#include "math.h"
#include "windows.h"
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "graphics.h"
int Draw_yuan(int r,int p1,int p2,int color)
{
int x,y;
double d;
x = p1;
y = p2 + r;
d = 1.25 -r;
putpixel(x,y,color);
while(x <= y)
{
if(d <0)
{
x = x + 1;
d = (x-p1+1)*(x-p1+1) + (y-p2-0.5)*(y-p2-0.5) - r * r;
}
else
{
x = x + 1;
y = y - 1;
d = (x-p1+1)*(x-p1+1) + (y-p2-0.5)*(y-p2-0.5) - r * r;
}
putpixel(x,y,color);
putpixel(y,x,color);
putpixel(x,2*p2-y,color);
putpixel(y,2*p2-x,color);
putpixel(2*p1-x,y,color);
putpixel(2*p1-y,x,color);
putpixel(2*p1-x,2*p2-y,color);
putpixel(2*p1-y,2*p2-x,color);
}
return 0;
}
int main()
{
//硬件测试，将gd装入图形驱动器，gm置入最大图形模式。
int gd=DETECT,gm,p1,p2,r,color;
printf("绘制圆的中点画圆算法\n");
printf("请输入半径:");
scanf("%d",&r);
printf("请输入圆心坐标:");
scanf("%d%d",&p1,&p2);
printf("请输入颜色:");
scanf("%d",&color);
//图形初始化
initgraph(&gd,&gm,"c:\\tc");
//设置兰背景。
setbkcolor(BLUE);
cleardevice();
Draw_yuan(r,p1,p2,color);
getch();
closegraph();
return 0;
}
2.正负画圆算法
（1）设圆的方程为F(x,y)=X2 + Y2 - R2=0;
假设求得Pi的坐标为(xi,yi)；
则当Pi在圆内时-> F(xi,yi)<0 -> 向右-> 向圆外
Pi在圆外时-> F(xi,yi)>0 -> 向下-> 向圆内
（2）即求得Pi点后选择下一个象素点Pi+1的规则为：
（3）若F(xi,yi) 已知，计算F(xi+1,yi+1) 可分两种情况
1. F(xi,yi)≤0-> xi+1 = xi+1，yi+1 = yi;
F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2
= (xi+1)2+ yi2 -R2 = F(xi,yi) +2xi +1
2. F(xi,yi)＞0-> xi+1 = xi，yi+1 = yi -1;
F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2
= xi2+(yi –1)2-R2 = F(xi,yi) - 2yi +1
//正负画圆算法
#include "easyx.h"
#include "math.h"
#include "windows.h"
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "graphics.h"
int Draw_yuan(int r,int p1,int p2,int color)
{
int x0,y0,x,y; //画圆的起始点
x0 = p1;
y0 = p2 + r; //起始点坐标
x = x0;
y = y0;
int F0 = (x0-p1)*(x0-p1) + (y0-p2)*(y0-p2) - r * r;
int F1 = F0;
int F2;
while(x <= y)
{
if(F1 <= 0)
{
x = x + 1;
F2 = (x-p1)*(x-p1) + (y-p2)*(y-p2) - r * r;
}
else
{
y = y - 1;
F2 = (x-p1)*(x-p1) + (y-p2)*(y-p2) - r * r;
}
putpixel(x,y,color);
putpixel(y,x,color);
putpixel(x,2*p2-y,color);
putpixel(y,2*p2-x,color);
putpixel(2*p1-x,y,color);
putpixel(2*p1-y,x,color);
putpixel(2*p1-x,2*p2-y,color);
putpixel(2*p1-y,2*p2-x,color);
F1 = F2;
}
return 0;
}
int main()
{
//硬件测试，将gd装入图形驱动器，gm置入最大图形模式。
int gd=DETECT,gm,p1,p2,r,color;
printf("绘制圆的正负画圆算法\n");
printf("请输入半径:");
scanf("%d",&r);
printf("请输入圆心坐标:");
scanf("%d%d",&p1,&p2);
printf("请输入颜色:");
scanf("%d",&color);
//图形初始化
initgraph(&gd,&gm,"c:\\tc");
//设置兰背景。
setbkcolor(BLUE);
cleardevice();
Draw_yuan(r,p1,p2,color);
getch();
closegraph();
return 0;
}
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号