After grasping the fundamentals behind simple line drawing, I thought why not share the knowledge with the world. The result is this article. By writing this article, I myself am ensuring that I have got a good grasp on the algorithm. OK ! Enough of this introduction work. Let's get down to some work.
What we require is to draw a line on the screen when we have been provided with the endpoints. Lets say, the endpoints provided to us are not integers but fractions ! (oh my god). What we have to do is to draw a line segment that has the two given points as its endpoints.
Before developing the algorithm let us first understand the problems we face. (Had there been no problems why would you be reading this ?). A line is a continuous object. However, the computer monitor (screen) consists of a matrix of pixels. So then, how do we represent the continuous object on this discrete matrix. To understand the solution consider a staircase. (ah ! the name itself is enough). When a staircase is built, the requirement is to travel along a line. Now if we put up a slide from the starting point to endpoint can you imagine going up or down with ease. Of course NOT. To circumvent this problem, a staircase is built. It consists of discrete steps following which you reach the endpoint with ease. After moving some distance forward, you rise upwards and continue this sequence in discrete steps. The same approach has been used for drawing a line on the screen. So, keep in mind the wonderful staircase while we develop the mathematical approach to make a line.
Ok, so lets get down to some mathematics. A line can be represented by the equation:
y = m * x + b;
where 'y' and 'x' are the co-ordinates; 'm' is the slope i.e. a quantity which indicates how much 'y' increases when 'x' increases by one unit. 'b' is the intercept of line on 'y' axis (However we can safely ignore it for now).
So what's the trick behind the equation. Would you believe it, we already have the algorithm developed ! Pay close attention to the definition of 'm'. It states A quantity that indicates by how much 'y' changes when 'x' changes by one unit. So, instead of determining 'y' for every value of 'x' we will let 'x' have certain discrete values and determine 'y' for those values. Moreover since we have the quantity 'm'; we will increase 'x' by one and add 'm' to 'y' each time. This way we can easily plot the line. The only thing we are left with now, is the actual calculations.
Let us say we have two endpoints (xa,ya) and (xb,yb). Let us further assume that (xb-xa) is greater than (yb-ya) in magnitude and that (xa < xb). This means we will move from (xa) to the right towards (xb) finding 'y' at each point. The first thing however that we need to do is to find the slope 'm'. This can be done using the formulae:
m = (yb - ya) / (xb - xa)
Now we can follow the following algorithm to draw our line.
- Let R represent the row and C the column
- Set C = Round(xa)
- Let F = Round(xb)
- Let H = ya
- Find the slope m
- Set R = Round(H)
- Plot the point at R,C on the screen
- Increment C {C+1}
- If C <= F continue else goto step (12)
- Add m to H
- Goto step (6)
- STOP
I hope the algorithm has made things quite clear. You must note here that the algorithm presented above is not an efficient way to draw lines but then it is an algorithm that is quite easy to grasp (I hope) than the efficient algorithms.
Disclaimer: The above written article is an original work by the author Amod Karve.