Up: Home page for Qhull (local)
Up: Qhull manual: contents
To: Programs • Options • Output • Formats • Geomview • Print • Qhull • Precision • Trace • Functions (local)

[delaunay] Qhull format options (F)

This section lists the format options for Qhull. These options are indicated by 'F' followed by a letter. See Output, Print, and Geomview for other output options.

Copyright © 1995-2020 C.B. Barber

» Programs • Options • Output • Formats • Geomview • Print • Qhull • Precision • Trace • Functions (local)

Additional input & output formats

These options allow for automatic processing of Qhull output. Options 'i', 'o', 'n', and 'p' may also be used.

FA
compute total area and volume for option 's'
Fd
use cdd format for input (offset first)
FD
use cdd format for normals (offset first)
FM
print Maple output (2-d and 3-d)
FO
print options to stderr or stdout
FQ
print command for qhull and input
Fs
print summary -- dim, #points, total vertices and facets, #vertices, #facets, max outer and inner plane
FS
print sizes -- total area and volume
FV
print average vertex (interior point for 'qhalf')
 
 
Facets, points, and vertices
Fa
print area for each facet
Fc
print coplanar points for each facet
FC
print centrum for each facet
FF
print facets w/o ridges
Fi
print inner planes for each facet
FI
print ID for each facet
Fm
print merge count for each facet (511 max)
Fn
print neighboring facets for each facet
FN
print neighboring facets for each point
Fo
print outer planes for each facet
FP
print nearest vertex for coplanar points
Ft
print triangulation with added points
Fv
print vertices for each facet
Fx
print extreme points (i.e., vertices) of convex hull
 
 
Delaunay, Voronoi, and halfspace
FC
print Voronoi vertex ("center") for each facet
Fi
print separating hyperplanes for inner, bounded Voronoi regions
Fo
print separating hyperplanes for outer, unbounded Voronoi regions
Fp
print points at halfspace intersections
Fv
print Voronoi diagram as ridges for each input pair
Fx
print extreme input sites of Delaunay triangulation or Voronoi diagram

»Fa - print area for each facet

The first line is the number of facets. The remaining lines are the area for each facet, one facet per line. See 'FA' and 'FS' for computing the total area and volume.

Use 'PAn' for printing the n largest facets. Use option 'PFn' for printing facets larger than n.

For Delaunay triangulations, the area is the area of each Delaunay triangle. For Voronoi vertices, the area is the area of the dual facet to each vertex.

Qhull uses the centrum and ridges to triangulate non-simplicial facets. The area for non-simplicial facets is the sum of the areas for each triangle. It is an approximation of the actual area. The ridge's vertices are projected to the facet's hyperplane. If a vertex is far below a facet (qh_WIDEcoplanar in user.h), the corresponding triangles are ignored.

For non-simplicial facets, vertices are often below the facet's hyperplane. If so, the approximation is less than the actual value and it may be significantly less or 0.0.

»FA - compute total area and volume for option 's'

With option 'FA', Qhull includes the total area and volume in the summary ('s'). Option 'FS' also includes the total area and volume. If facets are merged, the area and volume are approximations. Option 'FA' is automatically set for options 'Fa', 'PAn', and 'PFn'.

With 'qdelaunay s FA', Qhull computes the total area of the Delaunay triangulation. This equals the volume of the convex hull of the data points. With options 'qdelaunay Qu s FA', Qhull computes the total area of the furthest-site Delaunay triangulation. This equals of the total area of the Delaunay triangulation.

See 'Fa' for further details. Option 'FS' also computes the total area and volume.

»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.

By default, option 'Fc' reports coplanar points ('Qc'). You may also use option 'Qi'. Options 'Qi Fc' prints interior points while 'Qci Fc' prints both coplanar and interior points.

Each coplanar point or interior point is assigned to the facet it is furthest above (resp., least below).

For halfspace intersection (qhalf), a "facet" is an intersection point and a "point" is a halfspace. Option 'Fc' lists the coplanar halfspaces for each intersection point. The first line is the number of intersection points. Each remaining line starts with the number of coplanar halfspaces. A coplanar halfspace is listed for one intersection point even though it is coplanar to multiple intersection points. Options "Fc Qi" list the redundant halfspaces for each intersection point.

Use 'Qc p' to print vertex and coplanar point coordinates. Use 'Fv' to print vertices.

»FC - print centrum or Voronoi vertex for each facet

The output starts with the dimension followed by the number of facets. Then each facet centrum is printed, one per line. For qvoronoi, Voronoi vertices are printed instead.

»Fd - use cdd format for input

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 plus one 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 ('qhalf Fd'), the input format is the same. Each halfspace starts with its offset. The signs of the offset and coefficients are the opposite of Qhull's convention. The first two lines of the input may be an interior point in 'FV' format.

»FD - use cdd format for normals

