Главная
База знаний "Allbest"
Программирование, компьютеры и кибернетика
Разработка программного средства для построения характеристической области для задачи взаимного размещения двух многоугольников
Разработка программного средства для построения характеристической области для задачи взаимного размещения двух многоугольников
Размещение одного многоугольника внутри другого: разработка программного средства для построения характеристической области задачи. Алгоритм построения в случае выпуклых исходных объектов, их односвязности и многосвязности. Входные и выходные данные.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 08.03.2012 |
| Размер файла | 423,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
- Введение
- 1. Постановка задачи
- 1.1 Исследовательская часть
- 2. Построение характеристической области
- 2.1 Алгоритм построения характеристической области в случае выпуклых исходных объектов
- 2.2 Алгоритм построения характеристической области в случае односвязности исходных объектов
- 2.3 Алгоритм построения характеристической области в случае многосвязности исходных объектов
- 2.4 Вычислительная сложность алгоритмов
- 3. Простой геометрический поиск
- 4. Данные для работы программного средства
- 4.1 Входные данные
- 4.2 Выходные данные
- Заключение
- Список использованных источников
Введение
Тема проекта: разработка программного средства для построения характеристической области для задачи взаимного размещения двух многоугольников.
Среди существующего многообразия прикладных задач важное место занимают задачи размещения, суть которых в размещении без взаимных пересечений набора геометрических объектов в определенной области. В двухмерном случае данные задачи являются задачами раскроя и могут применяться в швейной, обувной, метало - и деревообрабатывающей промышленностях. В трехмерном случае задачи размещения могут быть использованы для моделирования упаковки грузов в наземный, воздушный и морской виды транспорта, а так же при компоновке оборудования в машиностроении и строительстве.
В математической постановке задача оптимального размещения состоит в размещении подвижных геометрических объектов внутри неподвижных, при условии минимизации определенного функционала, значение которого определяется положением подвижных объектов. К задачам подобного типа относится, например, наиболее плотное заполнение заданной области геометрическими объектами.
Задача размещения одного многоугольника внутри другого сводится к задаче геометрического поиска для специально построенной характеристической области и заданной точки подвижного многоугольника. При этом, используя заранее рассчитанные структуры данных, можно определить, находится ли один многоугольник внутри другого за логарифмическое время. Этот подход можно использовать для конструктивного описания взаимного расположения сложных полигональных объектов.
1. Постановка задачи
Целью данной работы является разработка и программная реализация алгоритма для решения задачи взаимного размещения плоских полигональных объектов.
Задачи:
• Разработать и программно реализовать алгоритм построения характеристической области.
• Реализовать алгоритм простого геометрического поиска.
Рассмотрим задачу взаимного размещения многоугольников на
плоскости в следующей постановке:
Даны две многосвязные области с кусочно-линейной границей, удовлетворяющие условиям:
• границы каждой области не самопересекаются;
• одна из областей (А) - неподвижна, а другая область (В) - может перемещаться с помощью параллельного переноса.
Рис.1. Пример задачи взаимного размещения многоугольников.
Зафиксируем некоторую точку О многоугольника В. Рассмотрим геометрическое место точек, которое описывает данная вершина O при всех положениях подвижного многоугольника, в которых он находится внутри неподвижного. Граница этой области Х описывается точкой О при скольжении области В изнутри по границе области А. Полученная фигура также будет являться многоугольником, возможно, многосвязным, назовем его характеристическим. Выделенная точка принадлежит соответствующей ей характеристической области X тогда и только тогда, когда весь подвижный многоугольник B лежит внутри неподвижного A. Если происходит касание, то точка лежит на границе.
Докажем следующее утверждение: пусть точка P, принадлежащая подвижному многоугольнику, лежит вне неподвижного, тогда точка P, не принадлежит своей характеристической области. Так как все характеристические области лежат полностью внутри неподвижного многоугольника либо касаются некоторых его сторон, то точка P не может принадлежать своей характеристической области, так как лежит вне неподвижного многоугольника. Обратно. Пусть точка P принадлежит подвижному многоугольнику. Рассмотрим горизонтальное перемещение подвижной области внутри неподвижной. Возможны два случая.
1. Подвижная область B не может перемещаться внутри области A хотя в одном из двух направлений. В этом случае P принадлежит границе области B.
2. Область B может перемещаться по двум направлениям (налево и направо). В этом случае можно переместить область B по обоим направлениям вплоть до касания с областью A (это справедливо для простых многоугольников). Ясно, что точка P лежит внутри отрезка, принадлежащего характеристической области.
Таким образом, эта задача сводится к задаче простого геометрического поиска на плоскости. Для многоугольника строятся специальные структуры данных, с использованием которых вычислительная сложность проверки, является ли некоторая точка для многоугольника внутренней, составляет O (logN), где N - количество его вершин.
1.1 Исследовательская часть
Исследовательская часть заключается в изучении алгоритмов, предложенных моим руководителем. А также в нахождении наиболее оптимальных решений и реализации их. В результате исследовательской части было выявлено, что при нахождении, наиболее оптимального решении возникают различного рода проблемы. При полном обходе образуется несколько замкнутых областей. Замкнутые области, в которых нормали направлены внутрь, назовем регулярными областями. Чтобы определить, является ли регулярная область надо поместить подвижный многоугольник в одну из граничных точек контура и проверить пересечения сторон многоугольников, если пересечения есть, то область не будет являться характеристической.
Рис.2. Пример, показывающий необходимость проверки регулярных областей.
Характеристические области не могут накладываться друг на друга и находиться одна в другой, но могут соприкасаться друг с другом, т.е. иметь одну или несколько общих граничных точек.
2. Построение характеристической области
2.1 Алгоритм построения характеристической области в случае выпуклых исходных объектов
1. Выбирается угол подвижного многоугольника.
2. Ищется сторона неподвижного, по которой угол подвижного (j) может скользить. Если сторона, по которой может скользить угол, найдена, то переходим на шаг 3, иначе - выбираем следующий угол (j+1) подвижного, повторяем шаг 2.
3. Строим вектор движения v1, полученный параллельным переносом стороны неподвижного многоугольника на вектор FjO.
4. Выбирается следующая сторона неподвижного многоугольника. Если данный угол не может скользить по ней, то выбираем следующий угол, повторяем шаг 4. Если угол может скользить по стороне, то строится вектор движения vi, переходим на шаг 5. Если все стороны неподвижного многоугольника и углы подвижного рассмотрены и не найдено замкнутого контура, то подвижный многоугольник не может лежать внутри неподвижного, алгоритм завершается.
5. Ищется вектор vj, j < i (j = i-1, i-2,.), который пересекается с vi, удаляются все векторы vj+1,., vi-1, так как они не будут входить в контур. Если же вектор vj не найден, тогда оставляется только текущий вектор vi, переходим на шаг 1.
6. Если вектор vi пересекается с v1, то получен замкнутый контур, являющийся характеристической областью, то алгоритм завершается, иначе переходим на шаг 3.
Все вершины неподвижного и подвижного многоугольников осматриваются только 1 раз, следовательно, вычислительная сложность - O (N+M), где N - количество вершин неподвижного, M - количество вершин подвижного многоугольника.
2.2 Алгоритм построения характеристической области в случае односвязности исходных объектов
Все вычисления производятся в системе координат неподвижного многоугольника A. В данной системе зададим положение подвижного многоугольника B, просто взяв все координаты из его собственной системы координат. Обозначим точки неподвижного многоугольника A: E0, E1, …, EN и точки подвижного B: F0, F1, …, FM.
1. Для всех сторон каждого многоугольника находим нормали n= (nx, ny) (для неподвижного - внутренние, для подвижного - внешние). Для вершин Ei ni= (Ei,y-Ei+1,y, Ei+1,x-Ei,x), для Fj nj= (Fj+1,y-Fj,y, Fj,x-Fj+1,x).
2. Проверка возможностей скольжения.
2.1. Для каждой стороны неподвижного многоугольника находим углы подвижного, по которым она может скользить. (условие скольжения: углы между внутренней нормалью стороны неподвижного многоугольника и сторонами угла подвижного - острые, т.е. когда nx (Ei+1,x-Ei,x) + ny (Ei+1,y-Ei,y) > 0)). Строим вектор движения для выделенной точки O - v= (v1, v2), v1= (v1,x, v1,y), v2= (v2,x, v2,y), полученный параллельным переносом стороны EiEi+1 на вектор FjO для каждой вершины Fj, способной скользить по нему. При этом v1= (Ei,x+ (FjO) x, Ei,y+ (FjO) y), v2= (Ei+1,x+ (FjO) x, Ei+1,y+ (FjO) y).
Рис.3. Необходимое условие скольжения
2.2. Для каждой стороны подвижного многоугольника находим углы неподвижного, по которым она может скользить. (условие скольжения: углы между внешней нормалью стороны подвижного многоугольника и сторонами угла неподвижного - острые, т.е. когда nx (Fi+1,x-Fi,x) + ny (Fi+1,y-Fi,y) > 0)). Строим вектор движения для выделенной точки v, который будет направлен в противоположную сторону, т.е. повернут на 180о. При этом v1= (Ei,x+ (FjO) x, Ei,y+ (FjO) y), v2= (Fj+1,x-Fj,x+Ei,x+ (FjO) x, Fj+1,y-Fj,y +Ei,y+ (FjO) y).
3. Находим точки пересечения всех полученных векторов, которые упорядочиваются по удаленности от начала вектора, обозначим множество таких точек для v через a (v) = {av0, av1, …, avs}.
4. Удаляем из рассмотрения векторы, у которых нет точек пересечения или всего одна, а также векторы, лежащие снаружи неподвижного многоугольника.
5. Составление контуров. Выбираем вектор vєV и точку avlєa (v), начинаем обход, добавляем следующую точку пересечения для данного вектора avl+1 в новый контур, переходим на следующий вектор, имеющий наименьший угол с данным, также добавляем следующую точку. Если она принадлежит первоначальному вектору v, то формируем этот контур. Если такой точки нет, то контур получается не замкнутым. Повторяем процесс для другого вектора vєV и (или) точки avlєa (v), пока не будут "осмотрены" все векторы из V и все точки пересечения для этих векторов.
6. Из полученных контуров добавляются в характеристическую область те, в которых нормали к сторонам направлены внутрь контура. Также для определения принадлежности контура характеристической области надо поместить подвижный многоугольник в одну из граничных точек контура и проверить пересечения сторон многоугольников, если пересечения есть, то контур не будет принадлежать характеристической области.
После окончания этого процесса получаем искомую характеристическую область, состоящую из замкнутых контуров (многоугольников).
2.3 Алгоритм построения характеристической области в случае многосвязности исходных объектов
1. Для всех сторон внешних контуров каждой области находим нормали (для неподвижной - внутренние, для подвижной - внешние), а также для всех внутренних контуров ("дырок") (для неподвижной области - внешние, для подвижной - внутренние).
2. Проверка возможностей скольжения.
2.1. Для каждой стороны внешнего контура неподвижного многоугольника находим углы подвижного, по которым она может скользить (условие скольжения: углы между внутренней нормалью стороны неподвижного многоугольника и сторонами угла подвижного - острые). Строим вектор движения для выделенной точки.
2.2. Для каждой стороны внешнего контура подвижного многоугольника находим углы неподвижного, по которым она может скользить (условие скольжения: углы между внешней нормалью стороны подвижного многоугольника и сторонами угла неподвижного - острые). Строим вектор движения для выделенной точки.
2.3. Для каждой стороны внутренних контуров ("дырок") неподвижного многоугольника находим углы подвижного, по которым она может скользить. (условие скольжения: углы между внешней нормалью стороны "дырки" и сторонами угла подвижного - острые).
Строим вектор движения для выделенной точки.
2.4. Для каждой стороны подвижного многоугольника находим углы "дырок" неподвижного, по которым она может скользить. (условие скольжения: углы между внешней нормалью стороны подвижного многоугольника и сторонами угла "дырки" неподвижного - острые).
Строим вектор движения для выделенной точки.
2.5. Для каждой стороны "дырки" подвижного многоугольника находим углы неподвижного, по которым она может скользить (условие скольжения: углы между внутренней нормалью стороны "дырки" и сторонами угла неподвижного - острые).
Строим вектор движения для выделенной точки.
2.6. Для каждой стороны неподвижного многоугольника находим углы "дырок" подвижного, по которым она может скользить. (условие скольжения: углы между внутренней нормалью стороны неподвижного многоугольника и сторонами угла "дырки" подвижного - острые).
Строим вектор движения для выделенной точки.
2.7. Для каждой стороны "дырки" подвижного многоугольника находим углы "дырок" неподвижного, по которым она может скользить. (условие скольжения: углы между внутренней нормалью стороны "дырки" подвижного и сторонами угла "дырки" неподвижного - острые).
Строим вектор движения для выделенной точки.
2.8. Для каждой стороны "дырки" неподвижного многоугольника находим углы "дырок" подвижного, по которым она может скользить. (условие скольжения: углы между внешней нормалью стороны "дырки" неподвижного многоугольника и сторонами угла "дырки" подвижного - острые).
Строим вектор движения для выделенной точки.
3. Находим точки пересечения всех полученных векторов, которые упорядочиваются по удаленности от начала вектора.
4. Удаляем из рассмотрения векторы, у которых нет точек пересечения или всего одна, а также векторы, лежащие снаружи неподвижного многоугольника.
5. Составление контуров.
6. Из полученных контуров добавляются в характеристическую область те, в которых нормали к сторонам направлены внутрь контура, а также контуры, лежащие внутри этих, с направлением нормалей наружу, они будут являться "дырками".
алгоритм характеристическая область многоугольник
7. Получаем искомую характеристическую область, состоящую из многосвязных областей.
Рис.4. Пример характеристической области для задачи взаимного размещения многосвязных областей.
2.4 Вычислительная сложность алгоритмов
Пусть N - кол-во вершин неподвижного многоугольника, M - кол-во вершин подвижного. При выполнении шага 2, т.е. проверки возможности скольжений, например, в 2.1 для каждой стороны неподвижного поиск углов неподвижного - О (M), следовательно, для всех сторон - О (NM), всего получаем О (NM) векторов. На шаге 3, находим пересечения полученных векторов - О (N2M2). Составление контуров происходит линейным образом, т.е. точки пересечений каждого вектора просматриваются только один раз. Таким образом, общая вычислительная сложность алгоритма - О (N2M2).
3. Простой геометрический поиск
Рассмотрим следующую задачу. Имеется некоторый многоугольник. Для заданной точки нужно определить, лежит ли она внутри данного многоугольника. Считаем, что решение данной задачи должно быть ориентировано на массовые запросы, то есть проверка будет осуществляться для большого количества точек. Для этого нужно предварительно построить специальную информационную структуру и использовать ее для оптимизации проверок.
Рассмотрим этап построения структуры.
Рис.5
Проведем через вершины многоугольника прямые, лежащие в плоскости XY и параллельные оси X. Получаем разбиение плоскости XY на полосы, строго внутри которых не происходит пересечения отрезков сторон и не содержится вершин многоугольника. Таким образом, части отрезков, лежащие внутри полосы, можно упорядочить, получив упорядоченную последовательность трапеций. Отметим, что строго внутри трапеций нет вершин многоугольника. Причем, все внутренние точки такой области целиком либо принадлежат многоугольнику, либо нет. Для каждой трапеции запомним принадлежность ее внутренних точек многоугольнику. Получаем структуру для геометрического поиска.
Задача определения принадлежности точки многоугольника решается в два этапа, причем, на каждом шаге используется дихотомия. Пусть дана точка (x; y). На первом этапе ищется полоса, в которой лежит точка. На втором - трапеция в этой полосе, в которую попадает точка. Получи область, мы определяем, лежат ли ее внутренние точки внутри многоугольника. Благодаря дихотомии вычислительная сложность этапа проверки составляет O (log N), где N - количество вершин многоугольника.
Вычислительная сложность предобработки - N2, сложность проверки, используя полученную структуру - логарифм от T, где T - количество вершин характеристической области.
4. Данные для работы программного средства
4.1 Входные данные
В задачи на построение характеристической области, входные данные задаются пользователем в отдельном текстовом файле в виде числовых значений, вершины многоугольников, отсортированные против часовой стрелки. Одна из вершин подвижного многоугольника B, O.
· E. txt: это файл со значениями, которые необходимы для отрисовки неподвижного многоугольника (все координаты вершин)
· F. txt: это файл со значениями, которые необходимы для отрисовки подвижного многоугольника (все координаты вершин)
4.2 Выходные данные
Координаты вершин характеристических областей, отсортированные против часовой стрелки. Руководство пользователя:
При запуске программы, для работы с многоугольниками пользователь использует клавиатуру. Ниже описаны клавиши и функции, которые они выполняют: "1"-рисуются векторы движений для выделенной точки, "2"-находятся все точки пересечения векторов, "3"-удаляются векторы, которые не могут входить в контуры (кол-во точек пересечения 0 или 1), "4"-формирование контуров, "5"-проверка регулярных областей
Содержимое файлов:
Пример содержимого файла F. txt (координаты подвижного многоугольника)
1) 3
85 80
35 90
10 30
первая строка - кол - во вершин, далее через пробел все координаты.
Пример содержимого файла F. txt (координаты неподвижного многоугольника)
1) 14 1
4
550 425
400 450
первая строка - кол - во, вершин и через пробел - кол-во дырок, 0 или 1, т.е.14 - кол-во вершин у внешней компоненты, 1 - есть внутренняя
компонента; 4-кол-во вершин у внутреннего многоугольника.
Также, пользователь может пользоваться мышью: левой кнопкой мыши можно приближать область (в то числе отображать зеркально), средней кнопкой - перемещать подвижный многоугольник и правая кнопка мыши - убрать масштабирование, т.е. восстанавливать исходный масштаб.
Тестирование
1.1. Построение характеристической области при помощи двух простых многоугольников.
1) Задаются координаты вершин многоугольников. Происходит отрисовка самих многоугольников:
черный, неподвижный многоугольник;
зеленый, подвижный многоугольник;
красным кружком обозначена вершина подвижного
Рис 6. Изображение двух многоугольников
2) После запуска программы, автоматически происходит обход и рисуется характеристическая область:
красным цветом выделено начало вектора;
синим цветом, выделен конец вектора;
Рис 7. Изображение полученной области
1.2. Построение характеристической области при помощи двухсвязного неподвижного многоугольника и простого подвижного
1) Задаются координаты вершин многоугольников и вершины внутренней "дырки". Происходит отрисовка самих многоугольников.
черный, неподвижный многоугольник;
зеленый, подвижный многоугольник;
Рис 8. Изображение двух многоугольников, один из которых с "дыркой"
1) После запуска программы, автоматически происходит обход и рисуется характеристическая область
красным цветом выделено начало вектора;
синим цветом, выделен конец вектора;
Рис 9. Изображение полученной области
Заключение
Под руководством научного Александра Ивановича Куликова разработан и реализован алгоритм для решения задачи взаимного размещения многоугольников для последующего его использования в исследованиях, проводящихся в вычислительной геометрии. Этот метод может использоваться для конструктивного описания взаимного расположения сложных полигональных объектов.
В соответствии с поставленной задачей, была проделана следующая работа:
1. Изучена предметная область
2. Изучены выбранные среды программирования
Как видно из работы программного средства, работа выполнена в полном объеме.
Данный алгоритм можно использовать при разработке алгоритма для 3D случая.
Ограничения в работе алгоритма: необходимо исключать вырожденные случаи, пересекающиеся стороны, и очень малые размеры отдельных сторон многоугольников, чтобы исключить возникновение вырожденных случаев из-за погрешности в вычислениях.
Получены следующие результаты:
1. Разработан и реализован алгоритм для построения характеристического многоугольника.
2. Реализован алгоритм простого геометрического поиска.
Результаты работы были представлены на XLIX Международной научной студенческой конференции.
Данное программное средство предназначено для пользователей, желающих наглядно посмотреть и проследить за геометрическим процессом построения характеристической областью.
Список использованных источников
1. Куликов А.И. Некоторые задачи вычислительной геометрии. Изогеометрическое сглаживание и геометрический поиск. // Труды конференции, GraphiCon2005, Novosibirsk, June 20 - June 24. - P.382-385.
2. Ласло М. Вычислительная геометрия и компьютерная графика на C++. - М.: БИНОМ, 1997 [стр.150]
3. Препарата Ф., Шеймос М. Вычислительная геометрия: введение - М: Мир, 1989.
4. Стоян Ю.Г. Размещение геометрических объектов - Киев: Наукова Думка 1975.
Размещено на Allbest.ru
Подобные документы
Алгоритм построения характеристического многогранника для случая выпуклых исходных объектов. Оценка вычислительной сложности. Построение характеристического многогранника, при условии, что исходные объекты необязательно выпуклые. Система плагинов.
курсовая работа [1,4 M], добавлен 07.03.2012Программные продукты для решения задачи построения оптимального маршрута. Выбор аппаратных и программных средств для построения маршрута обхода пациентов. Математическая модель муравьиного алгоритма: состав, структура, тестирование, отладка, реализация.
дипломная работа [1,9 M], добавлен 03.12.2017Разработка стратегии и выбор способа автоматизации задачи снабжения для предприятия. Построение функциональной модели бизнес-процессов предметной области. Создание программного средства "1С: Конфигурация ОМТС" для оптимального решения задач снабжения.
дипломная работа [7,2 M], добавлен 12.04.2012Обзор средств построения систем электронной коммерции, их преимущества и основные направления развития. Особенности корпоративных серверов Microsoft. Разработка программного механизма для ведения статистики по действиям пользователя в разных модулях.
отчет по практике [1,6 M], добавлен 26.06.2014Разработка программного комплекса, нацеленного на предоставление информации о комплектации персонального компьютера. Входные и выходные данные системы. Описание предметной области. Краткая информация о языке Clips. Проектирование экспертной системы.
курсовая работа [36,0 K], добавлен 23.06.2011Разработка программного средства для поиска альтернативных решений многокритериальных задач. Проектирование программного средства с помощью объектно-ориентированного подхода. Пример листинга программного кода. Особенности работы программы на примере.
контрольная работа [346,5 K], добавлен 11.06.2011Назначение и цели создания системы учета по подключению Интернет-сети. Анализ методов решения задачи, входные и выходные данные. Разработка информационной модели, алгоритма задачи и интерфейса пользователя. Этапы тестирования программного продукта.
дипломная работа [1,8 M], добавлен 08.05.2009Анализ проектирования баз данных и освещение методов построения форм и отчетов на примере построения программы ведения электронной документации учебного заведения. Разработка и построение инфологической модели по предметной области "Университет".
курсовая работа [6,3 M], добавлен 03.11.2014Математические методы решения задачи расчета химического равновесия. Структура программного средства. Схема отношений базы данных химических элементов и соединений. Программная реализация Генетического Алгоритма для расчета химического равновесия.
дипломная работа [6,6 M], добавлен 07.07.2012Математическая постановка задачи. Обоснование выбора средств разработки. Входные и выходные данные работы программы. Решение задачи теста для написания и отладки программы. Описание программных модулей. Разработка алгоритма, анализ полученных результатов.
курсовая работа [2,2 M], добавлен 13.12.2015
