From 0558b53493a77bae44831cf87bb0f59359828ef5 Mon Sep 17 00:00:00 2001 From: bubnikv Date: Wed, 19 Sep 2018 11:02:24 +0200 Subject: WIP: Moved sources int src/, separated most of the source code from Perl. The XS was left only for the unit / integration tests, and it links libslic3r only. No wxWidgets are allowed to be used from Perl starting from now. --- src/qhull/html/qh-optf.htm | 736 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 736 insertions(+) create mode 100644 src/qhull/html/qh-optf.htm (limited to 'src/qhull/html/qh-optf.htm') diff --git a/src/qhull/html/qh-optf.htm b/src/qhull/html/qh-optf.htm new file mode 100644 index 000000000..3c7a2b1db --- /dev/null +++ b/src/qhull/html/qh-optf.htm @@ -0,0 +1,736 @@ + + + + +Qhull format options (F) + + + +

Up: Home page for Qhull
+Up: Qhull manual: Table of Contents
+To: Programs +• Options +• Output +• Formats +• Geomview +• Print +• Qhull +• Precision +• Trace +• Functions

+
+ +

[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-2015 C.B. Barber

+ +
+ +

» Programs +• Options +• Output +• Formats +• Geomview +• Print +• Qhull +• Precision +• Trace +• Functions

+ +

Additional input & output formats

+ +

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

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

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

+ +

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

+ +

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.

+ +

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.

+ +

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

+ +

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.

+ +

Option 'Fo' gives the hyperplanes for the unbounded rays of +the unbounded regions of the Voronoi diagram. Each hyperplane +goes through the midpoint of the corresponding input sites. The +rays are directed away from the input sites.

+ +

Use 'Fi' for bounded regions, +and 'Fv' for the corresponding +Voronoi vertices. Use 'Tv' to verify +that the corresponding Voronoi vertices lie on the hyperplane.

+ +

»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,...] 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. +

+ +

»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 +counterclockwise 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
+Up: Qhull manual: Table of Contents
+To: Programs +• Options +• Output +• Formats +• Geomview +• Print +• Qhull +• Precision +• Trace +• Functions

+
+ +

The Geometry Center +Home Page

+ +

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

+ + -- cgit v1.2.3