Алгоритм простого геометрического поиска

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ПОСТАНОВКА ЗАДАЧИ

ГЛАВА 2. ПОСТРОЕНИЕ ХАРАКТЕРИСТИЧЕСКОЙ ОБЛАСТИ

2.1 Алгоритм построения характеристической области в случае выпуклых исходных объектов

2.2 Алгоритм построения характеристической области в случае односвязности исходных объектов

2.3 Алгоритм построения характеристической области в случае многосвязности исходных объектов

2.4 Вычислительная сложность алгоритмов

ГЛАВА 3. ПРОСТОЙ ГЕОМЕТРИЧЕСКИЙ ПОИСК

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

ВВЕДЕНИЕ

алгоритм простой геометрический поиск

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

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

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

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

ГЛАВА 1. ПОСТАНОВКА ЗАДАЧИ

Целью работы является разработка и реализация эффективного алгоритма для решения задачи взаимного размещения плоских полигональных объектов.

Задачи:

Разработать и программно реализовать алгоритм построения характеристической области.

Реализовать алгоритм простого геометрического поиска.

Рассмотрим задачу взаимного размещения многоугольников на плоскости в следующей постановке:

Даны две многосвязные области с кусочно-линейной границей, удовлетворяющие условиям:

1. границы каждой области не самопересекаются;

2. одна из областей А - неподвижна, а другая область - В может перемещаться с помощью параллельного переноса (Рис. 1).

Рис. 1. Пример задачи взаимного размещения многоугольников.

Зафиксируем некоторую точку О многоугольника В. Рассмотрим геометрическое место точек, которое описывает данная вершина O при всех положениях подвижного многоугольника, в которых он находится внутри неподвижного. Граница этой области Х описывается точкой О при скольжении области В изнутри по границе области А. Полученная фигура также будет являться многоугольником, возможно, многосвязным, назовем его характеристическим. Выделенная точка принадлежит соответствующей ей характеристической области X тогда и только тогда, когда весь подвижный многоугольник B лежит внутри неподвижного A. Если происходит касание, то точка лежит на границе.

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

Подвижная область B не может перемещаться внутри области A хотя в одном из двух направлений. В этом случае P принадлежит границе области B.

Область B может перемещаться по двум направлениям (налево и направо). В этом случае можно переместить область B по обоим направлениям вплоть до касания с областью A (это справедливо для простых многоугольников). Ясно, что точка P лежит внутри отрезка, принадлежащего характеристической области.

Таким образом, эта задача сводится к задаче простого геометрического поиска на плоскости. Для многоугольника строятся специальные структуры данных, с использованием которых вычислительная сложность проверки, является ли некоторая точка для многоугольника внутренней, составляет O(logN), где N - количество его вершин.

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

Результатом работы алгоритма является искомая характеристическая область.

ГЛАВА 2. ПОСТРОЕНИЕ ХАРАКТЕРИСТИЧЕСКОЙ ОБЛАСТИ

2.1 Алгоритм построения характеристической области в случае выпуклых исходных объектов

Выбирается угол подвижного многоугольника.

Ищется сторона неподвижного, по которой угол подвижного (j) может скользить. Если сторона, по которой может скользить угол, найдена, то переходим на шаг 3, иначе - выбираем следующий угол (j+1) подвижного, повторяем шаг 2.

Строим вектор движения v1, полученный параллельным переносом стороны неподвижного многоугольника на вектор FjO.

Выбирается следующая сторона неподвижного многоугольника. Если данный угол не может скользить по ней, то выбираем следующий угол, повторяем шаг 4. Если угол может скользить по стороне, то строится вектор движения vi, переходим на шаг 5. Если все стороны неподвижного многоугольника и углы подвижного рассмотрены и не найдено замкнутого контура, то подвижный многоугольник не может лежать внутри неподвижного, алгоритм завершается.

