To: ProgramsOptionsOutputFormatsGeomviewPrintQhullPrecisionTrace
To: synopsis • input • outputs • controls • graphics • notes • conventions • options

# qhalf -- halfspace intersection about a point

The intersection of a set of halfspaces is a polytope. The polytope may be unbounded. See Preparata & Shamos ['85] for a discussion. In low dimensions, halfspace intersection may be used for linear programming.

Example: rbox c | qconvex FQ FV n | qhalf Fp
Print the intersection of the facets of a cube. rbox c generates the vertices of a cube. qconvex FV n returns of average of the cube's vertices (in this case, the origin) and the halfspaces that define the cube. qhalf Fp computes the intersection of the halfspaces about the origin. The intersection is the vertices of the original cube.

Example: rbox c d G0.55 | qconvex FQ FV n | qhalf Fp

Print the intersection of the facets of a cube and a diamond. There are 24 facets and 14 intersection points. Four facets define each diamond vertext. Six facets define each cube vertex.

Example: rbox c d G0.55 | qconvex FQ FV n | qhalf Fp Qt

Same as above except triangulate before computing the intersection points. Three facets define each intersection point. There are two duplicates of the diamond and four duplicates of the cube.

Qhull computes a halfspace intersection by the geometric duality between points and halfspaces. See halfspace examples, qhalf notes, and option 'p' of qhalf outputs.

By default, halfspace intersections may be defined by more than d halfspaces. See the previous cube and diamond example. This is the expected output for halfspace intersection.

You can try triangulated output and joggled input. It demonstrates that triangulated output is more accurate than joggled input.

If you use 'Qt' (triangulated output), all halfspace intersections are simplicial (e.g., three halfspaces per intersection in 3-d). In 3-d, if more than three halfspaces intersect at the same point, triangulated output will produce duplicate intersections, one for each additional halfspace. See the previous cube and diamond example.

If you use 'QJ' (joggled input), all halfspace intersections are simplicial. This may lead to nearly identical intersections. For example, replace 'Qt' with 'QJ' above and compare the duplicated intersections. See Merged facets or joggled input.

The 'qhalf' program is equivalent to 'qhull H' in 2-d to 4-d, and 'qhull H Qx' in 5-d and higher. It disables the following Qhull options: d n v Qbb QbB Qf Qg Qm Qr QR Qv Qx Qz TR E V Fa FA FC FD FS Ft FV Gt Q0,etc.

### »qhalf synopsis

```qhalf- halfspace intersection about a point.
input (stdin): [dim, 1, interior point]
dim+1, n
halfspace coefficients + offset

options (qhalf.htm):
Hn,n - specify coordinates of interior point
Qt   - triangulated output
QJ   - joggle input instead of merging facets
Tv   - verify result: structure, convexity, and redundancy
.    - concise list of all options
-    - one-line description of all options

output options (subset):
s    - summary of results (default)
Fp   - intersection coordinates
Fv   - non-redundant halfspaces incident to each intersection
Fx   - non-redundant halfspaces
o    - OFF file format (dual convex hull)
G    - Geomview output (dual convex hull)
m    - Mathematica output (dual convex hull)
QVn  - print intersections for halfspace n, -n if not
TO file - output results to file, may be enclosed in single quotes

examples:
rbox d | qconvex n | qhalf s H0,0,0 Fp
rbox c | qconvex FV n | qhalf s i
rbox c | qconvex FV n | qhalf s o
```

### »qhalf input

The input data on stdin consists of:

• [optional] interior point
• dimension
• 1
• coordinates of interior point
• dimension + 1
• number of halfspaces
• halfspace coefficients followed by offset

Use I/O redirection (e.g., qhalf < data.txt), a pipe (e.g., rbox c | qconvex FV n | qhalf), or the 'TI' option (e.g., qhalf TI data.txt).

Qhull needs an interior point to compute the halfspace intersection. An interior point is inside all of the halfspaces Hx+b <= 0. The interior point may be in the input. If not, option 'Hn,n' defines the interior point as [n,n,0,...] where 0 is the default coordinate (e.g., 'H0' is the origin). Use linear programming if you do not know the interior point (see halfspace notes),

The input to qhalf is a set of halfspaces. Each halfspace is defined by d coefficients followed by a signed offset. This defines a linear inequality. The coefficients define a vector that is normal to the halfspace. The vector may have any length. If it has length one, the offset is the distance from the origin to the halfspace's boundary.

This is the same format used for output options 'n', 'Fo', and 'Fi'. Use option 'Fd' to use cdd format for the halfspaces.

For example, here is the input for computing the intersection of halfplanes that form a cube.

rbox c | qconvex FQ FV n TO data

```RBOX c | QCONVEX FQ FV n
3 1
0      0      0
4
6
0      0     -1   -0.5
0     -1      0   -0.5
1      0      0   -0.5
-1      0      0   -0.5
0      1      0   -0.5
0      0      1   -0.5
```

qhalf s Fp < data

```
Halfspace intersection by the convex hull of 6 points in 3-d:

Number of halfspaces: 6
Number of non-redundant halfspaces: 6
Number of intersection points: 8

Statistics for: RBOX c | QCONVEX FQ FV n | QHALF s Fp

Number of points processed: 6
Number of hyperplanes created: 11
Number of distance tests for qhull: 11
Number of merged facets: 1
Number of distance tests for merging: 45
CPU seconds to compute hull (after input):  0

3
3
8
-0.5    0.5    0.5
0.5    0.5    0.5
-0.5    0.5   -0.5
0.5    0.5   -0.5
0.5   -0.5    0.5
-0.5   -0.5    0.5
-0.5   -0.5   -0.5
0.5   -0.5   -0.5
```

### »qhalf outputs

The following options control the output for halfspace intersection.

Intersections
FN
list intersection points for each non-redundant halfspace. The first line is the number of non-redundant halfspaces. Each remaining lines starts with the number of intersection points. For the cube example, each halfspace has four intersection points.
Fn
list neighboring intersections for each intersection point. The first line is the number of intersection points. Each remaining line starts with the number of neighboring intersections. For the cube example, each intersection point has three neighboring intersections. In 3-d, a non-simplicial intersection has more than three neighboring intersections. Use option 'QJ' to avoid non-simplicial intersections.
Fp
print intersection coordinates. The first line is the dimension and the second line is the number of intersection points. The following lines are the coordinates of each intersection.
FI
list intersection IDs. The first line is the number of intersections. The IDs follow, one per line.

Halfspaces
Fx
list non-redundant halfspaces. The first line is the number of non-redundant halfspaces. The other lines list one halfspace per line. A halfspace is non-redundant if it defines a facet of the intersection. Redundant halfspaces are ignored. For the cube example, all of the halfspaces are non-redundant.
Fv
list 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. For the cube example, each intersection is incident to three halfspaces.
i
list non-redundant halfspaces incident to each intersection point. The first line is the number of intersection points. Each remaining line lists the incident, non-redundant halfspaces. For the cube example, each intersection is incident to three halfspaces.
Fc
list 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.
Qi Fc
list redundant halfspaces for each intersection point. The first line is the number of intersection points. Each remaining line starts with the number of redundant halfspaces. Use options 'Qc Qi Fc' to list coplanar and redundant halfspaces.

General
s
print summary for the halfspace intersection. Use 'Fs' if you need numeric data.
o
print vertices and facets of the dual convex hull. The first line is the dimension. The second line is the number of vertices, facets, and ridges. The vertex coordinates are next, followed by the facets, one per line.
p
print vertex coordinates of the dual convex hull. Each vertex corresponds to a non-redundant halfspace. Its coordinates are the negative of the hyperplane's coefficients divided by the offset plus the inner product of the coefficients and the interior point (-c/(b+a.p). Options 'p Qc' includes coplanar halfspaces. Options 'p Qi' includes redundant halfspaces.
m
Mathematica output for the dual convex hull in 2-d or 3-d.
FM
Maple output for the dual convex hull in 2-d or 3-d.
G
Geomview output for the dual convex hull in 2-d, 3-d, or 4-d.

### »qhalf controls

Qt
triangulated output. If a 3-d intersection is defined by more than three hyperplanes, Qhull produces duplicate intersections -- one for each extra hyperplane.
QJ
joggle the input instead of merging facets. In 3-d, this guarantees that each intersection is defined by three hyperplanes.
f
facet dump. Print the data structure for each intersection (i.e., facet)
TFn
report summary after constructing n intersections
QVn
select intersection points for halfspace n (marked 'good')
QGn
select intersection points that are visible to halfspace n (marked 'good'). Use -n for the remainder.
Qbk:0Bk:0
remove the k-th coordinate from the input. This computes the halfspace intersection in one lower dimension.
Tv
verify result
TI file
input data from file. The filename may not use spaces or quotes.
TO file
output results to file. Use single quotes if the filename contains spaces (e.g., TO 'file with spaces.txt'
Qs
search all points for the initial simplex. If Qhull can not construct an initial simplex, it reports a descriptive message. Usually, the point set is degenerate and one or more dimensions should be removed ('Qbk:0Bk:0'). If not, use option 'Qs'. It performs an exhaustive search for the best initial simplex. This is expensive is high dimensions.

### »qhalf graphics

To view the results with Geomview, compute the convex hull of the intersection points ('qhull FQ H0 Fp | qhull G'). See Halfspace examples.

### »qhalf notes

If you do not know an interior point for the halfspaces, use linear programming to find one. Assume, n halfspaces defined by: aj*x1+bj*x2+cj*x3+dj>=0, j=1..n. Perform the following linear program:

max(x5) aj*x1+bj*x2+cj*x3+dj*x4-x5>=0, j=1..n

Then, if [x1,x2,x3,x4,x5] is an optimal solution with x4,x5>0 we get:

aj*(x1/x4)+bj*(x2/x4)+cj*(x3/x4)+dj>=(x5/x4)>0, j=1..n

and conclude that the point [x1/x4,x2/x4,x3/x4] is in the interior of all the halfspaces. Note that x5 is optimal, so this point is "way in" the interior (good for precision errors).

After finding an interior point, the rest of the intersection algorithm is from Preparata & Shamos ['85, p. 316, "A simple case ..."]. Translate the halfspaces so that the interior point is the origin. Calculate the dual polytope. The dual polytope is the convex hull of the vertices dual to the original faces in regard to the unit sphere (i.e., halfspaces at distance d from the origin are dual to vertices at distance 1/d). Then calculate the resulting polytope, which is the dual of the dual polytope, and translate the origin back to the interior point [S. Spitz and S. Teller].

### »qhalf conventions

The following terminology is used for halfspace intersection in Qhull. This is the hardest structure to understand. The underlying structure is a convex hull with one vertex per non-redundant halfspace. See convex hull conventions and Qhull's data structures.

• interior point - a point in the intersection of the halfspaces. Qhull needs an interior point to compute the intersection. See halfspace input.
• halfspace - d coordinates for the normal and a signed offset. The distance to an interior point is negative.
• non-redundant halfspace - a halfspace that defines an output facet
• vertex - a dual vertex in the convex hull corresponding to a non-redundant halfspace
• coplanar point - the dual point corresponding to a similar halfspace
• interior point - the dual point corresponding to a redundant halfspace
• intersection point- the intersection of d or more non-redundant halfspaces
• facet - a dual facet in the convex hull corresponding to an intersection point
• non-simplicial facet - more than d halfspaces intersect at a point
• good facet - an intersection point that satisfies restriction 'QVn', etc.

### »qhalf options

```qhalf- compute the intersection of halfspaces about a point
http://www.qhull.org

input (stdin):
optional interior point: dimension, 1, coordinates
first lines: dimension+1 and number of halfspaces
other lines: halfspace coefficients followed by offset

options:
Hn,n - specify coordinates of interior point
Qt   - triangulated ouput
QJ   - joggle input instead of merging facets
Qc   - keep coplanar halfspaces
Qi   - keep other redundant halfspaces

Qhull control options:
QJn  - randomly joggle input in range [-n,n]
Qbk:0Bk:0 - remove k-th coordinate from input
Qs   - search all halfspaces for the initial simplex
QGn  - print intersection if redundant to halfspace n, -n for not
QVn  - print intersections for halfspace n, -n if not

Trace options:
T4   - trace at level n, 4=all, 5=mem/gauss, -1= events
Tc   - check frequently during execution
Ts   - print statistics
Tv   - verify result: structure, convexity, and redundancy
Tz   - send all output to stdout
TFn  - report summary when n or more facets created
TI file - input data from file, no spaces or single quotes
TO file - output results to file, may be enclosed in single quotes
TPn  - turn on tracing when halfspace n added to intersection
TMn  - turn on tracing at merge n
TWn  - trace merge facets when width > n
TVn  - stop qhull after adding halfspace n, -n for before (see TCn)
TCn  - stop qhull after building cone for halfspace n (see TVn)

Precision options:
An  - cosine of maximum angle.  Merge facets if cosine > n or non-convex
C-0 roundoff, A-0.99/C-0.01 pre-merge, A0.99/C0.01 post-merge
Rn   - randomly perturb computations by a factor of [1-n,1+n]
Un   - max distance below plane for a new, coplanar halfspace
Wn   - min facet width for outside halfspace (before roundoff)

Output formats (may be combined; if none, produces a summary to stdout):
f    - facet dump
G    - Geomview output (dual convex hull)
i    - non-redundant halfspaces incident to each intersection
m    - Mathematica output (dual convex hull)
o    - OFF format (dual convex hull: dimension, points, and facets)
p    - vertex coordinates of dual convex hull (coplanars if 'Qc' or 'Qi')
s    - summary (stderr)

More formats:
Fc   - count plus redundant halfspaces for each intersection
-   Qc (default) for coplanar and Qi for other redundant
Fd   - use cdd format for input (homogeneous with offset first)
FF   - facet dump without ridges
FI   - ID of each intersection
Fm   - merge count for each intersection (511 max)
FM   - Maple output (dual convex hull)
Fn   - count plus neighboring intersections for each intersection
FN   - count plus intersections for each non-redundant halfspace
FO   - options and precision constants
Fp   - dim, count, and intersection coordinates
FP   - nearest halfspace and distance for each redundant halfspace
FQ   - command used for qhalf
Fs   - summary: #int (8), dim, #halfspaces, #non-redundant, #intersections
for output: #non-redundant, #intersections, #coplanar
halfspaces, #non-simplicial intersections
#real (2), max outer plane, min vertex
Fv   - count plus non-redundant halfspaces for each intersection
Fx   - non-redundant halfspaces

Geomview output (2-d, 3-d and 4-d; dual convex hull)
Ga   - all points (i.e., transformed halfspaces) as dots
Gp  -  coplanar points and vertices as radii
Gv  -  vertices (i.e., non-redundant halfspaces) as spheres
Gi   - inner planes (i.e., halfspace intersections) only
Gn  -  no planes
Go  -  outer planes only
Gc	 - centrums
Gh   - hyperplane intersections
Gr   - ridges
GDn  - drop dimension n in 3-d and 4-d output

Print options:
PAn  - keep n largest facets (i.e., intersections) by area
Pdk:n- drop facet if normal[k] <= n (default 0.0)
PDk:n- drop facet if normal[k] >= n
Pg   - print good facets (needs 'QGn' or 'QVn')
PFn  - keep facets whose area is at least n
PG   - print neighbors of good facets
PMn  - keep n facets with most merges
Po   - force output.  If error, output neighborhood of facet
Pp   - do not report precision problems

.    - list of all options
-    - one line descriptions of all options
```