为什么我们需要对凸多边形进行三角剖分以便从中均匀采样？
Why do we need to triangulate a convex polygon in order to sample uniformly from it?
假设我想对凸多边形内的点进行均匀采样。
这里和 Internet 上描述的最常见的方法之一通常是对多边形进行三角剖分，并使用不同的方案在每个三角形内生成均匀随机的点。
我发现最实用的方法是从均匀分布生成指数分布，例如 -log(U) 并将总和归一化为一。
在 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 维结构）使其适用于它们而不适用于其他多边形？
如果有人能给我一个现象的直观解释，或者只是指出一些可以帮助我理解正在发生的事情的参考，我将不胜感激。
好吧，有更便宜的方法可以在三角形中均匀采样。您正在对单纯形 d+1 中的 Dirichlet 分布进行采样并进行投影、计算指数等。我会推荐你参考代码示例和论文参考 here，只有平方根，算法更简单。
关于复杂区域（在您的情况下为四边形）中的均匀采样，一般方法非常简单：
- 三角测量。你会得到两个顶点为 (a,b,c)0 和 (a,b,c)1
的三角形
- 使用f.e计算三角形面积A0和A1。 Heron's formula
- 第一步，根据面积随机select其中一个三角形。
如果（随机（）
0/（A0+A1））select triangle 0 else select triangle 1. random() 应 return 在 [0...1] 范围内浮动
- 使用上述方法在 selected 三角形中采样点。
这种方法可以很容易地扩展到对任何密度均匀的复杂区域进行采样：N 个三角形，概率与面积成正比的分类分布采样将得到 selected 三角形，然后是三角形中的采样点。
更新
我们必须进行三角剖分，因为我们知道很好的（快速、可靠、只有 2 个 RNG 调用，...）算法可以在三角形中以均匀的密度进行采样。然后我们可以在此基础上构建，好的软件都是关于可重用性的，选择一个三角形（以另一个 rng 调用为代价）然后返回从中采样，总共三个 RNG 调用以从任何区域、凸面和凹的一样非常通用的方法，我会说。三角测量是一个已解决的问题，并且
基本上你做一次（三角测量和构建权重数组 Ai/Atotal）并采样直到无穷大。
答案的另一部分是我们（我，准确地说，但我已经使用随机抽样工作了 ~20 年）不知道从任意凸面以均匀密度精确抽样的好算法 more-than-three-vertices 闭合多边形。你根据直觉提出了一些算法，但没有成功。而且它不应该起作用，因为您使用的是 d+1 单纯形中的 Dirichlet distribution 并将其投影回 d 超平面。它甚至不能扩展到四边形，而不是一些任意的凸多边形。我想说的是，即使存在这样的算法，n-vertices 多边形也需要对 RNG 进行 n-1 次调用，这意味着没有三角测量设置，但每次调用来获取一个点都会相当昂贵。
简单介绍一下采样的复杂性。假设您进行了三角测量，那么通过对 RNG 的 3 次调用，您将在多边形内均匀采样一个点。
但是采样的三角形数量 N 的复杂性最多为 O(log(N))。 YOu 基本上会对 Ai/Atotal.
的部分和进行二进制搜索
您可以做得更好，使用三角形的 Alias sampling 进行 O(1)（恒定时间）采样。成本会多一点设置时间，但它可以与三角测量融合。此外，它还需要一个 RNG 调用。因此，对于四个 RNG 调用，您将拥有独立于多边形复杂性的恒定点采样时间，适用于任何形状
我应该指出，为了从中均匀采样，不一定需要对多边形进行三角剖分。另一种对形状进行采样的方法是 拒绝采样 并按如下方式进行。
- 确定一个覆盖整个形状的边界框。对于多边形，这就像找到多边形的最高和最低 x 和 y 坐标一样简单。
- 在边界框中随机均匀地选择一个点。
- 如果该点位于形状内部，return 该点。 （对于多边形，判断这个的算法统称为point-in-polygon predicates。）否则，转到步骤2。
但是，有两件事会影响这个算法的 运行 时间：
- 时间复杂度很大程度上取决于所讨论的形状。一般来说，该算法的接受率是形状的体积除以边界框的体积。 （特别是，high-dimensional 形状的接受率通常非常低，部分原因是 维数灾难 ：典型形状覆盖的体积比它们的边界框小得多。 )
- 此外，算法的效率取决于确定点是否位于所讨论形状中的速度。正因为如此，复杂的形状通常由更简单的形状组成，例如三角形、圆形和矩形，因此很容易确定一个点是否位于复杂形状中或确定该形状的边界框。
请注意，拒绝抽样原则上可以应用于对任何尺寸的任何形状进行抽样，而不仅仅是凸二维多边形。因此，它适用于圆形、椭圆形和弯曲形状等。
事实上，原则上，一个多边形可以分解成三角形以外的无数种形状，其中一种形状按其面积的比例进行采样，该形状中的一个点通过拒绝采样随机采样。
现在，稍微解释一下您在第二张图片中给出的现象：
您所拥有的不是 4 边（2 维）多边形，而是投影到 2 维 space 的 3 维单纯形（即四面体）。 （另请参阅上一个答案。）此投影解释了为什么“多边形”内的点在内部看起来比在角落处更密集。如果将“多边形”描绘成四个角位于不同深度的四面体，您就会明白为什么。随着单纯形的更高维数，这种现象变得越来越严重，部分原因是维数灾难。
假设我想对凸多边形内的点进行均匀采样。
这里和 Internet 上描述的最常见的方法之一通常是对多边形进行三角剖分，并使用不同的方案在每个三角形内生成均匀随机的点。
我发现最实用的方法是从均匀分布生成指数分布，例如 -log(U) 并将总和归一化为一。
在 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 维结构）使其适用于它们而不适用于其他多边形？
如果有人能给我一个现象的直观解释，或者只是指出一些可以帮助我理解正在发生的事情的参考，我将不胜感激。
好吧，有更便宜的方法可以在三角形中均匀采样。您正在对单纯形 d+1 中的 Dirichlet 分布进行采样并进行投影、计算指数等。我会推荐你参考代码示例和论文参考 here，只有平方根，算法更简单。
关于复杂区域（在您的情况下为四边形）中的均匀采样，一般方法非常简单：
- 三角测量。你会得到两个顶点为 (a,b,c)0 和 (a,b,c)1 的三角形
- 使用f.e计算三角形面积A0和A1。 Heron's formula
- 第一步，根据面积随机select其中一个三角形。
如果（随机（）
- 使用上述方法在 selected 三角形中采样点。
这种方法可以很容易地扩展到对任何密度均匀的复杂区域进行采样：N 个三角形，概率与面积成正比的分类分布采样将得到 selected 三角形，然后是三角形中的采样点。
更新
我们必须进行三角剖分，因为我们知道很好的（快速、可靠、只有 2 个 RNG 调用，...）算法可以在三角形中以均匀的密度进行采样。然后我们可以在此基础上构建，好的软件都是关于可重用性的，选择一个三角形（以另一个 rng 调用为代价）然后返回从中采样，总共三个 RNG 调用以从任何区域、凸面和凹的一样非常通用的方法，我会说。三角测量是一个已解决的问题，并且 基本上你做一次（三角测量和构建权重数组 Ai/Atotal）并采样直到无穷大。
答案的另一部分是我们（我，准确地说，但我已经使用随机抽样工作了 ~20 年）不知道从任意凸面以均匀密度精确抽样的好算法 more-than-three-vertices 闭合多边形。你根据直觉提出了一些算法，但没有成功。而且它不应该起作用，因为您使用的是 d+1 单纯形中的 Dirichlet distribution 并将其投影回 d 超平面。它甚至不能扩展到四边形，而不是一些任意的凸多边形。我想说的是，即使存在这样的算法，n-vertices 多边形也需要对 RNG 进行 n-1 次调用，这意味着没有三角测量设置，但每次调用来获取一个点都会相当昂贵。
简单介绍一下采样的复杂性。假设您进行了三角测量，那么通过对 RNG 的 3 次调用，您将在多边形内均匀采样一个点。 但是采样的三角形数量 N 的复杂性最多为 O(log(N))。 YOu 基本上会对 Ai/Atotal.
的部分和进行二进制搜索您可以做得更好，使用三角形的 Alias sampling 进行 O(1)（恒定时间）采样。成本会多一点设置时间，但它可以与三角测量融合。此外，它还需要一个 RNG 调用。因此，对于四个 RNG 调用，您将拥有独立于多边形复杂性的恒定点采样时间，适用于任何形状
我应该指出，为了从中均匀采样，不一定需要对多边形进行三角剖分。另一种对形状进行采样的方法是 拒绝采样 并按如下方式进行。
- 确定一个覆盖整个形状的边界框。对于多边形，这就像找到多边形的最高和最低 x 和 y 坐标一样简单。
- 在边界框中随机均匀地选择一个点。
- 如果该点位于形状内部，return 该点。 （对于多边形，判断这个的算法统称为point-in-polygon predicates。）否则，转到步骤2。
但是，有两件事会影响这个算法的 运行 时间：
- 时间复杂度很大程度上取决于所讨论的形状。一般来说，该算法的接受率是形状的体积除以边界框的体积。 （特别是，high-dimensional 形状的接受率通常非常低，部分原因是 维数灾难 ：典型形状覆盖的体积比它们的边界框小得多。 )
- 此外，算法的效率取决于确定点是否位于所讨论形状中的速度。正因为如此，复杂的形状通常由更简单的形状组成，例如三角形、圆形和矩形，因此很容易确定一个点是否位于复杂形状中或确定该形状的边界框。
请注意，拒绝抽样原则上可以应用于对任何尺寸的任何形状进行抽样，而不仅仅是凸二维多边形。因此，它适用于圆形、椭圆形和弯曲形状等。
事实上，原则上，一个多边形可以分解成三角形以外的无数种形状，其中一种形状按其面积的比例进行采样，该形状中的一个点通过拒绝采样随机采样。
现在，稍微解释一下您在第二张图片中给出的现象：
您所拥有的不是 4 边（2 维）多边形，而是投影到 2 维 space 的 3 维单纯形（即四面体）。 （另请参阅上一个答案。）此投影解释了为什么“多边形”内的点在内部看起来比在角落处更密集。如果将“多边形”描绘成四个角位于不同深度的四面体，您就会明白为什么。随着单纯形的更高维数，这种现象变得越来越严重，部分原因是维数灾难。