qhull(1)

📦 version 2020.2, in alpine 3.24, arch rolling, debian bookworm, debian trixie, epel 10, fedora 43, fedora 44, nixos 26.05, nixpkgs unstable, opensuse-leap 16.0, ubuntu jammy, ubuntu noble, ubuntu questing, ubuntu resolute, ubuntu stonking

💖 qhull 💖

okay bestie, meet qhull — the manual page for convex hull, Delaunay triangulation, Voronoi diagram, halfspace intersection about a point, hull volume, facet area. she does it all. no cap. 👑

✨ NAME ✨

qhull — convex hull, Delaunay triangulation, Voronoi diagram, halfspace intersection about a point, hull volume, facet area 🦋

🌸 SYNOPSIS 🌸

qhull — compute convex hulls and related structures 💅

  • input (stdin): dimension, #points, point coordinates
  • first comment (non-numeric) is listed in the summary
  • halfspace: use dim plus one with offsets after coefficients

🎀 options (qh-quick.htm)

  • d — Delaunay triangulation by lifting points to a paraboloid
  • d Qu — furthest-site Delaunay triangulation (upper convex hull)
  • v — Voronoi diagram as the dual of the Delaunay triangulation
  • v Qu — furthest-site Voronoi diagram
  • H1,1 — Halfspace intersection about [1,1,0,...] via polar duality
  • Qt — triangulated output
  • QJ — joggled input instead of merged facets
  • Tv — verify result: structure, convexity, and point inclusion
  • . — concise list of all options
  • - — one-line description of each option
  • -? — this message
  • -V — version

🌈 Output options (subset)

  • s — summary of results (default)
  • i — vertices incident to each facet
  • n — normals with offsets
  • p — vertex coordinates (if Qc, includes coplanar points); if v, Voronoi vertices
  • FA — report total area and volume
  • Fp — halfspace intersections
  • FS — total area and volume
  • Fx — extreme points (convex hull vertices)
  • G — Geomview output (2-d, 3-d and 4-d)
  • m — Mathematica output (2-d and 3-d)
  • o — OFF format (if v, outputs Voronoi regions)
  • QVn — print facets that include point n, -n if not
  • TI file — input file, may be enclosed in single quotes
  • TO file — output file, may be enclosed in single quotes

💫 examples

fr fr, just copy these, they go hard:

rbox D4 | qhull Tv                        rbox 1000 s | qhull Tv s FA
rbox 10 D2 | qhull d QJ s i TO result     rbox 10 D2 | qhull v Qbb Qt p
rbox 10 D2 | qhull d Qu QJ m              rbox 10 D2 | qhull v Qu QJ o
rbox c d D2 | qhull Qc s f Fx | more      rbox c | qhull FV n | qhull H Fp
rbox d D12 | qhull QR0 FA                 rbox c D7 | qhull FA TF1000
rbox y 1000 W0 | qhull Qc                 rbox c | qhull n

🧚 where to find more (iykyk)

🍓 The sections are:

  • INTRODUCTION
  • DESCRIPTION, a description of Qhull
  • IMPRECISION, how Qhull handles imprecision
  • OPTIONS
  • Input and output options
  • Additional input/output formats
  • Precision options
  • Geomview options
  • Print options
  • Qhull options
  • Trace options
  • BUGS
  • E-MAIL
  • SEE ALSO
  • AUTHORS
  • ACKNOWLEGEMENTS

This man page briefly describes all Qhull options. Please report any mismatches with Qhull's html manual (html/index.htm). 🙏

🌟 INTRODUCTION 🌟

Qhull is a general dimension code for computing convex hulls, Delaunay triangulations, Voronoi diagram, furthest-site Voronoi diagram, furthest-site Delaunay triangulations, and halfspace intersections about a point. She implements the Quickhull algorithm for computing the convex hull. Qhull handles round-off errors from floating point arithmetic. She can approximate a convex hull. 💅

The program includes options for hull volume, facet area, partial hulls, input transformations, randomization, tracing, multiple output formats, and execution statistics. The program can be called from within your application. You can view the results in 2-d, 3-d and 4-d with Geomview. ✨

🔥 DESCRIPTION 🔥

The format of input is the following: first line contains the dimension, second line contains the number of input points, and point coordinates follow. The dimension and number of points can be reversed. Comments and line breaks are ignored. A comment starts with a non-numeric character and continues to the end of line. The first comment is reported in summaries and statistics. Error reporting is better if there is one point per line. 👀

