返回顶部

收藏

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

标签:C++,两点画直线

收藏

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++)
  9. mortoray 发表 2013-06-03 04:25:59 Overloading the broken universal reference ‘T&&’
  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 函数指针总结

发表评论