Up: Home page for Qhull (local)
Up: Qhull manual: contents
To: Programs • Options • Output • Formats • Geomview • Print • Qhull • Precision • Trace • Functions (local)
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 FV n | qhalf Fp

Print the intersection of the facets of a cube. rbox c generates the vertices of a cube. qconvex FV returns a feasible point for halfspace intersection. This feasible or interior point, qconvex FV, is the average of the cube's vertices (i.e., the origin). qconvex n returns the halfspaces that define the cube. qhalf Fp computes the intersection of the halfspaces about the feasible point. The intersection is the vertices of the original cube.

Example: rbox c | qconvex FQ n | qhalf H0.1,0.1,0.1

Compute the intersection of the facets of a cube and print a summary ('s'). Option 'FQ' prints the qconvex command as an input comment for the summary. 'qhalf Hn,n,n' specifies the feasible point as [0.1, 0.1, 0.1]. 'qhalf H0' would specify the feasible point as the origin.

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

Example: rbox 10 s t10 | qconvex FQ FV n | qhalf Fp Fn

Print the intersection of the facets of the convex hull of 10 cospherical points. Include the intersection points and the neighboring intersections. As in the previous examples, the intersection points are nearly the same as the original input points.

In Qhull, a halfspace is defined by the points on or below a hyperplane. The distance of each point to the hyperplane is less than or equal to zero.

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

Qhalf's outputs are the intersection points (Fp) and the neighboring intersection points (Fn). For random inputs, halfspace intersections are usually defined by more than d halfspaces. See the sphere example.

The identity pipeline for Qhull starts with points, produces the halfspaces for their convex hull, and intersects these halfspaces, returning the original points. For example, 'rbox c' is the unit cube.

	rbox c | qconvex FV n | qhalf Fp
	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

You can try triangulated output ('Qt') and joggled input ('QJ'). 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 third example, or add 'Qt' to the sphere example.

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

The 'qhalf' program is equivalent to 'qhull H'. It disables the following Qhull options: d n v Qbb QbB Qf Qg Qm 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): [dimension, 1, interior point]
                       dimension+1, number of halfspaces, coefficients+offset
    comments star