给定一个(可能是开放的)具有密度纹理和多个点的网格，我需要根据网格上的密度分布这些点。
到目前为止，我已经提出了几种解决方案，其中一些有效，而其他无效。我尝试的一种算法是使各点通过 Spring 连接，并模拟分布，直到达到平衡(或直到解决方案适合用户需求为止)。来源Retiling Polygonal Surfaces
不幸的是，这对于更高数量的点(> 2k)来说有点慢，因此我需要一个可行的解决方案来获得更大的数量。
我已经有了一些想法，但是我想听听是否有一些标准的解决方案。我尝试使用google，但我使用的关键字(分布密度离散)仅打开处理除我以外其他问题的页面。因此，如果您将我指向正确的词以进行搜索，我将很高兴。
最佳答案
通常，在具有任意密度函数的任意空间上，您可以通过rejection sampling得到一个合理的近似值。
D。 p。 r范围中选择一个随机数[0,D)。 p的密度大于r，请接受p作为您的要点之一。 我不确定这对您的案件有多简单。在网格上生成随机，均匀分布的点本身听起来像是一个棘手的问题。我能想到的唯一解决方案是计算网格中每个三角形的面积，随机选择一个与该三角形的面积成正比的三角形，然后在该三角形内选取一个random point。我相信您可以在N个三角形的O(logN)中进行选择。
但是考虑到您可能会将大部分这些点都扔掉了，这可能比您当前的方法差很多，因为网格足够大且密度函数不够令人满意(即最大比平均值大得多的密度函数)。
像任何类型的随机抽样一样，它需要花费很多时间才能开始类似于基础分布。一小部分点可能看起来或多或少是随机的。但是，您可以使用某种准随机的点放置方法来解决此问题(即使设置较大的点，它也可能会提供更好的结果)。
我想到的是上述方法与@BlackBear算法的混合。您可以计算每个三角形的面积和平均密度，然后使用它来确定每个三角形必须包含多少个点。然后，要将点实际放置在三角形内，请使用拒绝采样方法。
关于algorithm - 根据密度在网格上分布点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9294316/