Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости

Аннотация

Тема данной курсовой работы – " Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости". Для сравнения взяты четыре алгоритма: обход методом Грэхема, быстрый метод, метод “разделяй и властвуй” и динамический метод. Задача этой работы – раскрыть эти алгоритмы и провести исследования эффективности их.
Программная часть для курсовой работы выполнена на Borland Delphi 4.

Оглавление

Аннотация 2

Введение 4

Предварительная разработка алгоритма построения выпуклой оболочки 7

Метод обхода Грэхема 9

Быстрые методы построения выпуклой оболочки. 11

Алгоритмы типа “разделяй и властвуй”. 12

Динамические алгоритмы построения выпуклой оболочки 14

Сравнительный анализ алгоритмов построения выпуклой оболочки 17

Выводы 20

Заключение 21

Приложение Unit1.pas 22

Литература 34

Введение

Множество различных задач вычислительной геометрии связано с построением выпуклой оболочки. В настоящий момент эта задача хорошо исследована и имеет широкое применение в распознавании образов[i], обработке изображений[ii], а так же в задачах в задаче раскроя и компоновки материала[iii].
Само понятие выпуклой оболочки является довольно простым и интуитивно понятным. Если представить резиновый шнур, натянутый на множество точек, то это и будет выпуклая оболочка для данного множества точек. Но, не смотря на свою простоту, оно не конструктивно, поэтому далее будут рассмотрены способы построения эффективных алгоритмов для построения выпуклой оболочки.
Так как алгоритмы для решения нашей задачи, как правило, являются подзадачами других, более сложных задач, то интерес представляют только алгоритмы имеющие сложность O(N log N).
Само понятие выпуклой оболочки является довольно простым и интуитивно понятным. Если представить резиновый шнур, натянутый на множество точек, то это и будет выпуклая оболочка для данного множества точек. Но, не смотря на свою простоту, оно не конструктивно, поэтому далее будут рассмотрены способы построения эффективных алгоритмов для построения выпуклой оболочки.
Так как алгоритмы для решения нашей задачи, как правило, являются подзадачами других, более сложных задач, то интерес представляют только алгоритмы имеющие сложность O(N log N).
Для начала, несколько определений:

Определение 1. Область D принадлежащая пространству E2, будет называться выпуклой, если для любой пары точек q1 и q2 из D отрезок q1q2 целиком принадлежит D.

Определение 2. Выпуклой оболочкой множества точек S, принадлежащих пространству E2, называется граница наименьшей выпуклой области в E2, которая охватывает S.

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

Определение 3. Полиэдральным множеством или политопом называется пересечение конечного множества замкнутых полупространств.

Следующая теорема характеризует выпуклые оболочки в нужном нам плане.

Теорема 1[iv]. Выпуклая оболочка конечного множества точек в Ed является выпуклым политопом. Наоборот, каждый выпуклый политоп является выпуклой оболочкой конечного множества точек.

Прежде чем переходить к описанию алгоритмов следует произвести постановку задач и определить нижние оценки для решения их. Так как алгоритмы имеют дело с границей выпуклой оболочки множества L conv(L), то введем для нее обозначение CH(L) и будем ее также называть выпуклой оболочкой.
Сформулируем две основные задачи:

Поделитесь этой записью или добавьте в закладки