[School_ĐHMT] Midpoint algorithm to draw the line

December 16, 2014 nguyenvanquan7826 School Computer Graphics Leave a response

Content
Construction algorithm
Read more
1. General Principles of drawing straight lines
2. DDA algorithm to draw the line
3. Algorithm Breshenham draw straight lines

Construction algorithm
Give 2 endpoints M1(x1, y1), and M2(x2, y2). Equation line through M1, M2 form
$\frac{x-x1}{y-y1} = \frac{x2-x1}{y2-y1} \\ \Leftrightarrow \left ( y2-y1 \right )x - \left ( x2-x1 \right )y + x2y1-x1y2 \\ \Leftrightarrow Ax + By + C = 0 \\ Voi \indent A = Dy, B = -Dx, C = x2y1-x1y2$
Midpoint

At step k 1 we performed x is increased by one unit and seek medical calculated according to the integer x. Call S, P respectively the points with coordinates $(x_{k} + 1, y_{k}) , (x_{k} + 1, y_{k} + 1), M(x_{k} + 1, y_{k} + 0.5)$ the midpoint of SP (Point Midpoint), Q is looking. Point $Q(x_{k} + 1, y)$ the value depends on the position of the point Q than point M. If Q is less than M we take the point S $(y = y_{k})$ , take the opposite point P $(y = y_{k} + 1)$ .
Set $F(x, y) = Ax + By + C = 0$ . I have:
Point of M1M2 M <=> F(M) = 0.
M points above the M1M2 <=> F(M) < 0.
Point M lies below M1M2 <=> F(M) > 0.
To determine the location of M we consider the sign of the constant $P_{k} = 2F(M) = 2A(x_{k} + 1) + 2B(y_{k} + 0.5) + 2C$ .
+/ If $P_{k} < 0$ , M overlying M1M2 then Q is below M ie we take the point S $y = y_{k}$
$=> P_{k+1} = 2A(x_{k} + 1) + 2B(y_{k}) + 2C = 2A(x_{k}) + 2B(y_{k}) + 2C + 2A = P_{k} + 2Dy$
+/ If $P_{k} \geq 0$ , M belonging to or under M1M2 then Q is located on M we obtain P News $y = y_{k} + 1$
$\Rightarrow P_{k+1} = 2A(x_{k} + 1) + 2B(y_{k} + 1) + 2C \\ \indent \indent = 2A(x_{k}) + 2B(y_{k}) + 2C + 2A + 2B \\ \indent \indent = P_{k} + 2(Dy - Dx)$
Now we calculate the initial value P1.
$P_{1} = 2A(x_{1} + 1) + 2B(y_{1} + 0.5) + 2C \\ \indent \indent = 2Ax_{1} + 2By_{1} + 2C + 2A + B\\ \indent \indent = 2(Ax + By + C) + 2Dy - Dx \\ \indent \indent = 2Dy - Dx \\ \indent \indent(Ax + By + C = 0)\\$
I noticed Midpoint algorithm for computing with identical results Breshenham algorithm to build a simple but much more.