6

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

到目前为止，我已经提出了几种解决方案，其中一些有效，而另一些则无效。我尝试的一种算法是通过弹簧连接点并模拟分布直到平衡（或直到解决方案适合用户需要）。Source Retiling Polygonal Surfaces 不幸的是，对于更多的点（> 2k）来说，这有点慢，所以我需要一个可行的解决方案来处理更多的点。

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

4

3 回答 3

5

通常，在具有任意密度函数的任意空间中，您可以通过拒绝采样获得合理的近似值。

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

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

但是考虑到您可能会丢弃大部分这些点，这可能会比您当前的方法更糟糕，因为它有足够大的网格和足够令人不快的密度函数（即最大值远大于平均值的密度函数）。


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

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

于 2012-02-15T15:23:14.093 回答
4

这是我的想法：

  1. 将密度纹理分割成相等的矩形部分；
  2. 对于每个部分，计算一个介于 0.0 和 1.0 之间的数字，其中 1.0 表示“点的最高密度”，而 0.0 表示相反，“根本没有点”；
  3. 通过将要放置的点的总数除以所有平均值的总和，计算对应于 1.0 值的点数；
  4. 然后你知道你必须在每个矩形中绘制多少个点，所以要均匀地绘制它们；

现在，矩形越小，得到的结果就越精确。我做了一个小测试程序（C# 使用慢速方法，即位图上的 GetPixel 和 SetPixel），这是结果，假设 10k 点，256x256 px 图像。图片显示该算法使用 2^2、10^2、50^2 和 90^2 部分：

在此处输入图像描述

这是基准：

parts   time
------------------------
2      00:00:00.7957087
10     00:00:00.6713345
50     00:00:00.5873524
90     00:00:00.4153544
于 2012-02-15T15:13:51.440 回答
0

根据任意函数分布点云的问题与将灰度图像抖动为黑白图像是同构的。这些算法都具有与 O(N) 成正比的运行时复杂度（其中 N 是原始图像/位图/网格/无论什么）中的点数，使用简单的方法，例如拜耳矩阵有序抖动，每个点仅执行一个浮点比较，以及更复杂的误差扩散方法，其运行时间更像 O(24N)，但产生的结果更好，伪影更少。

使用简单的高斯密度函数，简单的拜耳矩阵方法可以在小至 32x32 矩阵的情况下产生令人惊讶的好结果： 拜耳矩阵抖动

给定所讨论的矩阵，可以以直接的方式生成基于矩阵的有序抖动：

matrix = generate_bayer(32);
for (y=0; y<height; y++) {
  for (var x=0; x<width; x++) {
    i = x % matrix.length;
    j = y % matrix.length;

    function_val = gaussian(x, y);  #returns a value 0<=x<=1
    scaled_val = function_val * matrix.length * matrix.length;  #scale to the max element in the matrix
    if (scaled_val > matrix[j][i]) {
      draw_pixel(x, y);
    }
  }
}

生成矩阵稍微复杂一些，但这里有一种迭代方法，用于边长为 2 的幂的矩阵：

//size should be a power of 2, and is the length of a side of the matrix
function generate_bayer(size) {
  base = [[0, 2],
          [3, 1]];
  old_matrix = base;
  mult = 4;

  //successively double the size of the matrix, using the previous one as the base
  while (old_matrix.length < size) {
    //generate a new matrix of the proper dimensions
    new_size = old_matrix.length * 2;
    matrix = new Array[new_size][new_size];

    for (y=0; y<old_matrix.length; y++) {
      for (x=0; x<old_matrix[y].length; x++) {
        //fill in the new 4x4 submatrix
        matrix[y*2]    [x*2]     = old_matrix[y][x] + (mult * base[0][0]);
        matrix[y*2]    [x*2 + 1] = old_matrix[y][x] + (mult * base[0][1]);
        matrix[y*2 + 1][x*2]     = old_matrix[y][x] + (mult * base[1][0]);
        matrix[y*2 + 1][x*2 + 1] = old_matrix[y][x] + (mult * base[1][1]);
      }
    }

    mult *= 4;
    old_matrix = matrix;
  }
  return old_matrix;
}
于 2017-04-13T19:51:40.670 回答