Midpoint Line Algorithm

Overview#

The Midpoint Line Algorithm is based on the Bresenham algorithm and is not a general approach, but a solution for screening lines between a slope of 0 and 1 (0 - 45°). If you draw a line in computer graphics, you are limited to the amount of pixel you can use. For example, a simple line could be realized in several different pixel arrangements

Original Representation#

Interpretation#

Another interpretation#

And these are just two of many possible solutions of creating the line.

So, besides the problem that we usually can't solve algorithmic problems graphically, we need a rule that tells us which pixels should be drawn and which not. The midpoint line algorithm does this in two steps:

1. Calculate the mid of two given pixels
2. Evaluate if the line that should be drawn is below or above that mid
   • If the line crosses above the mid the northeast (NE) pixel of the midpoint will be inked
   • if the line crosses below the mid, the east (E) pixel of the midpoint will be inked

As you see in this example, the mid between A (3 | 1) and B (3 | 2) is M (3 | 1.5). And the line we want to draw crosses above this midpoint. Thereby we can ink the pixel north-east of the midpoint.

Mathematical basics#

As you now should understand the problem and the suggested solution, we jump right into the mathematical basics for implementing this algorithm. This section should cover anything new for you; it's merely a reminder and a mutual definition of terms.

Linear function#

Whereas x and y are the corresponding x and y-coordinates in our euclidean grid, m is our slope coefficient, and b our y-intercept.

Slope Coefficient#

Next we need a way to calculate the slope coefficient m we achieve that by:

Whereas Δy describes the y-difference and Δx the x-difference.

Given these basics, we may now determine the linear function for the given example. As we want to draw the line between A (1 | 1) and B (9 | 4), we the following slope coefficient:

This alters our original definition of the linear function:

y-Intercept#

To calculate the y-intercept, we need to rearrange the equation to b and insert any point on the line.

Using the start point (1 | 1) we get b = 5/8:

Which finally, leads us to the linear function of

for our specific example.

Calculating the Midpoint#

To calculate the midpoint of two points in a vertical line in the grid, we take their x value (both points got the same value for x) and calculate the y value by calculating their mean value.

Given these conventions, we may calculate the midpoint of given coordinates A = (x | y) and B = (x | y+1) by:

As the y-difference between these two points always is 1, the formula can further be simplified as:

Determining a Midpoints Relative Position#

All that is left now is to evaluate either a given line crosses above or below the calculated midpoint. To do so, we need the y-difference between the midpoint and the line at specific x-coordinates.

This, in turn, can be achieved by merely calculating the difference between the y-value of the midpoint and the y-value of the line. To ease things further, we take the linear function and rewrite it to the implicit form:

For each point that belongs to our original linear function

This formula will return 0. For each point below our line, the function will return a positive value, and for each point above the line, the function will return a negative value. So we can easily evaluate if a calculated midpoint is:

1. above the line → the line crosses below the midpoint and E will be inked
2. below the line → the line crosses above the midpoint and NE will be inked

By convention, we call the return value of our function f(x,y) the decision parameter d as it decides which pixel will be inked. To make things even clearer we can fill in the values we already know into the abstract function:

xi and yi are specific values, whereas Δx and Δy belong to the original function. So if we test this for a point A = (1, 1) on the line, we get:

Formulate the Algorithm#

Given you understood the mathematical basics, you should now be able to formulate an algorithmic approach to solve the problem of drawing pixels.

To ease things, I will start by defining simple classes that describe points and linear functions in the scope we require.

class Point:

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def get_midpoint(self):
        return Point(self.x, self.y + 0.5)
    
    def __repr__(self):
        return f'({self.x} | {self.y})'

As you can see, I implemented a method get_midpoint() that returns the midpoint of the current coordinates and the same point in which the y-coordinatehas been incremented by 1. And arepr-function that alters the way the object is returned as a string.

