Распределить точки на сетке в соответствии с плотностью

Question

Учитывая (возможно, открытую) сетку с текстурой плотности и количеством точек, мне нужно распределить эти точки в соответствии с плотностью на сетке.

До сих пор я придумал несколько решений, некоторые из которых работали, а другие - нет. Один из алгоритмов, которые я попробовал, состоял в том, чтобы точки были соединены пружинами и имитировали распределение до равновесия (или до тех пор, пока решение не будет соответствовать потребностям пользователей). Источник Переплетение многоугольных поверхностей К сожалению, это несколько медленно для большого количества точек (> 2k), поэтому мне нужно подходящее решение для больших чисел.

У меня уже есть некоторые идеи, но я хотел бы услышать, есть ли какие-нибудь стандартные решения для этого. Я попробовал Google, но ключевые слова, которые я использовал (дискретная плотность распространения), только показывали страницы, которые справляются с другими проблемами, чем мои. Поэтому я был бы счастлив, если бы вы указали мне правильные слова для поиска.

Answer 1

В общем, в произвольном пространстве с произвольной функцией плотности вы можете получить разумное приближение с помощью выборки отклонения .

• Найдите свою максимальную плотность D.
• Выберите случайную точку p.
• Выберите случайное число r из диапазона [0,D).
• Если плотность на p больше r, примите p в качестве одной из ваших точек.

Я не уверен, насколько легко это будет применяться к вашему делу. Создание случайных, равномерно распределенных точек по сетке само по себе кажется сложной задачей. Единственное решение, которое я могу придумать, - это вычислить площадь каждого треугольника в вашей сетке, случайным образом выбрать треугольник с вероятностью, пропорциональной его площади, и выбрать случайную точку внутри треугольника. Я полагаю, что вы могли бы сделать этот выбор в O (logN) на N треугольников.

Но, учитывая, что вы, возможно, отбрасываете большинство этих точек, это может оказаться гораздо хуже, чем ваш нынешний подход, учитывая достаточно большую сетку и достаточно неприятную функцию плотности (то есть такую, у которой максимум намного больше среднего) .

Как и при любой случайной выборке, требуется немало точек, прежде чем она начнет напоминать базовое распределение; небольшой набор точек, вероятно, будет выглядеть более или менее случайным. Но вы можете обойти это с помощью некоторого квазислучайного метода размещения точек (и даже с большим набором, это может дать лучшие результаты).

Одна вещь, которая приходит на ум, - это гибрид вышеуказанного подхода и алгоритма @ BlackBear. Вы можете рассчитать площадь и среднюю плотность для каждого треугольника, и использовать это, чтобы решить, сколько точек должен содержать каждый. Затем для фактического размещения точек в треугольнике используйте метод выборки отклонения.

Answer 2

Вот моя идея:

1. Разделить текстуру плотности на равные прямоугольные части;
2. Для каждой части вычислите число в диапазоне от 0,0 до 1,0, где 1,0 означает «максимальная плотность».из точек "и 0,0 означает противоположное," вообще нет точек ";
3. Вычислите, сколько точек соответствуют значению 1,0, разделив общее количество точек, которые вы хотите разместить, и сумму всех средних;
4. Тогда вы знаете, сколько точек вы должны нарисовать в каждом прямоугольнике, поэтому начертите их равномерно;

Теперь, чем меньше прямоугольники, тем более точный результат вы получите.Я сделал небольшую тестовую программу (C #, используя медленные методы, например, GetPixel и SetPixel на растровом изображении), и вот результаты, предполагающие 10 тыс. Точек, изображение 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

Проблема распределения облака точек по произвольной функции изоморфна с сглаживанием черно-белого изображения с черно-белым изображением.Все алгоритмы имеют сложность во время выполнения, пропорциональную 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;
}