Distribute points on the grid by density

Question

Given a (possibly open) grid with a density texture and a few points, I need to distribute these points according to the density on the grid.

So far, I have made several solutions, some of which worked, while others did not. One of the algorithms I tried was to have the points connected by springs and mimic the distribution to equilibrium (or until the solution meets the needs of users). Source Retiling Polygonal Surfaces Unfortunately, for a higher number of points (> 2k) this slows down a bit, so I need a solution for higher numbers.

I already have ideas, but I would like to hear if there are some standard solutions for this. I tried Google, but the keywords that I used (discrete distribution density) only displayed pages that handle problems other than mine. Therefore, I would already be happy if you indicated the right words for the search.

Answer 1

In the general case, through an arbitrary space with an arbitrary density function, you can get a reasonable approximation through sampling .

• Find the maximum density D.
• Select a random point p.
• Select a random number rfrom the range [0,D).
• p , r, p .

, . , . , , - , , , . , O (logN) N .

, , , , ( , ).

, , ; , , . - ( , ).

, , - @BlackBear. , , . , , .

Answer 2

:

• ;
• 0.0 1.0, 1.0 " ", 0.0 " ";
• , 1.0, , , ;
• , , ;

, , . (#, , GetPixel SetPixel ), , 10k , 256x256 . , 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

Answer 3

- . algorithms , O (N) ( N - / //any), , Bayer , , O (24N), .

, 32x32:

Based on ordered smoothing based on a matrix, a given matrix can be generated in a simple way:

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

Generating a matrix is ​​somewhat more complicated, but here is an iterative approach for matrices where the side length is 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;
}