matlab - 为什么我们需要对凸多边形进行三角剖分才能从中均匀采样？

Question

假设我想对凸多边形内的点进行均匀采样。
这里和互联网上描述的最常见的方法之一是对多边形进行三角剖分，并使用不同的方案在每个三角形内生成均匀随机的点。
我发现最实用的方法是从均匀分布中生成指数分布，例如 -log(U) 并将总和归一化为 1。
在 Matlab 中，我们将使用以下代码在三角形内均匀采样:

vertex=[0 0;1 0;0.5 0.5]; %vertex coordinates in the 2D plane

mix_coeff=rand(10000,size(vertex,1)); %uniform generation of random coefficients
x=-log(x); %make the uniform distribution exponential
x=bsxfun(@rdivide,x,sum(x,2)); %normalize such that sum is equal to one
unif_samples=x*vertex; %calculate the 2D coordinates of each sample inside the triangle

这工作得很好:

然而，对三角形以外的任何事物使用完全相同的方案都会失败。例如对于四边形，我们得到以下结果:

显然，采样不再统一，添加的顶点越多，“到达”角落就越困难。
如果我先对多边形进行三角剖分，那么在每个三角形中进行均匀采样很容易，并且显然可以完成工作。
但为什么？为什么需要先进行三角测量？
哪个特定属性具有三角形(以及一般的单纯形，因为这种行为似乎扩展到 n 维结构)使其适用于它们而不适用于其他多边形？
如果有人能给我一个直观的现象解释，或者只是指出一些可以帮助我理解正在发生的事情的引用资料，我将不胜感激。

Answer 1

我应该指出，为了从中均匀采样，对多边形进行三角剖分并不是绝对必要的。另一种对形状进行采样的方法是拒绝采样，其过程如下。

确定一个覆盖整个形状的边界框。对于多边形，这就像找到多边形的最高和最低 x 和 y 坐标一样简单。

在边界框中随机均匀地选择一个点。

如果该点位于形状内部，则返回该点。 (对于多边形，确定这一点的算法统称为 point-in-polygon predicates 。)否则，转到步骤 2。

但是，有两件事会影响该算法的运行时间:

时间复杂度很大程度上取决于所讨论的形状。通常，该算法的接受率是形状的体积除以边界框的体积。 (特别是，高维形状的接受率通常非常低，部分原因是维数灾难:典型形状覆盖的体积比它们的边界框小得多。)

此外，算法的效率取决于确定点是否位于所讨论的形状中的速度。因此，复杂形状通常由简单的形状组成，例如三角形、圆形和矩形，因此很容易确定一个点是否位于复杂形状中或确定该形状的边界框。

请注意，原则上可以应用拒绝采样来采样任何维度的任何形状，而不仅仅是凸二维多边形。因此，它适用于圆形、椭圆形和弯曲形状等。
事实上，原则上，多边形可以分解为除三角形以外的无数形状，其中一个形状与其面积成比例采样，并且该形状中的一个点通过拒绝采样随机采样。

现在，解释一下您在第二张图片中给出的现象:
您拥有的不是 4 边(2 维)多边形，而是投影到 2 维空间的 3 维单纯形(即四面体)。 (另请参阅上一个答案。)此投影解释了为什么“多边形”内部的点在内部看起来比在角落中更密集。如果您将“多边形”描绘为具有不同深度的四个角的四面体，您就会明白为什么。随着单纯形的维数更高，这种现象变得越来越严重，部分原因是维数灾难。