Выпуклая оболочка набора точек Выпуклая оболочка набора точек Определение, применение, свойства, методы построения

Структура лекции Определение Определение Области применения Области применения Свойства выпуклых оболочек Свойства выпуклых оболочек Методы построения выпуклых оболочек Методы построения выпуклых оболочек Методы грубой силы Методы грубой силы Методы пошагового ввода Методы пошагового ввода Методы пошаговой выборки Методы пошаговой выборки Методы декомпозиции Методы декомпозиции Методы сканирования Методы сканирования

Литература по теме Препарата Ф., Шеймос М. «Вычислительная геометрия» (главы 3, 4). Препарата Ф., Шеймос М. «Вычислительная геометрия» (главы 3, 4). Майкл Ласло «ВГ и компьютерная графика на С++» (п.5.3, п.6.3, п.7.2, п.8.5). Майкл Ласло «ВГ и компьютерная графика на С++» (п.5.3, п.6.3, п.7.2, п.8.5).

Выпуклая оболочка набора точек S (CH(S)) – выпуклый полигон минимальной площади, содержащий все точки набора S. – выпуклый полигон минимальной площади, содержащий все точки набора S. т.е. это 1. Полигон 2. Выпуклый 3. Содержащий все точки набора S 4. Имеющий минимальную площадь из всех возможных вариантов Определение выпуклой оболочки Набор точек S Выпуклая оболочка CH(S)

Структура данных «Полигон» Полигон (многоугольник) - это геометрическая фигура, определяется как замкнутая ломаная. (wiki) Представляется упорядоченным набором вершин полигона. //Полигон через дин. массив вершин TPolygon2D = array of TPoint2D; //Полигон через список вершин //Вершина полигона TPolygonVertex2D = packed record Point: TPoint2D; //точка вершины Point: TPoint2D; //точка вершины //указатели на следующую и предыдущую вершину //указатели на следующую и предыдущую вершину Next, Prev: ^TPolygonVertex2D; Next, Prev: ^TPolygonVertex2D;end; //Полигон – указатель на вершину TPolygon2D = ^TPolygonVertex2D;

Применение выпуклых оболочек В распознавании образов для формирования кластеров в пространстве признаков. В распознавании образов для формирования кластеров в пространстве признаков. Для повышения эффективности поиска геометрического объекта содержащего точку. Для повышения эффективности поиска геометрического объекта содержащего точку. Оптимальная компоновка частей при раскрое материала Оптимальная компоновка частей при раскрое материала В моделировании движения (чтобы выпуклая оболочка движущегося объекта не задевала предметы). В моделировании движения (чтобы выпуклая оболочка движущегося объекта не задевала предметы). и много где еще… и много где еще…

Свойства выпуклой оболочки 1. Точки набора S по отношению к выпуклой оболочке CH(S) делятся на внутренние и крайние. В некоторых задачах крайние точки также делятся на выступающие и невыступающие. 2. Хорда – отрезок, соединяющий любую пару точек набора S. Любая хорда, лежит внутри выпуклой оболочки CH(S). Ребра выпуклой оболочки тоже являются хордами.

Свойства выпуклой оболочки 3. Прямая, проходящая через любое ребро выпуклой оболочки CH(S) отделяет все точки набора точек S от внешней полуплоскости. (Все точки набора S лежат по одну сторону от ребра выпуклой оболочки CH(S)) 4. Точка является внутренней точкой выпуклой оболочки CH(S) набора точек S, если она лежит в некотором треугольнике, вершинами которого являются точки набора S.

Методы построения выпуклых оболочек Методы грубой силы Методы грубой силы Исключение внутренних точек через треугольники Исключение внутренних точек через треугольники Распознавание ребер оболочки Распознавание ребер оболочки Методы пошагового ввода Методы пошагового ввода Инкрементальный алгоритм Инкрементальный алгоритм Методы пошаговой выборки Методы пошаговой выборки Метод заворачивания подарка (метод Джарвиса) Метод заворачивания подарка (метод Джарвиса) Методы декомпозиции Методы декомпозиции Разделяй и властвуй Разделяй и властвуй Методы сканирования Методы сканирования Прямолинейное сканирование Прямолинейное сканирование Полярное сканирование (метод Грэхема) Полярное сканирование (метод Грэхема)

