为什么我们需要对凸多边形进行三角剖分才能对其进行均匀采样？ [英] Why do we need to triangulate a convex polygon in order to sample uniformly from it?

问题描述

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

这里和互联网上描述的最常见的方法之一是对多边形进行三角剖分，并使用不同的方案在每个三角形内生成统一的随机点。

我发现最实用的方法是从均匀分布生成指数分布，例如-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. 如果该点位于形状内部，则返回该点。(对于一个多边形，确定这一点的算法统称为point-in-polygon predicates。)否则，请转到步骤2。

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

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

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

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

---

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

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

这篇关于为什么我们需要对凸多边形进行三角剖分才能对其进行均匀采样？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！