Pyhull is a Python wrapper to qhull (http://www.qhull.org/) for the computation of the convex hull, Delaunay triangulation and Voronoi diagram. It is written as a Python C extension, with both high-level and low-level interfaces to qhull. It is currently based on the 2012.1 version of qhull.
Currently, there is no effective port of the qhull algorithm, especially for higher dimensions. While isolated packages exist for up to 3D convex hulls, no effective package exist for higher dimensions. The only other known code which supports convex hulls in higher dimensions is the scipy.spatial package, but that code is extremely inefficient compared to the original Qhull in C. Pyhull is much faster than the scipy.spatial package.
Pyhull has been tested to scale to 10,000 7D points for convex hull calculations (results in ~ 10 seconds), and 10,000 6D points for Delaunay triangulations and Voronoi tesselations (~ 100 seconds). Higher number of points and higher dimensions should be accessible depending on your machine, but may take a significant amount of time.
Pyhull has been tested to install correctly on both BSD and POSIX systems (e.g., Mac OS X and most common Linux distros). It has not been tested on Windows as of yet. If anyone has tested it on Windows, let me know the results.
Pyhull is now in the Python Package Index (PyPI). The version on PyPI is always the latest stable release that will be relatively bug-free. If you have setuptools or pip installed installed, you can just type:
pip install pyhull
to install pyhull with most of the dependencies set up. Otherwise, the latest stable source can be downloaded at the PyPI site as well.
The bleeding edge developmental version is at the public pyhull’s Github repo. The developmental version is likely to be more buggy, but may contain new features. Note that the GitHub versions include test files as well for unit testing.
From the source, you can type:
python setup.py install
or to install the package in developmental mode:
python setup.py develop
It is generally recommended that you use the high-level wrapper functions and classes in pyhull.
For useful analysis outputs, please use the high-level ConvexHull, DelaunayTri and VoronoiTess classes in the convex_hull, delaunay and voronoi modules respectively. For example,
>>> from pyhull.convex_hull import ConvexHull >>> pts = [[-0.5, -0.5], [-0.5, 0.5], [0.5, -0.5], [0.5, 0.5], [0,0]] >>> hull = ConvexHull(pts) >>> hull.vertices [[0, 2], [1, 0], [2, 3], [3, 1]] >>> hull.points [[-0.5, -0.5], [-0.5, 0.5], [0.5, -0.5], [0.5, 0.5], [0, 0]] >>> >>> from pyhull.delaunay import DelaunayTri >>> tri = DelaunayTri(pts) >>> tri.vertices [[2, 4, 0], [4, 1, 0], [3, 4, 2], [4, 3, 1]] >>> tri.points [[-0.5, -0.5], [-0.5, 0.5], [0.5, -0.5], [0.5, 0.5], [0, 0]] >>> >>> from pyhull.voronoi import VoronoiTess >>> v = VoronoiTess(pts) >>> v.vertices [[-10.101, -10.101], [0.0, -0.5], [-0.5, 0.0], [0.5, 0.0], [0.0, 0.5]] >>> v.regions [[2, 0, 1], [4, 0, 2], [3, 0, 1], [4, 0, 3], [4, 2, 1, 3]]
The figure below is a plot of the output from pyhull for a set of 30 random 2D points. To see a sample of the code of how this graph is generated, check out the pyhull_demo.py script on the Github page.
If you need more detailed output, consider using the lower-level interface functions that are modelled after standard command line syntax of various qhull programs:
>>> from pyhull import qconvex, qdelaunay, qvoronoi >>> >>> pts = [[-0.5, -0.5], [-0.5, 0.5], [0.5, -0.5], [0.5, 0.5], [0,0]] >>> >>> qconvex("i", pts) ['4', '0 2', '1 0', '2 3 ', '3 1'] >>> >>> qdelaunay("i", pts) ['4', '2 4 0', '4 1 0', '3 4 2', '4 3 1'] >>> >>> qvoronoi("o", pts) ['2', '5 5 1', '-10.101 -10.101', '0 -0.5', '-0.5 0', '0.5 0', '0 0.5', '3 2 0 1', '3 4 0 2', '3 3 0 1', '3 4 0 3', '4 4 2 1 3']
The return values are simply a list of strings from the output.
The table below indicates the time taken in seconds to generate the convex hull for a given number of points in a specified number of dimensions. The final column (Cmd line) is the time taken to generate the data using a subprocess call to command line qconvex as a comparison for pyhull.
|No of points||Dim||scipy||pyhull||Cmd line|
It is clear from the above table that pyhull outperforms scipy.spatial for large number of points in higher dimensions. Also, pyhull is tested to be safe in terms of usage with Python multiprocessing, unlike a subprocess call to qhull.
The figures below show the scaling of the ConvexHull, DelaunayTri and VoronoiTess classes with number of points and dimension of points. You may use the numbers below to estimate how long the code will take for your specific use cases.
The API docs are generated using Sphinx auto-doc and outlines the purpose of all modules and classes, and the expected argument and returned objects for most methods. They are available at this link below
Pyhull is released under the MIT License. The terms of the license are as follows:
The MIT License (MIT) Copyright (c) 2011-2012 MIT Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.