[Schooll_ĐHMT] Algorithm Breshenham draw straight lines
Content
1. Construction algorithm
2. Flowchart algorithm
3. Code illustrations
4. Code for all cases
Read more
1. General Principles of drawing straight lines
2. DDA algorithm to draw the line
3. Midpoint algorithm to draw the line
1. Construction algorithm Breshenham
Give 2 endpoints M1 (x1, y1), M2(x2, y2) and paint C.
In all General principles of drawing straight lines we have built a straight line equation of the form:
To simplify the algorithm we consider the line with
At each step one for x increases 1 ie unit 
![m in [0,1] , Dx > 0](http://s0.wp.com/latex.php?latex=m+in+%5B0%2C1%5D+%2C+Dx+%3E+0&bg=ffffff&fg=000&s=0 "m in [0,1] , Dx > 0")
Suppose that at step k we get the following picture:
Call Medical is launching accuracy 
If d1 > Meanwhile d2
If d1 < Meanwhile d2
Therefore, if we identify signs of d1 – d2, then we will know the value of 
Dx > 0 should 
$latex
m = frac{y2-y1}{x2-x1} \\
\Rightarrow p_{to} = (x2-x1)(d1 – d2) \\
\indent indent= (x2-x1).\frac{2(y2-y1)(x_{to}+1) +(x2-x1)(-2y_{to} + 2b – 1)}{x2-x1} \\
\indent indent = 2(y2-y1)x_{to} – 2(x2-x1)y_{to} + 2(y2-y1) + (x2-x1)(2b-1) \\
\indent indent = 2x_{to}Two – 2y_{to}.Dx + c
\\
\Rightarrow p_{k 1} = 2(x_{to}+1)Two – 2y_{k 1}Dx + c, to : \left (c = 2Dy + (2b-1)Dx right ) \\
\\
TH1: P_{to} \geq 0 \Rightarrow d1 geq d2 \\
\indent indent rightarrow y_{k 1} = Y_{to} + 1 \\
\indent indent Rightarrow P_{k 1} = 2(x_{to}+1)Two – 2(y_{to} + 1)Dx + c = P_{to} + 2(Two – Dx) \\
\\
TH2: P_{to} < 0 \Rightarrow d1 < d2 \\
\indent \indent \Rightarrow y_{k+1} = y_{k} \\
\indent \indent \Rightarrow P_{k+1} = 2(x_{k}+1)Dy - 2y_{k}Dx + c = P_{k} + 2Dy \\
$
Tính P1, ta có:
$latex
y1 = m.x1 + b = \frac{Dy}{Dx}x1 + b\\
P_{1} = 2x1.Dy - 2y1.Dx + c
= 2x1.Dy - 2\left ( \frac{Dy}{Dx}x1 + b \right )Dx + 2Dy + (2b - 1)Dx\\
= 2Dy - Dx
$
2. Flowchart algorithm
Bresenham algorithm only on integer operations and calculations on addition and multiplication 2 (allows translation bit). This is a speed improvement increases significantly DDA algorithm. The main idea of this algorithm is that at point P i to the next decision point.
3. Code illustrations
/* Program create in Linux OS
* nguyenvanquan7826
*/
#include <graphics.h>
#define DELAY 10
int color = RED;
void Bresenham(int x1, int y1, int x2, int y2){
int x, y, Dx, Dy, p, c1, c2;
Dx = abs(x2 - x1);
Dy = abs(y2 - y1);
p = 2*Dy - Dx;
c1 = 2*Dy;
c2 = 2*(Dy-Dx);
x = x1;
y = y1;
int x_unit = 1, y_unit = 1;
putpixel(x,y,color);
while(x != x2){
delay(DELAY);
if (p<0) p += c1;
else{
p += c2;
y += y_unit;
}
x += x_unit;
putpixel(x, y, color);
}
}
int main(){
int gd,gm=VGAMAX; gd=DETECT;
initgraph(&gd,&gm,NULL);
setbkcolor(WHITE);
Bresenham(50,150, 300, 200); // ve duong thang
getchar();
return 0;
}
4. Code for all cases
The following code will draw 8 segment under 8 direction, starting from the center point.
/* Program create in Linux OS
* nguyenvanquan7826
*/
#include <graphics.h>
#define DELAY 10
int colorRedBlue = BLUE;
struct point
{
int x, y;
};
void lineBresenham(int x1, int y1, int x2, int y2){
int x, y, Dx, Dy, p, c1, c2;
Dx = abs(x2 - x1);
Dy = abs(y2 - y1);
p = 2*Dy - Dx;
c1 = 2*Dy;
c2 = 2*(Dy-Dx);
x = x1;
y = y1;
int x_unit = 1, y_unit = 1;
if (x2 - x1 < 0)
x_unit = -x_unit;
if (y2 - y1 < 0)
y_unit = -y_unit;
if (x1 == x2) // duong thang dung
{
while (y != y2+1)
{
delay(DELAY);
y += y_unit;
putpixel(x, y, colorRedBlue);
}
}
else if (y1 == y2) // duong ngang
{
while (x != x2+1)
{
delay(DELAY);
x += x_unit;
putpixel(x, y, colorRedBlue);
}
}
else{
putpixel(x, y, colorRedBlue);
while(x != x2){
delay(DELAY);
if (p<0) p += c1;
else{
p += c2;
y += y_unit;
}
x += x_unit;
putpixel(x, y, colorRedBlue);
}
}
}
int main(){
int gd,gm=VGAMAX; gd=DETECT;
initgraph(&gd,&gm,NULL);
setbkcolor(WHITE);
int x = 100, y = 200;
point A[9] = {{getmaxx()/2, getmaxy()/2},
{A[0].x-x, A[0].y-y},
{A[0].x-x, A[0].y+y},
{A[0].x+x, A[0].y+y},
{A[0].x+x, A[0].y-y},
{A[0].x, A[0].y-y},
{A[0].x-x, A[0].y},
{A[0].x, A[0].y+y},
{A[0].x+x, A[0].y},
};
for (int i=1; i<9; i++)
{
lineBresenham(A[0].x, A[0].y, A[i].x, A[i].y);
}
getchar();
return 0;
}
However, due to continuity of care due to rounding and rounding the value that was saved to calculate the line to be drawn by this algorithm is incorrect. We can observe the difference between this algorithm and DDA with the same 1 Contact the line.
A[] = {
{getmaxx()/2, getmaxy()/2},
{A[0].x-x, A[0].y-y},
{A[0].x-x, A[0].y+y},
{A[0].x+x, A[0].y+y},
{A[0].x+x, A[0].y-y},
{A[0].x, A[0].y-y},
{A[0].x-x, A[0].y},
{A[0].x, A[0].y+y},
{A[0].x+x, A[0].y}
}
The blue line is the Breshenham, Pink is the DDA. (DDA more accurate). The horizontal and vertical lines, they fit perfectly together. And here's the code for the algorithm improvements Breshenham.
// Ve duong thang Bresenham Cai tien
void lineBresenham_1(int x1, int y1, int x2, int y2)
{
int c2, c, Dx, Dy, x, y;
Dx = abs(x2 - x1);
Dy = abs(y2 - y1);
c = Dx - Dy;
c2 = 2*c;
x = x1;
y = y1;
int x_unit = 1, y_unit = 1;
if (x2 - x1 < 0)
x_unit = -x_unit;
if (y2 - y1 < 0)
y_unit = -y_unit;
putpixel(x, y, colorGreen);
if (x1 == x2) // duong thang dung
{
while (y != y2)
{
delay(DELAY);
y += y_unit;
putpixel(x, y, colorGreen);
}
}
else if (y1 == y2) // duong ngang
{
while (x != x2)
{
delay(DELAY);
x += x_unit;
putpixel(x, y, colorGreen);
}
}
else if (x1 != x2 && y1 != y2) // duong xien
{
while(x != x2+1)
{
delay(DELAY);
c2 =2*c;
if (c2 > -Dy)
{
c = c - Dy;
x = x + x_unit;
}
if (c2 < Dx)
{
c = c + Dx;
y = y + y_unit;
}
putpixel(x, y, colorGreen);
}
}
}
When you run this code than the DDA they completely coincide
He asked that the m e>1 the algorithm will be described bresenham how ạ
You see the code for all cases nhé.
I'm looking for the right place. Detailed instructions and easy to understand too. Thank you very much
The algorithm can be applied to the control 2 head moves motor working under 1 Your right lines. But I still do not understand how a pulse output according to this algorithm ? Hope you help her in this case !
What this algorithm is to draw a straight line. You say, I bear to export pulses, blind can not help you then.
a to e ask why put c = Dx – Two; and algorithm then understood how
else if (x1 != x2 && y1 != y2) // biasing
{
while(x != x2+1)
{
delay(DELAY);
c2 = 2 * c;
if (c2 > -Two)
{
c = c – Two;
x = x + x_unit;
}
if (c2 < Dx)
{
c = c + Dx;
y = y + y_unit;
}
putpixel(x, and, colorGreen);
}
}
This is the code has been transferred from construction algorithm. You review the algorithms offline.
Improved algorithm of its ideas how?
Its ideology is not round anymore, but based on the number of diagonal ratio to go to the right direction.
#include
#include
#include
#define c CYAN
int breseham (int x1, int y1, int x2, int y2){
int dx = abs (x2 – x1);
int dy = abs (y2 – y1);
int x_unit = 1, y_unit =1;
if (x2-x1 <0)
x_unit = -x_unit;
if (y2-y1 <0)
y_unit = -y_unit;
if (dx==0 && two!=0){
for (int i=0; in<= two; i ){
putpixel (x1, y1, c);
y1+= y_unit;
}
}
else if (two == 0 && dx!=0){
for (int j = 0; j=dy){
int p= 2*dy-dx;
int c1 = 2*dy, c2 = 2*dy – 2*dx;
while (x1!=x2){
if (p<0)
p + = c1;
else{
y1+= y_unit;
p + = c2;
}
putpixel (x1, y1, c);
x1 +=x_unit;
}
}
else {
int p=2*dx-dy;
int c1 = 2 * dx, c2 = 2 * dx – 2*two;
while (x1!=x2){
if (p<0)
p + = c1;
else {
x1+=x_unit;
p + = c2;
}
putpixel (x1, y1, c);
y1+=y_unit;
}
}
}
}
int main (){
int x1, y1, x2, y2;
printf ("nhap toa do diem A(x1, y1), B(x2, y2)");
printf ("\n x1= "); scanf ("% D",&x1);
printf ("\n y1= "); scanf ("% D",&y1);
printf ("\n x2= "); scanf ("% D",&x2);
printf ("\n y2= "); scanf ("% D",&y2);
initwindow (400,400);
breseham(x1, y1, x2, y2);
getch();
}
he asked me that declaration correctly
This code line int gd,gm=VGAMAX; gd=DETECT; What he used to do?
Initialize the initial value for the graphics mode nhé.
Improved algorithms have dental problems you because:
x1 = x2 + 1, then the code will draw the wrong
dx=1,2,3.. dx ie the smaller the error code also painted his dentist.
Thank you, I will review ^^
The statements that initialize the graphical display with the size depending on the size of the screen that do not need to set the value for it is not right