• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar
  • Skip to footer
Code Specialist

Code Specialist

Code and Programming Blog

  • Home
  • Clean Code
  • Code Principles
  • Code Interview
  • 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.

Home » Algorithms » Midpoint Line Algorithm

December 1, 2020 by Yannic Schröer Leave a Comment

Contents hide
1 Overview
2 Mathematical basics
2.1 Linear function
2.2 Slope Coefficient
2.3 y-Intercept
2.4 Calculating the Midpoint
2.5 Determining a Midpoints Relative Position
3 Formulate the Algorithm
4 Summary
4.1 Our Book Recommendations on Python (Affiliate)

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
  • Pixel interpretation 1
  • Pixel interpretation 2

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
Midpoint Line Algorithm example

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 east of 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

f(x) = y=mx+b

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:

m=\frac{\Delta y}{ \Delta x}

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:

m = \frac{4-1}{9-1}=\frac{3}{8}

This alters our original definition of the linear function:

f(x) = y=\frac{\Delta y}{ \Delta x}x+b

y-Intercept

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

y =mx+b
b=y-mx

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

b=1-\frac{3}{8}*1 = \frac{5}{8}

Which finally, leads us to the linear function of

f(x) =\frac{3}{8}*x+\frac{5}{8}

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:

F(M) = ( x_{A} | \frac{y_{A}+y_B}{2} )

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

F(M) = ( x_{A} | \frac{y_{A}+y_B}{2} )  = ( x_{A} | y_{A}+\frac{1}{2} ) 

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:

f(x, y) = \Delta y*x - \Delta x * y + b*\Delta x

For each point that belongs to our original linear function

f(x) =\frac{3}{8}*x+\frac{5}{8}

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:

\Delta x = 8 \\
\Delta y = 3\\
b=\frac{5}{8}
f(x_i, y_i) = 3x_i - 8y_i + \frac{5}{8}*8 = f(x_i, y_i) = 3x_i - 8y_i + 5

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:

f(1, 1) = 3*1 - 8*1 + 5 = 0

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.

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.

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.

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:

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:

Midpoint line algorithm in action

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!

Click to rate this post
[Total: 7 Average: 4.9]
Yannic Schröer

I am a developer and entrepreneur from Germany. I chose studying computer science because I love building things. I am of the opinion that there isn’t one truth (especially for computer science concepts) and whoever claims so isn’t that trustworthy in my eyes. I constantly try to improve things and myself. In my spare time I support businesses by offering them most of my services for free. Beside that I am kind of addict to e-learning courses.

Our Book Recommendations on Python (Affiliate)

Category iconAlgorithms,  Python Tag iconComputer Graphics

Related Posts

grey metal marching cubes
Marching Cubes Algorithm
5 (3)
December 5, 2020
Decorators in Python
5 (1)
February 23, 2021
New Syntax Features in Python 3.9
5 (3)
February 12, 2021

Reader Interactions

Leave a Reply Cancel reply

Your email address will not be published.

Primary Sidebar

Search

Categories

  • Algorithms
  • Code Interview
  • Code Principles
  • Environment
  • Errors
  • Hardware
  • Learn to Code
  • Nice to know
  • Object Orientation
  • Python
  • Technical Background
  • Write Better Code

Tags

Alternative (1) Announcement (1) Clean Code (6) Code (1) Code Interview Question (2) Code Philosophy (1) Comments (1) Computer Graphics (2) Concurrency (1) Control Characters (1) Data Science (1) Data Structures (1) decorators (2) dictionaries (3) Easter Eggs (1) funny (1) Github Actions (1) Marching Cubes (1) Meshing (1) Nice to know (1) Parallelisation (1) Programming Facts (1) Pythonic (3) PyYAML (1) Readability (4) Simple is good (2) Software Engineering (2) switch (1) Syntax (1) Tricks (1) type hints (1) Ubuntu 20.04 (1) Underscores (1) Unix (1) Video (1) Virtualization with Windows (1)

Footer

Recent Posts

  • 5 Hardware Ideas to Upgrade your Programming Experience
  • 5 Programming facts every programmer must know
  • Decorators in Python
  • New Syntax Features in Python 3.9
  • 5 Ways to Speed Up Python Code

Tags

Alternative Announcement Clean Code Code Code Interview Question Code Philosophy Comments Computer Graphics Concurrency Control Characters Data Science Data Structures decorators dictionaries Easter Eggs funny Github Actions Marching Cubes Meshing Nice to know Parallelisation Programming Facts Pythonic PyYAML Readability Simple is good Software Engineering switch Syntax Tricks type hints Ubuntu 20.04 Underscores Unix Video Virtualization with Windows

Categories

  • Algorithms
  • Code Interview
  • Code Principles
  • Environment
  • Errors
  • Hardware
  • Learn to Code
  • Nice to know
  • Object Orientation
  • Python
  • Technical Background
  • Write Better Code

Recent Comments

  • Nina on Bubble Sort in Python and how to Visualize it
  • Bhan on Concurrency in Python

Follow Us

  • Facebook
  • Instagram
  • Pinterest
  • Twitter

Quicklinks

  • About us
  • Become a writer

Privacy Policy | Legal Notice | Contact

 

All rights reserved © 2020-2021 code-specialist.com