Ищется вектор vj, j < i (j = i-1, i-2, ..), который пересекается с vi, удаляются все векторы vj+1, .. , vi-1, так как они не будут входить в контур. Если же вектор vj не найден, тогда оставляется только текущий вектор vi, переходим на шаг 1.

Если вектор vi пересекается с v1, то получен замкнутый контур, являющийся характеристической областью, то алгоритм завершается, иначе переходим на шаг 3.

Все вершины неподвижного и подвижного многоугольников осматриваются только 1 раз, следовательно, вычислительная сложность - O(N+M), где N - количество вершин неподвижного, M - количество вершин подвижного многоугольника.

2.2 Алгоритм построения характеристической области в случае односвязности исходных объектов

Все вычисления производятся в системе координат неподвижного многоугольника A. В данной системе зададим положение подвижного многоугольника B, просто взяв все координаты из его собственной системы координат. Обозначим точки неподвижного многоугольника A: E0, E1, …, EN и точки подвижного B: F0, F1, …, FM.

Для всех сторон каждого многоугольника находим нормали

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)

Проверка возможностей скольжения.

Для каждой стороны неподвижного многоугольника находим углы подвижного, по которым она может скользить. (условие скольжения: углы между внутренней нормалью стороны неподвижного многоугольника и сторонами угла подвижного - острые, т.е. когда

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).

Рис. 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).

Находим точки пересечения всех полученных векторов, которые упорядочиваются по удаленности от начала вектора, обозначим множество таких точек для v через

a(v) = {av0, av1, …, avs}.

Удаляем из рассмотрения векторы, у которых нет точек пересечения или всего одна, а также векторы, лежащие снаружи неподвижного многоугольника.

Составление контуров. Выбираем вектор vєV и точку avlєa(v), начинаем обход, добавляем следующую точку пересечения для данного вектора avl+1 в новый контур, переходим на следующий вектор, имеющий наименьший угол с данным, также добавляем следующую точку. Если она принадлежит первоначальному вектору v, то формируем этот контур. Если такой точки нет, то контур получается не замкнутым. Повторяем процесс для другого вектора vєV и (или) точки avlєa(v), пока не будут «осмотрены» все векторы из V и все точки пересечения для этих векторов.

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

После окончания этого процесса получаем искомую характеристическую область, состоящую из замкнутых контуров (многоугольников).

Рис. 3. Пример, показывающий необходимость проверки контуров, в которых нормали направлены внутрь.

2.3 Алгоритм построения характеристической области в случае многосвязности исходных объектов

Для всех сторон внешних контуров каждой области находим нормали (для неподвижной - внутренние, для подвижной - внешние), а также для всех внутренних контуров («дырок») (для неподвижной области - внешние, для подвижной - внутренние).

Проверка возможностей скольжения.

Для каждой стороны внешнего контура неподвижного многоугольника находим углы подвижного, по которым она может скользить. (условие скольжения: углы между внутренней нормалью стороны неподвижного многоугольника и сторонами угла подвижного - острые). Строим вектор движения для выделенной точки.

Для каждой стороны внешнего контура подвижного многоугольника находим углы неподвижного, по которым она может скользить. (условие скольжения: углы между внешней нормалью стороны подвижного многоугольника и сторонами угла неподвижного - острые). Строим вектор движения для выделенной точки.

Для каждой стороны внутренних контуров («дырок») неподвижного многоугольника находим углы подвижного, по которым она может скользить. (условие скольжения: углы между внешней нормалью стороны «дырки» и сторонами угла подвижного - острые). Строим вектор движения для выделенной точки.

Для каждой стороны подвижного многоугольника находим углы «дырок» неподвижного, по которым она может скользить. (условие скольжения: углы между внешней нормалью стороны подвижного многоугольника и сторонами угла «дырки» неподвижного - острые). Строим вектор движения для выделенной точки.

Для каждой стороны «дырки» подвижного многоугольника находим углы неподвижного, по которым она может скользить. (условие скольжения: углы между внутренней нормалью стороны «дырки» и сторонами угла неподвижного - острые). Строим вектор движения для выделенной точки.

