椭圆填充算法（走阶梯法）
算法说明：.如图所示，路线是沿绿色虚线走，从（x0,y0）点开始走阶梯，先向左走，碰到弧线记住该点后，接着往下走然后继续向左走，阶梯的高度为step ，每走完一个阶梯就会找到一个边界点。Step越小，记住的边界点会越多。走到(xn,yn)点后完成走阶梯任务，也就得到了椭圆的左边的边界点，然后用对称算法，获取右边的边界点。一但边界点计算完成，填充就很容易实现了。
算法分析：碰到弧线的条件是 x^2/a^2 + y^2/b^2 = 1,走阶梯算法优点是不会全区域扫描，只会走很小的区域很短的路径，因此速度很快。本算法的关键是走到下半部份时，如何往右走多少路程？其实下部绿色虚线不并不是真的路径。之所以这样图示，是为了对本算法的理解。为沿用上部份处理代码，在碰到下部分第一个圆弧上的点时先往下走出椭圆，然后从椭圆的外部移回到椭圆内部，然后往左走，移回的距离准确性很关键，否则移不到圆内，这种情况下，就会出现丢点。移回的距离的计算方法是当前点的x坐标到Y轴的距离的一半，快接近下部顶时，索性直接移回到Ｙ轴上。
代码如下：
//define the origin point offset， rect为椭圆的外边框。
int noffsetX = rect.left +rect.Width()/2;
int noffsetY = rect.top +rect.Height()/2;
//transform to standard ellipse;
//为了使椭圆的标准方程，有必要把圆心转换成到（0，0）位置
CRect rtEsc(rect);
rtEsc.OffsetRect(-rect.left, -rect.top);
rtEsc.OffsetRect(-rect.Width()/2,-rect.Height()/2);
CPoint c = CPoint((rtEsc.left +rtEsc.right) / 2, (rtEsc.top +rtEsc.bottom) / 2);
CPoint c0 = CPoint((rect.left +rect.right) / 2, (rect.top +rect.bottom) / 2);
int da = rtEsc.Width() /2;
int db = rtEsc.Height()/ 2;
int x,y;
x = c.x;
y = c.y - db +nDist;
//find out the dots on the line of ellipse ;
//nstep为阶楼高度，进阶度。
int nstep = nDist;
CPoint* m_pt = new CPoint[ ((2*db) /nstep) + 1];
CPoint* m_pt1 = new CPoint[ ((2*db) /nstep) +1]; //
//控制点数
for (inti= 0;i< 2*db/nstep+1 ;i++)
{
int x0 = -1;
int y0 = -1;
//控制椭圆边界
for(intj = x ; j >= rtEsc.left ;j--)
{
x0 = j;
y0 = y;
double nData = (double)(x0*x0)/(double)(da*da) + (double)(y0*y0)/(double)(db*db);
//实数、浮点数 与1.的比较
if (nData >=0.99999)
{
//calculate II记住左边点
m_pt[i].x =x0 + noffsetX;
m_pt[i].y =y0 + noffsetY;
//calculate I对称算法计算右边点
m_pt1[i].x = (m_pt[i].x + (c0.x - m_pt[i].x)*2 )-1;
m_pt1[i].y =m_pt[i].y;
break;
}
}
y += nstep;
if ( y < c.y)
x = x0;
else
{
if (y >rtEsc.bottom -30)
x =x0 + (c.x -x0)/2;
else
x =x0 + (c.x -x0);
}
}
// 根据边界点 对随圆画线填充 Bord 为边矩
for (inti= 0; i< 2*db/nstep;i++)
{
if (rect.bottom -m_pt1[i].y >Bord )
{
m_pDC->MoveTo(m_pt[i].x,m_pt[i].y);
m_pDC->LineTo(m_pt1[i].x ,m_pt1[i].y);
}
}
delete []m_pt;
delete []m_pt1;
随圆的填充算法-----走阶梯法,布布扣,bubuko.com
原文：http://blog.csdn.net/song_0962/article/details/22982899
