如何获得凸包中的均匀分布点？ [英] How to get uniformly distributed points in convex hull?

问题描述

给出一组点，

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

我想用列表均匀填充填充它们所位于的凸包所定义的体积（np形状为 nx3 的3d点数组。

I would like to uniformly fill the volume defined by the convex hull in which they lie by a list (np.array of shape nx3) of 3d points.

我可以通过

hull = scipy.spatial.ConvexHull(points)

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

What would be the fastest way to get a list of points that uniformly fills this hull's volume?

推荐答案

1）查找船体的delaunay简化符号

1) Find delaunay simplices of the hull

2）根据其面积随机采样简化符号

2) randomly sample the simplices based on their area

3）对于每个单纯形，使用 dirichelet 分布

3) for each simplex, find uniform distribution of sampled points using dirichelet distribution

寻找均匀的采样点分布4）将分布乘以

4) multiply the distributions with the simplices to find final points.

from scipy.spatial import ConvexHull, Delaunay
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 = points[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）

functionalized and extended to higher dimensions (Warning: ConvexHull only works up to 9D)

这篇关于如何获得凸包中的均匀分布点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！