Алгоритм для распространенного 2D распределения точки

Вам нужен дистрибутив диска Пуассона, но это сложно. При поиске можно найти множество научных статей о том, как это сделать эффективно: http://people.csail.mit.edu/thouis/JonesPoissonPreprint.pdf

Благодаря Всем за ответы!

Лучшее решение, по-видимому, заключается в использовании «предварительно созданных строительных блоков»: массивов nxn с уже выбранными ячейками, и покрывая ими массив пикселей.

Например, массив 4 x 4 с 12,5 % покрытия будет:

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

С покрытием 6,3%:

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

Чтобы получить процентное покрытие между ними, просто чередуйте эти блоки в соответствии с текущим подсчетом общего фактического% покрытия на данный момент. Чтобы покрыть ширину, не кратную 4, используйте блоки размером 3 x 3. Чтобы покрыть большую площадь более эффективно, просто используйте блоки большего размера.

Это эффективно охватывает весь массив без вычислений расстояния или арифметики с плавающей запятой.

Как насчет этого:

1. Найдите сумму расстояний от каждой точки до каждой другой точки. Итак, точка A имеет суммарное расстояние dist (A, B) + dist (A, C) + dist (A, D) + ...
2. Отсортируйте эти суммарные расстояния.
3. Удалите точки с наименьшим расстоянием сумм, пока вы не достигнете желаемого процента.

Это может быть достаточно точным, но если нет, вы всегда можете заменить шаг 3 на:

«Удалите точку с наименьшей суммой, и если вам нужно удалить больше точек чтобы достичь желаемого процента, затем вернитесь к шагу 1. "

Подождите. Теперь мне интересно. Вы пытаетесь найти точки, которые наиболее распространены из данного набора точек ... или пытаетесь из данного массива найти точки, которые будут наиболее разбросаны? Это совсем другое ... и все еще очень сложно.

Итерационный метод затопления тральщиками было бы несложно визуализировать.

1. Для каждой ячейки найдите две ближайшие точки и запишите произведение этих двух расстояний.
2. Те. ячейки с наибольшим количеством продуктов - это те, которые прикреплены к наиболее удаленным точкам.

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

Вместо использования целочисленного деления для поиска индексов вы можете ускорить это, найдя расстояние между каждой точкой в ​​строке / столбце и просто добавив смещение.

Как насчет вычисления начального значения "плотности" для каждого пикселя на основе его близости ко всем остальным пикселям. Затем несколько раз удаляйте самый «плотный» пиксель, пока в списке не останется меньше p%.

Вам нужно будет выполнить расчет расстояния, чтобы определить плотность между любыми заданными двумя точками не более двух раз. Первый раз будет, когда вы создадите исходный список - каждый пиксель нужно будет сравнить друг с другом. Во-вторых, когда вы удаляете пиксель из списка - вам нужно будет вычислить удаленный пиксель по каждому оставшемуся в списке. Это необходимо для учета изменения значений плотности при удалении каждого пикселя - например, 2 пикселя, расположенные непосредственно рядом друг с другом, будут иметь очень-очень высокое значение, но как только один будет удален, оставшийся может иметь очень низкое значение.

Некоторый быстрый псевдокод (обратите внимание, что в этом примере области с более высокой плотностью имеют низкую number)

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)

Если память менее важна, чем время вычисления, вы также можете сохранить расстояние между любыми двумя точками в простом 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)

Если память важнее времени вычисления, вы также можете сохранить расстояние между любыми двумя точками в простом 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)

Если память важнее времени вычисления, вы также можете сохранить расстояние между любыми двумя точками в простом 2-мерном массиве. Кроме того, вместо простого расстояния может быть полезно сделать вычисление расстояния экспоненциальным - это позволит избежать чего-то вроде того, чтобы две точки располагались почти друг над другом, но далеко от всего остального, и чтобы обе прошли через них.

Ой! Как насчет этого!

(Очень волнующе, поскольку я не знаю, является ли ваша матрица квадратной или какой-то другой ... Я предполагаю, что это так.)

Допустим, у вас есть массив 1000x1000, вы хотите поместить 47 точек (я выбрал 47, поэтому это необычное число, которое не подходит "хорошо").

Вы берете ceil (sqrt (47)) ... который даст вам значение (7). Итак, мы создаем квадрат 7x7, заполняем его 47 пикселями (некоторые из них пустые) и представляем, что помещаем его в угол массива.

Теперь переведем каждый из этих пикселей в новое место в зависимости от того, где они находятся. маленький (7x7) массив в большой массив (1000x1000). Простое уравнение должно сделать это за вас ... для координаты X, например:

xBigArrayIndex = xSmallArrayIndex * 1000 / 7;

Тогда ваши пиксели будут суперразложенными! И это красиво и быстро.

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

Вы можете использовать алгоритм выпуклой оболочки и исключить точки, которые этот алгоритм будет вычислять, и повторять его до тех пор, пока он будет соответствовать вашим критериям p%, или

выполнить шаги алгоритма выпуклой оболочки, проверить наличие точек, включенных в оболочку и внутри нее, на соответствие критериям 100% - p%

здесь представлены некоторые демонстрации выпуклой оболочки http://www.cs.unc.edu/~snoeyink/demos/

и здесь у вас есть дополнительная информация http://softsurfer.com/Archive/algorithm_0109/algorithm_0109.htm

You might try Wang tiles:
http://en.wikipedia.org/wiki/Wang_tile
(See the pages linked there to Cohen's paper, and Kopf's paper. I'm a new user so can't post all the links).

These tie together both the prebuilt tiles idea, as well as the evenly distributed requirement usually solved with Poisson-disk patterns. Wang tiles can avoid periodicity effects that are almost surely an issue with more direct use of prebuilt tiles.