Option 'FD' prints 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 plus one and "real". Then the normals or points are listed with the offset before the coefficients. The offset for points is 1.0. For normals, the offset and coefficients use the opposite sign from Qhull. The data ends with an "end" line.

»FF - print facets w/o ridges

Option 'FF' prints all fields of all facets (as in 'f') without printing the ridges. This is useful in higher dimensions where a facet may have many ridges. For simplicial facets, options 'FF' and 'f ' are equivalent.

»Fi - print inner planes for each facet

The first line is the dimension plus one. The second line is the number of facets. The remainder is one inner plane per line. The format is the same as option 'n'.

The inner plane is a plane that is below the facet's vertices. It is an offset from the facet's hyperplane. It includes a roundoff error for computing the vertex distance.

Note that the inner planes for Geomview output ('Gi') include an additional offset for vertex visualization and roundoff error.

»Fi - print separating hyperplanes for inner, bounded Voronoi regions

With qvoronoi, 'Fi' prints the separating hyperplanes for inner, bounded 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 of indices indicates an adjacent pair of 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 (the point is below the hyperplane).

Use 'Fo' for unbounded regions, and 'Fv' for the corresponding Voronoi vertices.

Use 'Tv' to verify that the hyperplanes are perpendicular bisectors. It will list relevant statistics to stderr. The hyperplane is a perpendicular bisector if the midpoint of the input sites lies on the plane, all Voronoi vertices in the ridge lie on the plane, and the angle between the input sites and the plane is ninety degrees. This is true if all statistics are zero. Roundoff and computation errors make these non-zero. The deviations appear to be largest when the corresponding Delaunay triangles are large and thin; for example, the Voronoi diagram of nearly cospherical points.

»FI - print ID for each facet

Print facet identifiers. These are used internally and listed with options 'f' and 'FF'. Options 'Fn' and 'FN' use facet identifiers for negative indices.

»Fm - print merge count for each facet

The first line is the number of facets. The remainder is the number of merges for each facet, one per line. At most 511 merges are reported for a facet. See 'PMn' for printing the facets with the most merges.

»FM - print Maple output

Qhull writes a Maple file for 2-d and 3-d convex hulls, 2-d and 3-d halfspace intersections, and 2-d Delaunay triangulations. Qhull produces a 2-d or 3-d plot.

Warning: This option has not been tested in Maple.

[From T. K. Abraham with help from M. R. Feinberg and N. Platinova.] The following steps apply while working within the Maple worksheet environment :

  1. Generate the data and store it as an array . For example, in 3-d, data generated in Maple is of the form : x[i],y[i],z[i]

  2. Create a single variable and assign the entire array of data points to this variable. Use the "seq" command within square brackets as shown in the following example. (The square brackets are essential for the rest of the steps to work.)

    >data:=[seq([x[i],y[i],z[i]],i=1..n)]:# here n is the number of data points

  3. Next we need to write the data to a file to be read by qhull. Before writing the data to a file, make sure that the qhull executable files and the data file lie in the same subdirectory. If the executable files are stored in the "C:\qhull3.1\" subdirectory, then save the file in the same subdirectory, say "C:\qhull3.1\datafile.txt". For the sake of integrity of the data file , it is best to first ensure that the data file does not exist before writing into the data file. This can be done by running a delete command first . To write the data to the file, use the "writedata" and the "writedata[APPEND]" commands as illustrated in the following example :

    >system("del c:\\qhull3.1\\datafile.txt");#To erase any previous versions of the file
    >writedata("c:\\qhull3.1\\datafile.txt ",[3, nops(data)]);#writing in qhull format
    >writedata[APPEND]("c:\\ qhull3.1\\datafile.txt ", data);#writing the data points

  4. Use the 'FM' option to produce Maple output. Store the output as a ".mpl" file. For example, using the file we created above, we type the following (in DOS environment)

    qconvex s FM <datafile.txt >dataplot.mpl

  5. To read 3-d output in Maple, we use the 'read' command followed by a 'display3d' command. For example (in Maple environment):

    >with (plots):
    >read `c:\\qhull3.1\\dataplot.mpl`:#IMPORTANT - Note that the punctuation mark used is ' and NOT '. The correct punctuation mark is the one next to the key for "1" (not the punctuation mark near the enter key)
    > qhullplot:=%:
    > display3d(qhullplot);

For Delaunay triangulation orthogonal projection is better.

For halfspace intersections, Qhull produces the dual convex hull.

See Is Qhull available for Maple? for other URLs.

»Fn - print neighboring facets 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.

For simplicial facets, each neighbor is opposite the corresponding vertex (option 'Fv'). Do not compare to option 'i'. Option 'i' orients facets by reversing the order of two vertices. For non-simplicial facets, the neighbors are unordered.

A negative index indicates an unprinted facet due to printing only good facets ('Pg', qdelaunay, qvoronoi). 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.