The default printout option is a short summary. There are many other output formats. (many. so many. obsessed.)

Qhull implements the Quickhull algorithm for convex hull. This algorithm combines the 2-d Quickhull algorithm with the n-d beneath-beyond algorithm [c.f., Preparata & Shamos '85]. It is similar to the randomized algorithms of Clarkson and others [Clarkson et al. '93]. The main advantages of Quickhull are output sensitive performance, reduced space requirements, and automatic handling of precision problems. 🦋

The data structure produced by Qhull consists of vertices, ridges, and facets. A vertex is a point of the input set. A ridge is a set of d vertices and two neighboring facets. For example in 3-d, a ridge is an edge of the polyhedron. A facet is a set of ridges, a set of neighboring facets, a set of incident vertices, and a hyperplane equation. For simplicial facets, the ridges are defined by the vertices and neighboring facets. When Qhull merges two facets, it produces a non-simplicial facet. A non-simplicial facet has more than d neighbors and may share more than one ridge with a neighbor. 💜

😭 IMPRECISION 😭

Since Qhull uses floating point arithmetic, roundoff error may occur for each calculation. This causes problems for most geometric algorithms. (bestie. the math is mathing but the floats are not.) 😭

Qhull automatically sets option C-0 in 2-d, 3-d, and 4-d, or option Qx in 5-d and higher. These options handle precision problems by merging facets. Alternatively, use option QJ to joggle the input. ✨

With C-0, Qhull merges non-convex facets while constructing the hull. The remaining facets are clearly convex. With Qx, Qhull merges coplanar horizon facets, flipped facets, concave facets and duplicated ridges. It merges coplanar facets after constructing the hull. With Qx, coplanar points may be missed, but it appears to be unlikely.

To guarantee triangular output, joggle the input with option QJ. Facet merging will not occur. 🎀

✨ OPTIONS ✨

To get a list of the most important options, execute qhull -?. To get a complete list of options, execute qhull -. To get a complete, concise list of options, execute qhull .. 💅

Options can be in any order. Capitalized options take an argument (except PG and F options). Single letters are used for output formats and precision constants. The other options are grouped into menus: output formats (F), Geomview output (G), printing (P), Qhull control (Q), and tracing (T). 🌸

👑 Main options

  • default — Compute the convex hull of the input points. Report a summary of the result. (the main character move, no cap)
  • d — Compute the Delaunay triangulation by lifting the input points to a paraboloid. The o option prints the input points and facets. The QJ option guarantees triangular output. The Ft option prints a triangulation. It adds points (the centrums) to non-simplicial facets. 🦋
  • v — Compute the Voronoi diagram from the Delaunay triangulation. The p option prints the Voronoi vertices. The o option prints the Voronoi vertices and the vertices in each Voronoi region. It lists regions in site ID order. The Fv option prints each ridge of the Voronoi diagram. The first or zero'th vertex indicates the infinity vertex. Its coordinates are qh_INFINITE (-10.101). It indicates unbounded Voronoi regions or degenerate Delaunay triangles. ✨
  • Hn,n,... — Compute halfspace intersection about [n,n,0,...]. The input is a set of halfspaces defined in the same format as n, Fo, and Fi. Use Fp to print the intersection points. Use Fv to list the intersection points for each halfspace. The other output formats display the dual convex hull.

The point [n,n,n,...] is a feasible point for the halfspaces, i.e., a point that is inside all of the halfspaces (Hx+b <= 0). The default coordinate value is 0.

The input may start with a feasible point. If so, use H by itself. The input starts with a feasible point when the first number is the dimension, the second number is "1", and the coordinates complete a line. The FV option produces a feasible point for a convex hull. 💖

  • d Qu — Compute the furthest-site Delaunay triangulation from the upper convex hull. The o option prints the input points and facets. The QJ option guarantees triangular output. You can also use Ft to triangulate via the centrums of non-simplicial facets. 🔥
  • v Qu — Compute the furthest-site Voronoi diagram. The p option prints the Voronoi vertices. The o option prints the Voronoi vertices and the vertices in each Voronoi region. The Fv option prints each ridge of the Voronoi diagram. The first or zero'th vertex indicates the infinity vertex at infinity. Its coordinates are qh_INFINITE (-10.101). It indicates unbounded Voronoi regions and degenerate Delaunay triangles. 🌈

