Друзья я не математик, но у меня возникла такая вот нехитрая задачка. Посоветуйте, в каком направлении «копать».
Дан прямоугольник-контейнер с изменяющимися шириной и высотой. Еще есть n-прямоугольников-детей. Задача заключается в том, чтобы заполнить контейнер прямоугольниками-детьми, таким образом, чтоб они занимали как можно большую площадь прямоугольника-контейнера (они могут располагаться как по горизонтали так и по вертикали и даже в несколько строк и столбцов если контейнер большой, а «детей» много). Ситуация омрачается еще тем, что прямоугольники-дети должны быть с одинаковыми размерами (но возможно мне это только кажется).
Подскажите, какие алгоритмы может посмотреть или уже есть реализации нечто подобного? Всю голову себе уже «сломал».
В том то и задача чтоб определить оптимальный размер прямоугольника потомка и расставить потомков внутри. Они не обязательно должны занимать всю площадь родителя. Нужно определить размер потомка и каким образом потомки должны быть расставлены в ряд, столбец или таблицей NхM.
Согласен, что условие не корректно. Т.к. непонятны какие ограничения по размерами и существуют ли они (относиться к большому прямоугольнику и к детям-прямоугольникам).
Откуда берется n (количество прямоугольников-детей)
одинакового размера прямоугольники дети или же нет?
первая мысль заполнить прямоугольниками которые равны следующему
главный прямоугольник размеры KxL
дальше находим два числа которые дают i x j = n
соответственно дети прямоугольники имеют размер (K/i)x(L/j)
я так понимаю, вы не понимаете чего хотите :) если можно как угодно менять размер потомков, то можно всем поставить высоту равную высоте контейнера, а ширину равную ширина_контейнера / количество_потомков. и тогда потомки будут занимать всю площадь контейнера целиком.
На сколько в итоге я понял у вас есть размер окна и размер n одинакового размера картинок.
Требует разместить их в окне, таким способом, чтобы картинки покрыли максимальную площадь окна.
Если я все правильно понял, то это и действительно является двумерной задачей об упаковке.
Рекомендую почитать: раз два три книжка
Я знаю чего я хочу :) может просто объясняю как-то не правильно :)
Уточняю. Есть прямоугольник (окно программы) у него будет меняться ширина и высота динамически (все зависит от пользователя), его нужно заполнить равными прямоугольниками (картинками), которых может быть разное кол-во, задаваемое также динамически. Так вот нужно определить в зависимости от размеров исходного окна (600х150 px к примеру) размер картинки (200х150 px к примеру) если картинок было 3-и и расположить картинки горизонтально. Другое условие: окно размером 150х600 px, размер картинок определить как 150х200 px и расположить картинки вертикально. И третье возможное условие все для тех же 3-х картинок, когда окно размером 600х600 px? то размер картинок должен быть определен как 300х300 px и они будут расположены в два столбца и в две строки. Вот примерно так :)