Методы грубой силы Исключение внутренних точек через треугольники Основан на 4-м свойстве, интерпретируемом как признак внутренних точек. A1 Метод грубой силы через треугольники 1. Цикл для всех точек набора S. - O(n) 2. Для каждой точки p i перебор всех треугольников на множестве точек S. - O(n 3 ) 2. Для каждой точки p i перебор всех треугольников на множестве точек S. - O(n 3 ) 3. Для треугольника t j проверить принадлежность точки p i треугольнику t j - O(c) 3. Для треугольника t j проверить принадлежность точки p i треугольнику t j - O(c) 4. Если точка p i принадлежит треугольнику t j, то исключить p i из набора S. - O(c) 4. Если точка p i принадлежит треугольнику t j, то исключить p i из набора S. - O(c) 5. Упорядочить оставшиеся точки по полярному углу - O(nlogn) Вычислительная сложность:

Методы грубой силы Распознавание ребер оболочки Основан на 3-м свойстве, интерпретируемом как признак ребер оболочки. Все точки набора S лежат по одну сторону от ребра выпуклой оболочкиCH(S) A2 Метод грубой силы через ребра 1. Цикл для всех пар точек набора S. - O(n 2 ) 2. Для каждой пары точки p i p j перебор всех точек набора S. - O(n) 2. Для каждой пары точки p i p j перебор всех точек набора S. - O(n) 3. Для каждой точки p k определить с какой стороны она лежит от прямой p i p j - O(c) 3. Для каждой точки p k определить с какой стороны она лежит от прямой p i p j - O(c) 4. Если все точки p k лежат с одной стороны, то отрезок p i p j - ребро CH(S) - O(c) 4. Если все точки p k лежат с одной стороны, то отрезок p i p j - ребро CH(S) - O(c) 5. Упорядочить найденные ребра по точкам сочленения - O(h 2 ) (h-кол-во ребер CH(S)) Вычислительная сложность: T A2 (n) = O(n 2 (nc+c) + h 2 ) = O(n 3 )

Методы пошагового ввода Инкрементальный алгоритм A3 Инкрементальный алгоритм («Ввод оболочки») 1. Цикл для каждой точки p i набора точек S. - O(n) 2. Классификация текущей точки p i относительно текущей оболочки CH(S). -O(n) 2. Классификация текущей точки p i относительно текущей оболочки CH(S). -O(n) 3. Если точка p i снаружи, то - O(c) 3. Если точка p i снаружи, то - O(c) 4. Найти опорные точки R и L касательных прямых от p i к текущей оболочке CH(S). - O(n) 4. Найти опорные точки R и L касательных прямых от p i к текущей оболочке CH(S). - O(n) 5. Исключить из CH(S) ближнюю цепочку точек L - … - R. - O(n) 5. Исключить из CH(S) ближнюю цепочку точек L - … - R. - O(n) 6. Вставить точку p i в цепочку L - p i - R. - O(с) 6. Вставить точку p i в цепочку L - p i - R. - O(с) Вычислительная сложность: T A3 (n) = O(n(n+c+n+n+c)) = O(n 2 )

Методы пошаговой выборки Метод заворачивания подарка (Джарвиса) Основан на 3-м свойстве, интерпретируемом как признак ребра оболочки. А4 Метод Джарвиса («Метод заворачивания подарка») 1. Найти экстремальную точку q набора точек S. - O(n) 2. Найти точку p 1 c минимальным углом min1 поворота к оси OX. - O(n) 3. Цикл пока не придем в исходную точку (p i q). - O(h) (где h-число точек в CH(S)) 4. Перейти на новую точку p i. - O(c) 4. Перейти на новую точку p i. - O(c) 5. Найти точку p i+1 с минимальным углом minI поворота относительно предыдущего ребра p i-1 p i. - O(n) 5. Найти точку p i+1 с минимальным углом minI поворота относительно предыдущего ребра p i-1 p i. - O(n) Вычислительная сложность метода T A4 (n) = O(n + n + h(c + n)) = O(hn) Наихудший случай h = n (все точки на границе оболочки) T A4 (n) = O(n 2 ) Наилучший случай h

Методы декомпозиции «Разделяй и властвуй» A5 Метод «Разделяй и властвуй» 0. Если точек в наборе S не более 3 шт, то CH(S) = S, - O(b) иначе 1. Разбиение набора точек S на 2 примерно равных подмножества S1 и S2. - O(c) 1. Разбиение набора точек S на 2 примерно равных подмножества S1 и S2. - O(c) 2. Нахождение выпуклой оболочки для наборов S1 и S2, т.е. CH(S1) и CH(S2). - O(T A5 (n/2) + T A5 (n/2)) 2. Нахождение выпуклой оболочки для наборов S1 и S2, т.е. CH(S1) и CH(S2). - O(T A5 (n/2) + T A5 (n/2)) 3. Объединение двух полученных оболочек точек CH(S1) и CH(S2) в одну CH(S). - O(n) 3. Объединение двух полученных оболочек точек CH(S1) и CH(S2) в одну CH(S). - O(n) Вычислительная сложность: T A5 (n) = O(nlog n)

