Как заполнить квадрат меньшими квадратами / прямоугольниками?

Question

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

Я пытаюсь написать метод, который будет принимать мои входные размеры (9 'x 8' 8 ") и минимальный / максимальный размер (1 'x 3', 2 ', 4' и т. Д.) И генерировать случайный набор квадратов и прямоугольников для заполнения стены. Я пытался сделать это вручную, но я просто не доволен полученным макетом, и каждый раз, когда я хочу «рандомизировать» макет, требуется около 35 минут.

Answer 1

Одно из решений - начать с x * y квадратов и случайным образом объединить квадраты в прямоугольники. Вы захотите придать разным весам квадраты разного размера, чтобы не допустить, чтобы алгоритм просто заканчивал множеством крошечных прямоугольников (то есть большие прямоугольники, вероятно, должны иметь более высокий шанс выбора для слияния, пока они не станут слишком большими).

Answer 2

Другая идея:

1. Randomly generate points on the wall
    Use as many points as the number of rectangles you want
    Introduce sampling bias to get cooler patterns
2. Build the kd-tree of these points

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

(см .: http://en.wikipedia.org/wiki/Kd-tree)

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

Answer 3

Звучит как Древовидная карта

Answer 4

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

http://en.wikipedia.org/wiki/Bin_packing_problem

http://mathworld.wolfram.com/Bin-PackingProblem.html

http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml

Таким образом, вы «можете» создать множество случайных квадратов и запустить его через упаковщик бинов, чтобы сгенерировать ваш шаблон.

Я сам не реализовал алгоритм упаковки бинов, но видел, как его делал коллега по сайту Nike. Желаем удачи

Answer 5

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

Я бы сказал, что вы можете сделать что-то простое:

   Pick an (x,y) coordinate that is not currently inside a rectangle.
   Pick a second (x,y) coordinate so that when you draw a rectangle between
      the two coordinates, it won't overlap anything. The bounding box of
      valid points is just bounded by the nearest rectangles' walls.
   Draw that rectangle.
   Repeat until, say, you have 90% of the area covered. At that point you
      can either stop, or fill in the remaining holes with as big rectangles
      as possible.

Может быть интересно параметризовать генерацию точек, а затем создать генетический алгоритм. Функцией фитнеса будет то, насколько вам нравится договоренность - она ​​будет составлять для вас сотни мероприятий, и вы будете оценивать их по шкале от 1 до 10. Затем он взял бы лучшие и настроил их, и повторял до тех пор, пока вы не получите соглашение, которое вам действительно нравится.

Answer 6

Построение ответа Филиппа Бодуана.

Существуют реализации древовидных карт на других языках, которые вы также можете использовать. В Ruby с RubyTreeMap вы можете сделать

require 'Treemap' 
require 'Treemap/image_output.rb'

root = Treemap::Node.new 0.upto(100){|i| root.new_child(:size => rand) } 

output = Treemap::ImageOutput.new do |o| 
   o.width = 800 
   o.height = 600 
end 

output.to_png(root, "C:/output/test.png") 

Однако он сортирует прямоугольники, поэтому выглядит не очень случайно, но это может быть началом. Для получения дополнительной информации см. Rubytreemap.rubyforge.org/docs/index.html

Answer 7

бункер или квадратная упаковка?

бин упаковка: http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml

Квадратная упаковка: http://www.maa.org/editorial/mathgames/mathgames_12_01_03.html

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

Answer 8

1. Определить область ввода;
2. Нарисуйте вертикальные линии в нескольких случайных горизонтальных местах по всей высоте;
3. Нарисуйте горизонтальные линии в нескольких вертикальных положениях по всей ширине;
4. Сместить некоторые «столбцы» вверх или вниз на произвольную величину;
5. Сместить несколько «строк» ​​влево или вправо на произвольную величину (может потребоваться подразделить некоторые ячейки для получения полных горизонтальных швов;
6. Снимайте швы в соответствии с эстетическими требованиями.

Этот графический метод имеет сходство с ответом Брайана .

Answer 9

Я предлагаю:

Начните с установки многоугольника с четырьмя вершинами, которые нужно съесть с кусочками прямоугольника различного размера (вплоть до макс.):

public double[] fillBoard(double width, double height, double maxside) {
  double[] dest = new int[0];
  double[] poly = new int[10];
  poly[0] = 0; poly[1] = 0; poly[2] = width; poly[3] = 0;
  poly[4] = width; poly[5] = height; poly[6] = 0; poly[7] = height;
  poly[8] = 0; poly[9] = 0;
  ...
  return dest; /* x,y pairs */
}

Затем выберите случайную вершину, найдите линии многоугольника в пределах (включительно) 2 X максимальной стороны линии. Найти значения x всех вертикальных линий и значения y всех горизонтальных линий. Создайте оценки для «правильности» выбора каждого значения x и y, а также уравнения для создания оценок для значений между значениями. Добротность измеряется как уменьшение количества линий в оставшемся многоугольнике. Сгенерируйте три варианта для каждого диапазона значений между двумя координатами x или двумя координатами y, используя псевдослучайный генератор. Оцените и выберите пары значений x и пары y на основе средневзвешенного значения, опираясь на хорошие варианты. Примените новый прямоугольник к списку, вырезав его форму из массива poly и добавив координаты прямоугольника к массиву dest.

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

EDIT

Проведите тестирование на попадание, чтобы устранить возможные совпадения. И есть шпинат, прежде чем начать печатать. ;)

Answer 10

Я бы генерировал все по спирали, медленно входящей в систему. Если в какой-то момент вы дойдете до точки, в которой ваше решение окажется «неразрешимым» (то есть IE не может поместить какие-либо квадраты в оставшуюся середину, чтобы удовлетворить ограничениям) перейдите к более раннему черновику и меняйте квадрат, пока не найдете удачное решение.

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

public Board GenerateSquares(direction, board, prevSquare)
{
   Rectangle[] rs = generateAllPossibleNextRectangles(direction, prevSquare, board);
   for(/*all possible next rectangles in some random order*/)){
      if(board.add(rs[x]){
           //see if you need to change direction)
           Board nBoard = GenerateSquares(direction, board, rs[x]);
           if(nBoard != null) return nBoard; //done
           else board.remove(rs[x]);
      }
  }
  //all possibilities tried, none worked
  return null;
}

}