class LinearFunction:

    def __init__(self, start: Point, end: Point):
        self.start = start
        self.end = end
        self.delta_y = point_b.y - point_a.y
        self.delta_x = point_b.x - point_a.x
        self.b = self._calculate_b()

    def _calculate_b(self):
        return self.start.y - self.delta_y / self.delta_x * self.start.x

    def point_is_below(self, point: Point):
        return 0 > self.delta_y * point.x - self.delta_x * point.y + self.b * self.delta_x

The LinearFunction class got a pseudo-private method _calculate_b() that calculates the y-intercept. If you read our meaningful names article, you might protest now that calculatey_intercept() might be a better name. And this is indeed a point; the name might be useless to someone defining linear functions with different variable names. However, next, we got a function point is_below() that implements the part from the implicit form of the "Determining a Midpoints Relative Position"-section. It returns True if a given point is below the line that is created by its function. And that's it. That's all we need to run the algorithm. Let's bring all this together with a MidpointLineAlgorithm-class.

class MidpointLineAlgorithm:

    def __init__(self, linear_function: LinearFunction):
        self.linear_function = linear_function

    def run(self):
        points = list()

        iterations = linear_function.delta_x
        y = linear_function.start.y
        x = linear_function.start.x

        for x_i in range(iterations):
            current_point = Point(x + x_i, y)
            current_mid_point = current_point.get_midpoint()

            if linear_function.point_is_below(current_mid_point):
                points.append((current_point, "East"))

            else:
                points.append((current_point, "Northeast"))
                y += 1

        return points

The Algorithm is initialized with a linear function. The number of iterations we need corresponds to the number of steps we can do or simply Δx of our linear function. Additionally, we need a starting point; we simply choose the first point ((1 | 1) in our specific case).

The point of interest is in each step defined by the initial x-value and the current iteration (x + xi), and the current y. Here's the only new thing: each time the algorithm decides we go northeast, we have to increment y as it only increases if we switch lines. So y is determined by the initial y plus the times we went northeast.

The full code for our specific example looks the following:

class Point:

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def get_midpoint(self):
        return Point(self.x, self.y + 0.5)

    def __repr__(self):
        return f'({self.x} | {self.y})'


class LinearFunction:

    def __init__(self, start: Point, end: Point):
        self.start = start
        self.end = end
        self.delta_y = point_b.y - point_a.y
        self.delta_x = point_b.x - point_a.x
        self.b = self._calculate_b()

    def _calculate_b(self):
        return self.start.y - self.delta_y / self.delta_x * self.start.x

    def point_is_below(self, point: Point):
        return 0 > self.delta_y * point.x - self.delta_x * point.y + self.b * self.delta_x


class MidpointLineAlgorithm:

    def __init__(self, linear_function: LinearFunction):
        self.linear_function = linear_function

    def run(self):
        points = list()

        iterations = linear_function.delta_x
        y = linear_function.start.y
        x = linear_function.start.x

        for x_i in range(iterations):
            current_point = Point(x + x_i, y)
            current_mid_point = current_point.get_midpoint()

            if linear_function.point_is_below(current_mid_point):
                points.append((current_point, "East"))

            else:
                points.append((current_point, "Northeast"))
                y += 1

        return points


if __name__ == "__main__":
    point_a = Point(1, 1)
    point_b = Point(9, 4)
    linear_function = LinearFunction(start=point_a, end=point_b)

    midpoint_line_algorithm = MidpointLineAlgorithm(linear_function=linear_function)

    points = midpoint_line_algorithm.run()

    print(points)

If you run the code it will output the following:

[
  ((1 | 1), 'East'),
  ((2 | 1), 'East'),
  ((3 | 1), 'Northeast'),
  ((4 | 2), 'East'),
  ((5 | 2), 'Northeast'),
  ((6 | 3), 'East'),
  ((7 | 3), 'East'),
  ((8 | 3), 'Northeast')
]

Which corresponds to the following picture:

Summary#

I hope you could grasp the functionality of the midpoint line algorithm and understood why and how the mathematical concepts are used to let it work properly. If there is anything left unclear, please don't hesitate to comment, and I will try to come back to you or adjust the post as soon as possible. Happy coding!