qhull / qhull Goto Github PK
View Code? Open in Web Editor NEWQhull development for www.qhull.org -- Qhull 2020.2 (8.1-alpha1) at https://github.com/qhull/qhull/wiki
License: Other
qhull's Introduction
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> ([email protected]: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, [email protected]: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 [email protected]: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/qhull.pc.in and lib/pkgconfig/qhull*.pc
With back-ticks, you can compile your C program with the Qhull library
gcc `pkg-config --cflags --libs qhull_r` -o my_app my_app.c
See html/qh-code.htm#reentrant for converting from Qhull-2012
Warning: You will need to understand Qhull's data structures and read the
code. Most users will find it easier to call Qhull as an external command.
The reentrant 'C' code (src/libqhull_r), passes a pointer to qhT
to most Qhull routines. This allows multiple instances of Qhull to run
at the same time. It simplifies the C++ interface.
The non-reentrant 'C' code (src/libqhull) looks unusual. It refers to
Qhull's global data structure, qhT, through a 'qh' macro (e.g., 'qh ferr').
This allows the same code to use static memory or heap memory.
If qh_QHpointer is defined, qh_qh is a pointer to an allocated qhT;
otherwise qh_qh is a global static data structure of type qhT.
------------------
Compiling Qhull with Microsoft Visual C++
To compile 32-bit Qhull with Microsoft Visual C++ 2010 and later
- Download and extract Qhull (either GitHub, .tgz file, or .zip file)
- Load solution build/qhull-32.sln
- Right-click 'Retarget solution' from toolset v110 to your Platform Toolset
File > Save All
- Build target 'Win32'
- Project qhulltest requires Qt for DevStudio (http://www.qt.io)
Set the QTDIR environment variable to your Qt directory (e.g., c:/qt/5.2.0/5.2.0/msvc2012)
If QTDIR is incorrect, precompile will fail with 'Can not locate the file specified'
- Copy Qt shared libraries, QtCore.dll and QtTest.dll, into the bin directory
To compile 64-bit Qhull with Microsoft Visual C++ 2010 and later
- 64-bit Qhull has larger data structures due to 64-bit pointers. This may slow down Qhull.
- Download and extract Qhull (either GitHub, .tgz file, or .zip file)
- Load solution build/qhull-64.sln
- Right-click 'Retarget solution' from toolset v110 to your Platform Toolset
File > Save All
- Build target 'x64'
- If build as 32-bit fails, use solution build/qhull-32.sln
- Project qhulltest requires Qt for DevStudio (http://www.qt.io)
Set the QTDIR environment variable to your Qt directory (e.g., c:/qt/5.2.0/5.2.0/msvc2012_64)
If QTDIR is incorrect, precompile will fail with 'Can not locate the file specified'
If error -- MSB8020: The build tools for Visual Studio 2012 (Platform Toolset = 'v110') cannot be found.
- 'Project > Retarget solution' for both qhull-32.sln and qhull-64.sln
- 'File > Open' your preferred solution (qhull-32.sln or qhull-64.sln)
- 'Save All' both projects
- DevStudio may need a restart
To compile Qhull with Microsoft Visual C++ 2005 (vcproj files)
- Download and extract Qhull (either GitHub, .tgz file, or .zip file)
- Load solution build/qhull.sln
- Build target 'win32' (not 'x64')
- Project qhulltest requires Qt for DevStudio (http://www.qt.io)
Set the QTDIR environment variable to your Qt directory (e.g., c:/qt/4.7.4)
If QTDIR is incorrect, precompile will fail with 'Can not locate the file specified'
------------------
Compiling Qhull with Qt Creator
Qt (http://www.qt.io) is a C++ framework for Windows, Linux, and Macintosh
Qhull uses QTestLib to test qhull's C++ interface (see src/qhulltest/)
To compile Qhull with Qt Creator
- Download and extract Qhull (either GitHub, .tgz file, or .zip file)
- Download the Qt SDK
- Start Qt Creator
- Load src/qhull-all.pro
- 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
------------------
Compiling Qhull with mingw/gcc on Windows
To compile Qhull with MINGW
- Download and extract Qhull (either GitHub, .tgz file, or .zip file)
- Install GitForWindows (https://gitforwindows.org/)
or MSYS2 (http://www.msys2.org/)
Install in C:\Git\... # Not 'Program Files\...' otherwise './configure && make' will not work
- Install MINGW-w64 with gcc (https://mingw-w64.org/)
1) Goto sourceforge -- https://sourceforge.net/projects/mingw-w64/files/
2) in folder -- mingw-w64
3) download installer -- MinGW-W64-install.exe
Run the installer
1) Select i686/posix/dwarf
2) Install in 'C:\mingw-w64' # Not 'Program Files\...'
Rename /c/mingw-w64/mingw32/bin/mingw32-make.exe to make.exe
Add the 'C:\mingw-w64\mingw32\bin' directory to your $PATH environment variable
Execute 'which make' to check that 'make' is mingw-w64's make
- Compile Qhull from the home directory
make help
make
Notes
- Mingw is included with Qt SDK in qt/Tools/mingw53_32
- If you use Windows XP
Install Road Bash (http://www.qhull.org/bash) or MSYS (http://www.mingw.org/wiki/msys)
Install MINGW (http://mingw.org/)
------------------
Compiling Qhull with cygwin on Windows
To compile Qhull with cygwin
- Download and extract Qhull (either GitHub, .tgz file, or .zip file)
- 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 tgz file
- tar zxf qhull-src.tgz
- cd qhull
- Use qhull/Makefile
Simpler Makefiles are qhull/src/libqhull/Makefile and qhull/src/libqhull_r/Makefile
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 libqhull_r.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 may compile with Borland C++ 5.0 bcc32. A Makefile is included.
Execute 'cd src/libqhull; make -f Mborland'. If you use the Borland IDE, set
the ANSI option in Options:Project:Compiler:Source:Language-compliance.
Qhull may compile with Borland C++ 4.02 for Win32 and DOS Power Pack.
Use 'cd src/libqhull; 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]
If you have troubles with the memory manager, you can turn it off by
defining qh_NOmem in mem.h.
------------------
Distributed files
README.txt // Instructions for installing Qhull
REGISTER.txt // Qhull registration
COPYING.txt // Copyright notice
QHULL-GO.lnk // Windows icon for eg/qhull-go.bat
Announce.txt // Announcement
CMakeLists.txt // CMake build file (2.6 or later)
File_id.diz // Package descriptor
index.htm // Home page
Makefile // Makefile for gcc and other compilers
qhull*.md5sum // md5sum for all files
bin/* // Qhull executables and dll (.zip only)
build/CMakeModules/CheckLFS.cmake // enables Large File Support in CMake
build/config.cmake.in // extract target variables
build/qhull.pc.in // pkg-config template for creating lib/pkgconfig/qhull*.pc
build/qhull-32.sln // 32-bit DevStudio solution and project files (2010 and later)
build/*-32.vcxproj
build/qhull-64.sln // 64-bit DevStudio solution and project files (2010 and later)
build/*-64.vcxproj
build/qhull.sln // DevStudio solution and project files (2005 and 2009)
build/*.vcproj
build/qhulltest/ // DevStudio project files for qhulltest (C++ and Qt)
build/README-build.txt // Contents of build/
eg/* // Test scripts and geomview files from q_eg
html/index.htm // Manual
html/qh-faq.htm // Frequently asked questions
html/qh-get.htm // Download page
html/qhull-cpp.xml // C++ style notes as a Road FAQ (www.qhull.org/road)
src/Changes.txt // Change history for Qhull and rbox
src/qhull-all.pro // Qt project
eg/
q_benchmark // shell script for precision and performance benchmark
q_benchmark-ok.txt // reviewed output from q_benchmark
q_eg // shell script for Geomview examples (eg.01.cube)
q_egtest // shell script for Geomview test examples
q_test // shell script to test qhull
q_test.bat // Windows batch test for QHULL-GO.bat
// cd bin; ..\eg\q_test.bat >q_test.x 2>&1
q_test-ok.txt // reviewed output from q_test
qhulltest-ok.txt // reviewed output from qhulltest (Qt only)
make-qhull_qh.sh // shell script to create non-reentrant qhull_qh from reentrant Qhull
make-vcproj.sh // shell script to create vcproj and vcxprog files
qhull-zip.sh // shell script to create distribution files
qtest.sh // shell script for testing and logging qhull
rbox consists of (bin, html):
rbox.exe // Win32 executable (.zip only)
rbox.htm // html manual
rbox.man // Unix man page
rbox.txt
qhull consists of (bin, html):
qconvex.exe // Win32 executables and dlls (.zip download only)
qhull.exe // Built with the reentrant library (about 2% slower)
qdelaunay.exe
qhalf.exe
qvoronoi.exe
qhull_r.dll
qhull-go.bat // command window
qconvex.htm // html manual
qdelaun.htm
qdelau_f.htm
qhalf.htm
qvoronoi.htm
qvoron_f.htm
qh-eg.htm
qh-code.htm
qh-impre.htm
index.htm
qh-opt*.htm
qh-quick.htm
qh--*.gif // images for manual
normal_voronoi_knauss_oesterle.jpg
qh_findbestfacet-drielsma.pdf
qhull.man // Unix man page
qhull.txt
bin/
msvcr80.dll // Visual C++ redistributable file (.zip download only)
src/
qhull/unix.c // Qhull and rbox applications using non-reentrant libqhullstatic.a
rbox/rbox.c
qconvex/qconvex.c
qhalf/qhalf.c
qdelaunay/qdelaunay.c
qvoronoi/qvoronoi.c
qhull/unix_r.c // Qhull and rbox applications using reentrant libqhullstatic_r.a
rbox/rbox_r.c
qconvex/qconvex_r.c // Qhull applications built with reentrant libqhull_r/Makefile
qhalf/qhalf_r.c
qdelaunay/qdelaun_r.c
qvoronoi/qvoronoi_r.c
user_eg/user_eg_r.c // example of using qhull_r.dll from a user program
user_eg2/user_eg2_r.c // example of using libqhullstatic_r.a from a user program
user_eg3/user_eg3_r.cpp // example of Qhull's C++ interface libqhullcpp with libqhullstatic_r.a
qhulltest/qhulltest.cpp // Test of Qhull's C++ interface using Qt's QTestLib
qhull-*.pri // Include files for Qt projects
testqset_r/testqset_r.c // Test of reentrant qset_r.c and mem_r.c
testqset/testqset.c // Test of non-rentrant qset.c and mem.c
src/libqhull
libqhull.pro // Qt project for non-rentrant, shared library (qhull.dll)
index.htm // design documentation for libqhull
qh-*.htm
qhull-exports.def // Export Definition files for Visual C++
qhull-nomerge-exports.def
qhull_p-exports.def
qhull_p-nomerge-exports.def
Makefile // Simple gcc Makefile for qhull and libqhullstatic.a
Mborland // Makefile for Borland C++ 5.0
libqhull.h // header file for qhull
user.h // header file of user definable constants
libqhull.c // Quickhull algorithm with partitioning
user.c // user re-definable functions
usermem.c
userprintf.c
userprintf_rbox.c
qhull_a.h // include files for libqhull/*.c
geom.c // geometric routines
geom2.c
geom.h
global.c // global variables
io.c // input-output routines
io.h
mem.c // memory routines, this is stand-alone code
mem.h
merge.c // merging of non-convex facets
merge.h
poly.c // polyhedron routines
poly2.c
poly.h
qset.c // set routines, this only depends on mem.c
qset.h
random.c // utilities w/ Park & Miller's random number generator
random.h
rboxlib.c // point set generator for rbox
stat.c // statistics
stat.h
src/libqhull_r
libqhull_r.pro // Qt project for rentrant, shared library (qhull_r.dll)
index.htm // design documentation for libqhull_r
qh-*_r.htm
qhull_r-exports.def // Export Definition files for Visual C++
qhull_r-nomerge-exports.def
Makefile // Simple gcc Makefile for qhull and libqhullstatic.a
libqhull_r.h // header file for qhull
user_r.h // header file of user definable constants
libqhull_r.c // Quickhull algorithm wi_r.hpartitioning
user_r.c // user re-definable functions
usermem.c
userprintf.c
userprintf_rbox.c
qhull_ra.h // include files for libqhull/*_r.c
geom_r.c // geometric routines
geom2.c
geom_r.h
global_r.c // global variables
io_r.c // input-output routines
io_r.h
mem_r.c // memory routines, this is stand-alone code
mem.h
merge_r.c // merging of non-convex facets
merge.h
poly_r.c // polyhedron routines
poly2.c
poly_r.h
qset_r.c // set routines, this only depends on mem_r.c
qset.h
random_r.c // utilities w/ Park & Miller's random number generator
random.h
rboxlib_r.c // point set generator for rbox
stat_r.c // statistics
stat.h
src/libqhullcpp/
libqhullcpp.pro // Qt project for renentrant, static C++ library
Qhull.cpp // Calls libqhull_r.c from C++
Qhull.h
qt-qhull.cpp // Supporting methods for Qt
Coordinates.cpp // input classes
Coordinates.h
PointCoordinates.cpp
PointCoordinates.h
RboxPoints.cpp // call rboxlib.c from C++
RboxPoints.h
QhullFacet.cpp // data structure classes
QhullFacet.h
QhullHyperplane.cpp
QhullHyperplane.h
QhullPoint.cpp
QhullPoint.h
QhullQh.cpp
QhullRidge.cpp
QhullRidge.h
QhullVertex.cpp
QhullVertex.h
QhullFacetList.cpp // collection classes
QhullFacetList.h
QhullFacetSet.cpp
QhullFacetSet.h
QhullIterator.h
QhullLinkedList.h
QhullPoints.cpp
QhullPoints.h
QhullPointSet.cpp
QhullPointSet.h
QhullSet.cpp
QhullSet.h
QhullSets.h
QhullVertexSet.cpp
QhullVertexSet.h
functionObjects.h // supporting classes
QhullError.cpp
QhullError.h
QhullQh.cpp
QhullQh.h
QhullStat.cpp
QhullStat.h
QhullUser.cpp
QhullUser.h
RoadError.cpp // Supporting base classes
RoadError.h
RoadLogEvent.cpp
RoadLogEvent.h
usermem_r-cpp.cpp // Optional override for qh_exit() to throw an error
src/libqhullstatic/
libqhullstatic.pro // Qt project for non-reentrant, static library
src/libqhullstatic_r/
libqhullstatic_r.pro // Qt project for reentrant, static library
src/qhulltest/
qhulltest.pro // Qt project for test of C++ interface
Coordinates_test.cpp // Test of each class
PointCoordinates_test.cpp
Qhull_test.cpp
QhullFacet_test.cpp
QhullFacetList_test.cpp
QhullFacetSet_test.cpp
QhullHyperplane_test.cpp
QhullLinkedList_test.cpp
QhullPoint_test.cpp
QhullPoints_test.cpp
QhullPointSet_test.cpp
QhullRidge_test.cpp
QhullSet_test.cpp
QhullVertex_test.cpp
QhullVertexSet_test.cpp
RboxPoints_test.cpp
RoadTest.cpp // Run multiple test files with QTestLib
RoadTest.h
------------------
Authors
C. Bradford Barber Hannu Huhdanpaa (Version 1.0)
[email protected] [email protected]
Qhull 1.0 and 2.0 were developed under NSF grants NSF/DMS-8920161
and NSF-CCR-91-15793 750-7504 at the Geometry Center and Harvard
University. If you find Qhull useful, please let us know.
qhull's People
Contributors
Stargazers
Watchers
Forkers
barak xelda1988 fflannery rotorliu mathstuf linwang741 niclasr chuckatkins blazesrus tkoyama010 lirmont vanwoos chongbingbao lidi100 pymesh linghushaoxia junjiezhang merlin-ext blldw sudohello ujayarat rickarkin frogsinspace haodongguo nine7nine caomw spirit-code nirzarrabi mabiaoxiaopang bergtholdt w77 minluli xuxcerberus growlercab houzhipi110 jbpkii myestro alalazo krimit hanhongyi dmitrysidorov surt91 pfem shartep scitao charliexu toreal con-phy miaowangtw sirokujira adegirmenci smcguffee chriscoxart ariellichtin dbukenberger kgreenek gruftikus zxp-proteus hjwang1 glotzerlab lordofblackwood chestnut42 hunter-packages f-feng vck davidcsterratt haraisao ericatplangrid ticiwang shihabrus markzh peitaozhao rhoneyager sxcblh yyxuxyy tamasmeszaros yunatoomi jxhhl dooxe simonmssu ceptontech kingmax shrikedehyperion joaander imerso3d zjudzl omsaaf freesciencecommunity alexrobomind zebus3d dsleep bartes1973 ishield avikde roehling pmorovic aabin shichongdong gajgeospatial stephanmgqhull's Issues
2015.1 is missing the CMakeModules directory
I tried to build qhull 2015.1from the tarball on www.qhull.org but cmake complained that it can't find CheckLFS.cmake. The directory CMakeModules seems to not have gone into the tarball.
Please update it.
3.7.2 tests fail on Cygwin
It does not happen on 3.7.1
Two tests are failing as Windows platform the file system is usualy case insensitive
and the binary qhull (aka qhull.exe) and the directory Qhull are seen from cygwin as the same
3/11 Testing: smoketest
3/11 Test: smoketest
Command: "/usr/bin/sh.exe" "-c" "./rbox D4 | ./qhull Tv"
Directory: /cygdrive/d/cyg_pub/devel/qhull/test2/qhull-2019.1-1.x86_64/build
"smoketest" start time: Dec 17 08:30 CET
Output:
----------------------------------------------------------
/usr/bin/sh: ./qhull: Is a directory
Starting the rbox smoketest for qhull. An immediate failure indicates
that non-reentrant rbox was linked to reentrant routines. An immediate
failure of qhull may indicate that qhull was linked to the wrong
qhull library. Also try 'rbox D4 | qhull T1'
<end of output>
Test time = 1.07 sec
----------------------------------------------------------
Test Failed.
"smoketest" end time: Dec 17 08:30 CET
"smoketest" time elapsed: 00:00:01
----------------------------------------------------------
4/11 Testing: rbox-10-qhull
4/11 Test: rbox-10-qhull
Command: "/usr/bin/sh.exe" "-c" "./rbox 10 | ./qhull Tv"
Directory: /cygdrive/d/cyg_pub/devel/qhull/test2/qhull-2019.1-1.x86_64/build
"rbox-10-qhull" start time: Dec 17 08:30 CET
Output:
----------------------------------------------------------
/usr/bin/sh: ./qhull: Is a directory
<end of output>
Test time = 0.13 sec
----------------------------------------------------------
Test Failed.
"rbox-10-qhull" end time: Dec 17 08:30 CET
"rbox-10-qhull" time elapsed: 00:00:00
----------------------------------------------------------
the problem is located at
write_basic_package_version_file(
"${CMAKE_CURRENT_BINARY_DIR}/Qhull/QhullConfigVersion.cmake"
and following lines.
A possible solution is to use a different directory name, as
write_basic_package_version_file(
"${CMAKE_CURRENT_BINARY_DIR}/Config/QhullConfigVersion.cmake"
QHull doesn't compute furthestdist
My qhull_r library and user code are built with #define qh_COMPUTEfurthest 0 which seems to mean that it is pre-computed and stored with the facets. However, the furthestdist field at this point https://github.com/yurivict/ChemWiz/blob/master/molecule-qhull.cpp#L35 is always zero.
Why doesn't it compute furthestdist?
Inconsistent builds
The builds for Qhull produce inconsistent results -- Qhull build systems
For example, the CMake build produces shared libraries for reentrant Qhull, non-reentrant Qhull, and qh_QHpointer (libqhull_r.so, libqhull.so, and libqhull_p.so). It installed functional documentation for Qhull with broken links {recently fixed).
CMake should only produce a shared library for reentrant Qhull. Non-reentrant Qhull is used for standalone applications without additional user code. The shared library libqhull_p.so (qh_QHpointer) should not be used.
The following changes are planned for Qhull 2020.2. Please let me know about worries or suggestions
-
CMakeLists.txt: Remove libqhull.so and libqhull_p.so from the default build targets
-
CMakeLists.txt: Allow disabling of static and shared library builds (#69). Rewrite the shared library builds to use libqhull_r.so.
-
CMakeLists.txt: Change the default CMAKE_INSTALL_PREFIX on Windows to '/usr/local'
-
DevStudio builds: remove libqhull and qhull_p from the default builds
-
All installs: Add the Qhull documentation tree to /usr/local/share/doc/qhull (index.htm, README.txt ... html/*, src/Changes.txt). Done for CMakeLists.txt
-
All installs: Add an 'uninstall' target
After Qhull 2020.2 is released, github users of Qhull should upgrade to libqhull_r.so (e.g., GDAL).
These changes for 2020.2 are on github
- CMakeLists.txt: Use same target name for Debug and non-Debug builds [Spacelm #76]
- CMakeLists.txt: Remove functional documentation from /usr/local/include/libqhull*
Most of the links are broken. - CMakeLists.txt: Move Qhull html documentation to /usr/local/share/doc/qhull/html/
Otherwise index.htm is overwritten and README links are broken - CMakeLists.txt: Add /usr/local/share/doc/qhull/src/Changes.txt
- Makefile, make install: Remove functional documentation from /usr/local/include/libqhull
and /usr/local/include/libqhullinclude/libqhull_r. Most of the links are broken. - Makefile, src/libqhull/Makefile: Add DEPRECATED.txt to /usr/local/include/libqhull
- Makefile, src/libqhull*/Makefile: Add 'make install' to the welcome prompt
- index.htm: Balance the top-page 'URL:' and 'To:' links
- index.htm: Send the top-page 'Functions' link to www.qhull.org (better 'src' links)
- index.htm: Make the bottom-page 'URL:' and 'To:' links the same as the top-page links
- index.htm: "please use rentrant Qhull (libqhull_r or libqhullstatic_r)"
- html/index.htm: Add rbox.txt to Contents and rename "Table of Contents"
- html/index.htm,qh-code.htm,qh-eg.htm,qh-impre.htm: Remove 'please wait while loading'
- libqhullcpp/qt-qhull.cpp: In toQList(), use count() to avoid a type error
- libqhullcpp/qt-qhull.cpp: In toQList(), use nullptr instead of NULL
- libqhullcpp/QhullSet.h: Declare 'QList toQList() const' to avoid a prototype error
- README.txt/Installing Qhull with Qt: The shadow build directory should be at the same level as 'src'
- README.txt/Compiling Qhull with Qt Creator: Copy steps from 'Installing Qhull with Qt'
Installing doesn't install bins or libs
Hi,
I'm building on Windows 7, with Visual Studio 2013, and Cmake 3.0.2
Cmake creates a solution, and then I am able to build it with VS 2013 (both Debug and Release) without any errors.
However, when I build the INSTALL project in VS 2013 (in order to copy the files to the install location), only the documentation and the include files are copied.
The binaries and libraries are not, and no bin or lib folder is created.
By looking at CmakeLists.txt, this line should be the faulty one:
install(TARGETS ${qhull_TARGETS_INSTALL}
RUNTIME DESTINATION ${BIN_INSTALL_DIR}
LIBRARY DESTINATION ${LIB_INSTALL_DIR}
ARCHIVE DESTINATION ${LIB_INSTALL_DIR})
but I don't know how to fix it.
Any help would be appreciated.
Best regards,
Stefan
libqhull and libqhull_r mutually exclusive: intended?
libqhull and libqhull_r have several similar symbols leading to ODR violation if libqhull and libqhull_r libs are both linked into the same project (for example through 2 dependencies, one depending on libqhull like gdal, and another one depending on libqhull_r):
extern const char qh_version[];
extern const char qh_version2[];
void qh_exit(int exitcode);
void qh_fprintf_stderr(int msgcode, const char *fmt, ... );
void qh_free(void *mem);
void *qh_malloc(size_t size);Is it intended?
It might be an issue in conan package manager (conan-io/conan-center-index#2408), because both libs are shipped together.
EDIT: I missed something, it's C, actually most functions in qhull and qhull_r lead to multiple definitions if both libs are linked :/
hull vertices order
I'm passing every single pixel of an image as a point to qhull so that I can receive a 2D outline. The problem is that the order of the vertices in the hull is somewhat tied to facets? I just want to draw the hull as a continuous line but when I iterate over the output of qhull.vertexList() the vertices are in a weird order. (Left: lines drawn between subsequent vertices in QhullVertexList, Right: Input Image)
Documentation says that "In 2-d, the extreme points (vertices) are listed in counterclockwise order". But that doesn't seem to be the case.
Any ideas on how to get the vertices in sequential order so that I can draw the convex hull correctly?
Compiler warnings in libqhull_r
i updating the R geometry library with the latest version of Qhull (pulled from github today), and I notice the following warnings when compiling:
d:/Compiler/gcc-4.9.3/mingw_32/bin/gcc -I"D:/RCompile/recent/R-3.5.2/include" -DNDEBUG -I"d:/RCompile/CRANpkg/lib/3.5/Rcpp/include" -I"d:/RCompile/CRANpkg/lib/3.5/RcppProgress/include" -I"d:/Compiler/gcc-4.9.3/local330/include" -include Rgeometry.h -O3 -Wall -std=gnu99 -mtune=core2 -c merge_r.c -o merge_r.o
merge_r.c: In function 'qh_premerge':
merge_r.c:79:7: warning: variable 'apexpointid' set but not used [-Wunused-but-set-variable]
int apexpointid;
^
merge_r.c: In function 'qh_getpinchedmerges':
merge_r.c:1787:32: warning: unused variable 'opposite' [-Wunused-variable]
vertexT *nearest, *pinched, *opposite= NULL, *bestvertex= NULL, *bestpinched= NULL;
^
merge_r.c:1786:9: warning: unused variable 'ridges' [-Wunused-variable]
setT *ridges= NULL;
^
merge_r.c: In function 'qh_merge_pinchedvertices':
merge_r.c:2568:9: warning: unused variable 'ridges' [-Wunused-variable]
setT *ridges= NULL;
^
merge_r.c: In function 'qh_next_facetmerge':
merge_r.c:4019:10: warning: unused variable 'bestdist' [-Wunused-variable]
coordT bestdist= REALmax;
^
merge_r.c: In function 'qh_rename_adjacentvertex':
merge_r.c:4390:9: warning: unused variable 'angledegen' [-Wunused-variable]
realT angledegen= qh_ANGLEdegen;
^
d:/Compiler/gcc-4.9.3/mingw_32/bin/gcc -I"D:/RCompile/recent/R-3.5.2/include" -DNDEBUG -I"d:/RCompile/CRANpkg/lib/3.5/Rcpp/include" -I"d:/RCompile/CRANpkg/lib/3.5/RcppProgress/include" -I"d:/Compiler/gcc-4.9.3/local330/include" -include Rgeometry.h -O3 -Wall -std=gnu99 -mtune=core2 -c poly2_r.c -o poly2_r.o
poly2_r.c: In function 'qh_checkfacet':
poly2_r.c:823:11: warning: suggest parentheses around operand of '!' or change '|' to '||' or '!' to '~' [-Wparentheses]
if (!ridge->tested | ridge->nonconvex | ridge->mergevertex) {
^
poly2_r.c: In function 'qh_matchdupridge':
poly2_r.c:2271:60: warning: unused variable 'samecycle_count' [-Wunused-variable]
int skip, newskip, nextskip= 0, maxskip= 0, maxskip2= 0, samecycle_count= 0, makematch;
^
poly2_r.c: In function 'qh_matchdupridge_coplanarhorizon':
poly2_r.c:2443:82: warning: unused variable 'ismergeridge' [-Wunused-variable]
boolT same, ismatch, ismergehorizon, isbesthorizon= False, isfirstmatch= True, ismergeridge= False, isdup;
^
poly2_r.c:2443:40: warning: unused variable 'isbesthorizon' [-Wunused-variable]
boolT same, ismatch, ismergehorizon, isbesthorizon= False, isfirstmatch= True, ismergeridge= False, isdup;
^
poly2_r.c: In function 'qh_addfacetvertex':
poly2_r.c:47:5: warning: 'vertex_i' may be used uninitialized in this function [-Wmaybe-uninitialized]
qh_setaddnth(qh, &facet->vertices, vertex_i, newvertex);
^
In file included from ./Rgeometry.h:24:0,
from <command-line>:0:
poly2_r.c: In function 'qh_matchdupridge_coplanarhorizon':
./qhull_ra.h:82:47: warning: 'horizon' may be used uninitialized in this function [-Wmaybe-uninitialized]
#define trace2(args) {if (qh->IStracing >= 2) qh_fprintf args;}
^
poly2_r.c:2438:42: note: 'horizon' was declared here
facetT *facet, *newfacet, *nextfacet, *horizon, *newhorizon, *neighbor;
^
poly2_r.c: In function 'qh_opposite_vertex':
poly2_r.c:2825:7: warning: 'facet' may be used uninitialized in this function [-Wmaybe-uninitialized]
qh_errexit2(qh, qh_ERRqhull, facet, neighbor);
^
poly2_r.c: In function 'qh_replacefacetvertex':
poly2_r.c:3120:10: warning: 'vertex_n' may be used uninitialized in this function [-Wmaybe-uninitialized]
new_i--;
^
It would be great if you could investigate.
Moving version 2018.0.1 to its own branch
Since you asked for advice on how to move version 2018.0.1 to a new branch in the wiki, I came up with the following procedure:
# Ensure you have a clean working directory
# Make sure master is up to date
$ git fetch
# Create the new branch for version 2018.0.1
$ git branch --no-track 2018.0.1 origin/master
# Reset master to version 7.2.1
$ git checkout master && git reset --hard v7.2.1
# Publish the changes to master
$ git checkout master && git push --force-with-lease
# Publish the new branch
$ git checkout 2018.0.1 && git push --set-upstream origin 2018.0.1This will move all commits since v7.2.1 to a new branch 2018.0.1.
Every contributor must also reset their local master after these changes. This is done with
$ git fetch
$ git checkout master && git reset --hard v7.2.1Finding Hulls in embedded spaces
I'm currently trying to find convex hulls for a small number of points in a potentially large dimension. The issue I'm having is that, the points themselves are not necessarily in general position, so they do not represent a polytope of the dimension they live in. For example, I could have a set of points that all lie on a line, but are given by a set of four coordinates embedded in 4D. I would still like qhull to tell me that the convex hull is the line connected the two extreme points, however it will not do this.
Is there are way to force qhull to do this as it stands or does it require a completely new set of tools to be written?
Qhull does not compile on macOS
Seeing this with both the latest stable release as well as master:
Scanning dependencies of target qhull
[ 73%] Building C object CMakeFiles/qhull.dir/src/qhull/unix_r.c.o
[ 75%] Linking C executable qhull
ld: can't open output file for writing: qhull, errno=21 for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)
Any thoughts?
QhullFacet seems to leak memory
When using this kind of range-based loop
for (QhullFacet facet : qhull.facetList()){
// ...
}
(which is used multiple times in the user_eg3_r.cpp example)
some memory seems not to be returned back.
It seems as though maybe the QhullFacet destructor doesn't release some memory that was allocated by the object.
One can naturally use a reference instead of a copy
for (QhullFacet& facet : qhull.facetList()){
// ...
}
which seems to work fine.
However, this should be fixed.
Software license unclear?
Thank you for the great tool!
Neither http://www.qhull.org/COPYING.txt nor github.com/qhull/qhull/COPYING.txt don't seem to declare license for your software. What license is qhull is opensource under, and would you clarify it somewhere?
Tag for v8.0.0 or release 2020.1
I was trying to clone the repository and execute git checkout 2020.1 or git checkout v8.0.0, but that doesn't work because it seems that a tag hasn't been created for 2020.1 or 8.0.0. Is that in the process of being done?
I'm mainly asking this because I'm working on Homebrew's livecheck feature which checks for the latest versions of packages, and qhull's latest 2020.1 release wasn't getting detected.
Thank you!
qhull.org website is defaced
It looks like the qhull.org website is defaced and is hosting pages that redirect to Viagra sales websites. Use the following google link to see that the viagra forwarding pages have been cached on google already: google.com/search?q=site:qhull.org+viagra
Can somebody on the team that is responsible be notified so that they can clean the server up and remove this from the webroot? This will badly affect qhulls results on google as soon as they become associated with such content.
Broken url
This url returns a 404 page: https://github.com/qhull/qhull/blob/master/Announce.txt#L28
Possible substitute: http://dl.acm.org/citation.cfm?id=235821
Qhull imported targets hard to consume
Currently, Qhull creates different imported targets for its components depending on shared and debug.
It makes it hard to properly consume Qhull in another library. Indeed, downstream build system shouldn't care weither Qhull was built as Debug or static/shared (it should be final app decision).
It would be nice to be able to consume Qhull like this:
find_package(Qhull REQUIRED libqhull libqhull_r CONFIG)
target_link_libraries(otherlibA PRIVATE Qhull::libqhull)
target_link_libraries(otherlibB PRIVATE Qhull::libqhull_r)instead of something tedious like this:
option(QHULL_SHARED "" OFF)
find_package(Qhull REQUIRED)
if(QHULL_SHARED)
if(CMAKE_BUILD_TYPE MATCHES "[dD]ebug")
target_link_libraries(otherlibA PRIVATE Qhull::qhull_d)
target_link_libraries(otherlibB PRIVATE Qhull::qhull_rd)
else()
target_link_libraries(otherlibA PRIVATE Qhull::libqhull)
target_link_libraries(otherlibB PRIVATE Qhull::qhull_r)
endif()
else()
if(CMAKE_BUILD_TYPE MATCHES "[dD]ebug")
target_link_libraries(otherlibA PRIVATE Qhull::qhullstatic_d)
target_link_libraries(otherlibB PRIVATE Qhull::qhullstatic_rd)
else()
target_link_libraries(otherlibA PRIVATE Qhull::qhullstatic)
target_link_libraries(otherlibB PRIVATE Qhull::qhullstatic_r)
endif()
endif()/usr/bin/ld: cannot open output file qhull: Is a directory
Hi!
I am using your great code! I have successfully config and generate the code by using cmake-3.16.0-rc4 on ubuntu 16.04, and my gcc/g++ version is 4.8.5, but when I make the code, errors occurred:
Can you give me some advice about that? Than you for your kind assistance!
Zeng
wrong convex hull reconstruction from the hyper planes returned by qhull
Hi, I'm doing some experiments with qhull to construct convex hull from points (c++), the problem occurred when debugging my program, I just found I can not reconstruct the convex hull from hyperplanes returned by qhull
here is the function
template <typename Number>
std::vector<ratbox::HalfSpace<Number>> getHalfSpaces(const orgQhull::Qhull& qhull)
{
std::vector<ratbox::HalfSpace<Number>> retHalfSpaces;
for (const orgQhull::QhullFacet& qhullFacet : qhull.facetList())
{
// retHalfSpaces.emplace_back(ratbox::HalfSpace<Number>(getNormal<Number>(qhullFacet.hyperplane()),
// getOffset<Number>(qhullFacet.hyperplane())));
retHalfSpaces.emplace_back(ratbox::HalfSpace<Number>(getNormal<Number>(qhullFacet.hyperplane()),
getOffset<Number>(qhullFacet.hyperplane())));
}
return retHalfSpaces;
}
so, is it wrong to call hyperplane() method?? or should I use an inner hyperplane or outer hyperplane?? or is there some operations else I haven't complete??
the algorithm I implemented to reconstruct the convex hull can be found in the link following:
https://ww2.mathworks.cn/matlabcentral/fileexchange/7894-con2vert-constraints-to-vertices
I just use this algorithm to get all the vertices and re-input them into qhull to construct the new convex hull, but it failed, there are some extremely strange points which coordinate are too close to the origin or too far away from the reasonable domain.
I've done some tests about the function conv2vert, the results are good, so I guess there may be some mistakes when using qhull?? can you help me to solve this problem??
any suggestion would be helpful
Best
Missing examples in the CMake file
I have found the examples user_eg1, user_eg2 and user_eg3 helpful to understand how to interact with the library. And I have noticed them thanks to this SO.
Why are they missing from the CMake file?
Installation make
Hey,
I want to use qhull in a C++ program; thus I wanted to build Qhull, static libraries, shared library, and C++ interface with gcc. However I got this error message :
make: *** No rule to make target src/libqhull/usermem_r.o', needed bybin/testqset_r'. Stop.
Thank you,
Option to use shared linking for executables by default
Currently, the executables are linked statically. It would be nice if there were an option to use dynamic linking.
Lines 473 to 477 in 7afedcc
Periodic Boundary Conditions
Would it be possible to implement containers with periodic boundary conditions?
Coplanar points not in the nearest facet
Hi,
when running this command using qhull built from the v7.3.0 branch
echo -e "3\n19\n0.40000000000000002 0.35999999999999999 1.0019424460431654\n0.40000000000000002 0.35999999999999999 1.0800000000000001\n0.40000000000000002 0.23999999999999994 1.0800000000000001\n0.40000000000000002 0.23999999999999999 1.0097122302158275\n0.40000000000000002 0.36000000000000004 1\n0.40000000000000002 0.23999999999999994 1\n0.41079136690647483 0.23999999999999994 1\n0.47999999999999998 0.24000000000000002 1\n0.47999999999999998 0.35999999999999999 1\n0.40215827338129495 0.36000000000000004 1\n0.36000000000000004 0.29999999999999999 0.95999999999999996\n0.36000000000000004 0.29999999999999999 1.0800000000000001\n0.47999999999999998 0.29999999999999999 1.0800000000000001\n0.48000000000000004 0.29999999999999999 0.95999999999999996\n0.35999999999999999 0.35999999999999999 0.95999999999999996\n0.35999999999999999 0.35999999999999999 1.0800000000000001\n0.47999999999999998 0.23999999999999999 1.0800000000000001\n0.47999999999999998 0.35999999999999999 0.95999999999999996\n0.47999999999999998 0.35999999999999999 1.0800000000000001" | qhull Qt Fc FP FI nI noticed that the point 9 and 6 are not in the closest facet. 9 should be in facet 41 and not 40. 6 should be in 63 and not 62. Am I misinterpret the docs or is this a bug?
Thanks
Add pkg-config support
For Linux users it would be valuable to provide a qhull.pc file. This allows for a standardized way of figuring out the location of qhull on the system. This configuration file is generated at configuration (i.e. during cmake runs) time. Note that pkg-config can also be used under Windows, and helps to find packages installed in non-standard locations.
I can send a PR if there is interest in this feature.
Computing the volume of a convex polytope when the vertices are known
First of all, thanks for the effort, qhull has been great help.
I have problem where I have a set of points which I know for certain to be vertices of a convex polytope, and I would like to compute the volume of that polytope. The issue when using qhull (from python, via the scipy.spatial interface) arises when the dimension of the space & the number of vertices gets large, as mentioned in the performance notes. I was wondering whether it is possible to stretch the limitations a bit by providing the vertices, or is the runtime dominated by the facet search?
The problem could also be simplified a bit as I believe I could also compute the facets.
The dimensionality ranges from 5 - ~35 -dim, and the number of points grows with the dimensionality.
Concretely, the problem I have is that I want to determine the ratio (only the ratio) of volumes of convex polytopes defined by the intersection of a hyperplane and the unit (n-1)-simplex in Rn. I would appreciate any help and pointers you might provide!
Broken QLinkedList::const_iterator::operator->
I report here a minor issue encounter while using this very useful library.
Shouldn't
qhull/src/libqhullcpp/QhullLinkedList.h
Line 175 in 7afedcc
be
const T * operator->() const { return &i; } ?
About qhull's version
what is the difference between the current version of qhull on the github and that on the gitorious, especiall for qhull's c++ interface? If there are some diffs, i hope there will be a doc to illustrate it. Thanks:)
Dangling pointer
Detected by clang trunk:
src/libqhullcpp/RoadError.h:67:52: warning: returning address of local temporary object [-Wreturn-stack-address]
static const char *stringGlobalLog() { return global_log.str().c_str(); }
because str() yields a temporary std::string, and thus this function returns a pointer to a destroyed buffer.
See
qhull/src/libqhullcpp/RoadError.h
Line 67 in 331d567
Halfspace intersections with C++ interface
Hi,
I'm trying to compute halfspace intersections with the C++ interface following this test example.
If I however try the simple case of an unit square in 2D
//halfspaces defining the unitsquare [0,1] x [0,1]
double normals[] = {-1, 0, 0,
0, -1, 0,
1, 0, -1,
0, 1, -1 };
Coordinates feasible(std::vector<double>({.5,.5}));
Qhull q;
q.setFeasiblePoint(feasible);
q.runQhull("unit square", 3, 4, normals, "H");
std::cout<< q.vertexList() << std::endl;I get the following output
- p3 (v2): 0 2
- p1 (v4): 0 -2
- p0 (v0): -2 0
- p2 (v1): 2 0
which is a bit unexpected. I guess I am missing something basic (e.g. if I change the feasible point slightly, the resulting vertices change vastly).
Is that behaviour expected, and if so, what would be the correct way to do it?
Any help is appreciated!
gcc 9.3 complains about redundant function declarations:
Please fix the following warnings. Interestingly, gcc doesn't silence those warnings, even if the qhull includes are declared as
-isystem. I consider that a gcc bug...
In file included from /opt/ws_moveit/src/geometric_shapes/src/bodies.cpp:44:
394/usr/include/libqhull_r/libqhull_r.h:1057:9: warning: redundant redeclaration of ‘void qh_printsummary(qhT*, FILE*)’ in same scope [-Wredundant-decls]
395 1057 | void qh_printsummary(qhT *qh, FILE *fp);
396 | ^~~~~~~~~~~~~~~
397/usr/include/libqhull_r/libqhull_r.h:1024:9: note: previous declaration of ‘void qh_printsummary(qhT*, FILE*)’
398 1024 | void qh_printsummary(qhT *qh, FILE *fp);
399 | ^~~~~~~~~~~~~~~
400/usr/include/libqhull_r/libqhull_r.h:1099:6: warning: redundant redeclaration of ‘void qh_meminit(qhT*, FILE*)’ in same scope [-Wredundant-decls]
401 1099 | void qh_meminit(qhT *qh, FILE *ferr);
402 | ^~~~~~~~~~
403In file included from /usr/include/libqhull_r/libqhull_r.h:31,
404 from /opt/ws_moveit/src/geometric_shapes/src/bodies.cpp:44:
405/usr/include/libqhull_r/mem_r.h:218:6: note: previous declaration of ‘void qh_meminit(qhT*, FILE*)’
406 218 | void qh_meminit(qhT *qh, FILE *ferr);
407 | ^~~~~~~~~~
408In file included from /opt/ws_moveit/src/geometric_shapes/src/bodies.cpp:44:
409/usr/include/libqhull_r/libqhull_r.h:1100:6: warning: redundant redeclaration of ‘void qh_memfreeshort(qhT*, int*, int*)’ in same scope [-Wredundant-decls]
410 1100 | void qh_memfreeshort(qhT *qh, int *curlong, int *totlong);
411 | ^~~~~~~~~~~~~~~
412In file included from /usr/include/libqhull_r/libqhull_r.h:31,
413 from /opt/ws_moveit/src/geometric_shapes/src/bodies.cpp:44:
414/usr/include/libqhull_r/mem_r.h:217:6: note: previous declaration of ‘void qh_memfreeshort(qhT*, int*, int*)’
415 217 | void qh_memfreeshort(qhT *qh, int *curlong, int *totlong);
416 | ^~~~~~~~~~~~~~~
417In file included from /opt/ws_moveit/src/geometric_shapes/src/bodies.cpp:44:
418/usr/include/libqhull_r/libqhull_r.h:1123:9: warning: redundant redeclaration of ‘void qh_collectstatistics(qhT*)’ in same scope [-Wredundant-decls]
419 1123 | void qh_collectstatistics(qhT *qh);
420 | ^~~~~~~~~~~~~~~~~~~~
421In file included from /usr/include/libqhull_r/libqhull_r.h:121,
422 from /opt/ws_moveit/src/geometric_shapes/src/bodies.cpp:44:
423/usr/include/libqhull_r/stat_r.h:515:9: note: previous declaration of ‘void qh_collectstatistics(qhT*)’
424 515 | void qh_collectstatistics(qhT *qh);
425 | ^~~~~~~~~~~~~~~~~~~~
426In file included from /opt/ws_moveit/src/geometric_shapes/src/bodies.cpp:44:
427/usr/include/libqhull_r/libqhull_r.h:1124:9: warning: redundant redeclaration of ‘void qh_printallstatistics(qhT*, FILE*, const char*)’ in same scope [-Wredundant-decls]
428 1124 | void qh_printallstatistics(qhT *qh, FILE *fp, const char *string);
429 | ^~~~~~~~~~~~~~~~~~~~~
430In file included from /usr/include/libqhull_r/libqhull_r.h:121,
431 from /opt/ws_moveit/src/geometric_shapes/src/bodies.cpp:44:
432/usr/include/libqhull_r/stat_r.h:519:9: note: previous declaration of ‘void qh_printallstatistics(qhT*, FILE*, const char*)’
433 519 | void qh_printallstatistics(qhT *qh, FILE *fp, const char *string);
434 | ^~~~~~~~~~~~~~~~~~~~~
Likely accidental zero'ification of variable
Found by Coverity Scan on the internal libqhull in GDAL
At https://github.com/qhull/qhull/blob/master/src/libqhull/io.c#L429, there's :
if (angle < 0)
angle -= angle;
This results in zero'ifying the variable, whereas changing its sign was probably intended.
Unable to compile qhull 2020.1 on MacOS
When I try to compile the library on MacOS I got the following error
In file included from /Users/runner/runners/2.263.0/work/bipedal-locomotion-framework/bipedal-locomotion-framework/qhull/src/libqhullcpp/QhullUser.cpp:9:
/Users/runner/runners/2.263.0/work/bipedal-locomotion-framework/bipedal-locomotion-framework/qhull/src/libqhullcpp/QhullUser.h:39:41: error: a space is required between consecutive right angle brackets (use '> >')
std::vector< std::vector< double>> doubles_vector; //! vectors for capturing ints and doubles
^~
> >
/Users/runner/runners/2.263.0/work/bipedal-locomotion-framework/bipedal-locomotion-framework/qhull/src/libqhullcpp/QhullUser.h:40:38: error: a space is required between consecutive right angle brackets (use '> >')
std::vector< std::vector< int>> ints_vector;
^~
> >
/Users/runner/runners/2.263.0/work/bipedal-locomotion-framework/bipedal-locomotion-framework/qhull/src/libqhullcpp/QhullUser.h:80:47: error: a space is required between consecutive right angle brackets (use '> >')
const std::vector< std::vector< double>> &doublesVector() const { return doubles_vector; }
^~
> >
/Users/runner/runners/2.263.0/work/bipedal-locomotion-framework/bipedal-locomotion-framework/qhull/src/libqhullcpp/QhullUser.h:84:44: error: a space is required between consecutive right angle brackets (use '> >')
const std::vector< std::vector< int>> &intsVector() const { return ints_vector; }
^~
> >
4 errors generated.
This error is caused because the compiler does not use C++11 Please find here the detailed explanation.
This problem can be easily solved by adding the following patch
diff --git a/CMakeLists.txt b/CMakeLists.txt
index bf7a259..b527e23 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -67,6 +67,8 @@
project(qhull)
cmake_minimum_required(VERSION 3.0)
+set(CMAKE_CXX_STANDARD 11)
+
# Define qhull_VERSION in README.txt, Announce.txt, qh-get.htm, CMakeLists.txt
# qhull-zip.sh (twice), qhull-wiki.md, qhull-news.htm, File_id.diz, index.htm
# Makefile (SO), qhull-warn.pri (VERSION), qhull-exports.def (VERSION 8.0), qhull_p-exports.def, qhull_r-exports.defFixing this issue will also allow the porting of the new version of the library in vcpkg (Associated issue: microsoft/vcpkg#12004)
Another solution is to use target_compile_features(mylib PUBLIC cxx_std_11) but this requires to changed the required version of cmake from 3.0 to 3.1.
If you are interested I can propose a PR with the first fix I proposed.
Qz option can lead to points being lost
As part of my work on R's geometry package, I'm trying to understand how the Qz option works. I had been planning to make this a default option in the next release, as it is in python and octave (davidcsterratt/geometry#4). However, it turns out that with a particular set of 2D points (attached; thanks to @Jean-Romain), this gives a triangulation with far fewer triangles than expected (davidcsterratt/geometry#11).
I don't think this behaviour is due to how the R geometry package has used the Qhull reentrant library, as I get similar behaviour when I give the same set of points to the qdelaunay program. Without Qz there are 156228 Delaunay regions:
$ bin/qdelaunay Qt < points.txt
Delaunay triangulation by the convex hull of 78150 points in 3-d:
Number of input sites: 78142
Number of nearly incident points: 8
Number of Delaunay regions: 156228
Number of triangulated facets: 7962
Statistics for: | qdelaunay Qt
Number of points processed: 78142
Number of hyperplanes created: 433708
Number of facets in hull: 156280
Number of distance tests for qhull: 4319091
Number of distance tests for merging: 2240387
Number of distance tests for checking: 1180894
Number of merged facets: 16903
CPU seconds to compute hull (after input): 0.56
Maximum distance of point above facet: 6.8e-09 (1.2x)
Maximum distance of vertex below facet: -9e-09 (1.5x)
With Qz there are 10732 regions:
$ bin/qdelaunay Qt Qz < points.txt
Delaunay triangulation by the convex hull of 78151 points in 3-d:
Number of input sites and at-infinity: 5394
Total number of deleted points due to merging: 180
Number of nearly incident points: 72577
Number of Delaunay regions: 10732
Number of triangulated facets: 3825
Statistics for: | qdelaunay Qt Qz
Number of points processed: 5574
Number of hyperplanes created: 27640
Number of facets in hull: 10784
Number of distance tests for qhull: 10858555
Number of distance tests for merging: 394406
Number of distance tests for checking: 2613735
Number of merged facets: 13954
CPU seconds to compute hull (after input): 0.33
Maximum distance of point above facet: 6.7e-09 (1.2x)
Maximum distance of vertex below facet: -1.1e-08 (1.9x)
I'd much appreciate it if you could let me know if this behaviour is expected, and if so why.
points.txt
Documentation is installed in include dir
The documentation for libqhull_r and libqhull is installed in ${INCLUDE_INSTALL_DIR}/libqhull_r and ${INCLUDE_INSTALL_DIR}/libqhullrespectively. I believe those htm files should rather go in ${DOC_INSTALL_DIR}.
Missing release tag
Hi, please could you add release tags every time a new release is there.
For example, it seems that the latest revision for Qhull 2015.2 is the commit 5a79a0009454c86e9848646b3c296009125231bf on 19 Jan, it would have been easier to find if it has been tagged.
Best regards
Memory leak
Hi, I'm using MSVC 2012 and having some issues with memory leaks.
I'm using the C++ Interface (qhullcpp and libqhullstatic_r) to compute convex hulls from my application.
The example user_eg3_r.cpp also have these leaks.
Are you working on it or have any advice for me to try to fix it?
Thanks.
ABI breakage from 2015.2 to 2019.1
Hi,
while working on the Debian package for qhull, I ran abi-compliance-checker on the library and noticed that version 2019.1 is not binary compatible to the previously packaged version 2015.2, yet they have the same SOVERSION (7). Could you please bump the SOVERSION to avoid version conflicts?
Thanks!
Error compiling reentrant Qhull on Linux
Hello,
I was trying to compile reentrant Qhull on a cluster running CentOS 7.3.1611 to use within an optimization algorithm (PA-DDS) but encountered some errors. Can you guys help me figure out what was the cause? Any suggestion would be appreciated. Thanks!
1. Running "make" under src/libqhull_r
[libqhull_r]$ make
# On MINSYS, 'ln -s' may create a copy instead of a symbolic link
[ -f qconvex_r.c ] || ln -s ../qconvex/qconvex_r.c
[ -f qdelaun_r.c ] || ln -s ../qdelaunay/qdelaun_r.c
[ -f qhalf_r.c ] || ln -s ../qhalf/qhalf_r.c
[ -f qvoronoi_r.c ] || ln -s ../qvoronoi/qvoronoi_r.c
[ -f rbox_r.c ] || ln -s ../rbox/rbox_r.c
[ -f testqset_r.c ] || ln -s ../testqset_r/testqset_r.c
[ -f unix_r.c ] || ln -s ../qhull/unix_r.c
[ -f user_eg_r.c ] || ln -s ../user_eg/user_eg_r.c
[ -f user_eg2_r.c ] || ln -s ../user_eg2/user_eg2_r.c
make: *** No rule to make target `qconvex_r.o', needed by `qhull_all'. Stop.
2. Running "make lib/libqhullstatic.a"
[qhull-2015.2]$ make lib/libqhullstatic.a
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/glbqhull/global.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/sthull/stat.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/geqhull/geom2.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/poqhull/poly2.c
src/libqhull/poly2.c: In function ‘qh_delridge’:
src/libqhull/poly2.c:1127:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
^
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/meqhull/merge.c
src/libqhull/merge.c: In function ‘qh_all_merges’:
src/libqhull/merge.c:219:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
^
src/libqhull/merge.c: In function ‘qh_appendmergeset’:
src/libqhull/merge.c:322:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
^
src/libqhull/merge.c: In function ‘qh_mergecycle_ridges’:
src/libqhull/merge.c:2091:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
^
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/lilibqhull/libqhull.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/gehull/geom.c
src/libqhull/geom.c: In function ‘qh_projectpoint’:
src/libqhull/geom.c:897:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
^
src/libqhull/geom.c: In function ‘qh_setfacetplane’:
src/libqhull/geom.c:935:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
^
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/pohull/poly.c
src/libqhull/poly.c: In function ‘qh_delfacet’:
src/libqhull/poly.c:248:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
^
src/libqhull/poly.c: In function ‘qh_makenew_nonsimplicial’:
src/libqhull/poly.c:564:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
^
src/libqhull/poly.c: In function ‘qh_newfacet’:
src/libqhull/poly.c:987:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
^
src/libqhull/poly.c: In function ‘qh_newridge’:
src/libqhull/poly.c:1020:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
^
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/qshull/qset.c
src/libqhull/qset.c: In function ‘qh_setfree’:
src/libqhull/qset.c:718:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
^
src/libqhull/qset.c: In function ‘qh_setnew’:
src/libqhull/qset.c:928:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
^
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/meull/mem.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/rabqhull/random.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/usibqhull/usermem.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/usc/libqhull/userprintf.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/ioll/io.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/ushull/user.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/rbibqhull/rboxlib.c
src/libqhull/rboxlib.c: In function ‘qh_rboxpoints’:
src/libqhull/rboxlib.c:93:7: warning: variable ‘coincidentcount’ might be clobbered by ‘longjmp’ or ‘vfored]
int coincidentcount=0, coincidenttotal=0, coincidentpoints=0;
^
src/libqhull/rboxlib.c:95:7: warning: variable ‘dim’ might be clobbered by ‘longjmp’ or ‘vfork’ [-Wclobb
int dim=3, numpoints=0, totpoints, addpoints=0;
^
src/libqhull/rboxlib.c:95:38: warning: variable ‘addpoints’ might be clobbered by ‘longjmp’ or ‘vfork’ [
int dim=3, numpoints=0, totpoints, addpoints=0;
^
src/libqhull/rboxlib.c:96:7: warning: variable ‘issphere’ might be clobbered by ‘longjmp’ or ‘vfork’ [-W
int issphere=0, isaxis=0, iscdd=0, islens=0, isregular=0, iswidth=0, addcube=0;
^
src/libqhull/rboxlib.c:96:19: warning: variable ‘isaxis’ might be clobbered by ‘longjmp’ or ‘vfork’ [-Wc
int issphere=0, isaxis=0, iscdd=0, islens=0, isregular=0, iswidth=0, addcube=0;
^
src/libqhull/rboxlib.c:96:30: warning: variable ‘iscdd’ might be clobbered by ‘longjmp’ or ‘vfork’ [-Wcl
int issphere=0, isaxis=0, iscdd=0, islens=0, isregular=0, iswidth=0, addcube=0;
^
src/libqhull/rboxlib.c:96:39: warning: variable ‘islens’ might be clobbered by ‘longjmp’ or ‘vfork’ [-Wc
int issphere=0, isaxis=0, iscdd=0, islens=0, isregular=0, iswidth=0, addcube=0;
^
src/libqhull/rboxlib.c:96:49: warning: variable ‘isregular’ might be clobbered by ‘longjmp’ or ‘vfork’ [
int issphere=0, isaxis=0, iscdd=0, islens=0, isregular=0, iswidth=0, addcube=0;
^
src/libqhull/rboxlib.c:96:62: warning: variable ‘iswidth’ might be clobbered by ‘longjmp’ or ‘vfork’ [-W
int issphere=0, isaxis=0, iscdd=0, islens=0, isregular=0, iswidth=0, addcube=0;
^
src/libqhull/rboxlib.c:96:73: warning: variable ‘addcube’ might be clobbered by ‘longjmp’ or ‘vfork’ [-W
int issphere=0, isaxis=0, iscdd=0, islens=0, isregular=0, iswidth=0, addcube=0;
^
src/libqhull/rboxlib.c:97:16: warning: variable ‘isspiral’ might be clobbered by ‘longjmp’ or ‘vfork’ [-
int isgap=0, isspiral=0, NOcommand=0, adddiamond=0;
^
src/libqhull/rboxlib.c:97:28: warning: variable ‘NOcommand’ might be clobbered by ‘longjmp’ or ‘vfork’ [
int isgap=0, isspiral=0, NOcommand=0, adddiamond=0;
^
src/libqhull/rboxlib.c:97:41: warning: variable ‘adddiamond’ might be clobbered by ‘longjmp’ or ‘vfork’
int isgap=0, isspiral=0, NOcommand=0, adddiamond=0;
^
src/libqhull/rboxlib.c:98:7: warning: variable ‘israndom’ might be clobbered by ‘longjmp’ or ‘vfork’ [-W
int israndom=0, istime=0;
^
src/libqhull/rboxlib.c:98:19: warning: variable ‘istime’ might be clobbered by ‘longjmp’ or ‘vfork’ [-Wc
int israndom=0, istime=0;
^
src/libqhull/rboxlib.c:99:7: warning: variable ‘isbox’ might be clobbered by ‘longjmp’ or ‘vfork’ [-Wclo
int isbox=0, issimplex=0, issimplex2=0, ismesh=0;
^
src/libqhull/rboxlib.c:99:16: warning: variable ‘issimplex’ might be clobbered by ‘longjmp’ or ‘vfork’ [
int isbox=0, issimplex=0, issimplex2=0, ismesh=0;
^
src/libqhull/rboxlib.c:99:29: warning: variable ‘issimplex2’ might be clobbered by ‘longjmp’ or ‘vfork’
int isbox=0, issimplex=0, issimplex2=0, ismesh=0;
^
src/libqhull/rboxlib.c:99:43: warning: variable ‘ismesh’ might be clobbered by ‘longjmp’ or ‘vfork’ [-Wc
int isbox=0, issimplex=0, issimplex2=0, ismesh=0;
^
src/libqhull/rboxlib.c:102:20: warning: variable ‘simplex’ might be clobbered by ‘longjmp’ or ‘vfork’ [-
double *coordp, *simplex= NULL, *simplexp;
^
src/libqhull/rboxlib.c:104:39: warning: variable ‘lensangle’ might be clobbered by ‘longjmp’ or ‘vfork’
double norm, factor, randr, rangap, lensangle=0, lensbase=1;
^
src/libqhull/rboxlib.c:104:52: warning: variable ‘lensbase’ might be clobbered by ‘longjmp’ or ‘vfork’ [
double norm, factor, randr, rangap, lensangle=0, lensbase=1;
^
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic/us.o src/libqhull/userprintf_rbox.c
==========================================
==== If ar fails, try make qhullx ====
==========================================
ar -rs lib/libqhullstatic.a src/libqhullstatic/global.o src/libqhullstatic/stat.o src/libqhullstatic/geohullstatic/poly2.o src/libqhullstatic/merge.o src/libqhullstatic/libqhull.o src/libqhullstatic/geom.o srtic/poly.o src/libqhullstatic/qset.o src/libqhullstatic/mem.o src/libqhullstatic/random.o src/libqhullsto src/libqhullstatic/userprintf.o src/libqhullstatic/io.o src/libqhullstatic/user.o src/libqhullstatic/rlibqhullstatic/userprintf_rbox.o
ar: lib/libqhullstatic.a: No such file or directory
make: *** [lib/libqhullstatic.a] Error 1
3. Running "make qhullx"
[qhull-2015.2]$ make qhullx
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/qconvex/qconvex.o src/qconvex/qconvex.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/qdelaunay/qdelaun.o src/qdelaunay/qdelaun.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/qhalf/qhalf.o src/qhalf/qhalf.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/qvoronoi/qvoronoi.o src/qvoronoi/qvoronoi.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/rbox/rbox.o src/rbox/rbox.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/qhull/unix_r.o src/qhull/unix_r.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/global_r.o src/libqhull_r/global_r.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/stat_r.o src/libqhull_r/stat_r.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/geom2_r.o src/libqhull_r/geom2_r.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/poly2_r.o src/libqhull_r/poly2_r.c
src/libqhull_r/poly2_r.c: In function ‘qh_delridge’:
src/libqhull_r/poly2_r.c:1127:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
^
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/merge_r.o src/libqhull_r/merge_r.c
src/libqhull_r/merge_r.c: In function ‘qh_all_merges’:
src/libqhull_r/merge_r.c:219:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
^
src/libqhull_r/merge_r.c: In function ‘qh_appendmergeset’:
src/libqhull_r/merge_r.c:322:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
^
src/libqhull_r/merge_r.c: In function ‘qh_mergecycle_ridges’:
src/libqhull_r/merge_r.c:2090:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
^
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/libqhull_r.o src/libqhull_r/libqhull_r.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/geom_r.o src/libqhull_r/geom_r.c
src/libqhull_r/geom_r.c: In function ‘qh_projectpoint’:
src/libqhull_r/geom_r.c:897:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
^
src/libqhull_r/geom_r.c: In function ‘qh_setfacetplane’:
src/libqhull_r/geom_r.c:935:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
^
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/poly_r.o src/libqhull_r/poly_r.c
src/libqhull_r/poly_r.c: In function ‘qh_delfacet’:
src/libqhull_r/poly_r.c:248:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
^
src/libqhull_r/poly_r.c: In function ‘qh_makenew_nonsimplicial’:
src/libqhull_r/poly_r.c:564:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
^
src/libqhull_r/poly_r.c: In function ‘qh_newfacet’:
src/libqhull_r/poly_r.c:987:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
^
src/libqhull_r/poly_r.c: In function ‘qh_newridge’:
src/libqhull_r/poly_r.c:1020:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
^
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/qset_r.o src/libqhull_r/qset_r.c
src/libqhull_r/qset_r.c: In function ‘qh_setfree’:
src/libqhull_r/qset_r.c:718:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
^
src/libqhull_r/qset_r.c: In function ‘qh_setnew’:
src/libqhull_r/qset_r.c:928:10: warning: variable ‘freelistp’ set but not used [-Wunused-but-set-variable]
void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
^
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/mem_r.o src/libqhull_r/mem_r.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/random_r.o src/libqhull_r/random_r.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/usermem_r.o src/libqhull_r/usermem_r.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/userprintf_r.o src/libqhull_r/userprintf_r.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/io_r.o src/libqhull_r/io_r.c
gcc -c -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -o src/libqhullstatic_r/user_r.o src/libqhull_r/user_r.c
gcc -o bin/qconvex -O3 -ansi -Isrc -fpic -Wall -Wcast-qual -Wextra -Wwrite-strings -Wshadow -lm src/libqhullstatic/global.o src/libqhullstatic/stat.o src/libqhullstatic/geom2.o src/libqhullstatic/poly2.o src/libqhullstatic/merge.o src/libqhullstatic/libqhull.o src/libqhullstatic/geom.o src/libqhullstatic/poly.o src/libqhullstatic/qset.o src/libqhullstatic/mem.o src/libqhullstatic/random.o src/libqhullstatic/usermem.o src/libqhullstatic/userprintf.o src/libqhullstatic/io.o src/libqhullstatic/user.o src/qconvex/qconvex.o
/usr/bin/ld: cannot open output file bin/qconvex: No such file or directory
collect2: error: ld returned 1 exit status
make: *** [qhullx] Error 1
Qhull compile error with intel compiler
Minor casting issue prevented builds with intel compiler.
Patch described here
CMake: using qhull as external project
I'm having trouble using qhull as an external Project via CMake. It always builds everything but installs nothing unless specified. But specifying -Dqhull_TARGETS_INSTALL=qhullstatic_r;qhullcpp will unfortunately not work.
It seems currently the only way to use the qhullcpp library as an external Project is:
include(ExternalProject)
ExternalProject_add(qhullstatic_r
SOURCE_DIR "${CMAKE_SOURCE_DIR}/thirdparty/qhull"
# GIT_REPOSITORY https://github.com/qhull/qhull
CMAKE_ARGS "-DCMAKE_INSTALL_PREFIX=${PROJECT_BINARY_DIR}/thirdparty-install;-Dqhull_TARGETS_INSTALL=qhullstatic_r"
PREFIX qhull-prefix
)
ExternalProject_add(qhullcpp
SOURCE_DIR "${CMAKE_SOURCE_DIR}/thirdparty/qhull"
# GIT_REPOSITORY https://github.com/qhull/qhull
CMAKE_ARGS "-DCMAKE_INSTALL_PREFIX=${PROJECT_BINARY_DIR}/thirdparty-install;-Dqhull_TARGETS_INSTALL=qhullcpp"
PREFIX qhull-prefix
DEPENDS qhullstatic_r
)
add_library(libqhullstatic_r STATIC IMPORTED)
set_property(TARGET libqhullstatic_r PROPERTY IMPORTED_LOCATION ${PROJECT_BINARY_DIR}/thirdparty-install/lib/${CMAKE_STATIC_LIBRARY_PREFIX}qhullstatic_r${CMAKE_STATIC_LIBRARY_SUFFIX})
add_dependencies(libqhullstatic_r qhullstatic_r)
add_library(libqhullcpp STATIC IMPORTED)
set_property(TARGET libqhullcpp PROPERTY IMPORTED_LOCATION ${PROJECT_BINARY_DIR}/thirdparty-install/lib/${CMAKE_STATIC_LIBRARY_PREFIX}qhullcpp${CMAKE_STATIC_LIBRARY_SUFFIX})
set_property(TARGET libqhullcpp PROPERTY INTERFACE_LINK_LIBRARIES libqhullstatic_r)
add_dependencies(libqhullcpp qhullcpp)
Is this by design or might it be improved?
Feature Request: Add version tags to your git repo?
Hey. Can you guys add qhull version tags to your github repo? It would be nice to be able to download qhull source from github rather than sourceforge.
qh.NOerrexit was not cleared before calling qh_initflags()
I am using a third party package which calls qhull functions, when I get a seemingly opaque error:
QH6245 qhull internal error (qh_initflags): qh.NOerrexit was not cleared before calling qh_initflags(). It should be cleared after setjmp(). Exit qhull.
What does this mean? The package in question leads to this error on MacOS Mojave (but not on High Sierra)
-Wstringop-truncation Warning
When running checks on the R geometry package using gcc-8 with -Wall I got the following error:
rboxlib_r.c:358:5: warning: ‘strncat’ output may be truncated copying between 0 and 199 bytes from a string of length 199 [-Wstringop-truncation]
strncat(command, seedbuf, sizeof(command)-strlen(command)-1);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
When I try to add _rd and other libraries built in lib folder Visual C++ gives error LINK1104 cannot open file file qhull_rd.lib
I tried several times with different versions of visual c++ but none worked.
qhalf strange intersection points
With the following input:
2 1
4.5 0.0
3
4
0 1 -4
0 1 -1
-1 0 1
-1 0 4
as tests/data, I tried to compute the intersection points with
qhalf Fp Fn < tests/data
and it returns
2
4
4 1
-10.101 -10.101
-10.101 -10.101
-10.101 -10.101
4
2 2 1
2 3 0
2 0 3
2 1 2
But clearly the point (-10.101, -10.101) is not within the halfspaces [-1, 0]x + 1 <= 0 or [-1, 0]x + 4 <= 0.
What is going on?
Linking error
I built qhull from sources (version 2019.1) and intend to use it in a C++ project that uses CMake. I work on ubuntu 18.04.
When linking to libqhullcpp.a, i get the following error:
/usr/bin/ld: ../qhull-install/lib/libqhullcpp.a(Qhull.cpp.o): relocation R_X86_64_PC32 against symbol `_ZSt4cerr@@GLIBCXX_3.4' can not be used when making a shared object; recompile with -fPIC
I tried using the CMake target Qhull::qhullcpp.
Am I doing something wrong ?
qhull compilation fails to compile witn Intel Compiler / Linux
hi,
I bumped into a build failure using the Intel Compiler and qhull on Archlinux 64bit. I had initially tried to compile CloudCompare, which uses an older version of qhull - which failed. Then I decided to give the current qhull_r a try (which I compiled on it's own) and bumped into the same issue;
[ 44%] Building CXX object CMakeFiles/qhullcpp.dir/src/libqhullcpp/Coordinates.cpp.o
In file included from /home/ninez/pkgs/Icc/qhull/src/qhull-2015.2/src/libqhullcpp/Coordinates.h(13),
from /home/ninez/pkgs/Icc/qhull/src/qhull-2015.2/src/libqhullcpp/Coordinates.cpp(9):
/home/ninez/pkgs/Icc/qhull/src/qhull-2015.2/src/libqhull_r/qhull_ra.h(105): error: this declaration may not have extern "C" linkage
template
^
compilation aborted for /home/ninez/pkgs/Icc/qhull/src/qhull-2015.2/src/libqhullcpp/Coordinates.cpp (code 2)
make[2]: *** [CMakeFiles/qhullcpp.dir/build.make:63: CMakeFiles/qhullcpp.dir/src/libqhullcpp/Coordinates.cpp.o] Error 2
make[1]: *** [CMakeFiles/Makefile2:216: CMakeFiles/qhullcpp.dir/all] Error 2
make: *** [Makefile:139: all] Error 2
Intel Compier version; icc -V
Intel(R) C Intel(R) 64 Compiler for applications running on Intel(R) 64, Version 17.0.0.098 Build 20160721 Copyright (C) 1985-2016 Intel Corporation. All rights reserved.
FOR NON-COMMERCIAL USE ONLY
qhull_ra.h seems to have this line defined FOR the Intel Compiler / on a non-windows version;
if defined(__cplusplus) && defined(__INTEL_COMPILER) && !defined(QHULL_OS_WIN)
but it doesn't seem to be working over here. Just thought I would point it out.
thanks!
Error in qhull_ra.h when building with icc
I am building qhull 2015.2 with Intel C++ 2017.2 (17.0.2.174) on SUSE Linux Enterprise Server 12 and receive the following error:
In file included from /stage/qhull-2015.2-build/qhull-2015.2/src/libqhullcpp/Coordinates.h(13),
from /stage/qhull-2015.2-build/qhull-2015.2/src/libqhullcpp/Coordinates.cpp(9):
/stage/qhull-2015.2-build/qhull-2015.2/src/libqhull_r/qhull_ra.h(105): error: this declaration may not have extern "C" linkage
template <typename T>
Integrating qdelaunay and qvoronoi function of qhull in c++
Hi,
I know basics of visual studio and c++, but I am not an advanced user or programmer. What I want to do is to perform delaunay triangulation and generate voronoi grids using qhull library (using visual studio c++ in windows). I have no problem with preparing necessary data for calculation. My questions are:
What is the minimum necessary files to be included from qhull? (from what publicly free, the qhull is very powerful and contains a huge amount of files)
How can I easily perform the delaunay triangulation and generate voronoi grids? (like in delaunayn.m file of Matlab it calls " t = qhullmx(x', 'd ', opt); " then get the delaunay triangulation. )
Thank you so much for sharing your experience!
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.