Name

  qhull, rbox         2012.1     2012/02/18

Convex hull, Delaunay triangulation, Voronoi diagrams, Halfspace intersection

  Documentation:
    html/index.htm
    http://www.qhull.org/html

  Available from:
    <http://www.qhull.org>
    <git@gitorious.org:qhull/qhull.git>
    <http://packages.debian.org/sid/libqhull5> [out-of-date]

  News and a paper:
    <http://www.qhull.org/news>
    <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405>

 Version 1 (simplicial only):
    <http://www.qhull.org/download/qhull-1.0.tar.gz>

Purpose

Qhull is a general dimension convex hull program that reads a set of points from stdin, and outputs the smallest convex set that contains the points to stdout. It also generates Delaunay triangulations, Voronoi diagrams, furthest-site Voronoi diagrams, and halfspace intersections about a point.

Rbox is a useful tool in generating input for Qhull; it generates hypercubes, diamonds, cones, circles, simplices, spirals, lattices, and random points.

Qhull produces graphical output for Geomview. This helps with understanding the output. http://www.geomview.org

Environment requirements

Qhull and rbox should run on all 32-bit and 64-bit computers. Use an ANSI C or C++ compiler to compile the program. The software is self-contained. It comes with examples and test scripts.

Qhull's C++ interface uses the STL. The C++ test program uses QTestLib from Nokia's Qt Framework. Qhull's C++ interface may change without notice. Eventually, it will move into the qhull shared library.

Qhull is copyrighted software. Please read COPYING.txt and REGISTER.txt before using or distributing Qhull.

To cite Qhull, please use

Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., "The Quickhull algorithm for convex hulls," ACM Trans. on Mathematical Software, 22(4):469-483, Dec 1996, http://www.qhull.org.

To contribute to Qhull

