Programming assignment 2

Submission

You should submit your source code and a README file. As before, submit by emailing the TA (drussel@graphics.stanford.edu) a compressed tarball of your sources, makefile and README.

User interface

You can assume that the data is input from a data file; you do not need to design an interactive interface to input the disks. However, you may still want to implement a simple interface to read in the input data file, to control the animation, and to draw the animation. LEDA provides interface features so that you can perform those tasks conveniently. For the details, please consult the LEDA manual pages (section 3.9) and (for instance) the sample program:

   /usr/class/cs368/LEDA-PLATFORM/demo/window/draw

At the moment, the sample program only works on the linux boxes. I can try to fix it on solaris someone wants to work on it, but I suggest developing on linux.

To obtain a smooth animation, it is a good idea to use double buffering. LEDA provides a standard way to do so. See section 3.4.15 in the LEDA manual.

Input data format

The following is an example of the input data format:

    4 3.0 0.5
    (1.0, 1.0)+(-1.0, -1.0).
    (1.0, 2.5)+(0.5, 0.3).
    (0.2, 1.5)+(0.2, 0.4).

In the file, the first line describes the number of objects, the size w of the box (the coordinates for the box are [0, w]x[0, w]), and the radius of the disks (when the radius is 0, then they are points and you do not need to detect collision between the objects).

Each remaining line describes the initial position and velocity of each disk. The format is (x,y)+(vx,vy)., where (x,y) and (vx, vy) represent the initial position and velocity, respectively. You may assume that the input data is valid, i.e. the disks are inside the box and are disjoint.

Polynomial library

We provide a library for manipulating polynomials. In addition to the normal arithmetic operations you would expect for polynomials, an object of the class polynomial has two interesting methods:

int polynomial::rroots(double roots[], int polish);
Computes all real roots of the polynomial, and returns the number n of roots. The roots are stored in roots[1]...roots[n]. If polish is non-zero, some additional time is spent to find the roots with better accuracy. The roots are not sorted
polynomial polymat_det3(polynomial mat[3][3]);
Computes the determinant of the 3x3 matrix mat whose entries are polynomials

Note that although the InCircle test was defined in class as the determinant of a 4x4 matrix, there is a simple way to reduce it to the determinant of a 3x3 matrix.

The library and a simple example on how to use it can be found in the directory:

    /usr/class/cs368/hw2-support/

Please do not modify the library. Make your own subclass if you want some additional or modified features, or write your new code in files with different names.

Tips, warnings, assumptions

Assume no degeneracies in the initial data.

The curse of floating point operations

An InCircle test output is given by the sign of a 4x4 determinant (one row per point involved in the test). If the coordinates of the points are linear functions of time, the determinant is a polynomial of degree 4. Hence, it has several roots.

If an edge e is certified by an InCircle test that fails at time t_0, the flipped edge e' that replaces e at t_0 is certified by the same InCircle test (with opposite sign). One of the roots of this test will be t_0. You will run into difficulties with numerical inaccuracies here, as you can expect that the root in question, as found by the numerical solver, will not be exactly t_0, but t_0 plus or minus a small epsilon. Beware.