# How does the midpoint line drawing algorithm work?

I'm having trouble understanding the mechanics of the midpoint algorithm. I understand the gist of what it does; it keeps us within a half a pixel of where the actual line should be printed. It does this by updating this $d$ value for each pixel that we traverse.

However, even after drawing some samples and observing what the $d$ value does, I can't figure out the true inner workings of it, and how updating it by these $\Delta_e$ and $\Delta_{ne}$ symbols (which are also a bit of a mystery to me) keeps our pixel placement in check.

Can someone summarize it in simple terms for the good of all humanity?

The Algorithm:

Line (x1, y1, x2, y2)
begin
int x, y, dx, dy, d, deltaE, deltaNE;
x <- x1;        y  <- y1;
dx <- x2 - x1;  dy <- y2 - y1;
d <- 2*dy - dx;
deltaE <- 2*dy;     deltaNE <- 2*(dy - dx);

PlotPixel(x, y);
while ( x < x2) do
if (d < 0) then
begin
d <- d + deltaE;
x <- x + 1;
end;
else begin
d <- d + deltaNE;
x <- x + 1;
y <- y + 1;
end;
PlotPixel (x, y);
end;
end;

• It appears that you copied the algorithm from somewhere else, but you didn't mention the source. StackExchange's policy is that copying of substantial material from other sources requires proper attribution, so I suggest that you attribute the source of the algorithm. Remember, quoting or copying from others always requires suitable attribution of your source. See, e.g., meta.stackexchange.com/q/160077/160917 and meta.stackexchange.com/q/160071/160917. (It is also your responsibility to check whether you have permission to make this available under cc-wiki copyright.) – D.W. Nov 19 '13 at 19:06
• I voted to close as off topic. See help: Questions about how a particular piece of software or hardware works aren't science. – Guy Coder Dec 20 '13 at 0:37
• It's not a question about how a particular piece of software works: it's a well-known, generic algorithm in computer graphics. – David Richerby Dec 20 '13 at 9:22
• I do not understand the close votes. The P.O. is asking for more information on a specific algorithm, which is clearly described. Why should this question be off topic? – J.-E. Pin Dec 26 '13 at 9:55

This is not a self-contained answer, but you can find all the details and pictures in the link below. However, I'll give a summary of the idea behind this algorithm.

Take $F(x,y) = (x-x_1)dy - (y-y_1)dx$ as the line function. Let $p=(x_p,y_p)$ be the last pixel we turned on, then $m=(x_p+1,y_p+0.5)$ is the point exactly between the right and the right-top neighbouring pixels. This is the middle point as the title suggests.

Now, if $F(x_m,y_m) > 0$ then the line is above $m$ and if $F(x_m,y_m) < 0$ then it is below $m$, otherwise the line passes through $m$. In the first case we turn on the pixel above the midpoint (i.e. top-right of $p$), and the pixel bellow $m$ (right of $p$) for the second case, and an arbitrary one for the third case.

$d$ initially is the value of $2.F(x,y)$ for the first midpoint (the reason for doubling it to get an integer and avoid floating point calculations), so $d$ is guiding us which direction (N or NE) we should go next. At each iteration instead of recalculating $d$, depending on our last choice of direction we just need to add $\Delta_{NE}$ or $\Delta_E$ to get the new value for $d$.

http://www.dgp.toronto.edu/~karan/courses/csc418/fall_2002/notes/lines.html

I hope it helps.