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

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

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

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

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

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

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

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

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

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

Полигональный метод хоть и даёт высокую точность представления, но имеет очень высокую вычислительную сложность. Сложность проверки расположений будет .

Для того, чтобы проверить нет ли нигде пересечений нужно выполнить набор тестов:

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

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

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

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

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

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

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

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

Самый простой метод представления ‒ это для занятого деталью места и для свободного. Раскраиваемый материал в данном случае представляется аналогично. На изображении ниже можно увидеть первичный вариант растрового представления. В данном случае занятые области отмечены серым цветом.

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

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

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

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

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

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

Иногда внутри фигур могут быть свободные области. Например, внутри большой гайки мы можем поместить ещё одну маленькую. Задача отделения контуров решается с помощью развития описанного выше алгоритма заливки. Первым шагом необходимо внешний контур фигуры. Условимся считать, что больше второго уровня вложенности контуров не может быть. Тогда повторяем первый шаг и заполняем необходимую внутреннюю часть фигуры с учётом вложенных контуров. Далее удаляем внешнюю заливку.

В данном варианте представления фигур можно выполнять движение несколькими способами. Можно выполнять движение со сквозным проходом по всему контейнеру плоскости через фигуры, выполняя суммирование в каждой точке, а можно выполнять движение способом «тетриса». Регулировать соотношение скорость-качество можно с помощью изменения размеров прямоугольников, например взять не , а . Огромный плюс данного метода ‒ простота работы с данными. Для того, чтобы задать зазор между фигурами. Для этого достаточно обвести контур ещё несколько раз.