A Delightful Sampling of Convex Hull Algorithms
Experience the wonders of three time honored convex hull algorithms, including the Graham Scan, the Jarvis March, and the Kirkpatrick Seidel Ultimate Planar Convex Hull algorithms.
Instructions (Basic Overview):
Enter a pointset, using the mouse or in text format in the option panel. The randomize, form regular poly, and form star poly buttons can be used to modify and create pointsets.
Make sure the pointset is in general position (but cocircular points are ok), and contains no 2 points on a vertical line. Use the check degeneracy and fix degeneracy buttons to detect these and fix them automatically.
Once a pointset has been entered, select an algorithm (Jarvis, Graham, or Kirkpatrick Seidel), and use the control buttons (located on the bottom right) to run through the algorithm.
To visualize the cost of each operation, select the "Complexity Analysis Report" tab on the lower panel.
And the details on the options panel (leftmost panel of the applet):
Explanation of sliders:
Selection sensitivity: How close the mouse must be to a point to select it.
Random count: How many random points are created with the Randomize button
Algorithm sleep time: The value of this slider at the beginning of an algorithm determines the speed the algorithm animates at when Play is pressed.
Explanation of action buttons:
Check Degeneracy: Finds all degenerate points (points that will cause issues with one or more of the available algorithms).
Fix Degeneracy: Nudges degenerate points repeatedly until none exist. This operation does time out, and can fail on extremely dense pointsets.
Re-Add Degen Points: Unmark all degenerate points, and add them into the main pointset.
Remove Degen Points: Delete all degenerate points.
Re-Add Convex: Unmark all convex hull points, and add them into the main pointset.
Remove Convex: Delete all convex hull points.
Randomize: Replace the active pointset with a randomly distributed pointset.
Clear: Remove all points from the active pointset, including convex hull and degenerate points.
Form Regular Poly: Arrange the active pointset into a regular polygon. Note: regular polygons with an even number of points are degenerate (they have nonunique x coordinates).
Form Star Poly: Arrange the active pointset into a pointset with no 2 points on any line drawn out from the center (the name is a bit misleading, but these pointsets could easily define very friendly star polygons).
To Text: Display a textual representation of the active pointset in the text window (located below the button).
From Text: Convert the text in the text window (below the button) into a pointset. Adds these points to the extant active pointset.
Save CSV/Read CSV: For security purposes, this button is not active in the applet version of the software.
Sort X: Sorts the active pointset by X coordinate.
Sort Y: Sorts the active pointset by Y coordinate.
Sort Clockwise: Sorts the active pointset radially clockwise.
Sort CClockwise: Sorts the active pointset radially counterclockwise.
Convex Hull Algorithms:
Kirkpatrick Seidel Ultimate Planar Convex Hull Algorithm
The control buttons function much like a cassete deck in that one can play and pause an algorithms animation. Additionally, an algorithm can be stopped, in which case it halts immediately and cannot be resumed, and it can be skipped, in which case it skips the animation and shows the final convex hull. Complexity information is still obtained when an algorithm is skipped, as only graphics are affected by this operation.
Explanation of Complexity Analysis Capabilities
This software uses Randall Munroe's XKCD color database: