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

Похоже на Древовидная карта

Another idea:

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

The kd-tree will split the space in a number of rectangles. There might be too much structure for what you want, but its still a neat geeky algorithm.

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

Edit: Just looked at JTreeMap, looks a bit like this is what its doing.

Если вы говорите о чисто программной проблеме;) Существует метод, называемый 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

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

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

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

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

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

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

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

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

This actually sounds more like an old school random square painting demo, circa 8-bit computing days, especially if you don't mind overlaps. But if you want to be especially geeky, create random squares and solve for the packing problem.

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

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

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;
}

}

Я предлагаю:

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

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 строки. Find x values of all vertical lines and y values of all horizontal lines. Create ratings for the "goodness" of choosing each x and y value, and equations to generate ratings for values in between the values. Goodness is measured as reducing number of lines in remaining polygon. Generate three options for each range of values between two x coordinates or two y coordinates, using pseudo-random generator. Rate and choose pairs of x and pair of y values on weighted average basis leaning towards good options. Apply new rectangle to list by cutting its shape from the poly array and adding rectangle coordinates to the dest array.

Question does not state a minimum side parameter. But if one is needed, algorithm should (upon hitting a hitch with a gap being too small) not include too small candidates in selection lists (whic will occasionally make them empty) and deselect a number of the surrounding rectangles in a certain radius of the problem with size and perform new regeneration attempts of that area, and hopefully the problem area, until the criteria are met. Recursion can remove progressively larger areas if a smaller relaying of tiles fails.

EDIT

Do some hit testing to eliminate potential overlaps. And eat some spinach before starting the typing. ;)

Основываясь на ответе Филиппа Бодуэна.

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

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

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