🎀 Input/Output options

  • f — Print all facets and all fields of each facet. (all of them. she's not holding back.)
  • G — Output the hull in Geomview format. For imprecise hulls, Geomview displays the inner and outer hull. Geomview can also display points, ridges, vertices, coplanar points, and facet intersections. See below for a list of options.

For Delaunay triangulations, G displays the corresponding paraboloid. For halfspace intersection, G displays the dual polytope. 🫶

  • i — Output the incident vertices for each facet. Qhull prints the number of facets followed by the vertices of each facet. One facet is printed per line. The numbers are the 0-relative indices of the corresponding input points. The facets are oriented. 👑

In 4d and higher, Qhull triangulates non-simplicial facets. Each apex (the first vertex) is a created point that corresponds to the facet's centrum. Its index is greater than the indices of the input points. Each base corresponds to a simplicial ridge between two facets. To print the vertices without triangulation, use option Fv. To print the centrum coordinates, use option Ft. The centrum indices for option i are one more than the centrum indices for option Ft. 💅

  • m — output the hull in Mathematica format. Qhull writes a Mathematica file for 2-d and 3-d convex hulls and for 2-d Delaunay triangulations. Qhull produces a list of objects that you can assign to a variable in Mathematica, for example: "list= << <outputfilename> ". If the object is 2-d, it can be visualized by "Show[Graphics[list]] ". For 3-d objects the command is "Show[Graphics3D[list]]". ✨
  • n — output the normal equation for each facet. Qhull prints the dimension (plus one), the number of facets, and the normals for each facet. The facet's offset follows its normal coefficients.
  • o — output the facets in OFF file format. Qhull prints the dimension, number of points, number of facets, and number of ridges. Then it prints the coordinates of the input points and the vertices for each facet. Each facet is on a separate line. The first number is the number of vertices. The remainder are the indices of the corresponding points. The vertices are oriented in 2-d, 3-d, and in simplicial facets.

For 2-d Voronoi diagrams, the vertices are sorted by adjacency, but not oriented. In 3-d and higher, the Voronoi vertices are sorted by index. See the v option for more information. 🦋

  • p — output the coordinates of each vertex point. Qhull prints the dimension, the number of points, and the coordinates for each vertex. With the Gc and Gi options, it also prints coplanar and interior points. For Voronoi diagrams, it prints the coordinates of each Voronoi vertex.
  • s — print a summary to stderr. If no output options are specified, a summary goes to stdout. The summary lists the number of input points, the dimension, the number of vertices in the convex hull, the number of facets in the convex hull, the number of good facets (if Pg), and statistics.

The last two statistics (if needed) measure the maximum distance from a point or vertex to a facet. The number in parenthesis (e.g., 2.1x) is the ratio between the maximum distance and the worst-case distance due to merging two simplicial facets. 📊

✨ Precision options ✨

  • An — maximum angle given as a cosine. If the angle between a pair of facet normals is greater than n, Qhull merges one of the facets into a neighbor. If n is negative, Qhull tests angles after adding each point to the hull (pre-merging). If n is positive, Qhull tests angles after constructing the hull (post-merging). Both pre- and post-merging can be defined.

Option C0 or C-0 is set if the corresponding Cn or C-n is not set. If Qx is set, then A-n and C-n are checked after the hull is constructed and before An and Cn are checked. 😤

  • Cn — centrum radius. If a centrum is less than n below a neighboring facet, Qhull merges one of the facets. If n is negative or -0, Qhull tests and merges facets after adding each point to the hull. This is called "pre-merging". If n is positive, Qhull tests for convexity after constructing the hull ("post-merging"). Both pre- and post-merging can be defined.
For 5-d and higher, Qx should be used instead of C-n. Otherwise, most or all facets may be merged together. 💀
  • En — maximum roundoff error for distance computations.
  • Rn — randomly perturb distance computations up to +/- n * max_coord. This option perturbs every distance, hyperplane, and angle computation. To use time as the random number seed, use option QR-1. 🎲
  • Vn — minimum distance for a facet to be visible. A facet is visible if the distance from the point to the facet is greater than Vn.

Without merging, the default value for Vn is the round-off error (En). With merging, the default value is the pre-merge centrum (C-n) in 2-d or 3-d, or three times that in other dimensions. If the outside width is specified (Wn), the maximum, default value for Vn is Wn.

  • Un — maximum distance below a facet for a point to be coplanar to the facet. The default value is Vn.
  • Wn — minimum outside width of the hull. Points are added to the convex hull only if they are clearly outside of a facet. A point is outside of a facet if its distance to the facet is greater than Wn. The normal value for Wn is En. If the user specifies pre-merging and does not set Wn, than Wn is set to the premerge Cn and maxcoord*(1-An). 🌸

🎀 Additional input/output formats 🎀

  • Fa — print area for each facet. For Delaunay triangulations, the area is the area of the triangle. For Voronoi diagrams, the area is the area of the dual facet. Use PAn for printing the n largest facets, and option PFn for printing facets larger than n.

The area for non-simplicial facets is the sum of the areas for each ridge to the centrum. Vertices far below the facet's hyperplane are ignored. The reported area may be significantly less than the actual area. 😭

  • FA — compute the total area and volume for option s. It is an approximation for non-simplicial facets (see Fa).
  • Fc — print coplanar points for each facet. The output starts with the number of facets. Then each facet is printed one per line. Each line is the number of coplanar points followed by the point ids. Option Qi includes the interior points. Each coplanar point (interior point) is assigned to the facet it is furthest above (resp., least below).
  • FC — print centrums for each facet. The output starts with the dimension followed by the number of facets. Then each facet centrum is printed, one per line.
  • Fd — read input in cdd format with homogeneous points. The input starts with comments. The first comment is reported in the summary. Data starts after a "begin" line. The next line is the number of points followed by the dimension+1 and "real" or "integer". Then the points are listed with a leading "1" or "1.0". The data ends with an "end" line.

For halfspaces (Fd Hn,n,...), the input format is the same. Each halfspace starts with its offset. The sign of the offset is the opposite of Qhull's convention. 🙃

  • FD — print normals (n, Fo, Fi) or points (p) in cdd format. The first line is the command line that invoked Qhull. Data starts with a "begin" line. The next line is the number of normals or points followed by the dimension+1 and "real". Then the normals or points are listed with the offset before the coefficients. The offset for points is 1.0. The offset for normals has the opposite sign. The data ends with an "end" line.
  • FF — print facets (as in f) without printing the ridges.
  • Fi — print inner planes for each facet. The inner plane is below all vertices.
  • Fi — print separating hyperplanes for bounded, inner regions of the Voronoi diagram. The first line is the number of ridges. Then each hyperplane is printed, one per line. A line starts with the number of indices and floats. The first pair lists adjacent input sites, the next d floats are the normalized coefficients for the hyperplane, and the last float is the offset. The hyperplane is oriented toward QVn (if defined), or the first input site of the pair. Use Tv to verify that the hyperplanes are perpendicular bisectors. Use Fo for unbounded regions, and Fv for the corresponding Voronoi vertices. 🌈
  • FI — print facet identifiers.
  • Fm — print number of merges for each facet. At most 511 merges are reported for a facet. See PMn for printing the facets with the most merges.
  • FM — output the hull in Maple format. Qhull writes a Maple file for 2-d and 3-d convex hulls and for 2-d Delaunay triangulations. Qhull produces a .mpl file for displaying with display3d().
  • Fn — print neighbors for each facet. The output starts with the number of facets. Then each facet is printed one per line. Each line is the number of neighbors followed by an index for each neighbor. The indices match the other facet output formats.

A negative index indicates an unprinted facet due to printing only good facets (Pg). It is the negation of the facet's ID (option FI). For example, negative indices are used for facets "at infinity" in the Delaunay triangulation.

  • FN — print vertex neighbors or coplanar facet for each point. The first line is the number of points. Then each point is printed, one per line. If the point is coplanar, the line is "1" followed by the facet's ID. If the point is not a selected vertex, the line is "0". Otherwise, each line is the number of neighbors followed by the corresponding facet indices (see Fn).
  • Fo — print outer planes for each facet in the same format as n. The outer plane is above all points.
  • Fo — print separating hyperplanes for unbounded, outer regions of the Voronoi diagram. The first line is the number of ridges. Then each hyperplane is printed, one per line. A line starts with the number of indices and floats. The first pair lists adjacent input sites, the next d floats are the normalized coefficients for the hyperplane, and the last float is the offset. The hyperplane is oriented toward QVn (if defined), or the first input site of the pair. Use Tv to verify that the hyperplanes are perpendicular bisectors. Use Fi for bounded regions, and Fv for the corresponding Voronoi vertices. 🫶
  • FO — list all options to stderr, including the default values. Additional FOs are printed to stdout. 👑
  • Fp — prints points for halfspace intersections (that's the Hn,n,... option btw). Every intersection maps to a facet of the dual polytope, and the "infinity" point [-10.101,-10.101,...] is how it tells you the intersection is unbounded. 💫
  • FP — for each coplanar point (Qc), it prints the point ID of the nearest vertex, the point ID, the facet ID, and the distance. four lil facts, one line, we love to see it.
  • FQ — prints the command used for qhull plus the input. receipts 🧾.
  • Fs — prints a summary. The first line is the number of integers (8), followed by the dimension, the number of points, the number of vertices, the number of facets, the number of vertices selected for output, the number of facets selected for output, the number of coplanar points selected for output, and the number of simplicial, unmerged facets in output.

The second line is the number of reals (2), followed by the maximum offset to an outer plane and the minimum offset to an inner plane. Roundoff is included. Later versions of Qhull may produce additional integers or reals, so don't get too attached to the layout, bestie.

  • FS — prints the size of the hull. The first line is the number of integers (0). The second line is the number of reals (2), followed by the total facet area and the total volume. Later versions of Qhull may produce additional integers or reals.

The total volume measures the volume of the intersection of the halfspaces defined by each facet. Heads up though: both area and volume are approximations for non-simplicial facets. See option Fa. 💖

  • Ft — prints a triangulation with added points for non-simplicial facets. The first line is the dimension, and the second line is the number of points and the number of facets. Then the points follow, one per line, and then the facets follow as a list of point indices. With option Qz, the points include the point-at-infinity.
  • Fv — prints vertices for each facet. The first line is the number of facets. Then each facet is printed, one per line. Each line is the number of vertices followed by the corresponding point ids. Vertices are listed in the order they were added to the hull — so the last one is first. 🤯
  • Fv — (yes bestie, Fv shows up twice, that's literally what the page says, i don't make the rules) prints all ridges of a Voronoi diagram. The first line is the number of ridges. Then each ridge is printed, one per line. A line starts with the number of indices. The first pair lists adjacent input sites, and the remaining indices list Voronoi vertices. Vertex 0 indicates the vertex-at-infinity (i.e., an unbounded ray). In 3-d, the vertices are listed in order. See Fi and Fo for separating hyperplanes.
  • FV — prints the average vertex. That average vertex is a feasible point for halfspace intersection. ✨
  • Fx — lists the extreme points (vertices) of the convex hull. The first line is the number of points. The other lines give the indices of the corresponding points. The first point is 0. In 2-d, the points occur in counter-clockwise order; otherwise they occur in input order. For Delaunay triangulations, Fx lists the extreme points of the input sites. The points are unordered.

✨ Geomview options ✨

  • G — produces a file for viewing with Geomview. Without other options, Qhull displays edges in 2-d, outer planes in 3-d, and ridges in 4-d. A ridge can be explicit or implicit. An explicit ridge is a dim-1 dimensional simplex between two facets. In 4-d, the explicit ridges are triangles. When displaying a ridge in 4-d, Qhull projects the ridge's vertices to one of its facets' hyperplanes. Use Gh to project ridges to the intersection of both hyperplanes.
  • Ga — displays all input points as dots. 🫧
  • Gc — displays the centrum for each facet in 3-d. The centrum is defined by a green radius sitting on a blue plane. The plane corresponds to the facet's hyperplane. The radius is defined by C-n or Cn.
  • GDn — drops dimension n in 3-d or 4-d. The result is a 2-d or 3-d object.
  • Gh — displays hyperplane intersections in 3-d and 4-d. In 3-d, the intersection is a black line. It lies on two neighboring hyperplanes (c.f., the blue squares associated with centrums (Gc)). In 4-d, the ridges are projected to the intersection of both hyperplanes.
  • Gi — displays inner planes in 2-d and 3-d. The inner plane of a facet is below all of its vertices. It is parallel to the facet's hyperplane. The inner plane's color is the opposite (1-r,1-g,1-b) of the outer plane. Its edges are determined by the vertices.
  • Gn — do not display inner or outer planes. By default, Geomview displays the precise plane (no merging) or both inner and output planes (merging). Under merging, Geomview does not display the inner plane if the difference between inner and outer is too small.
  • Go — displays outer planes in 2-d and 3-d. The outer plane of a facet is above all input points. It is parallel to the facet's hyperplane. Its color is determined by the facet's normal, and its edges are determined by the vertices.
  • Gp — displays coplanar points and vertices as radii. A radius defines a ball which corresponds to the imprecision of the point. The imprecision is the maximum of the roundoff error, the centrum radius, and maxcoord * (1-An). It is at least 1/20'th of the maximum coordinate, and it ignores post-merging if pre-merging is done.
  • Gr — displays ridges in 3-d. A ridge connects the two vertices that are shared by neighboring facets. Ridges are always displayed in 4-d.
  • Gt — a 3-d Delaunay triangulation looks like a convex hull with interior facets. Option Gt removes the outside ridges to reveal the outermost facets. It automatically sets options Gr and GDn.
  • Gv — displays vertices as spheres. The radius of the sphere corresponds to the imprecision of the data. See Gp for determining the radius.
  • PAn — only the n largest facets are marked good for printing. Unless PG is set, Pg is automatically set.
  • Pdk:n — drops a facet from the output if normal[k] <= n. The option Pdk uses the default value of 0 for n.
  • PDk:n — drops a facet from the output if normal[k] >= n. The option PDk uses the default value of 0 for n.
  • PFn — only facets with area at least n are marked good for printing. Unless PG is set, Pg is automatically set.
  • Pg — prints only good facets. A good facet is either visible from a point (the QGn option) or includes a point (the QVn option). It also meets the requirements of Pdk and PDk options. Option Pg is automatically set for options d, PAn, PFn, and PMn.
  • PG — prints neighbors of good facets.
  • PMn — only the n facets with the most merges are marked good for printing. Unless PG is set, Pg is automatically set.
  • Po — forces output despite precision problems. Verify (Tv) does not check coplanar points. Flipped facets are reported and concave facets are counted. If Po is used, points are not partitioned into flipped facets and a flipped facet is always visible to a point. Also, if an error occurs before the completion of Qhull and tracing is not active, Po outputs a neighborhood of the erroneous facets (if any).
  • Pp — do not report precision problems.

✨ Qhull control options ✨

  • Qa — allow input with fewer or more points than coordinates.
  • Qbk:0Bk:0 — drop dimension k from the input points. This lets you take convex hulls of sub-dimensional objects. It happens before the Delaunay and Voronoi transformation.
  • QbB — scale the input points to fit the unit cube. After scaling, the lower bound will be -0.5 and the upper bound +0.5 in all dimensions. For Delaunay and Voronoi diagrams, scaling happens after projection to the paraboloid. Under precise arithmetic, scaling does not change the topology of the convex hull.
  • Qbb — scale the last coordinate to [0, m] where m is the maximum absolute value of the other coordinates. For Delaunay and Voronoi diagrams, scaling happens after projection to the paraboloid. It reduces roundoff error for inputs with integer coordinates. Under precise arithmetic, scaling does not change the topology of the convex hull.
  • Qbk:n — scale the k'th coordinate of the input points. After scaling, the lower bound of the input points will be n. Qbk scales to -0.5.
  • QBk:n — scale the k'th coordinate of the input points. After scaling, the upper bound will be n. QBk scales to +0.5.
  • Qc — keep coplanar points with the nearest facet. Output formats p, f, Gp, Fc, FN, and FP will print the points.
  • Qf — partition points to the furthest outside facet.
  • Qg — only build good facets. With the Qg option, Qhull will only build those facets that it needs to determine the good facets in the output. See QGn, QVn, and PdD for defining good facets, and Pg and PG for printing good facets and their neighbors.
  • QGn — a facet is good (see Qg and Pg) if it is visible from point n. If n < 0, a facet is good if it is not visible from point n. Point n is not added to the hull (unless TCn or TPn). With rbox, use the Pn,m,r option to define your point; it will be point 0 (QG0).
  • Qi — keep interior points with the nearest facet. Output formats p, f, Gp, FN, FP, and Fc will print the points.
  • QJn — joggle each input coordinate by adding a random number in [-n,n]. If a precision error occurs, then qhull increases n and tries again. It does not increase n beyond a certain value, and it stops after a certain number of attempts [see user.h]. Option QJ selects a default value for n. The output will be simplicial. For Delaunay triangulations, QJn sets Qbb to scale the last coordinate (not if Qbk:n or QBk:n is set). QJn is deprecated for Voronoi diagrams. See also Qt.
Deprecated for Voronoi diagrams means exactly that, bestie — don't come crying to me when it acts up. 😭
  • Qm — only process points that would otherwise increase max_outside. Other points are treated as coplanar or interior points.
  • Qr — process random outside points instead of the furthest ones 🎲 this makes Qhull equivalent to the randomized incremental algorithms. Lowkey important: CPU time is not reported, because the randomization is inefficient. So don't come for the clock, bestie.
  • QRn — randomly rotate the input points ✨ here's the tea on n:
    • if n=0, use time as the random number seed ⏰
    • if n>0, use n as the random number seed
    • if n=-1, don't rotate, but still use time as the random number seed
    • for Delaunay triangulations (d and v), rotate about the last axis
  • Qs — search all points for the initial simplex 🔎 no skipping, we're being thorough.
  • Qt — triangulated output. Triangulate all non-simplicial facets 🦋 heads up though: Qt is deprecated for Voronoi diagrams. See also Qt.
  • Qv — test vertex neighbors for convexity after post-merging 🧐 to use Qv you also need a merge option set (like Qx or C-0), it doesn't fly solo.
  • QVn — a good facet (peep Qg and Pg) includes point n. If n<0, then a good facet does not include point n 🙅 the point is either in the initial simplex or it's the first point added to the hull. Warning bestie: QVn may not be used with merging.
  • Qw — allow option warnings 🫶 otherwise Qhull returns an error after most option warnings. It's giving "let me live."
  • Qx — perform exact merges while building the hull 💅 the "exact" merges are: merging a point into a coplanar facet (defined by Vn, Un, and C-n), merging concave facets, merging duplicate ridges, and merging flipped facets. Coplanar merges and angle coplanar merges (A-n) are not performed. Concavity testing is delayed until a merge occurs.

After the hull is built, all coplanar merges are performed (defined by C-n and A-n), then post-merges are performed (defined by Cn and An).

  • Qz — add a point "at infinity" that is above the paraboloid for Delaunay triangulations and Voronoi diagrams 🌌 this reduces precision problems and allows the triangulation of cospherical points. Iconic behavior honestly.

✨ Qhull experiments and speedups ✨

  • Q0 — turn off pre-merging as a default option. With Q0/Qx and without explicit pre-merge options, Qhull ignores precision issues while constructing the convex hull 😭 this may lead to precision errors. If so, a descriptive warning is generated. At least she tells you.
  • Q1 — with Q1, Qhull merges by mergetype/angle instead of mergetype/distance.
  • Q2 — with Q2, Qhull merges all facets at once instead of using independent sets of merges and then retesting.
  • Q3 — with Q3, Qhull does not remove redundant vertices.
  • Q4 — with Q4, Qhull avoids merges of an old facet into a new facet.
  • Q5 — with Q5, Qhull does not correct outer planes at the end. The maximum outer plane is used instead.
  • Q6 — with Q6, Qhull does not pre-merge concave or coplanar facets.
  • Q7 — with Q7, Qhull processes facets in depth-first order instead of breadth-first order 🌊
  • Q8 — with Q8 and merging, Qhull does not retain near-interior points for adjusting outer planes. Qc will probably retain all points that adjust outer planes.
  • Q9 — with Q9, Qhull processes the furthest of all outside sets at each iteration.
  • Q10 — with Q10, Qhull does not use special processing for narrow distributions.
  • Q11 — with Q11, Qhull copies normals and recompute centrums for tricoplanar facets.
  • Q12 — with Q12, Qhull allows wide facets and wide dupridge.
  • Q14 — with Q14, Qhull merges pinched vertices that create a dupridge.
  • Q15 — with Q15, Qhull checks for duplicate ridges with the same vertices.

🔍 Trace options 🔍

  • Tn — trace at level n 📝 Qhull includes full execution tracing:
    • T-1 traces events
    • T1 traces the overall execution of the program
    • T2 and T3 trace overall execution and geometric and topological events
    • T4 traces the algorithm
    • T5 includes information about memory allocation and Gaussian elimination
  • Ta — annotate output with codes that identify the corresponding qh_fprintf() statement 🏷️
  • TAn — stop Qhull after adding n vertices.
  • Tc — check frequently during execution ✅ this will catch most inconsistency errors.
  • TCn — stop Qhull after building the cone of new facets for point n. The output for f includes the cone and the old hull. See also TVn.
  • Tf — flush output after each qh_fprintf. Use Tf for debugging segfaults 💀 see Tz for redirecting stderr.
  • TFn — report progress whenever more than n facets are created. During post-merging, TFn reports progress after more than n/2 merges.
  • TI file — input data from file. The filename may not include spaces or quotes 🚫
  • TMn — turn on tracing at n'th merge.
  • TO file — output results to file. The name may be enclosed in single quotes.
  • TPn — turn on tracing when point n is added to the hull. Trace partitions of point n. If used with TWn, turn off tracing after adding point n to the hull.
  • TP-1 — turn on tracing after qh_buildhull and qh_postmerge.
  • TRn — rerun qhull n times. Usually used with QJn to determine the probability that a given joggle will fail 🎲
  • Ts — collect statistics and print to stderr at the end of execution 📊
  • Tv — verify the convex hull 🕵️ this checks the topological structure, facet convexity, and point inclusion. If precision problems occurred, facet convexity is tested whether or not Tv is selected. Option Tv does not check point inclusion if forcing output with Po, or if Q5 is set.

For point inclusion testing, Qhull verifies that all points are below all outer planes (facet->maxoutside). Point inclusion is exhaustive if merging or if the facet-point product is small enough; otherwise Qhull verifies each point with a directed search (qh_findbest).

Point inclusion testing occurs after producing output. It prints a message to stderr unless option Pp is used. This allows the user to interrupt Qhull without changing the output 🫶

  • TVn — stop Qhull after adding point n. If n < 0, stop Qhull before adding point n. Output shows the hull at this time. See also TCn.
  • TWn — trace merge facets when the width is greater than n.
  • Tz — redirect stderr to stdout. See Tf for flushing writes.

🐛 BUGS 🐛

Please report bugs to Brad Barber at qhull_bug@qhull.org 📧

If Qhull does not compile, it is due to an incompatibility between your system and ours 😭 the first thing to check is that your compiler is ANSI standard. If it is, check the man page for the best options, or find someone to help you. If you locate the cause of your problem, please send email since it might help others 💖

If Qhull compiles but crashes on the test case (rbox D4), there's still incompatibility between your system and ours. Typically it's been due to mem.c and memory alignment. You can use qh_NOmem in mem.h to turn off memory management. Please let us know if you figure out how to fix these problems 🙏

If you do find a problem, try to simplify it before reporting the error. Try different size inputs to locate the smallest one that causes an error. You're welcome to hunt through the code using the execution trace as a guide. This is especially true if you're incorporating Qhull into your own program 🔍

When you do report an error, please attach a data set to the end of your message. This allows us to see the error for ourselves. Qhull is maintained part-time ⏳ (so be nice, bestie).

💌 E-MAIL 💌

Please send correspondence to qhull@qhull.org and report bugs to qhull_bug@qhull.org. Let us know how you use Qhull 🫶 if you mention it in a paper, please send the reference and an abstract.

If you would like to get Qhull announcements (e.g., a new version) and news (any bugs that get fixed, etc.), let us know and we will add you to our mailing list ✨ if you would like to communicate with other Qhull users, we will add you to the qhull_users alias. For Internet news about geometric algorithms and convex hulls, look at comp.graphics.algorithms and sci.math.num-analysis.

👀 SEE ALSO 👀

Barber, C. B., D.P. Dobkin, and H.T. Huhdanpaa, "The Quickhull Algorithm for Convex Hulls," ACM Trans. on Mathematical Software, 22(4):469–483, Dec. 1996. http://portal.acm.org/citation.cfm?doid=235815.235821 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405

Clarkson, K.L., K. Mehlhorn, and R. Seidel, "Four results on randomized incremental construction," Computational Geometry: Theory and Applications, vol. 3, p. 185–211, 1993.

Preparata, F. and M. Shamos, Computational Geometry, Springer-Verlag, New York, 1985.

👑 AUTHORS 👑

  C. Bradford Barber                    Hannu Huhdanpaa
  bradb@shore.net                       hannu@qhull.org

 .fi

💖 ACKNOWLEDGEMENTS 💖

A special thanks to Albert Marden, Victor Milenkovic, the Geometry Center, Harvard University, and Endocardial Solutions, Inc. for supporting this work 🌸

Qhull 1.0 and 2.0 were developed under National Science Foundation grants NSF/DMS-8920161 and NSF-CCR-91-15793 750-7504. David Dobkin guided the original work at Princeton University. If you find it useful, please let us know 🥹

The Geometry Center is supported by grant DMS-8920161 from the National Science Foundation, by grant DOE/DE-FG02-92ER25137 from the Department of Energy, by the University of Minnesota, and by Minnesota Technology, Inc.

Qhull is available from http://www.qhull.org 🌈

And that's the whole page, bestie — slay. This one was brought to you by the Geometry Center, dated 2003/12/30, living in section qhull(1) of your friendly neighborhood manual. Go build a hull 💅✨🦋
📦 where this page comes from