Как распределить прямоугольники с минимальным перекрытием

Question

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

1. Хотя места достаточно, прямоугольники не перекрываются или перекрываются совсем немного.
2. Когда не хватает места, прямоугольники перекрываются, но при этом пытаются перекрывать друг друга возможно (поэтому все они складываются в одном месте).

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

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

Затем я попытался назначить «точки» пространству и разместить прямоугольники рядом с этими точками. Чем ближе был прямоугольник к точке, тем большее «давление» он оказывал на него. И это давление складывается для каждого прямоугольника, который был помещен. Алгоритм пытался расположить прямоугольники вблизи точек с минимальным давлением. К сожалению, это привело к тому, что прямоугольники сложились рядом с верхним левым и нижним правым углами.

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

Answer 1

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

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

Answer 2

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

Разделите экран на n частей и случайным образом выберите часть из нее и сохраните ее. Если он снова выздоровеет, пренебрегайте им, продолжайте и продолжайте заполнять его прямоугольниками. Вы можете формировать фигуры, похожие на фигуры прямоугольников, и написать другой алгоритм для этого. Как и в пазле, вы найдете кусочки из вашего набора прямоугольников, пытаясь подогнать каждую фигуру под примерную фигуру к пазлу. Таким образом, преобразование проблемы таким образом может помочь. Вы можете превратить задачу в случайный пример, чтобы решить задачу. Удачи.

• Шаг 1: случайным образом выберите и площадь,
• Шаг 2: распределите прямоугольник,
• Шаг 3: Если перекрытие, удалите последний шаг,
• Шаг 4: Если перекрытия, выберите новую область случайным образом,

Вы можете l oop этот процесс.