A Line

$$$APPLET

Applet Line between points (x1,y1) and (x2,y2)

    A line is one of basic computer elements. While in analytical geometry basic points of a line are included in the line, on a screen a line stacks from end points. Nevertheless, it is relatively simple, its frame is mostly given by a command remark. Composite graphic objects are mostly composed of lines, and for all those it is our tendency to draw a line with the highest effectivity.

    A line is usually defined by its end points [x1,y1] and [x2,y2], eventually by one point only [x1,y1], and by a vector of distinction of the co-ordinates [dx, dy] = [x2-x1, y2-y1].

    An analytical expression of a line that is not parallel with the axis y, is expressed as

    y = m x + q  (m, q∈ R)

where m is slope of the line and q is displacement on the axis y. End points of a line determine a line with parameters m and q:

            (y2-y1)                       (x2*y1-x1*y2)
m =  ----------    and         q =  ----------------
     (x2-x1)                            (x2-x1)

Scan Converting Lines

Raster decomposition of a line is based on sampling with an invariable step according to the axis x, alternatively y. It depends on the inclination of the line, which is represented by the slope m.

$$$APPLET

Applet Value slope m for different the inclination of the line.

    If |m|<1, then the line's inclination to axis x is smaller than 45 grades, therefore the line is patterned according to axis x with a step of 1 pixel. If  |m|>1, then it is patterned according to axis y. A line with slope 1 is called diagonal and it is patterned by any axis. The axis according to which it is patterned is called operative (main) axis. The name of second axis is incident axis.

The Basic Incremental Algorithm

    Simple incremental algorithm is well-known also look like DDA (Digital Differential Analyzer) algorithm. The pricnip of this algorithm is based on periodical increase dx for co-ordinate x and also dy for co-ordinate y. Start point is one from end point a line. Because we pattern in raster, increase on directional axis will be  (providing, if line be inclined to axis x is directional axis x) right one dot.

$$$APPLET

Applet Increase for value x and y.

    Method is following. In one loop we shall step by step add to co-ordinate on a main axis value 1 and to co-ordinate on incident axis add increase. If axis x is main, value slope equal m.If axis y then value slope equal 1/m. Real number co-ordinates of the displayed objects must be rounded off. DDA algorithm used to calculations new co-ordinate values before dot.

$$$APPLET

Applet Dwawing a line from left top dot. Please select second end dot. Key 1,2 for zooming.


  The Basic Incremental Algorithm [4]. 

// drawing a line from starting point x1,y1 to ending point x2,y2

 rasterline(int x1, int y1, int x2, int y2)
 {

     // if point x1, y1 is rightmost point from point x2,y2 then replace it
     if (x1 > x2) { rasterline(x2, y2, x1, y1); return; } 

     double y = y1;                                          // increment
     double m = (double)(y2 - y1) / (x2 - x1);  // slope

     //  if m < 45 degrees to axis x then main axis is axis x
     if (Math.abs(m) <= 1) 
      { 
         for (int i = x1; i <= x2; i++) 
          {
             setpix(i, (int) Math.round(y) ); 
             y += m;  
          }
       }
      else        {  
          rastersteepline(yi, xi, yf, xf); 
       }
 }

public void rastersteepline(int x3, int y3, int x4, int y4) 
  {

    // if point x3, y3 is on the right of point x4,y4, change them
     if (x3 > x4) { rastersteepline(x4, y4, x3, y3); return; }

     double y = y3;                                          // increment
     double m = (double)(y4 - y3) / (x4 - x3);  // slope

     for (int i = x3; i <= x4; i++) 
      { 
         setpix( (int) Math.round(y), i);
         y += m;
      }
  }

Bresenham algorithm for a line

    In DDA algorithm we usage real number, which we are then round. In next algorithm we will use only an integral operation.

$$$APPLET

Applet Bresenham algorithm for a line. Interaction : select end dot, key 1,2 for zooming.

    Advance are point at applet, in which is representation element screen, bunk displayed pixle lines with directional axis x. Advance from left endpoint
lines (dot and) and own designate, if next dot lines with coordinate xi+1 own own equal co-ordinate y (tj, yi), alternatively coordinate y at one biggies (tj. yi+1). Other said whether another dot lines will be dot B otherwise C. Responsibilities algorithm is designate, which value y own choose, in order to myself approach right y-coordinate lines.

$$$APPLET

Bresenham algorithm for a line  interactivity: select starting point of a line and moving  with mouse transfer ending points.


 

Bresenham algorithm for a line[4].

// draw a line from point x1,y1 into x2,y2
public void bresenham_line(int x1, int y1, int x2, int y2) 
 { 

     // if point x1, y1 is on the right side of point x2, y2, change them
     if ((x1 - x2) > 0) {bresenham_line(x2, y2, x1, y1); return;}

     // test inclination of line
     // function Math.abs(y) defines absolute value y
     if (Math.abs(y2 - y1) > Math.abs(x2 - x1)) 
       {
          // line and y axis angle is less then 45 degrees
          // that swhy go on the next procedure
          bresteepline(y1, x1, y2, x2); return; 
        }
     // line  and x axis angle is less then 45 degrees, so x is guiding

     // auxiliary variables
     int x = x1, y = y1, sum = x2 - x1,  Dx = 2 * (x2 - x1), Dy = Math.abs(2 * (y2 - y1));
     int prirastokDy = ((y2 - y1) > 0) ? 1 : -1;

     // draw line
     for (int i = 0; i <= x2 -x1; i++) 
      {
         setpix(x, y);
         x++;
         sum -= Dy;
         if (sum < 0) {y = y + prirastokDy; sum += Dx;}
     }
 }

public void bresteepline(int x3, int y3, int x4, int y4) 
 {
     // if point x3, y3 is on the right side of point x4, y4, change them
     if ((x3 - x4) > 0) {bresteepline(x4, y4, x3, y3); return;}

     int x = x3, y = y3, sum = x4 - x3,   Dx = 2 * (x4 - x3), Dy = Math.abs(2 * (y4 - y3));
     int prirastokDy = ((y4 - y3) > 0) ? 1 : -1;

     for (int i = 0; i <= x4 -x3; i++) 
      {
         setpix(y, x);
         x++;
          sum -= Dy;
         if (sum < 0) {y = y + prirastokDy; sum += Dx;}
      }
 }