Bezier curve interpolation

Introduction

Given n points, how can you draw a curve that goes around the points and is smooth?

There are infinitely many curves that could be drawn between two points in a plane. Given n number of points one can fit straight lines between them and a curve is drawn. In order for that curve to be smooth there must be an infinite number of points. That is practically impossible on a computer. Instead, n points are selected and a curve is fitted through them. When the number n is small, the curve looks choppy. But sometimes it is difficult to find the points on the curve, especially for a human. That's why people use computers which are able to draw a curve between two points that is smooth (it is not really smooth but on the computer screen it is, given the number of points on the curve is greater than the number of pixels). One type of a curve that a computer can draw between 2 points is a Bezier curve.

Sometimes, however, you might need to draw a curve that is smooth between some points. Drawing random Bezier curves between points doesn't guarantee you that the transition between points is smooth. A Bezier curve is a parametric curve which means that there is a parametric equation which could give you the points on the curve. Guaranteeing the smooth transition is achieved by solving a system of equations involving the derivative of the parametric function of that curve. The points which are interpolated describe a smooth shape, on the outline of which lie the initial points.

How to use?

The Bezier.py file includes a Bezier class which represents a Bezier curve. In order to use it, you must first import the class.

Create the object as follows:

curve = Bezier(points, curve_pts_num)

The arguments are as follows:

Argument name	Default value	Description
points	-	A list of lists of point coordinates or a numpay array of that list. A list of point coordinates looks like [x, y], where x is the x-axis coordinate and y is the y-axis coordinate of the point. For example, [[50, 30], [100, 100]] represents the two points (50, 30) and (100, 100). Important: the points must be put in the same order as we want the curve to go through the points
curve_pts_num	30	The number of points on each of the Bezier curves. The bigger the number the smoother is the curve

These are the available methods:

Method	Arguments	Returns	Description
findPoints()	-	-	Finds the points on the smooth shape
getPoints()	-	Numpy array of the points	Returns a numpy array of the points on the outline of the smooth shape. Each sublist of that list contains point coordinates
draw()	-	-	Draws the plot of the shape. In blue is drawn the smooth outline, in black the initial points, through which the curve is interpolated

An example of drawing a shape:

points = [
    [400, 505],
    [580, 400],
    [400, 130],
    [280, 400]
]
curve = Bezier(points, 50)
curve.findPoints()
curve.draw()

This will find the points and draw the following plot using matplotlib.pyplot:

To get the points on the smooth shape outline, you can simply call

curve.getPoints()

which will return the points as numpy array so that they can be used by another method.

Explanation of how the interpolation works

In the code we use a cubic Bezier curve. It has the following parameterization:

where . is the first control point, also a starting point, - the second and third control points and is the fourth control point, also an end point.

The smooth transitioning between two consecutive points is guaranteed when the first and second derivatives at the same point in both equations are respectively equal.

We obtain the first and second derivatives:

Now we let for point i, , . Then for example the first derivative looks like:

In order to ensure the smooth transitioning, the following equations must be satisfied:

Solving the system for t we get the following system of equations:

That system of equations has 2n equations. Now, by applying little algebra to each pair of equations in the system, so the pairs are 1^st and 2^nd, 3^rd and 4^th, etc. equations, we arrive at the following system of equations:

We have to be careful with the indeces as they should always be less than n. If an index becomes greater or equal to n, then the index becomes the remainder of a division with n. The first equation could be solved easily using a matrix of coefficients. Let C be the coefficient matrix, b be the vector of sum of the end points (right side of equation 1) and x be the vector of points K which are the second control point on each Bezier curve. Then we have to solve Cx=b for x. Matrix C looks like that:

Vector b looks like this:

Vector x looks like this:

Then we have to solve the following equation for x:

Now we can easily find the third control point for each Bezier curve by solving equation 2 in the system. Then we have obtained all the control points. Then for each of the n curves we get a set of m points (this corresponds to curve_pts_num) such that:

Then each point G on on the closed path for the n Bezier curves could be found using these equations:

License

Licensed under MIT.