Для каждой стороны неподвижного многоугольника находим углы «дырок» подвижного, по которым она может скользить. (условие скольжения: углы между внутренней нормалью стороны неподвижного многоугольника и сторонами угла «дырки» подвижного - острые). Строим вектор движения для выделенной точки.

Для каждой стороны «дырки» подвижного многоугольника находим углы «дырок» неподвижного, по которым она может скользить. (условие скольжения: углы между внутренней нормалью стороны «дырки» подвижного и сторонами угла «дырки» неподвижного - острые). Строим вектор движения для выделенной точки.

Для каждой стороны «дырки» неподвижного многоугольника находим углы «дырок» подвижного, по которым она может скользить. (условие скольжения: углы между внешней нормалью стороны «дырки» неподвижного многоугольника и сторонами угла «дырки» подвижного - острые). Строим вектор движения для выделенной точки.

Находим точки пересечения всех полученных векторов, которые упорядочиваются по удаленности от начала вектора.

Удаляем из рассмотрения векторы, у которых нет точек пересечения или всего одна, а также векторы, лежащие снаружи неподвижного многоугольника.

Составление контуров.

Из полученных контуров добавляются в характеристическую область те, в которых нормали к сторонам направлены внутрь контура, а также контуры, лежащие внутри этих, с направлением нормалей наружу, они будут являться «дырками».

Получаем искомую характеристическую область, состоящую из многосвязных областей.

Рис. 4. Пример характеристической области для задачи взаимного размещения многосвязных областей.

2.4 Вычислительная сложность алгоритмов

Пусть N - кол-во вершин неподвижного многоугольника, M - кол-во вершин подвижного. При выполнении шага 2, т.е. проверки возможности скольжений, например, в 2.1 для каждой стороны неподвижного поиск углов неподвижного - О(M), следовательно, для всех сторон - О(N*M), всего получаем О(N*M) векторов. На шаге 3, находим пересечения полученных векторов - О(N2*M2). Составление контуров происходит линейным образом, т.е. точки пересечений каждого вектора просматриваются только один раз. Таким образом, общая вычислительная сложность алгоритма - О(N2*M2).

ГЛАВА 3. ПРОСТОЙ ГЕОМЕТРИЧЕСКИЙ ПОИСК

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

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

Задача определения принадлежности точки многоугольника решается в два этапа, причем, на каждом шаге используется дихотомия. Пусть дана точка (x; y). На первом этапе ищется полоса, в которой лежит точка. На втором - трапеция в этой полосе, в которую попадает точка. Получив область, мы определяем, лежат ли ее внутренние точки внутри многоугольника. Благодаря дихотомии вычислительная сложность этапа проверки составляет O(log N), где N - количество вершин многоугольника.

ЗАКЛЮЧЕНИЕ

Под руководством научного руководителя Александра Ивановича Куликова разработан и реализован алгоритм для решения задачи взаимного размещения многоугольников для последующего его использования в исследованиях, проводящихся в вычислительной геометрии. Этот метод может использоваться для конструктивного описания взаимного расположения сложных полигональных объектов.

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

Результаты работы были представлены на XLIX Международной научной студенческой конференции.

ЛИТЕРАТУРА

Куликов А.И. Некоторые задачи вычислительной геометрии. Изогеометрическое сглаживание и геометрический поиск. //Труды конференции, GraphiCon2005, Novosibirsk, June 20 - June 24. - P.382-385.

Препарата Ф., Шеймос М. Вычислительная геометрия: введение - М: Мир, 1989. - 480 с.

Рвачев В.Л. Теория R-функций и некоторые ее приложения - Киев: Наукова Думка, 1982.

Стоян Ю.Г. Размещение геометрических объектов - Киев: Наукова Думка, 1975. - 249 с.

Размещено на Allbest.ru