TD 4 - Graph drawing and network visualization

Introduction:

The goal of this exercice session is to implement three algorithms for computing graph layouts.

Before starting to code

You can download here a few examples of meshes (OFF format) and networks (MTX formats) for testing your code.
Download the following classes (to be completed and for testing): src.zip
As in previous TDs you need the following Java libraries: Jcg.jar, TC.jar, core.jar (Processing library, v 1.51),
Here is the Javadoc for this TD (you can find the Javadoc of the Jcg library on the Moodle webpage of INF562)

In order to test your code, you can run (as Java application) the classes MeshParameterization and SpringDrawing which provides methods for rendering the original mesh and computing the corresponding 2D and 3D layouts.
Remarks:

you can perform one iteration of the iterative methods with the touch c
you can change the rendering mode with the touch r

1. Planar Parameterization

The pictures below show the planar parameterization of the sphere (162 vertives) and horse (20k vertices) meshes.

Exercice

Tasks: The goal of this exercice is to implement the iterative computation of the Tutte's barycentric embedding
By default, we set as outer face an arbitarty triangle face 0 (e.g. having index 10): the k vertices belonging to the outer face are classified as boundary vertices, while all remaining n-k vertices are called inner vertices.

complete the class IterativeTutteLayout that allows to compute a planar layout of the mesh; you will be asked to complete the method oneIteration() that perform one iteration of the Tutte algorithm to compute the 2D coordinates of the vertices (they are stored in the field Point_2[] points).

2. Force-directed layouts of network:

Implement the force-directed paradigm illustrated in the lecture in order to compute a 2D layout of the input network

complete the class FR91Layout that allows you to compute a (2D) layout of the input network obtained with the FR91 algorithm (for more details, see the slides the lecture 4). You will be asked to complete the method oneIteration().