Matplotlib has functionality to created animations and can be used to create dynamic visualizations. In this post, I will explain the concepts and techniques for creating animated charts using Python and Matplotlib.
I find this technique very helpful in creating animations showing how certain algorithms work. This post also contains Python implementations of two common geometry simplification algorithms and they will used to create animations showing each step of the algorithm. Since both of these implementations use a recursive function, the technique shown in the post can be extended to visualize other recursive functions using matplotlib. You will learn how to create animated plots like below.
The complete notebook containing the code and explanation can be accessed from here.
Animation Basics
The matplotlib.animation module provides a FuncAnimation class to create animated plots. This allows you to make an animation by repeatedly calling a function and saving the output as a frame in the animation.
Before we dive into more complex example. it is helpful to understand the basics of matplotlib animation. Let’s define 3 positions and we will create an animation of a point moving between them.
points = [(0.1, 0.5), (0.5, 0.5), (0.9, 0.5)]
We need to define a function that takes the frame number and generates a plot from it. Here we define a function animation that takes the frame index and creates a plot from the point at the same index in the points list. So at frame 0, it will display the first point, frame 1 the second point and so on.
%matplotlib inline
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
fig, ax = plt.subplots(1, 1)
fig.set_size_inches(5,5)
def animate(i):
ax.clear()
# Get the point from the points list at index i
point = points[i]
# Plot that point using the x and y coordinates
ax.plot(point[0], point[1], color='green',
label='original', marker='o')
# Set the x and y axis to display a fixed range
ax.set_xlim([0, 1])
ax.set_ylim([0, 1])
ani = FuncAnimation(fig, animate, frames=len(points),
interval=500, repeat=False)
plt.close()
The animation is now contained in the ani object. We can call save() and save the result as an animated GIF. We need to specify a writer that supports the output format.
from matplotlib.animation import PillowWriter
# Save the animation as an animated GIF
ani.save("simple_animation.gif", dpi=300,
writer=PillowWriter(fps=1))
Animating Plots
Now that you understand the basics, it’s time to apply this technique to animate plots. I will show 2 different approaches for animating matplotlib plots. I find it very helpful in visualizing iterative algorithms. We will take examples of two popular geometry simplification algorithms and visualize how they work.
- Visvalingam and Whyatt algorithm
- Douglas-Peucker algorithm
Note:
The implementations for both Visvalingam and Whyatt and Douglas-Peucker algorithms in the post are not necessarily the fastest or the most optimized. They are meant for educational purposes and therefore are written in a way that is easy to understand.
Let’s take a line segment defined by a list of (x,y) coordinates as below.
point_list = [(0,3), (1,0), (2,1), (3, 2), (5, 3),
(7,4), (8,4), (10,3), (11,1), (12,1),
(15,2), (17, 3), (18, 3), (20, 2)]
We will use the shapely library to create a LineString object and plot it.
import matplotlib.pyplot as plt
from shapely.geometry import LineString
original = LineString(point_list)
fig, ax = plt.subplots(1, 1)
fig.set_size_inches(20,5)
ax.plot(*original.xy, color='red',
label='input', marker='o')
ax.set_title('Original Line Segment', fontsize=20)
ax.legend()
plt.savefig('line.png', bbox_inches='tight', dpi=300)
plt.show()
Visualizing Visvalingam and Whyatt Algorithm
This algorithm simplifies a line segment by successively removing vertices till the required number of vertices remain. It calculates the areas of triangle formed by three consecutive points and then removes the vertex with the smallest area. Learn more.
Below is a python implementation of this algorithm. We use the shapely library to calculate polygon areas. This implementation uses a recursive approach to achieve the result.
import math
from shapely.geometry import Polygon
def visvalingam_whyatt_recursive(point_list, required_points):
# Copy the original list since we will be modifying it
points = point_list.copy()
if len(points) == required_points:
return points
# Calculate traingle areas of each point
areas = []
for index, point in enumerate(points):
if index == 0 or index == len(points)-1:
areas.append(math.inf)
else:
p1 = points[index-1]
p2 = point
p3 = points[index+1]
polygon = Polygon([p1, p2, p3])
areas.append(polygon.area)
min_area = min(areas)
remove_index = areas.index(min_area)
# Remove the vertex with smallest area
points.pop(remove_index)
if len(points) == required_points:
return points
else:
# Call the function recursively with updated point list
return visvalingam_whyatt_recursive(
points, required_points)
Let’s test the function and simplify the line to retain only 50% of the original vertices. We can plot both the original and simplified segment to see the result.
required_points = int(len(point_list)/2)
simplified_list = visvalingam_whyatt_recursive(
point_list, required_points)
fig, ax = plt.subplots(1, 1)
fig.set_size_inches(20,5)
original = LineString(point_list)
simplified = LineString(simplified_list)
ax.plot(*original.xy, color='red',
label='original', marker='o')
ax.plot(*simplified.xy, color='blue',
linestyle='dashed', label='simplified', marker='o')
ax.set_title('Visvalingam and Whyatt Simplification',
fontsize=20)
ax.legend()
plt.savefig('visvalingam_whyatt.png',
bbox_inches='tight', dpi=300)
plt.show()
Animating the Algorithm
This algorithm removes 1 point at a time. We can visualize how the algorithm works by plotting the results of simplifying the original segment with successively smaller number of points. The animate() function gets input as the frame number i and we use it to calculate how many points to retain in each iteration. The resulting animation shows how the algorithm chooses the vertex with the smallest area first and removes it – continuing to do the same till only the start and end points remain.
fig, ax = plt.subplots(1, 1)
fig.set_size_inches(20,5)
fig.tight_layout(rect=[0, 0.03, 1, 0.95])
def animate(i):
ax.clear()
simplified_list = visvalingam_whyatt_recursive(
point_list, len(point_list)-i)
original = LineString(point_list)
simplified = LineString(simplified_list)
ax.plot(*original.xy, color='red',
label='original', marker='o')
ax.plot(*simplified.xy, color='blue',
linestyle='dashed', label='simplified', marker='o')
ax.set_title(
'Visvalingam and Whyatt Algorithm - \
Eliminated {} Points'.format(i), fontsize=20)
ax.legend()
ani = FuncAnimation(fig, animate, frames=len(point_list)-1,
interval=500, repeat=False)
plt.close()
from matplotlib.animation import PillowWriter
# Save the animation as an animated GIF
ani.save("visvalingam_whyatt.gif",
dpi=300, writer=PillowWriter(fps=1))
Visualizing Douglas-Peucker Algorithm
The Douglas-Peucker algorithm successively removes vertices from a segment using the distance between the original segment and simplified segment. It removes points whose distance is less than the specified threshold e Learn more.
Below is a python implementation of this algorithm. We use the shapely library to calculate distance between a point and a line segment. This implementation uses a recursive approach to achieve the result. The implementation is adapted from https://github.com/fhirschmann/rdp
from shapely.geometry import Point, LineString
def douglas_peuker_recursive(point_list, e):
dmax = 0
index = -1
for i in range(1, len(point_list)):
point = Point(point_list[i])
line = LineString([point_list[0], point_list[-1]])
d = point.distance(line)
if d > dmax:
index = i
dmax = d
if dmax > e:
r1 = douglas_peuker_recursive(point_list[:index+1], e)
r2 = douglas_peuker_recursive(point_list[index:], e)
return r1[:-1] + r2
else:
return [point_list[0], point_list[-1]]
We can test the function with e=1 and plot the results.
e = 1
simplified_list = douglas_peuker_recursive(point_list, e)
fig, ax = plt.subplots(1, 1)
fig.set_size_inches(20,5)
fig.tight_layout(rect=[0, 0.03, 1, 0.95])
original = LineString(point_list)
simplified = LineString(simplified_list)
ax.plot(*original.xy, color='red',
label='original', marker='o')
ax.plot(*simplified.xy, color='blue',
linestyle='dashed', label='simplified', marker='o')
ax.set_title('Douglas-Peucker Simplification', fontsize=20)
ax.legend()
plt.savefig('douglas_peucker.png',
bbox_inches='tight', dpi=300)
plt.show()
Animating the Algorithm¶
The Douglas-Peucker algorithm is harder to visualize because each step is done recursively and you need to capture the result of it and plot it. Here I present another strategy to animate each step. We can capture the intermediate results in a separate list and use that list with the animate() function. To capture the output of each invocation of the function, we can use a decorator. Since our function is already defined, we can directly call the track function instead of the @track syntax for decorating the douglas_peuker_recursive() function.
Remember that the recursive function may be called multiple times till it before it meets the condition to actually remove a point. So we save the input and output both to our temporary list.
steps_list = []
# Decorator function to save the input/output from a function
def track(func):
def inner(*args, **kwargs):
# Save the input to the function
steps_list.append(
{'type': 'input', 'line': args[0]})
output = func(*args, **kwargs)
# Save the output from the function
steps_list.append({
'type': 'output', 'line': output
})
return output
return inner
# Decorate the function
douglas_peuker_recursive = track(douglas_peuker_recursive)
# Run the function
simplified_list = douglas_peuker_recursive(point_list, e)
We have now captured each step of the algorithm in the steps_list. We can now write an animation function to display each step from it.
fig, ax = plt.subplots(1, 1)
fig.set_size_inches(20,5)
fig.tight_layout(rect=[0, 0.03, 1, 0.95])
def animate(frame):
ax.clear()
step = steps_list[frame]
original = LineString(point_list)
ax.plot(*original.xy, color='red',
label='original', marker='o')
if step['type'] == 'input':
part = LineString(step['line'])
ax.plot(*part.xy, color='yellow',
linestyle='dashed', label='_part', marker='x')
elif step['type'] == 'output':
simplified = LineString(step['line'])
ax.plot(*simplified.xy, color='blue',
label='simplified', marker='o')
ax.set_title('Douglas-Peucker - Step {}'.format(frame),
fontsize=20)
ani = FuncAnimation(fig, animate, frames=len(steps_list),
interval=500, repeat=False)
plt.close()
from matplotlib.animation import PillowWriter
# Save the animation as an animated GIF
ani.save("douglas_peucker.gif",
dpi=300, writer=PillowWriter(fps=1))
The resulting animation is shown below. You can now see each step of the algorithm as it splits the line segments and removes points outside of the specified threshold.
