![[halfspace]](qh--half.gif)
Examples of QhullUp: Home
page for Qhull
Up: Qhull manual: Table of Contents
To: Programs
• Options
• Output
• Formats
• Geomview
• Print
• Qhull
• Precision
• Trace
• Functions
To: Qhull examples: Table of Contents (please wait
while loading)
Examples of QhullThis section of the Qhull manual will introduce you to Qhull and its options. Each example is a file for viewing with Geomview. You will need to use a Unix computer with a copy of Geomview.
If you are not running Unix, you can view pictures for some of the examples. To understand Qhull without Geomview, try the examples in Programs and Programs/input. You can also try small examples that you compute by hand. Use rbox to generate examples.
To generate the Geomview examples, execute the shell script eg/q_eg. It uses rbox. The shell script eg/q_egtest generates test examples, and eg/q_test exercises the code. If you find yourself viewing the inside of a 3-d example, use Geomview's normalization option on the 'obscure' menu.
Copyright © 1995-2018 C.B. Barber
The first example is a cube in 3-d. The color of each facet indicates its normal. For example, normal [0,0,1] along the Z axis is (r=0.5, g=0.5, b=1.0). With the 'Dn' option in rbox, you can generate hypercubes in any dimension. Above 7-d the number of intermediate facets grows rapidly. Use 'TFn' to track qconvex's progress. Note that each facet is a square that qconvex merged from coplanar triangles.
The second example is a cube plus a diamond ('d') scaled by rbox's 'G' option. In higher dimensions, diamonds are much simpler than hypercubes.
The rbox s option generates random points and projects them to the d-sphere. All points should be on the convex hull. Notice that random points look more clustered than you might expect. You can get a smoother distribution by merging facets and printing the vertices, e.g., rbox 1000 s | qconvex A-0.95 p | qconvex G >eg.99.
In 2-d, there are many ways to generate a convex hull. One of the earliest algorithms, and one of the fastest, is the 2-d Quickhull algorithm [c.f., Preparata & Shamos '85]. It was the model for Qhull.
One rotation of a spiral.
This demonstrates how Qhull handles precision errors. Option 'C-0.03' requires a clearly convex angle between adjacent facets. Otherwise, Qhull merges the facets.
This is the convex hull of random points in a square. The facets have thickness because they must be outside all points and must include their vertices. The colored lines represent the original points and the spheres represent the vertices. Floating in the middle of each facet is the centrum. Each centrum is at least 0.03 below the planes of its neighbors. This guarantees that the facets are convex.
Here's the same distribution but in 3-d with Qhull handling machine roundoff errors. Note the large number of facets.
The sphere is just barely poking out of the cube. Try the same distribution with randomization turned on ('Qr'). This turns Qhull into a randomized incremental algorithm. To compare Qhull and randomization, look at the number of hyperplanes created and the number of points partitioned. Don't compare CPU times since Qhull's implementation of randomization is inefficient. The number of hyperplanes and partitionings indicate the dominant costs for Qhull. With randomization, you'll notice that the number of facets created is larger than before. This is especially true as you increase the number of points. It is because the randomized algorithm builds most of the sphere before it adds the cube's vertices.
This is a combination of the diamond distribution and the sphere.
Each half of the lens distribution lies on a sphere of radius three. A directed search for the furthest facet below a point (e.g., qh_findbest in geom.c) may fail if started from an arbitrary facet. For example, if the first facet is on the opposite side of the lens, a directed search will report that the point is inside the convex hull even though it is outside. This problem occurs whenever the curvature of the convex hull is less than a sphere centered at the test point.
To prevent this problem, Qhull does not use directed search all the time. When Qhull processes a point on the edge of the lens, it partitions the remaining points with an exhaustive search instead of a directed search (see qh_findbestnew in geom2.c).
The next 4 examples show how Qhull adds a point. The point [0.5,0.5,0.5] is at one corner of the bounding box. Qhull adds a point using the beneath-beyond algorithm. First Qhull finds all of the facets that are visible from the point. Qhull will replace these facets with new facets.