Формирование карты гильотинного раскроя листа по функциям гильотинного размещения

В статье для решения задачи прямоугольной ортогональной упаковки предложено расширение понятия функции гильотинного размещения, которое представляет собой функцию, ставящую в соответствие ширине листа тройку значений. Помимо стандартного для функции гильотинного размещения результата – минимальной длины листа заданной ширины, достаточного для размещения гильотинным образом заданного набора прямоугольников, используется два дополнительных значения. Они представляют собой информацию о способе раскроя этого листа, с помощью которой можно однозначно построить карты гильотинного раскроя листа и гильотинного размещения набора прямоугольников на нем. Этой информацией являются характеристики первого разреза листа, а также соответствующее разрезу разбиение набора прямоугольников на два поднабора, которое однозначно определяется номером одного из поднаборов разбиения.
Описание первого разреза моделируется одной числовой величиной, которая отражает как размер отступа от левого нижнего угла листа, так и ориентацию разреза – вдоль или поперек листа требуется производить разрез. Показано, что этой информации достаточно для восстановления карты гильотинного раскроя листа и карты гильотинного размещения набора прямоугольников.
Для определения дополнительной информации о первом разрезе и вычисления расширения функции гильотинного размещения предложены модификации алгоритмов получения суммы двух ступенчатых полунепрерывных справа монотонно невозрастающих функций с конечным числом ступеней, а также минимума двух таких функций. Предложен также алгоритм формирования карт гильотинного раскроя и гильотинного размещения прямоугольников на листе, использующий вычисленные расширения функций гильотинного размещения для всех поднаборов требуемого набора прямоугольников.