algorithm - 根据密度在网格上分配点

Question

给定一个具有密度纹理的(可能是开放的)网格和一些点，我需要根据网格上的密度分布这些点。

到目前为止，我已经制定了几种解决方案，其中一些有效，而另一些则无效。我尝试的一种算法是让点通过 Spring 连接并模拟分布直到达到平衡(或直到解决方案满足用户需求)。来源Retiling Polygonal Surfaces不幸的是，对于更多点数 (>2k)，这有点慢，所以我需要一个可行的解决方案来处理更多点数。

我已经有了一些想法，但我想听听是否有一些标准的解决方案。我尝试了谷歌，但我使用的关键字(分布密度离散)只出现了处理其他问题而不是我的问题的页面。因此，如果您指出要搜索的正确词，我会很高兴。

Answer 1

通常，在具有任意密度函数的任意空间中，您可以通过 rejection sampling 获得合理的近似值.

• 找到你的最大密度 D。
• 选择一个随机点p。
• 从 [0,D) 范围内选择一个随机数 r。
• 如果 p 处的密度大于 r，则接受 p 作为你的点之一。

我不确定将其应用到您的案例中有多容易。在网格中生成随机、均匀分布的点本身就是一个棘手的问题。我能想到的唯一解决方案是计算网格中每个三角形的面积，随机选择一个概率与其面积成正比的三角形，然后选择一个 random point。三角形内。我相信您可以在 O(logN) 中对 N 个三角形进行此选择。

但是考虑到您可能会丢弃其中的大部分点，如果网格足够大且密度函数足够令人不快(即最大值远大于平均值)，这可能会比您当前的方法糟糕得多.

像任何一种随机抽样一样，它需要相当多的点才能开始类似于基础分布；一小组点可能看起来或多或少是随机的。但是您可以通过某种准随机点放置方法来解决这个问题(即使是大集合，它也可能会产生更好的结果)。

想到的一件事是上述方法和@BlackBear 算法的混合体。您可以计算每个三角形的面积和平均密度，并以此来决定每个三角形必须包含多少个点。然后，要将点实际放置在三角形内，请使用拒绝采样方法。