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

Question

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

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

Это не обязательно должно быть идеально, просто нужно избегать точечных кластеров настолько, насколько это можно сделать эффективно.

Answer 1

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

Вы можете использовать квазислучайные последовательности , которые предназначены для таких задач. Наиболее распространенными являются последовательности Соболя , для которых вы можете найти готовые пакеты практически для любого языка. Они невероятно быстрые: только побитовая арифметика.

Скорее всего, они создадут несколько кластеров, но этого можно избежать, выбрав «затравку» для предварительного измерения размеров x и y и проверив ее невооруженным глазом.

Это зависит от того, что вы хотите сделать с точками: если важно «визуальное распространение», это может быть не тем, что вы хотите. Если вам нужны точки, которые «равномерно заполняют плоскость», они отлично справляются со своей задачей. Они особенно полезны для быстрого усреднения чего-либо на изображении, так как для этого требуется меньше точек, чем при «нормальной» случайной генерации. Поэкспериментируйте с разными размерами и посмотрите.

См. Также по этой ссылке для примеров экспериментов и рисунков.

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

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

Answer 3

Вы можете попробовать плитки Ван:
http://en.wikipedia.org/wiki/Wang_tile
(См. Страницы, на которых есть ссылки на статью Коэна и статью Копфа. Я новый пользователь, поэтому не могу опубликовать все ссылки).

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

Answer 4

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

Answer 5

Спасибо всем за ответы!

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

Например, массив 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. Чтобы более эффективно покрыть большую площадь, просто используйте более крупные блоки.

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

Answer 6

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

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

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

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

Answer 7

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

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

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

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

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

xBigArrayIndex = xSmallArrayIndex * 1000 / 7;

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

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

Answer 8

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

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

Answer 9

Как насчет вычисления значения "плотности" для каждого пикселя, с которого он должен начинаться, исходя из его близости ко всем остальным пикселям. Затем несколько раз удаляйте самый «плотный» пиксель, пока не останетесь ниже 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)

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

Answer 10

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

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

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

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

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