-A A +A

Gawain Convex Hull

Primary tabs

Collection:   AlgoViz
Source: http://algoviz.org/node/1067
Format:   Java Applet
Recommendation: Has Potential.
Description: An intro page is given that describes what Convex Hull is, with links to three AVs showing algorithms to implement Convex Hull: Jarvis' March (gift wrapping), Graham's scan, and a quicksort-like 'Quick hull' algorithm. Each displays a set of (random) points and shows, step by step, processing appropriate to that algorithm. For example, the Graham's scan shows the search for the lowest point (pivot), sorting the other points in order of angle from the pivot and forming the convex hull by traversing the polygon constructed from these points. User interaction is limited to starting and pausing the animation.
Evaluation: The visual representations in the animation (points, polygon edges in different colours, slanted lines for angles) are mostly obvious and clear, but rely on colour to distinguish different points and edges (for example, lines in the initial polygon from the convex hull that is being built). The animation proceeds quite quickly (and lacks speed control and stepping), making it hard to observe the behaviour of the algorithm on the level of individual steps. The supporting text is a brief summary of the algorithm, which is mostly adequate but leaves out details of the backtracking in the final phase. The animation itself does not explain the decisions made by the algorithm in the final phase at all, it just adds and removes edges from the view, making it hard to see why some points are added to the convex hull and some are not. As such, the animation can be used to get an overview of the algorithm, but a detailed understanding is hard to get and exploration is not supported.
Creator: Alejo Hausner  
Publisher: Princeton University  
Subject:   Computational geometry  
Language: english  
Relation: Stand-alone  
Rights: Available but unlicensed
ACM CCS 2012:
Theory of computation Randomness, geometry and discrete structures Computational geometry