Методы сканирования Общие принципы «Сканирующая линия» - воображаемая прямая линия, которая в каждый момент сканирования делит набор точек на 3 части: «Спящие точки» – еще не обработанные точки (справа от сканирующей линии). «Спящие точки» – еще не обработанные точки (справа от сканирующей линии). «Активные точки» – обрабатываемые в данный момент (на сканирующей линии). «Активные точки» – обрабатываемые в данный момент (на сканирующей линии). «Мертвые точки» – уже обработанные точки (слева от сканирующей линии). «Мертвые точки» – уже обработанные точки (слева от сканирующей линии). Весь набор точек, упорядоченных по координате x – перечень точек-событий. «Структура сканирующей линии» – результат решения задачи для текущего набора уже обработанных («мертвых») точек. Сканирование - перемещение сканирующей линии по точкам-событиям и включение активных точек в текущее решение задачи.

Методы сканирования Прямолинейное сканирование A6 Метод сканирования 1. Создание перечня точек-событий S (сортировка точек по координате x ). - O(nlogn) 2. Цикл сканирования по всем точкам-событиям S. - O(n) 3. Для активной точки p i поиск верхней опорной точки H начиная с p i-1. - O(u) 4. Поиск нижней опорной точки L начиная с p i-1. - O(v) 5. Удаление цепочки точек от нижней L до верхней H. - O(u+v) 6. Вставка звена L -p i - H. - O(c) Вычислительная сложность T A6 (n) = O(nlogn+n(u+v+(u+v)+c))= = O(nlog n) Достоинства метода: + легко обобщается на трехмерный случай; + наглядность и прост для понимания.

Методы сканирования Полярное сканирование (метод Грэхема) А7 Метод Грэхема 1. Найти экстремальную точку q набора точек S - O(n) 2. Отсортировать все точки набора S по возрастанию полярного угла точек, используя точку q. - O(n logn) 3. Организовать двунаправленный кольцевой список на упорядоченном наборе точек. - O(n) 4. Обход Грэхема - обход всех точек по созданному списку, начиная с точки q: - O(n) 5. Если в текущей точке p i поворот налево, то переход к следующей точке. - O(c) 6. Если в текущей точке p i поворот направо, то 7. Исключить точку p i из списка. -O(c) 8. Возвращение к предыдущей точке p i-1. -O(c) Вычислительная сложность алгоритма: T A7 (n) = O(n + nlog n + n + n(c + c + c))= = O(nlog n)

Характеристики методов построения выпуклых оболочек Время в среднем Время в худшем Сложность реализации Методы грубой силы Методы грубой силы Через треугольники Через треугольники Через ребра Через ребра O(n 4 ) O(n 3 ) O(n 4 ) O(n 3 ) 43 Методы пошагового ввода Методы пошагового ввода Инкрементальный алгоритм Инкрементальный алгоритм O(n 2 ) 3 Методы пошаговой выборки Методы пошаговой выборки Метод Джарвиса Метод ДжарвисаO(h*n) O(n 2 ) 1 Методы декомпозиции Методы декомпозиции Разделяй и властвуй Разделяй и властвуй Быстрый алгоритм :( Быстрый алгоритм :(O(n*logn) O(n*logn) O(n*logn) O(n 2 ) 52 Методы сканирования Методы сканирования Прямолинейное сканирование Прямолинейное сканирование Метод Грэхема Метод ГрэхемаO(n*logn)O(n*logn)O(n*logn)O(n*logn)23

О чем это мы? О выпуклых оболочках! Определение Определение Области применения Области применения Свойства выпуклых оболочек Свойства выпуклых оболочек Методы построения выпуклых оболочек Методы построения выпуклых оболочек Методы грубой силы Методы грубой силы Методы пошагового ввода Методы пошагового ввода Методы пошаговой выборки Методы пошаговой выборки Методы декомпозиции Методы декомпозиции Методы сканирования Методы сканирования

Литература по теме Препарата Ф., Шеймос М. «Вычислительная геометрия» (главы 3, 4). Препарата Ф., Шеймос М. «Вычислительная геометрия» (главы 3, 4). Майкл Ласло «ВГ и компьютерная графика на С++» (п.5.3, п.6.3, п.7.2, п.8.5). Майкл Ласло «ВГ и компьютерная графика на С++» (п.5.3, п.6.3, п.7.2, п.8.5).

Спасибо за внимание!!