This is the first day of my participation in the Gwen Challenge in November. Check out the details: the last Gwen Challenge in 2021

1 the introduction

DDA algorithm and Bresenham algorithm are famous scan conversion algorithms of straight lines. Although the latter is slightly more complicated than the former, it has higher efficiency. This paper will be improved on the basis of Bresenham algorithm, mainly including the following points:

  • Converts all discriminant floating-point types to integers
  • Store all points on the line and then draw it once
  • Outputs the coordinates of all points on the line

2 ideas

The algorithm only considers the slope of the line between 0 and 1, and other slopes can be transformed into the basic case through symmetry.

The core of the midpoint algorithm is to compare the position relationship between the midpoint and the line. If the line is above the midpoint, the point above the midpoint is selected. Instead, take the point below

The general steps of the improved algorithm are as follows:

  1. First draw the starting point

  2. Will represent for the implicit equation, the linear d0 = F (x0 + 1, y0 + 0.5) = 0.5 – kd_ {0} = F \ left (x_ {0} + 1, y_ {0} \ right) + 0.5 = 0.5 kd0 = F (x0 + 1, y0 + 0.5) = 0.5 – k

  3. To convert a floating point type to an integer type, multiply it by 2 δ x2\Delta x2 δ x, that is, d0=2 δ x− δ yd_{0}=2\Delta x-\Delta yd0=2 δ x− δ y (δ x, δ y\Delta x, Delta y δ x, Delta y δ x, Delta y)

  4. Next, determine the symbol of DDD recursively:

    • If d < < 0 0 d d < 0, the (x, y) (x, y) (x, y) update for (x + 1, y + 1) (x + 1, y + 1) (x + 1, y + 1), DDD update for d + 2 Δ x – 2 Δ yd + 2 yd Delta, Delta x – 2, + 2 Δ Δ y x – 2
    • Otherwise (x, y) (x, y) (x, y) update for (x + 1, y) (x + 1, y) (x + 1, y), DDD update for d – 2 Δ yd – 2 \ Delta yd – 2 Δ y

  5. Calculate the discriminant concurrent memory point until the last point is drawn;

3 process

First, find the slope of the line and convert all cases to k>=0&&k<=1

k=(y1-y0)/(x1-x0);
if k>=- 1&&k<0 The % 1 < = k < 0, y axial symmetry
    x0=-x0;
    x1=-x1;
end
if k>1 % k > 1, the exchange of xytemp0=x0; temp1=x1; x0=y0; x1=y1; y0=temp0; y1=temp1;end
if k<- 1 %k<-1temp0=x0; temp1=x1; x0=-y0; x1=-y1; y0=temp0; y1=temp1;end
% is guaranteed to start with a small y coordinate
if y1-y0<0tempX=x0; tempY=y0; x0=x1; y0=y1; x1=tempX; y1=tempY;end
Copy the code

The discriminant is then constructed, first constructing the initial expression, then recursively assigning to the next expression, and looping savepoints

deltaX=x1-x0;
deltaY=y1-y0;
d=deltaX2 -*deltaY; % (0.5 k) * 2 * (x1 - x0)
% save point, exit loop when x>x1
while(x<x1) 
    if d<0 % take the top point
        x(end+1)=x(end) +1;
        y(end+1)=y(end) +1;
        d=d+2*(deltaX-deltaY);
    else % take the lower dot
        x(end+1)=x(end) +1;
        y(end+1)=y(end);
        d=d2 -*deltaY;
    end
end
Copy the code

To obtain each point on the drawn line, the stored coordinates need to be converted back to their corresponding coordinate system.

In short, when we converted the slope of all the lines to 0~1 in the first step, we actually changed the coordinates of the line from the beginning to the end, and now we need to output the correct coordinates, we need to convert them back.

% to the correct coordinates
if k>=- 1&&k<0
    x=-x;
elseif k>1
    temp=x;
    x=y;
    y=temp;
elseif k<- 1
    temp=-x;
    x=y;
    y=temp;
end
Copy the code

Plot (x,y,’r.’) for the last plot;

4 Running Results

Enter several execution statements on the command line to combine different lines to draw custom shapes

See Bresenham(gitee.com) for the full code