Случайное и эффективное заполнение пространства фигурами

Question

Каков наиболее эффективный способ случайного заполнения пространства множеством непересекающихся фигур?В моем конкретном случае я заполняю круг кружками.Я случайным образом размещаю круги до тех пор, пока не будет заполнен определенный процент внешнего круга ИЛИ определенное количество мест размещения не будет выполнено (т. Е. Было размещено в положении, которое перекрывает существующий круг).Это довольно медленно и часто оставляет пустые места, если я не допущу огромного количества сбоев.

Итак, есть ли какой-то другой тип алгоритма заполнения, который я могу использовать, чтобы быстро заполнить как можно больше места, но все же посмотретьслучайный?

Answer 1

Проблема, с которой вы столкнулись

Вы столкнулись с проблемой Сборщика купонов , потому что вы используете метод Отклонение выборки .

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

---

Решение

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

---

Возможные опасности

Однако вы должны быть осторожны при кодировании! Возможные опасности:

• Если вы делаете что-то вроде if (random point in invalid grid){ generateAnotherPoint() }, тогда вы игнорируете идею выгоды / ядра этой оптимизации.
• Если вы сделаете что-то вроде pickARandomValidGridbox(), то вы немного уменьшите вероятность создания кругов у края большего круга (хотя это может быть хорошо, если вы делаете это для графического художественного проекта, а не для научного или математический проект); однако, если вы сделаете размер сетки 1 / sqrt (2), умноженный на радиус круга, вы не столкнетесь с этой проблемой, потому что будет невозможно нарисовать блоки на краю большого круга, и, таким образом, вы можете игнорировать все поля сетки на краю.

---

Осуществление

Таким образом, обобщение вашего метода, чтобы избежать проблемы купонного сборщика, выглядит следующим образом:

Inputs: large circle coordinates/radius(R), small circle radius(r)
Output: set of coordinates of all the small circles
Algorithm:
  divide your LargeCircle into a grid of r/sqrt(2)

  ValidBoxes = {set of all gridboxes that lie entirely within LargeCircle}

  SmallCircles = {empty set}

  until ValidBoxes is empty:
    pick a random gridbox Box from ValidBoxes
    pick a random point inside Box to be center of small circle C

    check neighboring gridboxes for other circles which may overlap*
    if there is no overlap:
      add C to SmallCircles
      remove the box from ValidBoxes  # possible because grid is small
    else if there is an overlap:
      increase the Box.failcount
      if Box.failcount > MAX_PERGRIDBOX_FAIL_COUNT:
        remove the box from ValidBoxes

  return SmallCircles

(*) Этот шаг также является важной оптимизацией, которую я могу только предположить, что у вас ее еще нет. Без этого ваша функция didThisCircleOverlapAnother (...) невероятно неэффективна - O(N) на запрос, что делает невозможным заполнение кругов при больших отношениях R>>r.

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

---

Обобщение для более крупных нерегулярных функций

edit: Поскольку вы отметили, что это игра, и вас интересуют неправильные формы, вы можете обобщить это следующим образом. Для любой маленькой неправильной формы заключите ее в круг, который показывает, насколько далеко вы хотите, чтобы он был от вещей. Ваша сетка может иметь размер наименьшего элемента местности. Большие функции могут включать смежные блоки 1x2, 2x2, 3x2, 3x3 и т. Д. Обратите внимание, что во многих играх с функциями, которые охватывают большие расстояния (горы) и небольшие расстояния (факелы), часто требуются сетки, которые рекурсивно разбиваются (то есть некоторые блоки разбиваются на дополнительные субблоки 2x2 или 2x2x2), создавая древовидную структуру. Эта структура с обширной бухгалтерией позволит вам случайным образом размещать смежные блоки, однако это требует много кодирования. Однако вы можете использовать алгоритм круговой сетки, чтобы сначала разместить более крупные объекты (когда на карте достаточно места для работы, и вы можете просто проверить соседние ячейки сетки на коллекцию, не сталкиваясь с проблемой сборщика купонов), тогда поместите меньшие особенности. Если вы можете разместить свои функции в этом порядке, это почти не требует дополнительного кодирования, кроме проверки соседних ячеек сетки на наличие коллизий, когда вы размещаете 1x2 / 3x3 / и т. Д. группа.

Answer 2

Один из способов добиться интересного результата -

create an empty NxM grid
create an empty has-open-neighbors set
for i = 1 to NumberOfRegions
   pick a random point in the grid
   assign that grid point a (terrain) type
   add the point to the has-open-neighbors set
while has-open-neighbors is not empty
   foreach point in has-open-neighbors
      get neighbor-points as the immediate neighbors of point 
          that don't have an assigned terrain type in the grid
      if none
         remove point from has-open-neighbors
      else
         pick a random neighbor-point from neighbor-points
         assign its grid location the same (terrain) type as point
         add neighbor-point to the has-open-neighbors set

. Когда все готово, has-open-соседей будет пустым, а сетка будет заполнена не более чем в областях NumberOfRegions (некоторые регионы содин и тот же тип местности может быть смежным и поэтому будет объединяться в одну область).

Пример вывода с использованием этого алгоритма с 30 точками, 14 типами местности и миром 200x200 пикселей:

Редактировать: попытался уточнить алгоритм.

Answer 3

Как насчет использования двухэтапного процесса:

1. Выберите случайным образом группу из n точек - они станут центрами окружностей.
2. Определите радиусы этихкруги, чтобы они не перекрывались.

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

Чтобы убедиться, что это работает, рассмотрите любую точку p и ееближайший сосед q, который на некотором расстоянии d от p.Если p также является ближайшим соседом q, то обе точки получат окружности с радиусом d / 2, что, следовательно, будет касанием;OTOH, если q имеет другого ближайшего соседа, он должен быть на расстоянии d '

Answer 4

Я бы хотел начать с компактной сетки. Затем возьмите каждый круг и возмущайте его в некотором случайном направлении. Расстояние, на которое вы его возмущаете, также может быть выбрано случайным образом (просто убедитесь, что это расстояние не перекрывает другой круг).

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