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

假设我想对凸多边形内的点进行均匀采样。

这里和互联网上描述的最常见的方法之一通常包括对多边形进行三角测量，并使用不同的方案在每个三角形内生成均匀的随机点。

我发现最实用的方法是从均匀分布生成指数分布，例如 -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 维构造），使其适用于它们而不适用于其他多边形？

如果有人能给我对这些现象的直观解释，或者只是指出一些可以帮助我理解正在发生的事情的参考资料，我将不胜感激。

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

1. 确定覆盖整个形状的边界框。对于多边形，这就像查找多边形的最高和最低 x 和 y 坐标一样简单。
2. 在边界框中均匀随机选择一个点。
3. 如果该点位于形状内部，则返回该点。 （对于多边形，确定这一点的算法统称为多边形内的点谓词 https://en.wikipedia.org/wiki/Point_in_polygon.) 否则，请转至步骤 2。

然而，有两件事会影响该算法的运行时间：

1. 时间复杂度很大程度上取决于所讨论的形状。一般来说，该算法的接受率是形状的体积除以边界框的体积。 （特别是，对于高维形状的接受率通常非常低，部分原因是维数诅咒：典型形状覆盖的体积比其边界框小得多。）
2. 此外，算法的效率取决于确定一个点是否位于相关形状中的速度。因此，通常情况下，复杂的形状是由更简单的形状（例如三角形、圆形和矩形）组成的，因此很容易确定一个点是否位于复杂形状中或确定该形状的边界框。

请注意，原则上，拒绝采样可以应用于对任何维度的任何形状进行采样，而不仅仅是凸二维多边形。因此，它适用于圆形、椭圆形和弯曲形状等。

事实上，原则上，多边形可以分解为除三角形之外的无数形状，其中一个形状与其面积成比例采样，并且该形状中的一个点通过拒绝采样随机采样。

现在，解释一下您在第二张图片中给出的现象：

你所拥有的不是一个 4 边（2 维）多边形，而是一个投影到 2 维空间的 3 维单纯形（即四面体）。 （另请参见前面的答案。）此投影解释了为什么“多边形”内的点在内部看起来比在角上更密集。如果您将“多边形”想象为四个角深度不同的四面体，您就会明白为什么。随着单纯形的维度越来越高，这种现象变得越来越严重，部分原因是维数诅咒.