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

Question

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

matlabrandompolygontriangulation

4

假设我想在一个凸多边形内均匀采样点。

其中最常见的方法是对该多边形进行三角剖分，然后使用不同的方案在每个三角形中生成均匀随机点。

我发现其中最实用的一种方法是通过从均匀分布中生成指数分布，例如取-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

这很有效：

然而，对于除了三角形以外的任何东西，完全相同的方案都会失败。例如对于一个四边形，我们得到以下结果：

显然，采样不再均匀，顶点越多，越难“到达”这些顶点。

如果我先将多边形三角化，那么在每个三角形中进行均匀采样就很容易，很明显可以完成任务。

但是为什么？为什么需要先三角化？

具有哪些特性的三角形（和一般的simplex，因为这种行为似乎扩展到n维构造）使其对它们有效而对其他多边形无效？

如果有人能给我一个直观的解释或只是指出一些参考资料，帮助我理解发生了什么，我将不胜感激。

- Xav59130

2个回答

3

我应该指出，为了从多边形中均匀采样，不一定严格需要三角剖分。另一种采样形状的方法是拒绝采样，其步骤如下：

确定覆盖整个形状的边界框。对于多边形来说，这就是找到多边形的最高和最低x和y坐标。
在边界框内随机选择一个点。
如果该点位于形状内，则返回该点。（对于多边形，确定此点的算法称为点-多边形谓词。）否则，转到步骤2。

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

时间复杂度很大程度上取决于所涉及的形状。通常情况下，该算法的接受率是形状体积除以外包盒体积。(特别地，对于高维形状来说，接受率通常非常低，部分原因是由于“维数灾难”：典型的形状覆盖的体积远小于它们的外包盒。)
此外，该算法的效率取决于确定一个点是否在所涉及的形状中的速度有多快。因此，通常情况下，复杂形状由简单形状组成，例如三角形、圆形和矩形，对于这些形状，确定一个点是否在复杂形状中或确定该形状的外包盒都很容易。

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

事实上，一个多边形可以被分解成无数种形状，而不仅仅是三角形，其中一种形状按比例采样，然后通过拒绝采样在该形状中随机采样一个点。

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

您看到的不是一个4边形（2维多边形），而是一个三维单体（即四面体），它被投影到了二维空间中。（请参见前面的答案。）这种投影解释了为什么内部的点比角落里的点更密集出现在“多边形”内部。如果您将“多边形”想象成一个四面体，其四个角位于不同的深度，那么您就可以看到为什么了。随着单体维数的增加，这种现象变得越来越明显，部分原因是由于“维数灾难”。

- Peter O.

我现在明白发生了什么以及为什么它不能按照我最初的想法工作。系数之和为一确实使我的四边形实际上成为了一个在二维空间中的四面体投影，这也解释了为什么顶点越多情况就会变得更糟。我必须再仔细研究一下细节，但你给了我缺失的洞察力来解决问题。 - Xav59130

@Xav59130 关于 #2 的问题，说获取关于点内/点外的答案可能会很昂贵实在是低估了。对于具有潜在孔洞的复杂非凸多边形，算法的运行时间将为O(N)，其中N是边数。而且通常情况下，人们无论如何都会三角剖分多边形，以获得已知的点内/点外代码或射线交点计算。我的意思是，你必须选择你的复杂度所在的地方，但你不能避免它。 - Severin Pappadeux

@Xav59130，我更新了我的回答，请看一下。 - Severin Pappadeux

@SeverinPappadeux：在我的回答中，我想要表达的重点是对凸多边形进行采样并不一定意味着必须将该多边形分解为_三角形_。采样多边形或任何其他形状的时间复杂度并不是我回答的主要观点。 - Peter O.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Severin Pappadeux · Accepted Answer

嗯，有更便宜的方法来在三角形中进行均匀采样。您可以在单纯形 d+1 中采样狄利克雷分布，并进行投影、计算指数等操作。我建议您参考代码示例和论文引用 here，这是一个更简单的算法，只需要平方根。

关于在复杂区域（例如四边形）中进行均匀采样，一般的方法非常简单：

将其三角化。您将得到两个顶点为 (a,b,c)₀ 和 (a,b,c)₁ 的三角形。
使用例如Heron公式计算三角形面积 A₀ 和 A₁。
第一步，根据面积随机选择其中一个三角形。如果 (random() < A₀/(A₀+A₁))，则选择三角形 0；否则选择三角形 1。random() 应返回范围在 [0...1] 的浮点数。
使用上述提到的方法在所选三角形中采样点。

这种方法可以轻松地扩展到任何具有均匀密度的复杂区域进行抽样：N个三角形，使用与面积成比例的概率的分类分布抽样将使您选择三角形，然后在三角形中抽样点。

更新

我们必须进行三角剖分，因为我们知道如何在三角形中进行均匀密度抽样的良好算法（快速、可靠、仅需2个随机数生成器调用...）。然后我们可以在此基础上构建，优秀的软件都是关于可重用性的。我们选择一个三角形（以另一个 RNG 调用的代价）并返回从中抽样，总共需要三个 RNG 调用，即可从任何区域（凸多边形和凹多边形）进行均匀密度抽样。相当通用的方法，我认为。而且三角剖分是解决问题，基本上只需要一次（三角剖分和构建权重数组 A_i/A_total），然后无限抽样。

另一个答案的部分是，我们（准确地说是我，但我已经与随机抽样合作了约20年）不知道如何从任意凸多于三个顶点的封闭多边形中精确均匀密度采样的好算法。您提出了一些基于直觉的算法，但并没有成功。而且它不应该起作用，因为您使用的是Dirichlet distribution在d+1单纯形中，并将其投影回d超平面。它甚至不能扩展到四边形，更不用说任意凸多边形了。我会陈述一个猜想，即使存在这样的算法，n个顶点的多边形也需要n-1次RNG调用，这意味着没有三角剖分设置，但每次获取点的调用都会相当昂贵。

有关采样复杂性的几句话。假设您进行了三角剖分，则使用3次RNG，您将获得一个在多边形内均匀采样的点。但是，采样复杂性与三角形数量N的关系最多为O(log(N))。您基本上会在A_i/A_total的部分和的二进制搜索中执行此操作。

您可以做得更好，使用三角形的Alias sampling进行O(1)（常数时间）采样。这将需要一些设置时间，但它可以与三角剖分融合。此外，它需要一个额外的随机数生成器调用。因此，对于四个RNG调用，您将具有独立于多边形复杂度的恒定点采样时间，适用于任何形状。