![[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-2015 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.
These are the facets that are not visible from the point. Qhull will keep these facets.
These facets are the horizon facets; they border the visible facets. The inside edges are the horizon ridges. Each horizon ridge will form the base for a new facet.
This is the cone of points from the new point to the horizon facets. Try combining this image with eg.10c.sphere.horizon and eg.10a.sphere.visible.
This is the convex hull after [0.5,0.5,0.5] has been added. Note that in actual practice, the above sequence would never happen. Unlike the randomized algorithms, Qhull always processes a point that is furthest in an outside set. A point like [0.5,0.5,0.5] would be one of the first points processed.
The 'QVn', 'QGn ' and 'Pdk' options define good facets for Qhull. In this case 'QV0' defines the 0'th point [0.5,0.5,0.5] as the good vertex, and 'Qg' tells Qhull to only build facets that might be part of a good facet. This technique reduces output size in low dimensions. It does not work with facet merging.
This is the convex hull of 500 points on the surface of a cube. Note the large, non-simplicial facet for each face. Qhull merges non-convex facets.
If the facets were not merged, Qhull would report precision problems. For example, turn off facet merging with option 'Q0'. Qhull may report concave facets, flipped facets, or other precision errors:
rbox 500 W0 | qhull QR0 Q0
Like the previous examples, this is the convex hull of 500 points on the surface of a cube. Option 'Qt' triangulates the non-simplicial facets. Triangulated output is particularly helpful for Delaunay triangulations.
This is the convex hull of 500 joggled points on the surface of a cube. The option 'QJ5e-2' sets a very large joggle to make the effect visible. Notice that all of the facets are triangles. If you rotate the cube, you'll see red-yellow lines for coplanar points.
With option 'QJ', Qhull joggles the input to avoid precision problems. It adds a small random number to each input coordinate. If a precision error occurs, it increases the joggle and tries again. It repeats this process until no precision problems occur.
Joggled input is a simple solution to precision problems in computational geometry. Qhull can also merge facets to handle precision problems. See Merged facets or joggled input.
The input file, eg.data.17, consists of a square, 15 random points within the outside half of the square, and 6 co-circular points centered on the square.
The Delaunay triangulation is the triangulation with empty circumcircles. The input for this example is unusual because it includes six co-circular points. Every triangular subset of these points has the same circumcircle. Option 'Qt' triangulates the co-circular facet.
This is the same example without triangulated output ('Qt'). qdelaunay merges the non-unique Delaunay triangles into a hexagon.
This is how Qhull generated both diagrams. Use Geomview's 'obscure' menu to turn off normalization, and Geomview's 'cameras' menu to turn off perspective. Then load this object with one of the previous diagrams.
The points are lifted to a paraboloid by summing the squares of each coordinate. These are the light blue points. Then the convex hull is taken. That's what you see here. If you look up the Z-axis, you'll see that points and edges coincide.
The Voronoi diagram is the dual of the Delaunay triangulation. Here you see the original sites and the Voronoi vertices. Notice the each vertex is equidistant from three sites. The edges indicate the Voronoi region for a site. Qhull does not draw the unbounded edges. Instead, it draws extra edges to close the unbounded Voronoi regions. You may find it helpful to enclose the input points in a square. You can compute the unbounded rays from option 'Fo'.
Instead of triangulated output ('Qt'), this example uses joggled input ('QJ'). Normally, you should use neither 'QJ' nor 'Qt' for Voronoi diagrams.
This looks the same as the previous diagrams, but take a look at the data. Run 'qvoronoi p <eg/eg.data.17'. This prints the Voronoi vertices.
With 'QJ', there are four nearly identical Voronoi vertices within 10^-11 of the origin. Option 'QJ' joggled the input. After the joggle, the cocircular input sites are no longer cocircular. The corresponding Voronoi vertices are similar but not identical.
This example does not use options 'Qt' or 'QJ'. The cocircular input sites define one Voronoi vertex near the origin.
Option 'Qt' would triangulate the corresponding Delaunay region into four triangles. Each triangle is assigned the same Voronoi vertex.
This is the 3-d Delaunay triangulation of a small cube inside a prism. Since the outside ridges are transparent, it shows the interior of the outermost facets. If you slice open the triangulation with Geomview's ginsu, you will see that the innermost facet is a cube. Note the use of 'Qz' to add a point "at infinity". This avoids a degenerate input due to cospherical points.
The furthest-site Voronoi diagram contains Voronoi regions for points that are furthest from an input site. It is the dual of the furthest-site Delaunay triangulation. You can determine the furthest-site Delaunay triangulation from the convex hull of the lifted points (eg.17c.delaunay.2-3). The upper convex hull (blue) generates the furthest-site Delaunay triangulation.
This is the upper convex hull of the preceding example. The furthest-site Delaunay triangulation is the projection of the upper convex hull back to the input points. The furthest-site Voronoi vertices are the circumcenters of the furthest-site Delaunay triangles.
This shows an incomplete furthest-site Voronoi diagram. It only shows regions with more than two vertices. The regions are artificially truncated. The actual regions are unbounded. You can print the regions' vertices with 'qvoronoi Qu o'.
Use Geomview's 'obscure' menu to turn off normalization, and Geomview's 'cameras' menu to turn off perspective. Then load this with the upper convex hull.
This shows the Voronoi region for input site 5 of a 3-d Voronoi diagram.
There are two things unusual about this cone. One is the large flat disk at one end and the other is the rectangles about the middle. That's how the points were generated, and if those points were exact, this is the correct hull. But rbox used floating point arithmetic to generate the data. So the precise convex hull should have been triangles instead of rectangles. By requiring convexity, Qhull has recovered the original design.
This is the convex hull of 200 cospherical points with precision errors ignored ('Q0'). To demonstrate the effect of roundoff error, we've added a random perturbation ('R0.01') to every distance and hyperplane calculation. Qhull, like all other convex hull algorithms with floating point arithmetic, makes inconsistent decisions and generates wildly wrong results. In this case, one or more facets are flipped over. These facets have the wrong color. You can also turn on 'normals' in Geomview's appearances menu and turn off 'facing normals'. There should be some white lines pointing in the wrong direction. These correspond to flipped facets.
Different machines may not produce this picture. If your machine generated a long error message, decrease the number of points or the random perturbation ('R0.01'). If it did not report flipped facets, increase the number of points or perturbation.
Qhull handles the random perturbations and returns an imprecise sphere. In this case, the output is a weak approximation to the points. This is because a random perturbation of 'R0.01 ' is equivalent to losing all but 1.8 digits of precision. The outer planes float above the points because Qhull needs to allow for the maximum roundoff error.
If you start with a smaller random perturbation, you can use joggle ('QJn') to avoid precision problems. You need to set n significantly larger than the random perturbation. For example, try 'rbox 200 s | qconvex Qc R1e-4 QJ1e-1'.
The next four examples compare post-merging and pre-merging ('Cn' vs. 'C-n'). Qhull uses '-' as a flag to indicate pre-merging.
Post-merging happens after the convex hull is built. During post-merging, Qhull repeatedly merges an independent set of non-convex facets. For a given set of parameters, the result is about as good as one can hope for.
Pre-merging does the same thing as post-merging, except that it happens after adding each point to the convex hull. With pre-merging, Qhull guarantees a convex hull, but the facets are wider than those from post-merging. If a pre-merge option is not specified, Qhull handles machine round-off errors.
You may see coplanar points appearing slightly outside the facets of the last example. This is becomes Geomview moves line segments forward toward the viewer. You can avoid the effect by setting 'lines closer' to '0' in Geomview's camera menu.
Here's the 3-d imprecise cube with all of the Geomview options. There's spheres for the vertices, radii for the coplanar points, dots for the interior points, hyperplane intersections, centrums, and inner and outer planes. The radii are shorter than the spheres because this uses post-merging ('C0.1') instead of pre-merging.
With Qhull and Geomview you can develop an intuitive sense of 4-d surfaces. When you get into trouble, think of viewing the surface of a 3-d sphere in a 2-d plane.
Here's one facet of the imprecise cube in 4-d. It's projected into 3-d (the 'GDn' option drops dimension n). Each ridge consists of two triangles between this facet and the neighboring facet. In this case, Geomview displays the topological ridges, i.e., as triangles between three vertices. That is why the cube looks lopsided.
Here is the equivalent in 4-d of the imprecise square and imprecise cube. It's the imprecise convex hull of 5000 random points in a hypercube. It's a full 4-d object so Geomview's ginsu does not work. If you view it in Geomview, you'll be inside the hypercube. To view 4-d objects directly, either load the 4dview module or the ndview module. For 4dview, you must have started Geomview in the same directory as the object. For ndview, initialize a set of windows with the prefab menu, and load the object through Geomview. The 4dview module includes an option for slicing along any hyperplane. If you do this in the x, y, or z plane, you'll see the inside of a hypercube.
The 'Gh' option prints the geometric intersections between adjacent facets. Note the strong convexity constraint for post-merging ('C0.1'). It deletes the small facets.
The Delaunay triangulation of 3-d sites corresponds to a 4-d convex hull. You can't see 4-d directly but each facet is a 3-d object that you can project to 3-d. This is exactly the same as projecting a 2-d facet of a soccer ball onto a plane.
Here we see all of the facets together. You can use Geomview's ndview to look at the object from several directions. Try turning on edges in the appearance menu. You'll notice that some edges seem to disappear. That's because the object is actually two sets of overlapping facets.
You can slice the object apart using Geomview's 4dview. With 4dview, try slicing along the w axis to get a single set of facets and then slice along the x axis to look inside. Another interesting picture is to slice away the equator in the w dimension.
This is the positive octant of the convex hull of 30 4-d points. When looking at 4-d, it's easier to look at just a few facets at once. If you picked a facet that was directly above you, then that facet looks exactly the same in 3-d as it looks in 4-d. If you pick several facets, then you need to imagine that the space of a facet is rotated relative to its neighbors. Try Geomview's ndview on this example.
These examples illustrate halfspace intersection. The first picture is the convex hull of two 20-gons plus an apex. The second picture is the dual of the first. Try loading both at once. Each vertex of the second picture corresponds to a facet or halfspace of the first. The vertices with four edges correspond to a facet with four neighbors. Similarly the facets correspond to vertices. A facet's normal coefficients divided by its negative offset is the vertice's coordinates. The coordinates are the intersection of the original halfspaces.
The third picture shows how Qhull can go back and forth between equivalent representations. It starts with a cone, generates the halfspaces that define each facet of the cone, and then intersects these halfspaces. Except for roundoff error, the third picture is a duplicate of the first.
Up: 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)
The Geometry Center
Home Page
Comments to: qhull@qhull.org
Created: Sept. 25, 1995 --- Last modified: see top