Skip to content

Pyhull is a Python wrapper to Qhull (http://www.qhull.org/) for the computation of the convex hull, Delaunay triangulation and Voronoi diagram.

License

Notifications You must be signed in to change notification settings

materialsvirtuallab/pyhull

Repository files navigation

Pyhull

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.

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.

For more information, visit the documentation page at http://packages.python.org/pyhull/. To report bugs, please use the pyhull's Github Issues page at https://github.com/materialsvirtuallab/pyhull/issues.

Note

At the time of development of pyhull, the scipy.spatial package was the only other package that supports the computation of higher dimensional convex hulls. However, the version of scipy at that time (scipy 0.11.0) only supported the computation of Delaunay triangulation and the convex hull was computed from the Delaunay triangulation, which is slower and less reliable than directly computing the convex hull. As of version 0.12.0, scipy now supports the direct computation of convex hulls and is in fact ~50% faster than pyhull for larger hulls. I will still make pyhull available for the simple reason that the scipy package is fairly large and not everyone wants to install such a large package for computing hulls.

Performance of pyhull

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 col (Cmd-line qconvex) is the time taken to generate the data using a subprocess call to command line qconvex as a comparison for pyhull. Note that these are based on older versions of scipy (< 0.12.0) where the hull is computed by first performing the Delaunay triangulation.

No of points Dim scipy pyhull Cmd line
100 3 0.00237 0.00209 0.01354
100 4 0.00609 0.00333 0.01053
100 5 0.03125 0.00834 0.01743
100 6 0.16662 0.04627 0.05048
1000 3 0.02543 0.01166 0.01398
1000 4 0.15308 0.01438 0.01741
1000 5 1.04724 0.05105 0.05279
1000 6 7.45985 0.25104 0.29058
2000 3 0.05124 0.01968 0.02431
2000 4 0.32277 0.02326 0.02742
2000 5 2.38308 0.06664 0.06845
2000 6 20.64062 0.41188 0.42673

Here are new benchmarks for pyhull against scipy 0.12.0, which supports the direct computation of the convex hull.

Npts Dim scipy pyhull
100 3 0.00044 0.00120
100 4 0.00062 0.00215
100 5 0.00347 0.00838
100 6 0.01382 0.03698
1000 3 0.00051 0.00778
1000 4 0.00194 0.01226
1000 5 0.01417 0.04079
1000 6 0.14036 0.20594
2000 3 0.00072 0.01772
2000 4 0.00392 0.02941
2000 5 0.02350 0.07712
2000 6 0.25601 0.36650

Usage

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]]

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.