Name

  qhull, rbox        2020.2        2020/08/31        (8.0.2)

Convex hull, Delaunay triangulation, Voronoi diagrams, Halfspace intersection

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

  Available from:
    <http://www.qhull.org>
    <http://www.qhull.org/download>
    <http://github.com/qhull/qhull/wiki> (git@github.com:qhull/qhull.git)

  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 the Qt Framework.

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 modify Qhull, particularly the C++ interface

Qhull is on GitHub (http://github.com/qhull/qhull/wiki, git@github.com:qhull/qhull.git)

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

To install Qhull

Qhull is precompiled for Windows 32-bit, otherwise it needs compilation.

Qhull includes Makefiles for gcc and other targets, CMakeLists.txt for CMake, .sln/.vcproj/.vcxproj files for Microsoft Visual Studio, and .pro files for Qt Creator. It compiles under Windows with mingw. (https://github.com/qhull/qhull/wiki/Qhull-build-systems)

Install and build instructions follow.

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

Index

Installing Qhull on Windows 10, 8, 7 (32- or 64-bit), Windows XP, and Windows NT Installing Qhull on Unix with gcc Installing Qhull with CMake 2.6 or later Installing Qhull with Qt Working with Qhull's C++ interface Calling Qhull from C programs Compiling Qhull with Microsoft Visual C++ Compiling Qhull with Qt Creator Compiling Qhull with mingw/gcc on Windows Compiling Qhull with cygwin on Windows Compiling from Makfile without gcc Compiling on other machines and compilers Distributed files Authors

Installing Qhull on Windows 10, 8, 7 (32- or 64-bit), Windows XP, and Windows NT

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. Qhull.exe and user-eg3.exe are compiled with the reentrant library while the other executables use the non-reentrant library.

To install Qhull:

Unzip the files into a directory (e.g., named 'qhull')
Click on QHULL-GO or open a command window into Qhull's bin directory.
Test with 'rbox D4 | qhull'

To uninstall Qhull

Delete the qhull directory

To learn about Qhull:

Execute 'qconvex' for a synopsis and examples. Or 'qconvex --help' or 'qconvex -?'
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

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 regularly use qhull on a Windows host, install a bash shell such as https://gitforwindows.org/ # based on MSYS2 https://github.com/git-for-windows/git/wiki http://www.msys2.org/ https://github.com/msys2/msys2/wiki [mar'19] Git for Windows v2.21 requires 'qhull --help' Install in C:\Git... # Not 'Program Files...' otherwise './configure && make' fails www.cygwin.com www.mingw.org/wiki/msys # for Windows XP Road Bash (www.qhull.org/bash) # based on MSYS

Installing Qhull on Unix with gcc

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

Download and extract Qhull (either GitHub, .tgz file, or .zip file)
make
export LD_LIBRARY_PATH=$PWD/lib:$LD_LIBRARY_PATH
make test

'make install' installs Qhull at '/usr/local/'. It installs pkg-config files at '/usr/local/lib/pkgconfig'. Change the install directory with DESTDIR and PREFIX.

To build 32-bit Qhull on a 64-bit host (uses 33% less memory in 4-d)

make new M32=-m32

To build 32-bit Qhull without -fpic (may be faster, but shared library may fail)

make new M32=-m32 FPIC=

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

A simple Makefile for Qhull is in src/libqhull and src/libqhull_r. To build the Qhull executables and libqhullstatic

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

Installing Qhull with CMake 2.6 or later

See CMakeLists.txt for examples and further build instructions

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

Download and extract Qhull (either GitHub, .tgz file, or .zip file)
cd build
cmake --help # List build generators
cmake -G "<generator>" .. # e.g., for MINGW-w64 -- cmake -G "MSYS Makefiles" ..
cmake ..
make
ctest
make install # If MSYS or UNIX, default CMAKE_INSTALL_PREFIX is '/usr/local' # otherwise if WINDOWS, installs to ../bin, ../include, and ../lib
make uninstall # Delete the files in install_manifest.txt

The ".." is important. It refers to the parent directory (i.e., qhull/)

CMake installs lib/pkgconfig/qhull*.pc for use with pkg-config

If CMAKE_INSTALL_PREFIX is C:/Program Files/qhull, you may need to give 'Users' "full control" to qhull's sub-directories: bin, doc, include, lib, and man (folder > Properties > Security > Edit > Users).

On Windows, CMake's 64-bit generators have a "Win64" tag. Qhull's data structures are substantial larger as 64-bit code than as 32-bit code. This may slow down Qhull.

If cmake fails with "No CMAKE_C_COMPILER could be found"

cmake was not able to find the build environment specified by -G "..."

If cmake's gcc smoketest fails after a Windows update

Reinstall MINGW-w64 and delete build/CMakeCache.txt. A Windows update can break gcc process creation for cc1.

Installing Qhull with Qt

To build Qhull, including its C++ test program (qhulltest)

Download and extract Qhull (either GitHub, .tgz file, or .zip file)
Load src/qhull-all.pro into QtCreator
Configure the project to use a Shadow build at the same level as 'src', 'bin', and 'lib' If, instead, the shadow build is a subdirectory of 'build', Qt Creator will install Qhull in 'build/bin' and 'build/lib'
Build
Build qhulltest with a C++11 or later compiler
qhulltest depends on shared libraries QtCore.a and QtTest.a. They may need to be copied into the bin directory. On Windows, copy Qt5Core.dll and Qt5Test.dll, e.g., /qt/5.11.2/msvc2017_64/bin
If qhulltest fails with exit status 127 and no error message, check for missing Q5Core.dll and Qt5Test.dll

Working with Qhull's C++ interface

See html/qh-code.htm#cpp for calling Qhull from C++ programs

Class and method documentation is limited

See html/qh-code.htm#reentrant for converting from Qhull-2012

Examples of using the C++ interface user_eg3_r.cpp qhulltest/*_test.cpp

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

To clone Qhull's next branch from http://github.com/qhull/qhull/wiki git init git clone git@github.com:qhull/qhull.git cd qhull git checkout next ... git pull origin next

Compile qhullcpp and libqhullstatic_r with the same compiler. Both libraries use the C routines setjmp() and longjmp() for error handling. They must be compiled with the same compiler.

Qhull provides pkg-config support with build/qhull.pc.in and lib/pkgconfig/qhull*.pc With back-ticks, you can compile your C++ program with the Qhull libraries: g++ pkg-config --cflags --libs qhullcpp qhullstatic_r -o my_app my_app.cpp or g++ pkg-config --cflags --libs qhullcpp qhull_r -o my_app my_app.cpp

qhullcpp must be linked before qhull_r, otherwise the linker reports an error -- "QhullUser ... multiple definition of `qh_fprintf'"

Calling Qhull from C programs

See html/qh-code.htm#library for calling Qhull from C programs

Qhull provides pkg-config support with build/q

Qhull

Install / Use

README