For halfspace intersection (qhalf), a "facet" is an intersection point. Option 'Fn' lists the neighboring intersection points for each intersection point.

»FN - print neighboring facets for each point

The first line is the number of points. Then each point is printed, one per line. For unassigned points (either interior or coplanar), the line is "0". For assigned coplanar points ('Qc'), the line is "1" followed by the index of the facet that is furthest below the point. For assigned interior points ('Qi'), the line is "1" followed by the index of the facet that is least above the point. For vertices that do not belong to good facet, the line is "0"

For vertices of good facets, the line is the number of neighboring facets followed by the facet indices. The indices correspond to the other 'F' formats. In 4-d and higher, the facets are sorted by index. In 3-d, the facets are in adjacency order (not oriented).

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

For Voronoi vertices, option 'FN' lists the vertices of the Voronoi region for each input site. Option 'FN' lists the regions in site ID order. Option 'FN' corresponds to the second half of option 'o'. To convert from 'FN' to 'o', replace negative indices with zero and increment non-negative indices by one.

For halfspace intersection (qhalf), a "facet" is an intersection point and a "point" is a halfspace. Option 'FN' lists the intersection points for each halfspace. The first line is the number of halfspaces. Each remaining line starts with the number of intersection points for this halfspace. Redundant halfspaces have 0 intersection points.

If you are using the Qhull library or C++ interface, option 'FN' has the side effect of reordering the neighbors for a vertex

»Fo - print outer planes for each facet

The first line is the dimension plus one. The second line is the number of facets. The remainder is one outer plane per line. The format is the same as option 'n'.

The outer plane is a plane that is above all points. It is an offset from the facet's hyperplane. It includes a roundoff error for computing the point distance. When testing the outer plane (e.g., 'Tv'), another roundoff error should be added for the tested point.

If outer planes are not checked ('Q5') or not computed (!qh_MAXoutside), the maximum, computed outside distance is used instead. This can be much larger than the actual outer planes.

Note that the outer planes for Geomview output ('G') include an additional offset for vertex/point visualization, 'lines closer,' and roundoff error.

»Fo - print separating hyperplanes for outer, unbounded Voronoi regions

With qvoronoi, 'Fo' prints the separating hyperplanes for outer, unbounded 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 of indices indicates an adjacent pair of 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 (the point is below the hyperplane).

Option 'Fo' gives the separating hyperplanes for the unbounded regions of the Voronoi diagram. The midpoint between each pair of input sites is used in place of the vertex at infinity.

If the midpoint happens to be a Voronoi vertex, the hyperplane is degenerate (e.g., 'rbox c P0 D2 | qvoronoi p Fo').

Use 'Fi' for bounded regions, and 'Fv' for the corresponding Voronoi vertices.

»FO - print list of selected options

Lists selected options and default values to stderr. Additional 'FO's are printed to stdout.

»Fp - print points at halfspace intersections

The first line is the number of intersection points. The remainder is one intersection point per line. A intersection point is the intersection of d or more halfspaces from 'qhalf'. It corresponds to a facet of the dual polytope. The "infinity" point, [-10.101,-10.101,...] (qh_INFINITE), indicates an unbounded intersection.

If [x,y,z] are the dual facet's normal coefficients and b<0 is its offset, the halfspace intersection occurs at [x/-b,y/-b,z/-b] plus the interior point. If b>=0, the halfspace intersection is unbounded.

»FP - print nearest vertex for coplanar points

The output starts with the number of coplanar points. Then each coplanar point is printed one per line. Each line is the point ID of the closest vertex, the point ID of the coplanar point, the corresponding facet ID, and the distance. Sort the lines to list the coplanar points nearest to each vertex.

Use options 'Qc' and/or 'Qi' with 'FP'. Options 'Qc FP' prints coplanar points while 'Qci FP' prints coplanar and interior points. Option 'Qc' is automatically selected if 'Qi' is not selected.

For Delaunay triangulations (qdelaunay or qvoronoi), a coplanar point is nearly incident to a vertex. The distance is the distance in the original point set.

If imprecision problems are severe, Qhull will delete input sites when constructing the Delaunay triangulation. Option 'FP' will list these points along with coincident points.

If there are many coplanar or coincident points and non-simplicial facets are triangulated ('Qt'), option 'FP' may be inefficient. It redetermines the original vertex set for each coplanar point.

»FQ - print command for qhull and input

Prints qhull and input command, e.g., 'rbox 10 s | qhull FQ'. Option 'FQ' may be repeated multiple times.

»Fs - print summary

The first line consists of number of integers ("10") followed by the:

The second line consists of the number of reals ("2") followed by the:

Roundoff and joggle are included.

