Quickhull convex hull in the plane
The divide & conquer
algorithm that is the analogue of Quicksort for sorting. Quadratic
worst case because the "pivot" is determined by geometry.
Chan's modifications make this O(n log h) worst case!
- Detail toggles the vertex numbers and some of the edge weights.
- Animate toggles some animation of partial computation
- Update is the button you push when the input is ready; If
comparing times, click
twice because the first time may include loading or swapping time.
- Random generates 50 random points
- Clear All and Delete Last give minimalist editing.
Code by Jack
Snoeyink, University of British Columbia
Back to Jack's Computational Geometry Demo page.