[ Graphics Archive | Up | Comments ]

Special Topics:Computational Geometry

Qhull cone by Brad Barber


The convex hull is the smallest convex set containing a set of points. For example, a cube is the convex hull of the cube's vertices. This cone is the convex hull of two 20-sided polygons and a cospherical point. It was generated by Qhull.

This cone illustrates a unique feature of Qhull. The program handles roundoff errors due to floating point arithmetic. If adjacent facets are non-convex, Qhull merges one of the facets into a neighbor. For example, the 20-sided facet and squares are merged facets. The result is an inner and outer approximation to the convex hull.

If exact arithmetic was used instead of floating point arithmetic, all of the facets would be non-coplanar triangles. This is because the point coordinates are floating point numbers. There were numeric errors in creating the regular polygons and additional errors in rotating the points.

How to make it: rbox r s 20 Z1 G0.2 | qhull s C-0 QR1 G >a

Image created: April 1995

[Qhull cone]

Copyright © April 1995 by The Geometry Center, Univerity of Minnesota. All rights reserved.
For permission to use this image, contact permission@geom.umn.edu.

External viewing: small (100x100 2k gif), medium (500x402 17k gif), or original size (1274x1023 140k tiff).

[HOME] The Geometry Center Home Page

Comments to: webmaster@geom.umn.edu
Created: Sat May 22 23:17:50 CDT 1999 --- Last modified: Sat May 22 23:17:50 CDT 1999