Algorithm for spread-out 2D point distribution

Question

In a 2D pixel array, I need an efficient algorithm that will select p% of pixels that are the most spread out.

This can be done adaptively by selecting points, then repeatedly adjusting the positions of points that are too close together. But this isn't efficient since it would require many iterations and distance calculations.

It doesn't have to be perfect, it just needs to avoid point clusters as much as can be done efficiently.

Answer 1

You want a Poisson Disk distribution, but it's tricky. Doing a search turns up lots of academic papers about how to do it efficiently: http://people.csail.mit.edu/thouis/JonesPoissonPreprint.pdf

Answer 2

Thanks to everyone for the answers!

The best solution appears to be using "prebuilt building blocks": n x n arrays with already-selected cells, and covering the pixel array with these.

For example, a 4 x 4 array with 12.5% coverage would be:

0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0

With 6.3% coverage:

0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0

To get a % coverage between these, just alternate between these blocks according to a running tally of the overall actual % coverage so far. To cover a width that's not a multiple of 4, use some 3 x 3 blocks. To cover a larger area more efficiently, just use larger blocks.

This covers the whole array efficiently with no distance calculations or floating-point arithmetic.

Answer 3

The "most spread out" selection of pixels is the set whose Delaunay triangulation consists of equilateral triangles. The set of points which leads to this triangulation is found by splitting the pixel array into a set of boxes, where each box is sqrt(3) longer than it is wide. Each box contributes 5 pixels to the final pixel set (one at each corner, plus a center node at the center of the box). The trick is to find how many rows and columns of boxes will give you this 1:sqrt(3) ratio. Without going through the derivation, here's how you get that:

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;
}

Instead of using integer division to find the indices, you could speed this up by finding the distance between each point in a row/column and just adding by the offset.