geometry - 展开二维点分布的算法

Question

在 2D 像素阵列中，我需要一种有效的算法来选择最分散的 p% 像素。

这可以通过选择点来自适应地完成，然后反复调整靠得太近的点的位置。但这效率不高，因为它需要多次迭代和距离计算。

它不必是完美的，它只需要尽可能有效地避免点簇。

score 1 · Accepted Answer

感谢大家的回答！

最好的解决方案似乎是使用“预构建的构建块”：nxn 阵列与已选择的单元格，并用这些覆盖像素阵列。

例如，覆盖率为 12.5% 的 4 x 4 阵列将是：

覆盖率为 6.3%：

要获得这些之间的百分比覆盖率，只需根据迄今为止总体实际百分比覆盖率的运行记录在这些块之间交替。要覆盖不是 4 的倍数的宽度，请使用一些 3 x 3 块。为了更有效地覆盖更大的区域，只需使用更大的块。

这有效地覆盖了整个阵列，无需距离计算或浮点运算。

score 1 · Accepted Answer

很老，但值得一试，因为答案错过了一个重要的方法，并专注于您不感兴趣的最佳解决方案。但是我建议的方法可能会也可能不会满足您的需求。

您可以使用专为此类问题设计的准随机序列。最普遍的是Sobol 序列，您可以找到几乎任何语言的罐头包。它们的速度非常快：只有按位算术。

它们很可能会产生一些簇，但这可以通过预先选择用于 x 和 y 维度的“种子”并用肉眼检查来避免。

这取决于你想用这些点做什么：如果“视觉展开”很重要，这可能不是你想要的。如果您想要几乎均匀地“填充平面”的点，它们可以完美地完成这项工作。它们对于快速平均图像上的某些东西特别有用，因为与“正常”随机生成相比，它需要更少的点。尝试不同的尺寸并查看。

另请参阅此链接以获取示例实验和图片。

score 1 · Accepted Answer

你可以试试 Wang 的瓷砖：
http
://en.wikipedia.org/wiki/Wang_tile （查看链接到 Cohen 的论文和 Kopf 的论文的页面。我是新用户，所以不能发布所有链接）。

这些将预先构建的瓦片想法以及通常用泊松盘模式解决的均匀分布的要求结合在一起。Wang 瓷砖可以避免周期性效应，这几乎肯定是更直接使用预制瓷砖的问题。

score 1 · Accepted Answer

像素的“最分散”选择是其 Delaunay 三角剖分由等边三角形组成的集合。通过将像素阵列拆分为一组框来找到导致此三角剖分的点集，其中每个框的 sqrt(3) 长于其宽度。每个框为最终的像素集贡献 5 个像素（每个角一个，加上框中心的一个中心节点）。诀窍是找出多少行和多少列的盒子会给你这个 1:sqrt(3) 的比率。无需经过推导，您可以通过以下方式获得：

std::vector<PixelIndices> PickPixels(int width, int height, float percent)
{
  int total_pixels = width*height;
  int desired_pixel_count = (int)total_pixels*percent;

  // split the region up into "boxes" with 4 corner nodes and a center node.
  // each box is sqrt(3) times taller than it is wide.

  // calculate how many columns of boxes
  float a = 1.155*height/(float)width;
  float b = .577*height/(float)width + 1;
  float c = 1 - desired_pixel_count;
  int num_columns = (int)((-b + sqrt(b*b -4*a*c))/(2*a));

  // Now calculate how many rows
  int num_rows = .577*height*num_columns/(float)width;

  // total number of pixels
  int actual_pixel_count = 2*num_rows*num_columns + num_rows + num_columns + 1;

  std::cout << "  Total pixels: " << total_pixels << std::endl;
  std::cout << "       Percent: " << percent << std::endl;
  std::cout << "Desired pixels: " << desired_pixel_count << std::endl;
  std::cout << " Actual pixels: " << actual_pixel_count << std::endl;
  std::cout << "   Number Rows: " << num_rows << std::endl;
  std::cout << "Number Columns: " << num_columns << std::endl;

  // Pre-allocate space for the pixels
  std::vector<PixelIndices> results;
  results.reserve(actual_pixel_count);

  // Now get the pixels, my integer math is probably wrong here, didn't test
  //  (didn't even finish, ran out of time)
  for (int row = 0; row <= num_rows; row++)
  {
    int row_index = row*height/num_rows;

    // Top of box
    for (int col = 0; col <= num_columns; col++)
    {
      int col_index = col*width/num_columns;
      results.push_back(PixelIndices(row_index, col_index));
    }

    // Middle of box
    if (row != num_columns)
    {
      for (int col = 0; col < num_columns; col++)
      {
         // I'll leave it to you to get this, I gotta go!
      }
    }
  }

  return results;
}

