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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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