Geometric Algorithm Visualizations

by Gavin Nishizawa

Project Goal

The project is to build an interactive educational tool for geometric algorithms, which is able to simultaneously highlight the geometric data currently being operated on and the high level algorithmic task being worked on. This should provide a visual link between the idea of the algorithm, and the visualized geometry of the problem.

Convex Hull via Graham's Scan

An interactive visualization of the graham's scan algorithm for computing the convex hull of a set of points.

Background

The convex hull of a set of points is the smallest convex shape which encloses the set of points. A planar shape is convex if none of its interior angles are greater than 180 degrees. Graham's scan is an incremental construction algorithm for computing the convex hull of a set of points. The algorithm constructs the upper and lower portions of the convex hull independently and joins the results. The upper and lower portions of the convex hull are split by the leftmost and rightmost points. It is an incremental construction algorithm because the hull is partially constructed as each point is added one at a time.

Algorithm Overview

The algorithm starts by sorting the points by x (primary) and y (secondary). For both the upper and lower hull sections, the following steps occur. Initialize a stack with the first 2 points. Repeatedly pop a point from the top of the stack while the interior angle between the next point to be added, and the top two points on the stack is greater than 180 degrees. Finally the add the point onto the stack before proceeding to the next point. The upper and lower hull sections process the points in opposite directions, one after the other.

Instructions

• Add specific points either by clicking or tapping on the canvas
• Add 10 random points each time you select the Add 10 Random Points button
• Play the algorithm visualization automatically with the Play/Pause button
• Adjust speed of automatic play with the speed sliderbar
• Use the step button while the algorithm is not playing to control each step of the algorithm
• Use the reset button to reset the state of the algorithm
• Wait for the algorithm to finish or reset it before adding new points

High-level algorithm state: Not running

References

1. Paper.js : paperjs.org
2. Mount, David. “CMSC 754 Computational Geometry. Lecture Notes” UMD Department of Computer Science, 2012, http://www.cs.umd.edu/~mount/754/Lects/754lects.pdf
3. Bootstrap : getbootstrap.com