中点画圆法
利用圆的八向对称性画圆。
假设从P点顺时针画圆,下一个像素点选P1还是P2呢? M为P1与P2的中点。
构造函数：
对于圆上的点，F(x, y)=0；对于圆外的点，F(x, y) > 0；而对于圆内的点，F(x, y) < 0。假设M是P1和P2的中点，即M=(xi+1, yi-0.5)。那么，当F(M)<0时，M在圆内，这说明P1距离圆弧更近，应取P1作为下一个像素。而F(M)>0时，M在圆外，这说明P2距离圆弧更近，应取P2作为下一个像素。当F(M)=0时，在P1和P2之中随便取一个即可，这里约定取P2。
构造判别式
若d<0，应取P1作为下一个像素。再下一个像素的判别式为:
所以，沿正右方向，此时d的增量为2xi+3。
而若d>=0，应取P2作为下一个像素，再下一个像素的判别式为：
所以，沿右下方向，此时d的增量为2(xi-yi)+5。
由于这里讨论的是按顺时针方向生成第二个八分之一圆，因此，第一个像素是(0, R)，判别式d的初始值为
代码: C#
private void MidPointCircle(int R)
{
int x, y;
double d;
x = 0; y = R; d = 1.25 - R;
SetPixel(x, y);
while(x < y)
{
if (d < 0)
{
d += 2 * x + 3;
x++;
}
else
{
d += 2 * (x - y) + 5;
x++;
y--;
}
SetPixel(x, y);
}
}
优化版: 消除浮点运算
private void MidPointCircle(int R)
{
int x, y;
double d;
x = 0; y = R; d = 1 - R;//去掉小数部分
SetPixel(x, y);
while(x < y)
{
//由于d始终为整数，
//所以d<-0.25等价于d<0
//if (d < -0.25f)
if (d < 0)
{
d += 2 * x + 3;
x++;
}
else
{
d += 2 * (x - y) + 5;
x++;
y--;
}
SetPixel(x, y);
}
}
优化版: 消除乘法运算
通过使用增量计算技术，可以进一步改进上术算法的效率。注意到上术算法中判别式d的增量x、y的线性函数。若d<0，P1为下一个像素，d的增量为:d1=2x+3，可见，x的变化将影响d1的值。若d>=0，P2为下一个像素，d的增量为d2=2(x-y)+5，可见，x和y的变化都将影响d2的值。
每当x递增1，d1递增2，d2递增2。每当y递减1，d2递增2。所以归纳起来，若d<0，P1为下一个像素，x递增1，d1递增2，d2递增2；若d>=0，P2为下一个像素，x递增1，y递减1，d1递增2，d2递增4。由于初始像素为(0, R)，所以d1的初始值为3，d2的初始值为-2R+5。再注意到乘2运算可以改用加法实现，至此可写出不含乘法、仅用整数实现的中点画圆算法。
private void MidPointCircle(int R)
{
int x, y, delta1, delta2, d;
x = 0; y = R; d = 1 - R;
delta1 = 3;
delta2 = 5 - R - R;
SetPixel(x, y);
while(x < y)
{
if (d < 0)
{
d += delta1;
delta1 += 2;
delta2 += 2;
x++;
}
else
{
d += delta2;
delta1 += 2;
delta2 += 4;
x++;
y--;
}
SetPixel(x, y);
}
}
完整示例: C#
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace MidCire
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{
//当窗口尺寸改变时重绘所有窗口
this.SetStyle(ControlStyles.AllPaintingInWmPaint | ControlStyles.ResizeRedraw, true);
}
private void Form1_Paint(object sender, PaintEventArgs e)
{
MidPointCircle(e.Graphics, 50);
}
private void MidPointCircle(Graphics g, int R)
{
int x, y, delta1, delta2, d;
x = 0; y = R; d = 1 - R;
delta1 = 3;
delta2 = 5 - R - R;
SetPixel(g, x, y);
while(x < y)
{
if (d < 0)
{
d += delta1;
delta1 += 2;
delta2 += 2;
x++;
}
else
{
d += delta2;
delta1 += 2;
delta2 += 4;
x++;
y--;
}
SetPixel(g, x, y);
}
}
private void SetPixel(Graphics g, int x, int y)
{
int centerOffset = 50;
Pen pen = new Pen(Brushes.Red);
g.DrawEllipse(pen, centerOffset + x, centerOffset + y, 1, 1);
}
}
}
运行截图
示例：画一个完整的圆
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace MidCire
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{
//当窗口尺寸改变时重绘所有窗口
this.SetStyle(ControlStyles.AllPaintingInWmPaint | ControlStyles.ResizeRedraw, true);
}
private void Form1_Paint(object sender, PaintEventArgs e)
{
MidPointCircle(e.Graphics, 50);
}
private void MidPointCircle(Graphics g, int R)
{
int x, y, delta1, delta2, d;
x = 0; y = R; d = 1 - R;
delta1 = 3;
delta2 = 5 - R - R;
SetPixel(g, x, y);
while(x < y)
{
if (d < 0)
{
d += delta1;
delta1 += 2;
delta2 += 2;
x++;
}
else
{
d += delta2;
delta1 += 2;
delta2 += 4;
x++;
y--;
}
SetPixel(g, x, y);
//利用圆的八向对称性画出其他弧线
SetPixel(g, -x, y);
SetPixel(g, x, -y);
SetPixel(g, -x, -y);
SetPixel(g, y, x);
SetPixel(g, -y, x);
SetPixel(g, y, -x);
SetPixel(g, -y, -x);
}
}
private void SetPixel(Graphics g, int x, int y)
{
int centerOffset = 50;
Pen pen = new Pen(Brushes.Red);
g.DrawEllipse(pen, centerOffset + x, centerOffset + y, 1, 1);
}
}
}
运行截图
