This term I am taking a course in computational geometry. As part of the course I was asked to implement a convex hull algorithms in a GUI of some sort. After doing some research on best ways of visualizing how computational geometry algorithms work step by step using HTML5, I ended up deciding on Raphaël.
First, the demo using Raphaël. Click on the area below to add points. You can also click the Random button to add ten random points. Once ready, either click Step, or Run to move one step ahead in the algorithm, or to start running the algorithm. You can click Clear to start over. Notice that once you click run or step, the points are locked and you can not add more points until you click Clear.
Convex Hull
And here is what I learned from this experiment:
- First implement the algorithm using the iterator pattern to allow for going through the steps of the algorithm one by one.
- In absence of Python's generators, use a state variable to keep track of what state the algorithm is in between iteration calls. (Also fantasize about a world in which you can use Python for client-side web programming!)
- Once the code is functional, go through it and using the observer pattern add events for key points of the algorithm to allow for a visualizer to listen in and do the visualization step by step.
- Finally, use an animation library like Raphaël to do the visualization on the GUI side by listening in on the events implemented in the previous step.
Below is the source for the demo above. The algorithm here is based off of one given in the book Computational Geometry: Algorithms and Applications. It first sorts the points from left to right (and bottom to top for points with the same axis) and then starts adding points to the convex hull one by one, at each stage ensuring that the added point does not make the convex hull non-convex. This is done by checking to make sure the added point does not form a left turn with the previous line added. Once one sweep to the right is complete, another sweep from right to left is done to add the bottom part of the convex hull.
Much of the code deals with ensuring the state of the algorithm is persistent between calls to step. The GUI is done separately and does the visualizations by handling the events implemented in the code below.
function Point(x, y, g) {
this.x = x || 0;
this.y = y || 0;
this.graphic = g;
this.main_line = null;
};
Point.prototype.x = null;
Point.prototype.y = null;
Point.prototype.graphic = null;
Point.prototype.main_line = null;
// Currently line_added, line_removed, direction_changed, and finished events are handled
function ConvexHullAlgorithm(points, events) {
this.States = {
STARTED: 'started', // Points need to be sorted
MOVING: 'moving', // Move right or left and add one more point to the convex hull
VERIFYING_POINT: 'veriyfing-point', // verify the added point was right turn
DONE: 'done'
};
this.points = points;
this.events = events;
this.moving_right = true;
this.state = this.States.STARTED;
this.i = 0;
this.convex_hull = [];
this.p = this.q = this.r = null;
this.convex_hull_sort = function () {
this.points = this.points.sort(function (a, b) {
dx = a.x - b.x;
if (dx == 0) {
return b.y - a.y;
}
return dx;
});
}
this.change_state = function(new_state) {
console.log('State change ' + this.state + '->' + new_state);
this.state = new_state;
}
// Use a determinant to determine if point r is right of the directed line pq
this.is_right_of_line = function (p, q, r) {
var D = p.x * q.y - p.x * r.y - p.y * q.x + p.y * r.x + q.x * r.y - q.y * r.x;
return D > 0;
}
this.add_point_to_hull = function (index) {
console.log('Adding #' + index.toString());
var p = this.points[index];
this.convex_hull.push(p);
var n = this.convex_hull.length;
if (this.events) {
if (n > 1) {
this.events.line_added(this.convex_hull[n - 2], this.convex_hull[n - 1]);
}
}
}
this.remove_point_from_hall = function () {
console.log('Removing point.');
var n = this.convex_hull.length;
var p = this.convex_hull[n - 2];
this.convex_hull.splice(n - 2, 1);
n--;
if (this.events) {
this.events.line_removed(p);
this.events.line_removed(this.convex_hull[n - 2]);
this.events.line_added(this.convex_hull[n - 2], this.convex_hull[n - 1]);
}
}
// The main part of the algorithm is done here
// Returns false when done
// This way you can do while(ch.step()); to go through all the steps
this.step = function () {
switch(this.state) {
case this.States.DONE:
return false;
case this.States.STARTED:
this.convex_hull_sort();
this.change_state(this.States.MOVING);
// We do not want the sort to count as a pausing step
// so let's call step again
return this.step();
case this.States.MOVING:
// Add first and second points to the hull
if (this.i == 0 && this.moving_right) {
if (this.points.length > 0) {
this.add_point_to_hull(0);
if (this.points.length > 1) {
this.add_point_to_hull(1);
}
}
this.i = 1;
if(this.points.length <= 2){
this.change_state(this.States.DONE);
}
return this.state != this.States.DONE;
}
if (this.moving_right) {
this.i++;
if (this.i >= this.points.length) {
// Change direction
if(this.events) {
this.events.direction_changed();
}
console.log('Changing direction');
this.i = this.points.length - 2;
this.moving_right = false;
this.add_point_to_hull(this.i);
}
}
// Moving left
if (!this.moving_right) {
this.i--;
if (this.i == -1) {
// We are done. Remove last item since it's the same as first.
this.convex_hull.splice(this.convex_hull.length - 1);
this.change_state(this.States.DONE);
if (this.events) {
this.events.finished(this.convex_hull);
}
return false;
}
}
this.add_point_to_hull(this.i);
this.change_state(this.States.VERIFYING_POINT);
this.r = this.convex_hull[this.convex_hull.length - 1];
return true;
case this.States.VERIFYING_POINT:
n = this.convex_hull.length;
if(n <= 2) {
this.change_state(this.States.MOVING);
return this.step();
}
this.p = this.convex_hull[n - 3];
this.q = this.convex_hull[n - 2];
if(!this.is_right_of_line(this.p, this.q, this.r)) {
this.remove_point_from_hall();
return true;
}
this.change_state(this.States.MOVING);
return this.step();
}
return true;
}
}
Comments