Эффективное позиционирование блоков переменного размера

Question

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

Мне было трудно это найти, просто я искал кого-то, кто бы указывал мне правильное направление.Просто ищите псевдокод (язык не имеет значения) или библиотеку, которая может быть реализована на Java, если это будет необходимо.Производительность - это проблема, поэтому мне действительно нужно, чтобы она была максимально эффективной во всех отношениях.

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

Answer 1

Статья о проблеме упаковки в Википедии ссылается на этот алгоритм , описанный в этой статье - "Оптимальная упаковка прямоугольника: первые результаты".

Answer 2

Я не уверен, как он соотносится с алгоритмом, на который указал Э., но однажды я построил оконную систему, и мне нужно было хранить прямоугольные фрагменты изображения вне экрана. Мой метод был такой:

Представьте, что пространство для хранения наклонено на 45 градусов влево, поэтому у вас есть V-образный контейнер. У него есть одна «точка долины», в самом низу (начало координат)

\    /
 \  /
  \/

Вставьте в него один блок, чтобы нижний угол блока находился в точке долины.

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

\    /
 \/\/

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

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