Bresenham's Line Algorithm

By DaPrimitive Soource -

♣ The Algorithm ::
  1. Compute the initial values:
    2.    dx = x2 - x1 Inc2 = 2(dy - dx)
   dy = y2 - y1 d = Inc1 - dx
   Inc1 = 2dy
  2. Set (x,y) equal to the lower left-hand endpoint and xend equal to the largest value of x. If dx < 0, then x = x2, y = y2, xend = x1. If dx > 0, then x = x1, y = y1, xend = x2.
  3. Plot a point at the current (x,y) coordinates.
  4. Test to see whether the entire line has been drawn. If x = xend, stop.
  5. Compute the location of the next pixel. If d < 0, then d = d + Inc1. If d >e; 0, then d = d + Inc2, and then y = y + 1.
  6. Increment x: x = x + 1.
  7. Plot a point at the current (x,y) coordinates.
  8. Go to step 4.

♣ C / C++ Code ::
void BresenhamsLine(int x1, int y1, int x2, int y2) {
    int dx, dy, Inc1, Inc2, d, x, y, xend; 
 
    dx = x2-x1; 
    dy = y2 - y1; 
    Inc1 = 2*dy; 
    Inc2 = 2*(dy - dx); 
    d = Inc1 - dx; 
 
    if(dx < 0) { x=x2, y=y2, xend=x1; } else 
    if(dx > 0) { x=x1, y=y1, xend=x2; } 
 
    while(x <= xend) { 
        if(d < 0) { d += Inc1; } else 
        if(d >= 0) { d += Inc2, y++; } 
        x++; 
        putpixel(x, y, LIGHTCYAN); 
    } 
}

♣ JAVA Code ::
public class BresenhamsLine extends JPanel { 
 
    private int x1, y1, x2, y2, dx, dy, Inc1, Inc2, d, x, y, xend;
 
    BufferedImage image = new BufferedImage(600, 600, BufferedImage.TYPE_INT_ARGB);  
    WritableRaster raster = image.getRaster(); 
 
    public BresenhamsLine(int x1, int y1, int x2, int y2) { 
        this.x1 = x1; 
        this.y1 = y1; 
        this.x2 = x2; 
        this.y2 = y2; 
    } 
 
    public void paintComponent(Graphics g) { 
        super.paintComponent(g); 
        int color[] = {250, 0, 0, 250}; 
        raster.setPixel(0, 0, color); 
 
        dx = x2 - x1; 
        dy = y2 - y1; 
        Inc1 = 2 * dy; 
        Inc2 = 2 * (dy - dx); 
        d = Inc1 - dx;
 
 
        if (dx < 0) { x = x2; y = y2; xend = x1; } else 
        if (dx > 0) { x = x1; y = y1; xend = x2; } 
 
        while (x <= xend) { 
            if (d < 0) { d += Inc1; } else 
            if (d >= 0) { d += Inc2; y++; } 
            x++;  
            g.drawImage(image, x, y, this); 
        }
    } 
}

♣ Source Codes ::
আবদুল্লাহ বিন ওমার (রাঃ) হতে বর্ণিত। 'রসূলুল্লাহ (সঃ) বলেছেনঃ তোমাদের কেউ নামায পড়লে সে যেন তার দু'কাপড়ে নামায পড়ে। সৌন্দর্য প্রকাশের অগ্রাধিকার আল্লাহর জন্যই।' (তাহাওয়ী, বায়হাকী, তাবরানী)

Popular posts from this blog

C++ :: Topological Sort Algorithm (using DFS)

By DaPrimitive Soource -
Image
A topological sort of a dag G = (V,E) is a linear ordering of all its vertices such that if G contains an edge (u,v), then u appears before v in the ordering. (If the graph contains a cycle, then no linear ordering is possible.) PSEUDOCODE TOPOLOGICAL-SORT(G) call DFS(G) to compute finishing times v.f for each vertex v as each vertex is finished, insert it onto the front of a linked list return the linked list of vertices
Read more

C++ :: Depth-First Search Algorithm (DFS)

By DaPrimitive Soource -
Image
.:: PSEUDOCODE ::. DFS(G) for each vertex u ∈ G.V u.color = WHITE u.π = NIL time = 0 for each vertex u ∈ G.V if u.color == WHITE DFS-VISIT(G,u) DFS-VISIT(G,u) time = time + 1 u.d = time u.color = GRAY for each v ∈ G.Adj[u] if v.color == WHITE v.π = u DFS-VISIT(G,v) u.color = BLACK time = time + 1 u.f = time
Read more

C++ :: Strongly Connected Components Algorithm (SCC)

By DaPrimitive Soource -
Image
Many algorithms that work with directed graphs begin with such a decomposition. After decomposing the graph into strongly connected components, such algorithms run separately on each one and then combine the solutions according to the structure of connections among components. ALGORITHM STRONGLY-CONNECTED-COMPONENTS(G) call DFS(G) to compute finishing times u.f for each vertex u compute GT call DFS(GT), but in the main loop of DFS, consider the verteces in order of decreasing u.f (as computed in line 2) output the vertices of each tree in the depth-first forest formed in line 4 as a separate strongly connected component
Read more