# C++ 在两点之间画一条直线

```/**
* Draws a line between two points p1(p1x,p1y) and p2(p2x,p2y).
* This function is based on the Bresenham's line algorithm and is highly
* optimized to be able to draw lines very quickly. There is no floating point
* arithmetic nor multiplications and divisions involved. Only addition,
* subtraction and bit shifting are used.
*
* Note that you have to define your own customized setPixel(x,y) function,
* which essentially lights a pixel on the screen.
*/
void lineBresenham(int p1x, int p1y, int p2x, int p2y)
{
int F, x, y;

if (p1x > p2x)  // Swap points if p1 is on the right of p2
{
swap(p1x, p2x);
swap(p1y, p2y);
}

// Handle trivial cases separately for algorithm speed up.
// Trivial case 1: m = +/-INF (Vertical line)
if (p1x == p2x)
{
if (p1y > p2y)  // Swap y-coordinates if p1 is above p2
{
swap(p1y, p2y);
}

x = p1x;
y = p1y;
while (y <= p2y)
{
setPixel(x, y);
y++;
}
return;
}
// Trivial case 2: m = 0 (Horizontal line)
else if (p1y == p2y)
{
x = p1x;
y = p1y;

while (x <= p2x)
{
setPixel(x, y);
x++;
}
return;
}

int dy            = p2y - p1y;  // y-increment from p1 to p2
int dx            = p2x - p1x;  // x-increment from p1 to p2
int dy2           = (dy << 1);  // dy << 1 == 2*dy
int dx2           = (dx << 1);
int dy2_minus_dx2 = dy2 - dx2;  // precompute constant for speed up
int dy2_plus_dx2  = dy2 + dx2;

if (dy >= 0)    // m >= 0
{
// Case 1: 0 <= m <= 1 (Original case)
if (dy <= dx)
{
F = dy2 - dx;    // initial F

x = p1x;
y = p1y;
while (x <= p2x)
{
setPixel(x, y);
if (F <= 0)
{
F += dy2;
}
else
{
y++;
F += dy2_minus_dx2;
}
x++;
}
}
// Case 2: 1 < m < INF (Mirror about y=x line
// replace all dy by dx and dx by dy)
else
{
F = dx2 - dy;    // initial F

y = p1y;
x = p1x;
while (y <= p2y)
{
setPixel(x, y);
if (F <= 0)
{
F += dx2;
}
else
{
x++;
F -= dy2_minus_dx2;
}
y++;
}
}
}
else    // m < 0
{
// Case 3: -1 <= m < 0 (Mirror about x-axis, replace all dy by -dy)
if (dx >= -dy)
{
F = -dy2 - dx;    // initial F

x = p1x;
y = p1y;
while (x <= p2x)
{
setPixel(x, y);
if (F <= 0)
{
F -= dy2;
}
else
{
y--;
F -= dy2_plus_dx2;
}
x++;
}
}
// Case 4: -INF < m < -1 (Mirror about x-axis and mirror
// about y=x line, replace all dx by -dy and dy by dx)
else
{
F = dx2 + dy;    // initial F

y = p1y;
x = p1x;
while (y >= p2y)
{
setPixel(x, y);
if (F <= 0)
{
F += dx2;
}
else
{
x++;
F += dy2_plus_dx2;
}
y--;
}
}
}
}

/* 用法 */
// Snippet of a sample program in OpenGL

void setPixel(int px, int py)
{
glBegin(GL_POINTS);
glVertex2i(px, py);
glEnd();
}

void display()
{
glClear(GL_COLOR_BUFFER_BIT);

// Draws a line from (100,100) to (400,300).
lineBresenham(100, 100, 400, 300);

glFlush();
}
```

0人收藏

0

0

1. Qiang 发表 2011-09-08 14:06:35 Lexing Python Indentation using Spirit.Lex
2. 霜天 发表 2013-03-22 03:58:33 分享两个强符号，弱符号引起的编译问题
3. Herb Sutter 发表 2012-04-30 21:36:26 C++ and Beyond Panel: Modern C++ = Clean, Safe, an
4. Herb Sutter 发表 2012-09-01 00:43:58 Reader Q&A: How to write a CAS loop using std::ato
5. Herb Sutter 发表 2013-01-01 17:34:09 Video: You Don’t Know const and mutable
6. Sana Mithani 发表 2013-02-26 20:32:00 The C++ REST SDK ("Casablanca")
7. bystander 发表 2013-04-11 00:45:38 并查集(C++实现)
8. bystander 发表 2013-05-22 08:16:24 引用和指针(C++)
10. Jim Hogg 发表 2013-07-04 20:00:00 Optimizing C++ Code : Constant-Folding
11. Todd 发表 2013-08-09 02:18:31 数据即代码：元驱动编程
12. wuyuan 发表 2013-09-21 10:47:46 函数指针总结