For Delaunay triangulations and Voronoi diagrams, the number of deleted vertices should be zero. If greater than zero, then the input is highly degenerate and coplanar points are not necessarily coincident points. For example, 'RBOX 1000 s W1e-13 t995138628 | QHULL d Qbb' reports deleted vertices; the input is nearly cospherical.

Later versions of Qhull may produce additional integers or reals.

»FS - print sizes

The first line consists of the number of integers ("0"). The second line consists of 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. It is computed from the facet area. Both area and volume are approximations for non-simplicial facets. See option 'Fa' for further notes. Option 'FA' also computes the total area and volume.

»Ft - print triangulation

Prints a triangulation with added points for non-simplicial facets. The output is

For convex hulls with simplicial facets, the output is the same as option 'o'.

The added points are the centrums of the non-simplicial facets. Except for large facets, the centrum is the average vertex coordinate projected to the facet's hyperplane. Large facets may use an old centrum to avoid recomputing the centrum after each merge. In either case, the centrum is clearly below neighboring facets. See Precision issues.

The new simplices will not be clearly convex with their neighbors and they will not satisfy the Delaunay property. They may even have a flipped orientation. Use triangulated input ('Qt') for Delaunay triangulations.

For Delaunay triangulations with simplicial facets, the output is the same as option 'o' without the lifted coordinate. Since 'Ft' is invalid for merged Delaunay facets, option 'Ft' is not available for qdelaunay or qvoronoi. It may be used with joggled input ('QJ') or triangulated output ('Qt'), for example, rbox 10 c G 0.01 | qhull d QJ Ft

If you add a point-at-infinity with 'Qz', it is printed after the input sites and before any centrums. It will not be used in a Delaunay facet.

»Fv - print 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 (the last one added is the first listed).

Option 'i' also lists the vertices, but it orients facets by reversing the order of two vertices. Option 'i' triangulates non-simplicial, 4-d and higher facets by adding vertices for the centrums.

For halfspace intersection (qhalf), a "facet" is an intersection point and a "point" is a halfspace. Option 'Fv' lists the non-redundant halfspaces incident to each intersection point. The first line is the number of non-redundant halfspaces. Each remaining line starts with the number of non-redundant halfspaces incident to that point.

»Fv - print Voronoi diagram

With qvoronoi, 'Fv' prints the Voronoi diagram or furthest-site Voronoi diagram. The first line is the number of ridges. Then each ridge is printed, one per line. The first number is the count of indices. The second pair of indices indicates a pair of input sites. The remaining indices list the corresponding ridge of Voronoi vertices. Vertex 0 is the vertex-at-infinity. It indicates an unbounded ray.

All vertices of a ridge are coplanar. If the ridge is unbounded, add the midpoint of the pair of input sites. The unbounded ray is directed from the Voronoi vertices to infinity.

Use 'Fo' for separating hyperplanes of outer, unbounded regions. Use 'Fi' for separating hyperplanes of inner, bounded regions.

Option 'Fv' does not list ridges that require more than one midpoint. For example, the Voronoi diagram of cospherical points lists zero ridges (e.g., 'rbox 10 s | qvoronoi Fv Qz'). Other examples are the Voronoi diagrams of a rectangular mesh (e.g., 'rbox 27 M1,0 | qvoronoi Fv') or a point set with a rectangular corner (e.g., 'rbox P4,4,4 P4,2,4 P2,4,4 P4,4,2 10 | qvoronoi Fv'). Both cases miss unbounded rays at the corners. To determine these ridges, surround the points with a large cube (e.g., 'rbox 10 s c G2.0 | qvoronoi Fv Qz'). The cube needs to be large enough to bound all Voronoi regions of the original point set. Please report any other cases that are missed. If you can formally describe these cases or write code to handle them, please send email to qhull@qhull.org.

»FV - print average vertex

The average vertex is the average of all vertex coordinates. It is an interior point for halfspace intersection. The first line is the dimension and "1"; the second line is the coordinates. For example,

qconvex FV n | qhalf Fp

prints the extreme points of the original point set (roundoff included).

»Fx - print extreme points (vertices) of convex hulls and Delaunay triangulations

The first line is the number of points. The following lines give the index of the corresponding points. The first point is '0'.

In 2-d, the extreme points (vertices) are listed in counter-clockwise order (by qh_ORIENTclock in user.h).

In 3-d and higher convex hulls, the extreme points (vertices) are sorted by index. This is the same order as option 'p' when it doesn't include coplanar or interior points.

For Delaunay triangulations, 'Fx' lists the extreme points of the input sites (i.e., the vertices of their convex hull). The points are unordered.

Up: Home page for Qhull (local)
Up: Qhull manual: contents
To: Programs • Options • Output • Formats • Geomview • Print • Qhull • Precision • Trace • Functions (local)

The Geometry Center Home Page

Comments to: qhull@qhull.org
Created: Sept. 25, 1995 --- Last modified: see top