如何获得凸包中均匀分布的点？

Question

给定一组点，

points = np.random.randn(...) # n 3d points

我想均匀地填充由凸包定义的体积，其中它们位于nx33d 点列表（ np.array of shape ）中。

我可以得到凸包

hull = scipy.spatial.ConvexHull(points)

获得均匀填充该船体体积的点列表的最快方法是什么？

Answer 1

1. 找到船体的 delaunay 单纯形

2. 根据单纯形的面积随机采样

3. dirichelet对于每个单纯形，使用分布找到采样点的均匀分布

4. 将分布与单纯形相乘以找到最终点。

   import numpy as np
   from numpy.linalg import det
   from scipy.stats import dirichlet
   
   
   def dist_in_hull(points, n):
       dims = points.shape[-1]
       hull = points[ConvexHull(points).vertices]
       deln = hull[Delaunay(hull).simplices]
   
       vols = np.abs(det(deln[:, :dims, :] - deln[:, dims:, :])) / np.math.factorial(dims)    
       sample = np.random.choice(len(vols), size = n, p = vols / vols.sum())
   
       return np.einsum('ijk, ij -> ik', deln[sample], dirichlet.rvs([1]*(dims + 1), size = n))
   
   

编辑：功能化并扩展到更高的维度（警告：ConvexHull仅适用于 9D）