SciPy 中带有 QHull 的凸包体积 [英] Volume of convex hull with QHull from SciPy

问题描述

我正在尝试使用 QHull 的 SciPy 包装器.

I'm trying to get the volume of the convex hull of a set of points using the SciPy wrapper for QHull.

根据 QHull 的文档，我应该通过 "FA" 选项以获得总表面积和体积.

According to the documentation of QHull, I should be passing the "FA" option to get the total surface area and volume.

这是我得到的……我做错了什么?

Here is what I get.. What am I doing wrong?

> pts
     [(494.0, 95.0, 0.0), (494.0, 95.0, 1.0) ... (494.0, 100.0, 4.0), (494.0, 100.0, 5.0)]


> hull = spatial.ConvexHull(pts, qhull_options="FA")

> dir(hull)

     ['__class__', '__del__', '__delattr__', '__dict__', '__doc__', '__format__', '__getattribute__', '__hash__', '__init__', '__module__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__', '_qhull', '_update', 'add_points', 'close', 'coplanar', 'equations', 'max_bound', 'min_bound', 'ndim', 'neighbors', 'npoints', 'nsimplex', 'points', 'simplices']

 > dir(hull._qhull)
     ['__class__', '__delattr__', '__doc__', '__format__', '__getattribute__', '__hash__', '__init__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__']

推荐答案

不管你传入什么参数，似乎没有什么明显的方法可以直接得到你想要的结果.应该不会太难如果您使用 而不是 ConvexHull 来计算自己Delaunay(它还提供了大部分与凸包相关的信息).

There does not seem to be any obvious way of directly getting the results you are after, regardless of what parameters you pass in. It shouldn't be too hard to compute yourself if, instead of ConvexHull, you use Delaunay (which also provides most of the convex hull related info).

def tetrahedron_volume(a, b, c, d):
    return np.abs(np.einsum('ij,ij->i', a-d, np.cross(b-d, c-d))) / 6

from scipy.spatial import Delaunay

pts = np.random.rand(10, 3)
dt = Delaunay(pts)
tets = dt.points[dt.simplices]
vol = np.sum(tetrahedron_volume(tets[:, 0], tets[:, 1], 
                                tets[:, 2], tets[:, 3]))

<小时>

编辑根据评论，以下是获得凸包体积的更快方法:

---

EDIT As per the comments, the following are faster ways of obtaining the convex hull volume:

def convex_hull_volume(pts):
    ch = ConvexHull(pts)
    dt = Delaunay(pts[ch.vertices])
    tets = dt.points[dt.simplices]
    return np.sum(tetrahedron_volume(tets[:, 0], tets[:, 1],
                                     tets[:, 2], tets[:, 3]))

def convex_hull_volume_bis(pts):
    ch = ConvexHull(pts)

    simplices = np.column_stack((np.repeat(ch.vertices[0], ch.nsimplex),
                                 ch.simplices))
    tets = ch.points[simplices]
    return np.sum(tetrahedron_volume(tets[:, 0], tets[:, 1],
                                     tets[:, 2], tets[:, 3]))

对于一些虚构的数据，第二种方法似乎快了大约 2 倍，并且数值精度似乎非常好(小数点后 15 位！！！)尽管必须有更多的病态案例:

With some made up data, the second method seems to be about 2x faster, and numerical accuracy seems very good (15 decimal places!!!) although there has to be some much more pathological cases:

pts = np.random.rand(1000, 3)

In [26]: convex_hull_volume(pts)
Out[26]: 0.93522518081853867

In [27]: convex_hull_volume_bis(pts)
Out[27]: 0.93522518081853845

In [28]: %timeit convex_hull_volume(pts)
1000 loops, best of 3: 2.08 ms per loop

In [29]: %timeit convex_hull_volume_bis(pts)
1000 loops, best of 3: 1.08 ms per loop

这篇关于SciPy 中带有 QHull 的凸包体积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！