Qhull is on Gitorious (http://gitorious.org:qhull, git@gitorious.org:qhull/qhull.git)

For internal documentation, see html/qh-code.htm

To install Qhull

Qhull is precompiled for Windows, otherwise it needs compilation.

Besides makefiles for gcc, qhull includes CMakeLists.txt for CMake, vcproj/sln files for Microsoft Visual Studio, and .pro files for Qt Creator. It compiles with mingw.

Install and build instructions follow.

See the end of this document for a list of distributed files.

Installing Qhull on Windows

The zip file contains rbox.exe, qhull.exe, qconvex.exe, qdelaunay.exe, qhalf.exe, qvoronoi.exe, testqset.exe, user_eg*.exe, documentation files, and source files.

To install Qhull:

Unzip the files into a directory. You may use WinZip32 <www.hotfiles.com>
Click on QHULL-GO or open a command window into Qhull's bin directory.

To uninstall Qhull

Delete the qhull directory

To learn about Qhull:

Execute 'qconvex' for a synopsis and examples.
Execute 'rbox 10 | qconvex' to compute the convex hull of 10 random points.
Execute 'rbox 10 | qconvex i TO file' to write results to 'file'.
Browse the documentation: qhull\html\index.htm
If an error occurs, Windows sends the error to stdout instead of stderr. Use 'TO xxx' to send normal output to xxx and error output to stdout

To improve the command window

Double-click the window bar to increase the size of the window
Right-click the window bar
Select Properties
Check QuickEdit Mode Select text with right-click or Enter Paste text with right-click
Change Font to Lucinda Console
Change Layout to Screen Buffer Height 999, Window Size Height 55
Change Colors to Screen Background White, Screen Text Black
Click OK
Select 'Modify shortcut that started this window', then OK

If you use qhull a lot, install MSYS (www.mingw.org), Road Bash (www.qhull.org/bash), or Cygwin (www.cygwin.com).

Installing Qhull on Unix with gcc

To build Qhull, static libraries, shared library, and C++ interface

Extract Qhull from qhull...tgz or qhull...zip
make
export LD_LIBRARY_PATH=$PWD/lib:$LD_LIBRARY_PATH

Or, to build Qhull and libqhullstatic.a

Extract Qhull from qhull...tgz or qhull...zip
cd src/libqhull
make

The Makefiles may be edited for other compilers. If 'testqset' exits with an error, qhull is broken

Installing Qhull with CMake 2.6 or later

To build Qhull, static libraries, shared library, and C++ interface

Extract Qhull from qhull...tgz or qhull...zip
cd build
cmake ..
make
make install

On Windows, CMake installs to C:/Program Files/qhull See CMakeLists.txt for further build instructions

Installing Qhull with Qt

To build Qhull, static libraries, shared library, C++ interface, and C++ test

Extract Qhull from qhull...tgz or qhull...zip
cd src
qmake
make

Installing Qhull with Autoconf [WARNING out-of-date]

The tar.gz tarball contains documentation, source files, and a config directory [R. Laboissiere].

[Nov 2011] Qhull 2009.1.2 does not include the C++ interface

To install Qhull

Extract the files
./configure
make
make install

Working with Qhull's C++ interface

Qhull's C++ interface is likely to change. Stay current with Gitorious.

To clone Qhull's next branch from http://gitorious.org/qhull git init git clone git://gitorious.org/qhull/qhull.git cd qhull git checkout next ... git pull origin next

Compiling Qhull with Microsoft Visual C++ 2005 or later

To compile Qhull with Microsoft Visual C++

Extract Qhull from Gitorious, qhull...tgz, or qhull...zip
Load solution build/qhull.sln
Build
Project qhulltest requires Qt for DevStudio (http://qt.nokia.com/downloads) Set the QTDIR environment variable to your Qt directory (e.g., c:/qt/4.7.4) If incorrect, precompile will fail with 'Can not locate the file specified'

Compiling Qhull with Qt Creator

Qt (http://qt.nokia.com) is a C++ framework for Windows, Linux, and Macintosh

Qhull uses QTestLib to test qhull's C++ interface (qhulltest)

To compile Qhull with Qt Creator

Extract Qhull from Gitorious, qhull...tgz, or qhull...zip
Download the Qt SDK from Nokia (http://qt.nokia.com/downloads)
Start Qt Creator
Load src/qhull-all.pro
Build

Compiling Qhull with mingw on Windows

To compile Qhull with MINGW

Extract Qhull from Gitorious, qhull...tgz, or qhull...zip
Install Road Bash (http://www.qhull.org/bash) or install MSYS (http://www.mingw.org/wiki/msys)
Install MINGW (http://www.mingw.org/). Mingw is included with Qt SDK.
make

Compiling Qhull with cygwin on Windows

To compile Qhull with cygwin

Extract Qhull from Gitorious, qhull...tgz, or qhull...zip
Install cygwin (http://www.cygwin.com)
Include packages for gcc, make, ar, and ln
make

Compiling from Makfile without gcc

The file, qhull-src.tgz, contains documentation and source files for qhull and rbox.

To unpack the gzip file

tar zxf qhull-src.tgz
cd qhull

Compiling qhull and rbox with Makefile

in Makefile, check the CC, CCOPTS1, PRINTMAN, and PRINTC defines
- the defaults are gcc and enscript
- CCOPTS1 should include the ANSI flag. It defines STDC
in user.h, check the definitions of qh_SECticks and qh_CPUclock.
- use '#define qh_CLOCKtype 2' for timing runs longer than 1 hour
type: make
- this builds: qhull qconvex qdelaunay qhalf qvoronoi rbox libqhull.a
type: make doc
- this prints the man page
- See also qhull/html/index.htm
if your compiler reports many errors, it is probably not a ANSI C compiler
- you will need to set the -ansi switch or find another compiler
if your compiler warns about missing prototypes for fprintf() etc.
- this is ok, your compiler should have these in stdio.h
if your compiler warns about missing prototypes for memset() etc.
- include memory.h in qhull_a.h
if your compiler reports "global.c: storage size of 'qh_qh' isn't known"
- delete the initializer "={0}" in global.c, stat.c and mem.c
if your compiler warns about "stat.c: improper initializer"
- this is ok, the initializer is not used
if you have trouble building libqhull.a with 'ar'
- try 'make -f Makefile.txt qhullx'
if the code compiles, the qhull test case will automatically execute
if an error occurs, there's an incompatibility between machines
- If you can, try a different compiler
- You can turn off the Qhull memory manager with qh_NOmem in mem.h
- You can turn off compiler optimization (-O2 in Makefile)
- If you find the source of the problem, please let us know
to install the programs and their man pages:
- define MANDIR and BINDIR
- type 'make install'
if you have Geomview (www.geomview.org)
- try 'rbox 100 | qconvex G >a' and load 'a' into Geomview
- run 'q_eg' for Geomview examples of Qhull output (see qh-eg.htm)

Compiling on other machines and compilers

Qhull compiles with Borland C++ 5.0 bcc32. A Makefile is included. Execute 'make -f Mborland'. If you use the Borland IDE, set the ANSI option in Options:Project:Compiler:Source:Language-compliance.

Qhull compiles with Borland C++ 4.02 for Win32 and DOS Power Pack.
Use 'make -f Mborland -D_DPMI'. Qhull 1.0 compiles with Borland C++ 4.02. For rbox 1.0, use "bcc32 -WX -w- -O2-e -erbox -lc rbox.c".
Use the same options for Qhull 1.0. [D. Zwick]

Qhull compiles with Metrowerks C++ 1.7 with the ANSI option. If you turn on full

Qhull

Install / Use

README