AnimaAlgo - Details

Initialization

This is the applet initialization process:

• The applet obtains a Graphics object representing the animation panel.
• Objects of type Points and Solution are instantiated.
• A new View2D is instantiated, and initialized with the Points, Solution and Graphics objects.
• The Points and Solution objects are initialized with a reference to the view View2D.

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
  do
  {
    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:

• adds an edge to the solution set;
• draws the added edge on the screen;
• pauses processing for a period of time specified in the user interface field "Delay", to slow down the animation.

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)));
      vector1=pts.elem(i).minus(pts.elem(ip1));
      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 sol. This 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.