Recommendation

Has Potential

Link

http://www.cs.princeton.edu/courses/archive/spr09/cos226/demo/ah/ConvexHull.html

Delivery Method

Java Applet

License

Unlicensed Sourcecode

Language

English

Author

Alejo Hausner

Institution

Princeton University

Project

StandAlone

RelationshipToProject

StandAlone

Works

Yes

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.

ActivityLevel

Animation; Step Control

GoodFor

Lecture Aid; Teaching the Concept

Screenshots

Videos

References

HowToUse

From the link given above, follow the links to the page for each Convex Hull algorithm. These are applets that load automatically. Just hit "Run" or "Step" to advance the algorithm. Hit "Init" to restart with a new set of random points.

First Visited

2007-09-22

Last Visited

2009-08-17

Last Updated

1997-05-30

Topic

ComputationalGeometry

Community

Edit

You may edit this entry if you have an account.