AnimaAlgo - Details


This is the applet initialization process:

Point set generation

From then on, the user can add, move or remove points, or generate random points. To add points, the user has to click with the mouse over the animation area. He/she can move points by dragging them, and delete points by clicking on them while pressing Alt.

Once the user is satisfied with the point set, he/she clicks on the button "Animate!". The applet searches for the user defined class, whose name is defined in the Algorithm field of the interface. The applet invokes the algorithm method from this class.

The animation

In order to illustrate the animation process, here is the source code for a convex hull algorithm, the Jarvis algorithm.

public static void algorithm(Points pts, Solution sol)
  int ip0, ip1, ip2, ip3;
  Point initialVector = new Point(1.0,0.0);
  Point currentVector;

  ip1 = pts.minimumY();
  ip2 = jarvisNext(pts, sol, ip1, initialVector);
  sol.add(new Edge(pts.elem(ip1), pts.elem(ip2)));
  ip0 = ip1; // saves initial element
    currentVector = pts.elem(ip2).minus(pts.elem(ip1));
    ip3 = jarvisNext(pts, sol, ip2, currentVector);
    sol.add(new Edge(pts.elem(ip2), pts.elem(ip3)));
    ip1=ip2; ip2=ip3;
  while (ip3 != ip0);

The function call sol.add(Edge e) performs three operations automatically:

This algorithm method invokes an auxiliary method, JarvisNext, defined below:
public static int jarvisNext(Points pts, Solution sol, int ip1, Point vector)
  Point vector1;
  double angle;
  double minAngle = 999;
  int minIp = 0;
  for (int i=0; i<pts.size(); i++)
    if (i!=ip1)
      sol.setCandidate(new Edge(pts.elem(ip1), pts.elem(i)));
      angle = vector.pseudoAngle(vector1);
      if (angle<minAngle)
        minAngle = angle;
        minIp = i;
 return minIp;

JarvisNext finds the next point to be added to the convex hull. It invokes sol.setCandidate(Edge e), who draws a candidate edge on the screen, in red color, without adding it to the solution set solThis method also pauses processing for a period of time defined by "delay".

In this fasion, we can call, from our algorithm, methods that present the construction of the solution step by step. The system shows not only each final edge added to the solution, but also candidate edges that the algorithm may be testing as one of its steps.

On the next section, we present extension possibilities.