如何才能算是最优的画线算法，各位大佬，你们是如何优化画线算法的！

Question

昨天面试时，让我写一个画线算法，我大喜，以为找着便宜了，没有十几分钟，就把画线算法写出来了，还洋洋得意，结果另人把我的代码一看，说我的程序肯定速　度慢，另外，又用vc自带的放大镜一看，说我直线中有些点的位置不对。我还自称精通图形学，太丢人了，请问各位老大，你们是如何优化画线算法的，　请给一段优秀的在光栅上画直线的算法给我学习学习。真想见一见传说中的最优画线算法，不知CDC中的LineTo是如何实现的。请各位高手成全小弟！

Answer 1

CDC中的LineTO算法我也不知道，有没有那位老况知道呀，其实画线算法中有很多学问，确实可以看出一个人的编程功力，先不说反走样了，就是做到高效精确的画线就不容易。每本　图形学的书都有介绍，但都介绍的不很清楚，只是说一说原理，进一步的了解只有靠长期　知识的积累了！　哈

Answer 2

就是图形学上的Bresenhan算法, 有什么不妥?
template<class Fun>
void
DrawLine(long x0, // start point
long y0,
long x1, // end point
long y1,
Fun &fu
)
{
long dx, dy;
long dxSign, dySign;
dxSign = (x1 > x0) ? 1 : ( (x1 == x0) ? 0 : -1 );//dxSign = 1, 0 , -1
dySign = (y1 > y0) ? 1 : ( (y1 == y0) ? 0 : -1 );
dx = abs(x1 - x0);
dy = abs(y1 - y0);

long x, y;
x = x0;
y = y0; bool bExchange = false;
if( dy > dx )
{
bExchange = true;
std::swap(dx, dy);
} long p;
p = dy * 2 - dx; 

long i;
for( i = 0; i <= dx; i++ )
{
if( !fu(x,y) )
{//over.
return;
}

if( p >= 0 )
{
x += dxSign;
y += dySign; p = p + (dy - dx)  * 2; // p = p - 2 * dx;
}
else{
if( bExchange )
{
y += dySign;
}
else{
x += dxSign;
}
p = p + dy * 2;// p = p + 2 * dx;
}
}
} //draw line.

Answer 3

我来评点一下楼上兄弟推荐的这个算法：见笑了。template<class Fun>
void
DrawLine(long x0, // start point//？为什么用long 型,字长的四倍速度较快，int 也是字长的四倍
long y0,
long x1, // end point
long y1,
Fun &fu
)
{
long dx, dy;
long dxSign, dySign;
dxSign = (x1 > x0) ? 1 : ( (x1 == x0) ? 0 : -1 );//dxSign = 1, 0 , -1
dySign = (y1 > y0) ? 1 : ( (y1 == y0) ? 0 : -1 );
dx = abs(x1 - x0);　　　//改成上两行的方式较好，或写成inline
dy = abs(y1 - y0);　　　　//同上

long x, y;
x = x0;
y = y0; bool bExchange = false;
if( dy > dx )
{
bExchange = true;
std::swap(dx, dy);
} long p;
p = dy * 2 - dx; 

long i;
for( i = 0; i <= dx; i++ )
{
if( !fu(x,y) )
{//over.
return;
}

if( p >= 0 )
{
x += dxSign;
y += dySign; p = p + (dy - dx)  * 2; // p = p - 2 * dx;//为什　么用移位运算
}
else{
if( bExchange )
{
y += dySign;
}
else{
x += dxSign;
}
p = p + dy * 2;// p = p + 2 * dx;
}
}
} //draw line.
说得不　对，请不要笑我，哈哈！

Answer 4

这个问题太难了，除非天天写这个，否则谁能默写出Bresenham算法