We developed an algorithm animation system called AnimaAlgo.
AnimaAlgo has the following characteristics:
Two different approaches could have been following during design: making the program very flexible and configurable, in which case the user would need a bigger effort to develop custom algorithms, or making the animation API very simple, in such a way to facilitate the construction and testing of algorithms, with the cost of a somewhat reduced flexibility of use.
The second approach was chosen. This way, the user can easily customize algorithms, writing them with not much concern about the animation system. This was achieved by implementing function calls to interesting events inside the point set and solution set classes. When the user, for example, adds a new edge to the solution set, this class invokes the corresponding event in the view, which results in the new edge being displayed.This is AnimaAlgo's class diagram:
The applet class is called AnimatedApplet2D, which is an extension of class Applet. This class instantiates objects from the four classes to the right: Points, Solution, View2D and the user algorithm, which is an extension of class Algorithm.
These classes are described below.
This is the main applet class. It has all the graphical components that appear on the user interface, and it handles all mouse events. It has objects from classes Points, Solution and View2D. It also instantiates an object from the user-defined algorithm class, and it invokes methods from this class to animate the algorithm.
A 2D point. Has methods which implement geometric primitives. The relevant methods are:
This class has a set of objects of class Point. The relevant methods are:
Class Point, as well as class Solution, has a reference to the view in use, which is class View2D. Class View2D, on its turn, has a reference back to classes Points and Solution, establishing a double link. The reason is explained below.
An Edge is defined by a pair of Points.
This class has a set of objects of class Edge, which represents the solution set. It has methods to add and remove edges.
This class, an extension of class View, implements graphical primitives that draw on a Java Graphics object. On this class are defined the point adn edge drawing commands. Class View has a Graphics object, which is inherited by View2D. This Graphics is the canvas where drawing is performed. AnimatedApplet2D is in charge of obtaining this object and passing it to View2D on the moment of initialization.
View2D, as well as other possible user-defined Views, need to access the point set and the solution set in order to draw them when the screen needs to be redrawn, or when a new point is added to the point set or solution. However, Point and Solution also invoke members of class View2D when a point is added to the solution, or when a point is moved or added on the point set. Therefore, these two classes also have a reference to class View2D. This is the reasoning behind the double-linking.
The user codes the algorithm to be visualized in a class that has its name, for example Jarvis or Graham. This class must extend class Algorithm, and it must have a method called animate, which is the main animation loop of the algorithm.
When coding his/her algorithm, the user doesn't need to worry about
invoking graphical primitives. They are invoked by classes Points and
Solution. This allows for a cleaner code in the algorithm side, and
On the next section, we show an outline of how the system works.