python

# Midpoint Line Algorithm

The midpoint line algorithm is a drawing algorithm in the field of computer graphics. It is used to determine how lines are translated into pixels.

## 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:

- Calculate the mid of two given pixels
- 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:

- above the line → the line crosses below the midpoint and
`E`

will be inked - 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 = xself.y = ydef 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-coordinate`

has been incremented by `1`

. And a`repr-function`

that alters the way the object is
returned as a string.

class LinearFunction:def __init__(self, start: Point, end: Point):self.start = startself.end = endself.delta_y = point_b.y - point_a.yself.delta_x = point_b.x - point_a.xself.b = self._calculate_b()def _calculate_b(self):return self.start.y - self.delta_y / self.delta_x * self.start.xdef 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 calculate`y_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_functiondef run(self):points = list()iterations = linear_function.delta_xy = linear_function.start.yx = linear_function.start.xfor 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 += 1return 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 = xself.y = ydef 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 = startself.end = endself.delta_y = point_b.y - point_a.yself.delta_x = point_b.x - point_a.xself.b = self._calculate_b()def _calculate_b(self):return self.start.y - self.delta_y / self.delta_x * self.start.xdef point_is_below(self, point: Point):return 0 > self.delta_y * point.x - self.delta_x * point.y + self.b * self.delta_xclass MidpointLineAlgorithm:def __init__(self, linear_function: LinearFunction):self.linear_function = linear_functiondef run(self):points = list()iterations = linear_function.delta_xy = linear_function.start.yx = linear_function.start.xfor 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 += 1return pointsif __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!