Разработка программы для решения задачи упаковки ортогональных многогранников

Для решения задач упаковки ортогональных объектов была разработана программная система.

Используемое программное обеспечение

Для проектирования и разработки программной системы были выбраны:

• тип приложения: веб-приложение;
• среда разработки: Visual Studio Code;
• язык программирования: JavaScript с использованием библиотеки JQuery.

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

Visual Studio Code – редактор исходного кода производства Microsoft, с помощью которой разработчики имеют доступ к инструментам для кроссплатформенного создания веб- и облачных приложений. Visual Studio Code создавалась на базе Electron и включает в себя отладчик, инструменты для работы с Git, средства для рефакторинга кода и подсветку синтаксиса.

Язык программирования JavaScript – объектно-ориентированный язык, разработанный компанией Netscape Communication Corporation. Первоначальное название – LiveScript. Предназначен для написания сценариев и манипулирования объектами активных HTML-страниц. Основные характеристики:

• Слабый (динамический) контроль типов;
• Объектно-ориентированность. В отличие от других языков программирования данного типа, JavaScript основан на прототипах, а не на классах.

Описание работы разработанной системы

Разработанная система состоит из нескольких компонентов:

- главное окно программы, позволяющее пользователю управлять поведением приложения;

- контекстное меню, благодаря которому пользователь может загружать файлы из файловой системы операционной системы, на которой было запущено приложение, выбирать режимы сортировки и размеры контейнера;

- главный поток, отвечающий за диспетчеризацию событий на виджеты соответствующего интерфейса пользователя, включая события графического представления. Он также является потоком, в котором приложение взаимодействует с компонентами из набора инструментов пользовательского интерфейса операционной системы.

- второстепенный поток, обрабатывающий входные данные и преобразующий текст в отдельные объекты с дальнейшим выводом их на экран;

При первом запуске приложения открывается начальный экран, на котором расположены кнопки управления, окно ручного ввода текста, панель индикации заполненности контейнера, загрузки файла и отрисовки объектов (рис. 1).

Рисунок 1. Главный экран приложения

Далее пользователь может загрузить файл с помощью меню выбора файла из файловой системы устройства, на котором запущено приложение. Система выдаст сообщение об успешной или неудачной загрузке файла.

Файл входных данных представляет из себя следующую структуру:

• WxH – первая строка файла, определяющая габариты контейнера, где W – ширина контейнера, H – высота. Помимо габаритов контейнера пользователь может задать значение «Авто». Таким образом размеры контейнера будут автоматически определяться на этапе упаковки объектов;
• Sort – вторая строка, определяющая режим предварительной сортировки объектов. На вход могут подаваться значения:
  • «Без сортировки» - упаковка без предварительной сортировки;
  • «Высота» - упаковка с предварительной сортировкой объектов по их высоте;
  • «Ширина» - упаковка с предварительной сортировкой объектов по их ширине;
  • «Площадь» - упаковка с предварительной сортировкой объектов по их площади;
• Objects – построчный перечень упаковываемых ортогональных объектов в виде набора прямоугольников, из которых он состоит, в формате rect1 (W x H) pos rect2 (W x H) x N, где W – ширина объекта, H – высота, N – количество объектов с идентичными параметрами, pos – расположение объектов относительно друг друга. Расположение определяется в зависимости от входных данных:
  • «l» - прямоугольник2 расположен слева относительно прямоугольника1;
  • «r» - прямоугольник2 расположен справа относительно прямоугольника1;
  • «t» - прямоугольник2 расположен сверху относительно прямоугольника1;
  • «b» - прямоугольник2 расположен снизу относительно прямоугольника1;

После успешной загрузки, пользователь нажимает кнопку «Read», файл обрабатывается и загружается во внутреннюю память приложения. Эта память представляет собой массив, в котором хранится обработанный текст в виде отдельных объектов.

Также пользователь может задавать все входные данные вручную. Для этого предусмотрено поле для описания упаковываемых объектов (рис. 2).

Рисунок 2. Ручной ввод данных об упаковке

После нажатия кнопки «Enter» на клавиатуре система проводит вычисления и отображает результаты решения заданной задачи.

Принципиальная схема работы разработанного приложения представлена на рис. 3.

Рисунок 3. Схема работы программной системы

В разработанном приложении реализованы два режима упаковки объектов:

• Упаковка прямоугольных объектов;
• ­Упаковка ортогональных объектов, состоящих из прямоугольников;

Режим упаковки зависит от входных данных об объектах:

• если на вход поступают данные вида “WxHxN” – будет работать режим упаковки прямоугольных объектов;
• если на вход поступают данные вида “WxHposWxHxN” – будет работать режим упаковки ортогональных объектов;

Рисунок 4. Пример работы приложения в режиме упаковки прямоугольных объектов

Рисунок 5. Пример работы приложения в режиме упаковки ортогональных объектов

Если в ходе упаковки не удалось разместить некоторые объекты в заданный контейнер, то система предоставит их перечень по завершении расчетов и отображения результатов упаковки (Рис. 6).

Рисунок 6. Отчёт о заполненности контейнера и об объектах, которые не вошли в него

Алгоритм размещения объектов

Рассматриваемый алгоритм размещения ортогональных объектов основан на офлайн алгоритме «Первый подходящий по убыванию» (First Fit Decreasing High, FFD), состоящий из следующих этапов:

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