Разница между 1.21
и текущей версией
МетодыПредставленияФигурДляРаскроя.
@@ -16,10 +16,36 @@
Самый сложный метод ‒ движение вдоль контура. В данном случае фигура движется вдоль контура контейнера, при нахождении подходящего места необходимо обновить контур с учетом расположения новой фигуры. На данный момент этот метод будет оставлен без особого внимания. Для его реализации необходимо создать цепь (растровую или же векторную) вдоль которой будет перемещаться фигура. Большую сложность, представляет в данном случае вопрос о выборе точки, относительно которой идёт движение.
+--Представление в виде полигона
+Представление фигур в виде полигона даёт хорошую точность аппроксимации. В таком представлении объем информации пропорционален числу вершин и не зависит от размера фигуры. Полигональное представление является первичным для фигур, а на его основе уже можно построить растровое представление, которое будет описано ниже.
+
+Полигональный метод хоть и даёт высокую точность представления, но имеет очень высокую вычислительную сложность. Сложность проверки расположений будет $$o(e sup n )$$.
+
+Для того, чтобы проверить нет ли нигде пересечений нужно выполнить набор тестов:
+ *проверить пересекаются ли описывающие прямоугольники фигур, если нет, то и фигуры не пересекаются, иначе перейти к следующему тесту;
+ *для каждой пары рёбер проверить, пересечение описывающих прямоугольников;
+ *проверить, пересекаются ли рёбра;
+ *проверить, лежат ли какие-либо вершины одного полигона, внутри другого.
+[[cs627421.vk.me/v627421641/3fc69/owgnhO7e1Pk.jpg|Представление фигуры в виде полигона|350px]]
+
+Проверка на пересечения текущей фигуры с ранее расположенными может выполняться различными способами. Первый вариант ‒ через уравнение прямой с угловым коэффициентом. Этот метод для данной задачи будет излишним, ведь кроме проверки пересечения можно найти точку пересечения. Лучше использовать метод проверки на основе псевдоскалярного произведения. Данный метод подробно рассматривается в задачах вычислительной геометрии.
+
+Для перемещения фигуры подходят только алгоритмы «тетрисного» движения. Применять «сквозное движение» мы не можем, так, как тогда придется постоянно проверять, не попала ли она внутрь другой, что в случае полигонов сделать достаточно сложно. Для этого необходимо применять метод «трассировки луча» или приближённо считать комплексный интеграл, пользуясь интегральной формулой Коши.
+
+Алгоритмы с представлением фигур в виде полигонов хорошо подходят для прямоугольников и несложных многоугольников с числом вершин до сотни. Для более сложных сильно возрастает время вычисления пересечений.
+
+Проблема данного метода состоит в сложности обработки контура. Построить эквидистантный (равноудалённый во всех точках от исходного) контур, чтобы задать зазор ‒ не такая уж легкая задача. Отделить внешний контур от внутренних тоже несколько сложнее, ведь контур может состоять из нескольких раздельных кривых, пусть и образующих в сумме одну замкнутую кривую.
+
--Растровый метод
+Растровый метод, позволяет упростить геометрическую сложность фигуры и снизить сложность вычислений до $$o(n sup 2 )$$.
+
Растровые методы предлагают разделить непрерывный раскройный лист на дискретные части, упрощая сложную геометрическую информацию до представления матрицей. Различные авторы предлагают различные методы представления.
-Самый простой метод представления ‒ это $$1$$ для занятого деталью места и $$0$$ для свободного. Раскраиваемый материал в данном случае представляется аналогично. Операция проверки на пересечения с другими фигурами, при текущем расположении в координате $$(x, y)$$ фигуры с шириной равной $$w$$ и высотой $$h$$, не требует никаких сложных действий. Производится простое суммирование по следующей формуле:
+Самый простой метод представления ‒ это $$1$$ для занятого деталью места и $$0$$ для свободного. Раскраиваемый материал в данном случае представляется аналогично. На изображении ниже можно увидеть первичный вариант растрового представления. В данном случае занятые области отмечены серым цветом.
+
+[[http://cs629508.vk.me/v629508641/46df6/INI9om6cQn0.jpg|Растровое представление|300px]]
+
+Операция проверки на пересечения с другими фигурами, при текущем расположении в координате $$(x, y)$$ фигуры с шириной равной $$w$$ и высотой $$h$$, не требует никаких сложных действий. Производится простое суммирование по следующей формуле:
%EQ
S = sum from i=1 to h { sum from j=1 to w } p sub i+y,j+x f sub i,j
@@ -27,12 +53,10 @@
В данном случае, $$p sub i+y,j+x$$ ‒ значение в матрице раскройной плоскости со смещением на координату $$(x, y)$$, а $$f sub i,j$$ ‒ значение в матрице фигуры. В случае если значение $$S > 0$$, то есть пересечение с некоторой фигурой, иначе его нет.
-Есть ряд проблем, с которыми сталкивается разработчик при реализации данного метода.
- *Как выделить контур?
- *Как выполнить заливку контура?
- *Каким образом перемещать фигуру на плоскости относительно других?
-
-[[http://cs627421.vk.me/v627421641/3fc72/4xkhygpBb6o.jpg|Растровое представление|350px]]
+Как видно на изображении выше, не все области внутри фигуры отмечены как занятые. В таком случае, некоторые фигуры могут попасть внутрь других, что является будет являться ошибкой. Данная проблема решается следующим образом:
+ *сначала необходимо отметить все свободные области вне фигуры отдельным номером, например $$2$$, на следующем изображении данные области отмечены тёмно-серым цветом; [[http://cs629508.vk.me/v629508641/46e00/glsuxCp9Rog.jpg|Первый шаг заливки|300px]]
+ *вторым шагом, все области отмеченные другими номерами, то есть $$1$$ и $$0$$, отметить как занятые номером $$1$$; [[http://cs629508.vk.me/v629508641/46e0a/9B1lbke1mNE.jpg|Второй шаг заливки|300px]]
+ *последним шагом, все области отмеченные временным номером $$2$$ отметить как свободные номером $$0$$. [[http://cs633318.vk.me/v633318641/31089/2i9EZLqiRk4.jpg|Последний шаг заливки|300px]]
----
* «Контур выделить является не самой сложной задачей.» -- Йода магистр фразу твою одобряет. -- АтрашкевичАндрей.
@@ -43,24 +67,6 @@
* «Учитывать внутреннее свободное пространство фигур, при данном методе представления, является не на столько сложной задачей, как в остальных случаях.» -- Вадим, перепиши, я вообще ничего не понял. -- АтрашкевичАндрей
----
-Выделение контура не является самой сложной задачей: для её решения достаточно закрасить те прямоугольники, в которых присутствуют составляющие части фигуры. Если выполнять заливку без учета свободного пространства внутри фигуры, то можно выполнить заливку внешнего пространства и инвертировать результат. Также внутри фигур могут быть свободные области. Например, внутри большой гайки мы можем поместить ещё одну маленькую. Выделение таких пустот, при данном методе представления, является не на столько сложной задачей, как в остальных случаях. Достаточно с помощью заливки отделить внешний контур от внутренних.
+Иногда внутри фигур могут быть свободные области. Например, внутри большой гайки мы можем поместить ещё одну маленькую. Задача отделения контуров решается с помощью развития описанного выше алгоритма заливки. Первым шагом необходимо внешний контур фигуры. Условимся считать, что больше второго уровня вложенности контуров не может быть. Тогда повторяем первый шаг и заполняем необходимую внутреннюю часть фигуры с учётом вложенных контуров. Далее удаляем внешнюю заливку.
В данном варианте представления фигур можно выполнять движение несколькими способами. Можно выполнять движение со сквозным проходом по всему контейнеру плоскости через фигуры, выполняя суммирование в каждой точке, а можно выполнять движение способом «тетриса». Регулировать соотношение скорость-качество можно с помощью изменения размеров прямоугольников, например взять не $$1 times 1$$, а $$10 times 10$$. Огромный плюс данного метода ‒ простота работы с данными. Для того, чтобы задать зазор между фигурами. Для этого достаточно обвести контур ещё несколько раз.
-
---Представление в виде полигона
-Растровое представление не является достаточно точным для представления фигур, альтернативой является представление фигур в виде полигонов. В таком представлении объем информации пропорционален числу вершин и не зависит от размера фигуры. Для растра проверка расположения будет $$o(n sup 2 )$$, а для полигонов уже $$o(e sup n )$$. Для того, чтобы проверить нет ли нигде пересечений нужно выполнить набор тестов:
- *проверить пересекаются ли описывающие прямоугольники фигур, если нет, то и фигуры не пересекаются, иначе перейти к следующему тесту;
- *для каждой пары рёбер проверить, пересечение описывающих прямоугольников;
- *проверить, пересекаются ли рёбра;
- *проверить, лежат ли какие-либо вершины одного полигона, внутри другого.
-[[cs627421.vk.me/v627421641/3fc69/owgnhO7e1Pk.jpg|Представление фигуры в виде полигона|350px]]
-
-В данном варианте представления также присутствует ряд проблем, которые необходимо решить:
- 1 Как определять пересечения между фигурами?
- 1 Как искать оптимальное расположение фигуры на плоскости?
-
-Можно определять пересечения через уравнение прямой с угловым коэффициентом, но это слишком сложно так, как имеет несколько специальных случаев. Лучше использовать для этого псевдоскалярное произведение отрезков, такой подход работает гораздо быстрее и не имеет специальных случаев. Для перемещения фигуры подходят только алгоритмы «тетрисного» движения. Применять «сквозное движение» мы не можем, так, как тогда придется постоянно проверять, не попала ли она внутрь другой.
-
-Алгоритмы с представлением фигур в виде полигонов хорошо подходят для прямоугольников и несложных многоугольников с числом вершин до сотни. Для более сложных сильно возрастает время вычисления пересечений.
-
-Проблема данного метода состоит в сложности обработки контура. Построить эквидистантный контур, чтобы задать зазор ‒ не такая уж легкая задача. Отделить внешний контур от внутренних тоже несколько сложнее, ведь контур может состоять из нескольких раздельных кривых, пусть и образующих в сумме одну замкнутую кривую.