您可以通过查找行/列中每个点之间的距离并仅添加偏移量来加快速度，而不是使用整数除法来查找索引。

score 1 · Accepted Answer

你想要一个泊松磁盘分布，但这很棘手。进行搜索会发现很多关于如何有效地做到这一点的学术论文：http: //people.csail.mit.edu/thouis/JonesPoissonPreprint.pdf

score 0 · Accepted Answer

这个怎么样：

发现每个点到其他点的距离之和。所以点 A 的总距离为 dist(A, B) + dist(A, C) + dist(A, D) + ...
对这些总和的距离进行排序。
删除距离总和最小的点，直到达到所需的百分比。

这可能足够准确，但如果不是，您始终可以将步骤 3 替换为：

“删除总和最小的点，如果您需要删除更多点以达到所需的百分比，则返回步骤 1。”

等待。现在我想知道。您是在尝试从给定的一组点中找到最分散的点……还是从给定的数组中找到最分散的点？那是完全不同的……而且仍然很难。

score 0 · Accepted Answer

如何根据每个像素与所有其他像素的接近程度来计算每个像素的“密度”值。然后，重复删除最“密集”的像素，直到列表中剩余的 p% 以下。

您需要进行距离计算以确定任何给定两点之间的密度最多两次。第一次是您构建原始列表时 - 每个像素都需要与其他像素进行比较。第二个是当您从列表中删除一个像素时 - 您必须根据列表中剩余的每个像素计算删除的像素。这是为了说明密度值随着每个像素的移除而发生变化 - 例如，直接相邻的 2 个像素将具有非常高的值，但一旦移除一个，剩余的像素可能具有非常低的值。

一些快速伪代码（请注意，在此示例中，较高密度区域的数字较低）

For I = 0 to MaxPixel
    For J = I to MaxPixel
        PixelDensity[I], PixelDensity[J] += DistanceBetween(Pixels[I], Pixels[J])

While PixelDensity.Count > TargetCount
    RemovePixel = IndexOfSmallest(PixelDensity)
    ForEach I in PixelDensity
        PixelDensity[I] -= DistanceBetween(Pixels[I], Pixels[RemovePixel])
    PixelDensity.Remove(RemovePixel)

如果内存比计算时间更重要，您还可以将任意两点之间的距离存储在一个简单的二维数组中。此外，而不是简单的距离，使距离计算成指数可能会有所帮助——这将避免像两个点几乎在彼此之上，但远离其他一切，并且两者都通过的事情。

score 0 · Accepted Answer

一种迭代的扫雷式洪水填充方法将很容易可视化。

对于每个单元格，找到最近的两个点并记录这两个距离的乘积。
那些具有最高产品的细胞是那些连接到最远点的细胞。

score 0 · Accepted Answer

您可以使用凸包算法，并排除该算法将计算并重复它的点，只要它达到您的 p% 标准，或者

执行凸包算法步骤，检查包含在包内和包内的点是否满足标准 100% - p%

凸包的一些演示在这里 http://www.cs.unc.edu/~snoeyink/demos/

在这里您可以获得更多信息 http://softsurfer.com/Archive/algorithm_0109/algorithm_0109.htm

score 0 · Accepted Answer

哦！这个怎么样！

（以一种非常随意的方式，因为我不知道你的矩阵是正方形还是其他什么......我假设它是。）

假设您有一个 1000x1000 数组，您想将 47 点放入其中（我选择 47 是因为它是一个不寻常的数字，不适合“很好”）。

你拿 ceil(sqrt(47)) ......这会给你一个值（7）。所以我们制作了一个 7x7 的正方形，用 47 个像素填充它（有些是空白的），并想象将它放在数组的角落。

现在，根据它们在小型 (7x7) 阵列到大型阵列 (1000x1000) 中的位置，将这些像素中的每一个转换到一个新位置。一个简单的方程式应该为您执行此操作...对于 X 坐标，例如：

xBigArrayIndex = xSmallArrayIndex * 1000 / 7;

然后你的像素会超级分散！它又好又快。

唯一的缺点是，只有在您的正方形开始时的理想间距时，这才能完美地工作……如果您天真地填充它（从左上角开始，穿过等），您最终会得到一个稍微不理想的结果传播......因为翻译后的像素不会完全到达大阵列的右下角。但也许这已经足够好了？如果不是，也许它是更容易处理的问题的一个较小的子集？

geometry - 展开二维点分布的算法

10 回答 10

Related

Reference