中点画圆法

作者：追风剑情发布于：2018-4-14 22:55 分类：计算机图形学

中点画圆法

利用圆的八向对称性画圆。

假设从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);
        }
    }
}

运行截图