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

Ответ 1

Проблема, с которой вы работаете в

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

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

Решение

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

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

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

• Если вы делаете что-то вроде 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

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

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

Обобщение на большие нерегулярные функции

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

Ответ 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

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

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

Изменить: попытался прояснить алгоритм.

Ответ 3

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

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

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

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

Ответ 4

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

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