• Вадим, попроси Борю или Лёшу переименовать статью. -- АтрашкевичАндрей
• DONE -- Борис
• thnx -- wolong

Методы представления фигур для раскроя

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

Методы перемещения фигур

Прежде чем перейти к рассмотрению методов представления фигур, следует осветить важный вопрос, обычно опускаемый в литературе связанной с раскроем: «Каким образом перемещать фигуры относительно друг друга?»

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

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

Самый сложный метод ‒ движение вдоль контура. В данном случае фигура движется вдоль контура контейнера, при нахождении подходящего места необходимо обновить контур с учетом новой фигуры.

Растровый метод

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

Самый простой метод представления ‒ это для занятого деталью места и для свободного. Позиционирование фигуры на листе сводится к простому суммированию матрицы из нулей и единиц, которая представляет объект. Если полученное значение больше нуля, то в области имеется пересечение фигур.

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

• Как выделить контур?
• Как выполнить заливку контура?
• Каким образом перемещать фигуру на плоскости относительно других?

• «Контур выделить является не самой сложной задачей.» -- Йода магистр фразу твою одобряет. -- АтрашкевичАндрей. Выделение контура не является самой сложной задачей: для её решения / реализации достаточно закрасить те прямоугольники, в которых присутствуют составляющие части фигуры.

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

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

Огромный плюс данного метода ‒ простота работы с данными. Для того, чтобы задать зазор между фигурами, достаточно увеличить растр. Например, вместо 1x1 взять 10x10. К тому же, такая регулировка аппроксимации значительно увеличивает скорость работы алгоритма, при совсем небольшом снижении качества.

Представление в виде полигона

Растровое представление не является достаточно точным для представления фигур, альтернативой является представление фигур в виде полигонов. В таком представлении объем информации пропорционален числу вершин и не зависит от размера фигуры. Для растра проверка расположения будет , а для полигонов уже . Для того, чтобы проверить нет ли нигде пересечений нужно выполнить набор тестов:

• проверить пересекаются ли описывающие прямоугольники фигур, если нет, то и фигуры не пересекаются, иначе перейти к следующему тесту;
• для каждой пары рёбер проверить, пересечение описывающих прямоугольников;
• проверить, пересекаются ли рёбра;
• проверить, лежат ли какие-либо вершины одного полигона, внутри другого.

В данном варианте представления также присутствует ряд проблем, которые необходимо решить:

1. Как определять пересечения между фигурами?
2. Как искать оптимальное расположение фигуры на плоскости?

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

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

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