TD 1 - A basic editor for curve interpolation

(Luca Castelli Aleardi)

The goal of this TD session is to design a basic editor for 2D objects: you are asked to implement some of the methods for curve interpolation described today.

   
        Examples of curve interpolation schemes (Lagrange and cubic spline interpolations)

Votre opinion sur le cours: Votre opinion sur le TD:



0. Getting started (a Processing frame for testing interpolation schemes)

Files to download today

Here are some files to download (and extract to the /src folder of your Eclipse project):
  • geometry.zip: some classes for manipulating geometric objects (such as points, vectors, affine and projective transformations in 2D).
  • core.jar: the Processing library.
  • Jama.jar: java library for matrix computations.
  • TC.jar: java library for input/output.

Java documentation

Here is the javaDoc concerning the packages and classes used today:

Testing classes draw

Class Draw provides a basic 2D editor for drawing (points and segments), and handling mouse events (for adding/moving/deleting points, zoom in/out, rotations, ...).

  • complete class Transformation_2 implementing the constructors 
    • Transformation_2(Vector_2 v)
    • Transformation_2(double s1, double s2)
    • Transformation_2(double theta)
    • Transformation_2(double theta, Point_2 center)
which correspond to: translations, scaling and rotations.

Execute class Draw to test your code.

Example of execution of class  Draw:
you should obtain a frame to display points and segments.
Click with left button to add a new point,
Click with right button, to delete a point,
Press 'd' to remove the last point.
Press 's' to change the interpolation method (by default, at the beginning there is no interpolation)

Additional features (you have to implement them)
Press 't' to perform a translation.
Press 'i' or 'o' to perform a scaling (zoom in/out).
Press 'r' to perform a rotation.


1. Linear interpolation

Implementing linear interpolation

  • complete class LinearInterpolation implementing method interpolate() which computes and plots the linear interpolation.

Example: linear interpolation of 6 points:
 (x0, y0) ... (x5, y5).

2. Function interpolation

2.1 Lagrange interpolation: solve linear system of equations


Given a set of n points to interpolate, you have to solve a system of n equations (with n variables), represented in matrix form (as illustrated during the Lecture), as follows:



  • complete class LagrangeInterpolation implementing method interpolate() which computes Lagrange interpolation.


Suggestions:
you can solve this task defining:

  • a method double[] computeCoefficients(Point_2[] P)  which returns an array containing the coefficients of the polynomial expression, given the input points,
  • a method  void plotPolynomial(double[] coeff, double min, double max, int n) which allows to plot a given polynomial expression in a given range.


Recall that Jama library computes solutions of linear systems:

  • use x=A.solve(b)  to obtain the vector solution of system Ax=b.

Example: Lagrange interpolation of 6 points:
 (x0, y0) ... (x5, y5).
The goal is to compute the coefficients of the polynomial
expression for f(x), by solving a linear system of equations.

The sequence of images below illustrates some drawbacks of Lagrange interpolation

Interpolating 10 points
 Addition of a point (the rightmost one)
 After adding a further point


2.2 Cubic spline interpolation: matrix form


Given a set of n points to interpolate, you have to solve a system of 4(n-1) equations (with 4(n-1) variables), represented in matrix form as below.


  • complete class CubicSplineInterpolation implementing the cubic spline interpolation (you can first consider the case of 4 points).


Suggestion: to specify colors use method frame.stroke(int r, int g, int b). For example:
 frame.stroke(255, 0, 0) allows to choose color red for drawing lines.
Example: cubic spline interpolation of 4 points:
 (x0, y0), (x1, y1), (x2, y2), (x3, y3).
The goal is to compute cubic polynomial expressions for f0, f1, f2




Example: cubic spline interpolation of 4 points: (x0, y0), (x1, y1), (x2, y2), (x3, y3).

3. Curve interpolation

3.1 Hermite cubic spline interpolation


Now, let us suppose we are given:
  • a set of n points to interpolate (added by the user in the frame),
  • a set of n vectors {ti}, where ti is tangent to the curve at point pi=(xi, yi).

Remark: for the sake of simplicity, the slopes (the n vectors {ti}) are provided as predefined parameters in the code (their are constant).

Goals and constraints: we want to find a cubic parametric curve f(t)=(x(t), y(t)), such that:
-) f interpolates points  pi=(xi, yi),
-) f respects C1 constraints (given by tangents)
  • complete class HermiteSplineInterpolation implementing the Hermite cubic spline interpolation.


Suggestion: as before, solve the problem in its matrix form, recalling that you should use curve parametrization.
Example: Hermite cubic spline interpolation of 3 points:
 (x0, y0), (x1, y1), (x2, y2).
The goal is to compute parametric expressions for f0, f1.