中点画圆法

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

中点画圆法

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

1111111.png

假设从P点顺时针画圆,下一个像素点选P1还是P2呢? M为P1与P2的中点。

构造函数:

222.png

对于圆上的点,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。

构造判别式

33333.png

若d<0,应取P1作为下一个像素。再下一个像素的判别式为:

4444.png

所以,沿正右方向,此时d的增量为2xi+3。

而若d>=0,应取P2作为下一个像素,再下一个像素的判别式为:

5555.png

所以,沿右下方向,此时d的增量为2(xi-yi)+5。

由于这里讨论的是按顺时针方向生成第二个八分之一圆,因此,第一个像素是(0, R),判别式d的初始值为

6666.png

代码: 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);
        }
    }
}


运行截图

11111.png


示例:画一个完整的圆

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);
        }
    }
}

运行截图

22222.png

标签: 计算机图形学

Powered by emlog  蜀ICP备18021003号   sitemap

川公网安备 51019002001593号