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

Ответ 1

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

Ответ 2

Звучит как Treemap

Ответ 3

Другая идея:

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-дерево разделит пространство на несколько прямоугольников. Там может быть слишком много структуры для того, что вы хотите, но ее по-прежнему аккуратный geeky алгоритм.

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

Изменить: просто посмотрел на JTreeMap, немного похоже на то, что он делает.

Ответ 4

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

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

Итак, вы можете "создать нагрузку случайных квадратов и запустить ее через упаковщик bin для генерации вашего шаблона".

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

Ответ 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. Затем он берет лучшие и настраивает их и повторяется до тех пор, пока вы не получите договоренность, которая вам действительно нравится.

Ответ 6

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

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

Площадь упаковки: http://www.maa.org/editorial/mathgames/mathgames_12_01_03.html

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

Ответ 7

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

Существуют версии treemap на других языках, которые вы также можете использовать. В 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 для получения дополнительной информации

Ответ 8

Я бы сгенерировал все по спирали, медленно вступая. Если в какой-то момент вы достигнете точки, где ваше решение окажется "неразрешимым" (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;
}

}

Ответ 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 maxside линии. Найдите значения x всех вертикальных линий и значений y всех горизонтальных линий. Создайте оценки для "доброты" выбора каждого значения x и y и уравнений для генерации оценок для значений между значениями. Доброта измеряется как уменьшение количества линий в оставшемся многоугольнике. Создайте три параметра для каждого диапазона значений между двумя координатами x или двумя координатами y, используя псевдослучайный генератор. Оцените и выберите пары x и пару значений y по средневзвешенной основе, опираясь на хорошие варианты. Примените новый прямоугольник для отображения, отрезая его форму от поли массива и добавляя координаты прямоугольника к массиву dest.

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

ИЗМЕНИТЬ

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

Ответ 10

• Определить область ввода;
• Нарисуйте вертикальные линии в нескольких случайных горизонтальных местоположениях по всей высоте;
• Нарисуйте горизонтальные линии в нескольких вертикальных положениях по всей ширине;
• Сдвиньте некоторые "столбцы" вверх или вниз на произвольные суммы;
• Сдвиньте некоторые "строки" влево или вправо на произвольные суммы (может потребоваться разбить некоторые ячейки для получения полных горизонтальных швов;
• Удалите швы как эстетически требуемые.

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