Расчёт вероятности ошибки линейных систем модуляции на основе диаграмм Вороного

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

Федеральное агентство связи

Федеральное государственное образовательное бюджетное учреждение

высшего профессионального образования

«Поволжский государственный университет телекоммуникаций и информатики»

Факультет Информационных систем и технологий

Направление (специальность) Программная инженерия

КафедраТеоретических основ радиотехники и связи

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

(БАКАЛАВРСКАЯ РАБОТА)

Расчёт вероятности ошибки линейных систем модуляции на основе диаграмм Вороного

Руководитель

доц. каф. ТОРС, доц., к.т.н.

Ю.В. Алышев

Разработал РПИС-31

П.П. Косяков

Самара 2017



Федеральное агентство связи

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования

«Поволжский государственный университет телекоммуникаций и информатики»

ЗАДАНИЕ

Студента

Косякова Павла Павловича

1 Тема ВКР

Расчёт вероятности ошибки линейных систем модуляции на основе диаграмм Вороного

Утверждена приказом по университету от 03.04.2017 № 74-2

2 Срок сдачи студентом законченной ВКР 13.04.17

3 Исходные данные и постановка задачи

1) Материалы исследования метода Форчуна

2) Модель расчёта вероятности ошибки линейных систем модуляции на основе диаграмм Вороного

3) Изучить модель метода Форчуна

4) Реализовать метод Форчуна в виде программы

5) Реализовать файловый интерфейс в консольной программе для метода

Метода Форчуна

6) Провести эксперимент замера скорости исполнения

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

4 Перечень подлежащих разработке в ВКР вопросов иликраткое содержание ВКР. Сроки исполнения 13.06.17

1) Изучение метода Форчуна построения диаграмм Вороного

2) Сравнение методов расчёта диаграмм Вороного

3) Реализация метода Форчуна в виде программы

4) Произведение контрольного расчёта для определённого вида модуляции

5) Сравнение результатов расчёта существующего решения и решения, основанного на диаграммах Вороного

5 Перечень графического материала. Сроки исполнения 13.06.17

1) Презентация по теме бакалаврской работы

6 Дата выдачи задания « 4 » апреля 2017 г.

Кафедра Теоретических основ радиотехники и связи

Утверждаю зав. каф. ТОРС, доц., д.т.н. 05.04.17 О.В. Горячкин

Руководитель доц. каф. ТОРС, доц., к.т.н. 05.04.17 Ю.В. Алышев

Задание принял к исполнению РПИС-31 05.04.17 П.П. Косяков



Федеральное агентство связи

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования

«Поволжский государственный университет телекоммуникаций и информатики»

ОТЗЫВ РУКОВОДИТЕЛЯ

Тип ВКР
Студента(ки)
Специальность/ направление
Тема ВКР
Руководитель
Ученая степень, звание
Место работы (должность)

АКТУАЛЬНОСТЬ ТЕМЫ

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

ОЦЕНКА СОДЕРЖАНИЯ РАБОТЫ

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

_________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

_________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

СТЕПЕНЬ ДОСТИЖЕНИЯ ЦЕЛИ И ПРАКТИЧЕСКАЯ ЗНАЧИМОСТЬ

(Полнота раскрытия исследуемой темы,практическая ценность и возможность внедрения)

__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

ЗАКЛЮЧЕНИЯ ПО ПРЕДСТАВЛЕННОЙ РАБОТЕ

(Степень самостоятельной работы студента; совокупная оценка труда студента и его квалификация)

_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Руководитель ВКР ________________ ________________ ____________________

Подпись Дата Инициалы Фамилия



Федеральное агентство связи

Федеральное государственное образовательное бюджетное учреждение

высшего профессионального образования

«Поволжский государственный университет телекоммуникаций и информатики»

ПОКАЗАТЕЛИ КАЧЕСТВА ВКР

По ВКР студента	Косякова Павла Павловича
На тему	Расчёт вероятности ошибки линейных систем модуляции
1 Работа выполнена :
- по теме, предложенной студентом
- по заявке предприятия
		наименование предприятия
- в области фундаментальных и поисковых научных исследований
		указать область исследований
2 Результаты ВКР:
- рекомендованы к опубликованию
		указать где
- рекомендованы к внедрению
		указать где
- внедрены
		акт внедрения
3 ВКР имеет практическую ценность
		в чем заключается практическая ценность
4 Использование ЭВМ при выполнении ВКР:
(ПО, компьютерное моделирование, компьютерная обработка данных и др.)
5. ВКР прошла проверку на объем заимствований



Студент	РПИС-31	14.06.17	П.П. Косяков
	Группа Подпись	Дата	Инициалы Фамилия
Руководитель ВКР	доц. каф. ТОРС, доц., к.т.н.	14.06.17	Ю.В. Алышев
	Должность Уч.степень, звание Подпись	Дата	Инициалы Фамилия

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Поволжский государственный университет телекоммуникаций и информатики»

РЕФЕРАТ

Название	Расчёт вероятности ошибки линейных систем модуляции на основе диаграмм Вороного
Автор	Косяков Павел Павлович
Научный руководитель	Алышев Юрий Витальевич
Ключевые слова	Плотность вероятности, вероятность ошибки, модуляций, диаграммы Вороного, алгоритм Форчуна
Дата публикации	2017
Библиографическое описание	Косяков, П.П. Расчёт вероятности ошибки линейных систем модуляции на основе диаграмм Вороного [текст]: бакалаврская работа / Косяков П.П. Поволжский Государственный университет телекоммуникаций и информатики. Факультет информационных систем и технологий (ФИСТ). Кафедра теоретических основ радиотехники и связи (ТОРС): науч. рук. Ю. В. Алышев - Самара. 2017. - 95 с.
Аннотация	В ВКР рассматривается универсальный метод расчёта вероятности ошибки линейных систем модуляции. Этот метод использует диаграммы Вороного и применим к любым видам модуляции. Прежде, универсального подхода к теоретическому расчёту не существовало. Основным аспектом ВКР являются алгоритмы вычисления диаграмм Вороного.

Руководитель ВКР		13.06.17	Ю.В. Алышев



Введение

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

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

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

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

С одной стороны, в плане вычислительной сложности, этот алгоритм работает на порядок быстрее простого алгоритма построения. Простой алгоритм обладает вычислительной сложностью , тогда как алгоритм Форчуна-. Т.е. вычислительная сложность этого алгоритма в nраз меньше, чем у простого алгоритма построения диаграмм Вороного.

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

Во-первых, связь триангуляции Делоне с диаграммами Вороного. Триангуляция Делоне - это разбиение на симплексы заданного множества точек Sна плоскости. Таким образом, в итоге триангуляции набор точек Sсоединяется некоторым количеством рёбер. Связь с диаграммой Вороного в том, что для любого набора точек S,рёбра триангуляции Делоне будут показывать, между какими точками будут проведены рёбра диаграммы Вороного.

Во-вторых, вычислительная сложность алгоритма «Разделяй и властвуй» для построения триангуляции Делоне - - такая же, как и у алгоритма Форчуна. Но при этом ясно, что на выходе в получается только триангуляция, и преобразование её в диаграмму Вороного потребует дополнительной вычислительной сложности, в худшем случае - .

Объектом исследования данной бакалаврской работы являются диаграммы Вороного и алгоритмы их построения.

Предметом исследования данной бакалаврской работы является алгоритм Форчуна построения диаграммы Вороного для некоторого набора точек на плоскости и его реализация на языке C#.

Целью данной бакалаврской работы является поиск оптимального алгоритма вычисления диаграмм Вороного. Для достижения указанной цели поставлены задачи:

изучить математическую модель алгоритма Форчуна;

исследовать существующие решения в сфере реализаций алгоритма Форчуна на различных языках программирования;

выявить возможности улучшения существующих реализаций алгоритма Форчуна;

реализовать алгоритм Форчуна в виде библиотеки классов для дальнейшего использования;

реализовать входной интерфейсный модуль для данной реализации алгоритма Форчуна;

реализовать выходной интерфейсный модуль для данной реализации алгоритма Форчуна;

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

провести контрольный расчёт вероятности ошибки с целью проверки применимости диаграмм Вороного к расчётам.

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

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

Введение данной бакалаврской работы раскрывает актуальность, определяет цель, задачи и методы исследования, раскрывает теоретическую и практическую значимость этой работы.

В первой главе данной бакалаврской работы описывается математическая модель алгоритма и всех важных для его реализации элементов.

Во второй главе описывается составленные к ПО требования, кратко описывается процесс проектирования необходимого ПО и предоставляются результаты проектирования ПО.

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

В четвёртой главе описываются результаты тестирования и контрольного расчёта вероятности ошибки.



1. Математическая теория

1.1 Расчёт вероятности ошибки на основе диаграмм Вороного

Для решения задачи расчёта вероятности ошибки до сих пор не найдено единого подхода, который стал бы универсальным для любого вида линейной модуляции. Метод расчёта, основанный на диаграммах Вороного является таким решением.

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

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

,

где - квадратурные компоненты низкочастотного эквивалента сигнала на передаче, соответствующего -й позиции.

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

Рис. 1.1 Представление области определения фигур, объём которых нужно найти

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

Рис. 1.2 Область, которую позволяет найти базовая функция, схематичное изображение



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

Рис. 1.3 Основание фигуры, показанной на рис. 1.1. Точка О - проекция вершины поверхности нормального распределения на плоскость диаграммы Вороного

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

где - функция вероятности ошибки.



Рис. 1.4 Вариант области для

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

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

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

1.2 Диаграмма Вороного

Диаграмма Вороного является разбиением множества точек S, элементы которого здесь и далее будут называться сайтами, в k-мерном пространстве, при котором каждая область этого разбиения состоит из множества точек, более близких к элементу множества Sвнутри области, чем к любому другому элементу множества S[1].

[2]

где - произвольная точка на плоскости;

- область диаграммы Вороного, в которую входит ;

- функция определения расстояния между точками и ;

- количество точек в множестве .

Рис. 1.5Демонстрация принадлежности области сайта

d(p,S_1) <d(p,S_2) - p ?V_1

В рамках данной бакалаврской работы, для решения поставленной задачи, kбыло определено равным 2, т.к. точки необходимо располагать в плоскости. Здесь и далее, если не оговорено иного, все математические доказательства будут приводиться для случаев двумерного пространства, или плоскости.

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

Вторая группа - это точки, лежащие на рёбрах разбиения Вороного, т.е. равноудалённые от двух и более сайтов.

где - произвольная точка на плоскости;

- область диаграммы Вороного, в которую входит ;

- функция определения расстояния между точками и ;

- количество точек в множестве .

Рис. 1.6 Демонстрация точки на ребре Вороного

d(p,S_1 )=d(p,S_2 )

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

где - подмножествосайтов S, к которым относится вершина Вороного p;

- произвольная точка на плоскости;

- функция определения расстояния между точками и ;

- количество точек в множестве .

Рис. 1.7Демонстрация вершины Вороного



d(p,S_1 )=d(p,S_2 )=d(p,S_3 )

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

1.2.1 Связь с пересечением полуплоскостей

Возьмём две точки на плоскости: и . Проведём серединный перпендикуляр к отрезку - вся плоскость будет разделена на две полуплоскости; полуплоскость, содержащую в себе pобозначим как , другую полуплоскость - . Заметим, что для точки rвыполняется условие ,тогда и только тогда, когда . Отсюда можно сделать вывод, что к области Вороного сайта будут относится всеточки, лежащие в его полуплоскости, относительно другого сайта , и что область Вороного сайта будет образована пересечением полуплоскостей относительно всех остальных сайтов диаграммы [3].

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



1.3 Триангуляция Делоне

Рис. 1.8 Триангуляция Делонедля множества точек S

Триангуляция Делоне - это разбиение набора точек Sна плоскости на симплексы, вершинами которых являются точки набора S. Конечно же, триангуляция Делона возможна и для -мерного пространства, но для данной бакалаврской работы необходимо рассматривать его только для плоскости. Для заданного множества , это такое разбиение на треугольники (так как для плоскости симплекс есть треугольник), при котором для каждого треугольника все точки множества будут лежать за пределами окружности, описанной вокруг треугольника, кроме трёх точек, являющихся его вершинами[4]. Так как окружность описана вокруг треугольника, довольно просто понять, что его вершины будут лежать на окружности.

1.3.1 Связь триангуляции Делоне с диаграммами Вороного

Важным свойством диаграмм Вороного является её двойственность триангуляции Делоне [4]. Если соединить отрезками сайты диаграммы, которые соприкасаются хотя бы углами, то полученный набор отрезков будет представлять из себя триангуляцию Делоне. При этом совершенно верно можно отметить, что возможна и обратная операция.

Рис. 1.9 Триангуляция Делоне (а) и диаграмма Вороного (б) для одного множества точек S (чёрные точки)

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

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



1.4 Простой алгоритм построения диаграммы Вороного

Простой алгоритм построения основан на связи диаграмм Вороного с полуплоскостями (1.4) [1]. Для каждого сайта множества изначальных точек будут вычисляться полуплоскостей за , где - количество сайтов в .Этот алгоритм можно записать так:

Пусть - множество сайтов диаграммы;

Для каждого элемента :

Пусть нынешний элемент - ;

Для каждого элемента S, который не является :

Пусть новый элемент - ;

Пересечь область с полуплоскостью ;

Если :

Закончить цикл;

Добавить область к диаграмме;

Если :

Закончить цикл;

При этом необходимо заметить, что сам алгоритм является подходом «в лоб», и никоим образом не оптимизирован с точки зрения алгоритма.

1.5 Алгоритм Форчуна построения диаграммы Вороного

Алгоритм Форчуна основан на алгоритмической парадигме «заметающей прямой», которая используется для решения разнообразных проблем в Евклидовом пространстве. Наиболее известный метод, основанный на этой парадигме - это алгоритм заметающей прямой, для нахождения пересечений набора отрезков на плоскости или в пространстве. Собственно, сам алгоритм Форчуна является модификацией этого алгоритма, только направлен на построение диаграмм Вороного [5].

Суть алгоритма заключается в двух его основных элементах: заметающей прямой и береговой линии.

Заметающая прямая - это воображаемая линия, которая продвигается через всю плоскость определения диаграммы, останавливаясь в определённых точках. Заметающая прямая делит всю область определения диаграммы на две части: с одной стороны находятся береговая линия и часть плоскости, на которой может быть известна диаграмма Вороного, с другой стороны могут находятся только необработанные сайты диаграммы[5].

Береговая линия - это сложная структура, состоящая из некоторого количества веток парабол, каждая из которых однозначно относится к одному или другому сайту диаграммы. Она, в свою очередь, разделяет плоскость определения на область, в которой известна диаграмма Вороного, независимо от точек, находящихся с другой стороны береговой линии, и область необработанных точек [6].

Береговая линия использует математическое определение параболы - «геометрическое множество точек, равноудалённых от некоторой прямой, называемой директрисой параболы, и некоторой точки, называемой фокусом параболы (1.5) [7]. Здесь можно найти тесную связь между определением параболы и определением областей диаграммы Вороного (1.1). В алгоритме, для каждой параболы из береговой линии сайт, к которому она относится, является фокусом, а заметающая прямая - директрисой. Таким образом, береговая линия позволяет правильно очертить области диаграммы Вороного, используя математическое определения парабол [8].

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

Рис. 1.10 Парабола и её определение

где - произвольная точка;

-парабола;

- фокус параболы ;

-директриса параболы;

-функция нахождения расстояния.

Отсюда следует, что если точки разбиения являются точками пересечения парабол, то расстояния от этих точек до фокусов соответствующих парабол одинаково, а значит точки разбиения всегда лежат на рёбрах диаграммы Вороного, согласно (1.2).

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

Структура двоичного дерева такова: в узлах этого дерева находятся точки разбиения и связанные с ними рёбра Вороного, а в листьях - параболы. Причём обратный обход (инфиксный, in--ordered) этого дерева даст линейный список элементов береговой линии в порядке их следования от одного крайнего элемента, к другому. Взаимное расположение парабол определяет то, как они будут добавлены в двоичное дерево. Если сайт (фокус) параболы лежит слева от той параболы, на которую она падает на береговую линию, то она будет «слева» и в двоичном дереве. Это верно, если она лежит справа.

Рис. 1.11 Добавление парабол к береговой линии, до добавления (а) и после него (б)

Список событий - это очередь с приоритетом [6], который содержит в себе некоторое количество событий, которые нужно обработать алгоритму до полного завершения. События в этом списке в первую очередь упорядочены по градиенту движения заметающей прямой, обычно по вектору направления одной из координатных осей плоскости. Во вторую очередь, события сортируются по их типу. Типов событий два: событие добавления параболы (появления сайта) и событие удаления параболы.

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

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

При событии удаления параболы, заметающая прямая проходит через определённую точку, в которой в береговой линии одна из парабол вырождается в точку. В этой точке сходятся две точки разбиения и параболу нужно удалять из береговой линии. Понятно, что в этой точке пересекаются три параболы, а значит расстояние от этой точки до по крайней мере трёх сайтов - одинаковое. Отсюда следует, что согласно (1.3) в этой точке находится вершина Вороного.

События удаления параболы заранее неизвестны, и добавляются в очередь по ходу действия алгоритма, причём они могут быть добавлены и в середину очереди, и в её начало [6].

1.6 Сравнение простого алгоритма и алгоритма Форчуна

Во-первых, алгоритмы отличаются математической сложностью. У простого алгоритма она равна , а у алгоритма Форчуна -, что на порядок меньше[9].

В простом алгоритме нужно обойти все nсайтов, для каждого из которых нужно обойти других сайтов, для пересечения полуплоскостей. У Форчуна же следует только «обход» n сайтов, с поиском и добавлением в двоичное дерево сложностью .

Во-вторых, простой алгоритм породит много лишних данных, которые будут дублировать друг друга, в отличие от алгоритма Форчуна. Так как для визуального и математического построения диаграммы Вороного важны рёбра этой диаграммы, то с их точки зрения и следует рассматривать алгоритмы.

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

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

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



2. Проектирование алгоритма Форчуна

2.1 Постановка задачи

Для написания ПО необходимо правильно понимать три вещи:

входные данные ПО;

выходные данные ПО;

детали реализации ПО.

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

входные данные ПО:

набор точек;

выходные данные ПО:

диаграмма Вороного для входного набора точек;

детали реализации:

алгоритм Форчуна.

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

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

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

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

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

Также, для удобства определения, каждое ребро должно иметь ссылки на сайты, которое оно разделяет. Это сделает структуру данных диаграммы Вороного более информативной и удобно - подобные ссылки могу понадобиться в дальнейшей обработке.

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

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

Список событий нужно реализовать как приоритетную очередь, с возможностью вставки элементов - событий.

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

На основе этого, список становится длиннее:

входные данные ПО:

массив точек;

каждая точка имеет две координаты - численные значения;

выходные данные ПО:

диаграмма Вороного для входного набора точек;

диаграмма хранит множество сайтов;

диаграмма хранит множество рёбер Вороного;

каждое ребро задано двумя точками;

точки ребра либо являются опорными, либо вершинами Вороного;

ребро хранит ссылки на два сайта, которые разделяет;

ребро хранит переменную для каждой определяющей точки - бесконечно ли с этой стороны ребро, или нет;

детали реализации:

алгоритм Форчуна;

обработка массива рёбер;

приоритетная очередь для очереди событий;

сортированный список для береговой линии.

2.2 Обзор существующих решений

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

2.2.1 Реализация Стивена Форчуна

Данная реализация алгоритма Форчуна была написана самим учёным Стивеном Форчуном[5]. Эта программа была написана в 1986 году, в то время когда Стивен опубликовал работу, в которой он и описал алгоритм построения диаграмм Вороного [10].

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

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

2.2.2 BOOST.POLYGON

Данная библиотека написана на языке программирования C++ и реализует набор алгоритмов для обработки и построения диаграмм Вороного.

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

Как аргумент против использования данной библиотеки в научной работе - необходимость изучения и работы с языком С++ для тестирования работоспособности библиотеки и математической правильности результата.



2.3 Выбор языка и среды программирования

Данный выбор был сделан довольно просто - на основе личного опыта написания программ был выбран язык C#, так как он наиболее хорошо мной изучен, по сравнению с прочими кандидатами:С++ иJava.

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

Javaв свою очередь чрезвычайно похож на C#: синтаксис обоих языков похож, и есть возможность даже написать комплексную программу, которая будет компилироваться на обоих языках. Большим плюсом языка Javaявляется его мультиплатформенность - скомпилированный код будет работать на большинстве операционных систем: Windows, Linux, MaxOS. При этом, язык проигрывает C# в многообразии: в Javaневозможно создать собственный индексатор - возможность обращения к классу по индексу того, или иного вида; в Javaнет возможности перегружать операторы, то есть вы не сможете в простом виде сложить два вектора, используя символ плюса - для любых подобных операций потребуется написание и вызов отдельного метода. В C# же такие возможности присутствуют, добавляя удобства при написании и поддержке кода.

Выбор среды разработки был также основан на опыте нескольких лет разработки. В качестве оной был выбран MicrosoftVisualStudio 2015 Enterprise - данная среда предоставляет удобный редактор кода, с поддержкой технологии автодополнения Intellisence, и, что самое главное, поддержку технологии модульного тестирования кода UnitTestingFramework. Последняя является довольно мощным инструментом для проверки и тестирования работоспособности кода - в случае разработки программы математических преобразований, существует возможность заранее подготовить набор тестов и входных значений для проверки. Также модульное тестирование позволит быстро проверять код на правильность в процессе рефакторинга.

2.4 Проектирование системы классов и модели данных

Проектирование программы является важным шагом при создании большинства программных продуктов - этот процесс составления плана для выполнения в дальнейшем.

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

2.4.1 UMLдиаграмма классов

Следует также описать детали реализации каждого из классов, известные на момент проектирования.

Основной класс(класс Fortune) должен содержать структуры данных для береговой линии, очереди событий и диаграммы Вороного. Класс расчёта должен иметь метод расчёта диаграммы Вороного из некоторого множества сайтом.

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

Парабола (класс Parabola) должна содержать в себе ссылку на сайт, к которому она принадлежит, опционально сквозную ссылку на фокус - саму точку сайта.Также парабола должна реализовывать метод получения координаты для любой координаты , которые вместе являются точкой на параболе, метод нахождения точек пересечения с другой параболой. Парабола должна задаваться общим уравнением вида и содержать переменные трёх коэффициентов . Также парабола должна реализовывать метод пересчёта коэффициентов из известной точки фокуса и директрисы. Входными данные для создания объекта параболы - это значение директрисы и фокуса. Следовательно, парабола должна ещё иметь метод получения директрисы.

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

Сайт (класс Site) должен содержать точку, определяющую сайт, и уникальный идентификатор - простое целое число.

Точка (класс Point) должна содержать две координаты - дробные числа двойной точности. Также точка должна реализовывать метод нахождения расстояния до любой другой точки.

Очередь событий (класс EventQueue) должны быть приоритетнойочередью и содержать список событий. Приоритетом событий в первую очередь будет точка возникновения события, затем - тип события, то есть класс. Очередь должна иметь метод добавления события в очередь по приоритету, метод изъятия верхнего события из очереди, метод получения верхнего события из очереди без его удаления и методы по удалению событий из очереди, так как алгоритм предусматривает удаление некоторых событий прямо из очереди.

Так как в очереди будет содержаться два типа событий, следует иметь абстрактный класс, который эти два типа и будет наследовать - класс FortuneEvent. Он должен реализовывать точку возникновения события.

Событие добавления параболы (класс ArcAppearEvent) в береговую линию должно содержать ссылку на сайт, который встречает заметающая прямая и арка которого добавляется в береговую линию.

Событие удаления параболы (класс ArcRemoveEvent) из береговой линии должно содержать ссылку на саму арку для удаления, вершину Вороного, которая была найдена для этого события, и радиус круга для вершины Вороного - расстояние между точкой возникновения события и вершиной Вороного.

Диаграмма Вороного (класс VoronoiDiagram) должна содержать список сайтов и список рёбер диаграммы.

Исходя из этого, можно составить следующую UMLдиаграмму классов [10][11]:

Рис 2.1UMLдиаграмма классов пакета Voronoi



Рис 2.2UML диаграмма классов пакета Events, вложенного в пакет Voronoi

2.4.2 Блок-схема алгоритма Форчуна

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

Алгоритм можно разбить на несколько частей:

Главная функция обработки;

Обработка события добавления параболы;

Обработка события удаления параболы;

Проверка и поиск события удаления параболы.

Далее приведены блок-схемы для каждой из данных частей алгоритма [12][13]:



Рис 2.3Блок-схема основного цикла алгоритма Форчуна

2.5 Тестирование алгоритма Форчуна

В конечном итоге будет необходимо провести два вида тестирования финального ПО: правильность и скорость исполнения. Для тестирования данного ПО необходимо будет использовать две стадии тестирования, интеграционное и модульное. Для удобства тестирования, модульное тестирование совмещается с тестированием на правильность и только с ним, тогда как общая скорость работы ПО будет тестироваться при интеграции вычислительной части с интерфейсной [14][15].



Рис 2.4,5 Блок-схема функции добавления параболы в береговую линию



Рис 2.6 Блок-схема функции проверки событий круга для параболы

2.5.1 Модульное тестирование

Модульное тестирование основного программного модуля на правильность предполагается проводить аналитическим путём, то есть путём анализа выходных данных алгоритма, так как для разработки полноценного средства для автоматизированного тестирования программы на различных множествах сайтов потребуется реализация другого алгоритма в той же среде программирования - правильность результата будет проверена через сравнение его с результатом для тех же исходных данных, но полученных другим путём.

В данном случае, для тестирования правильности работы программы будет использоваться ПО AutodeskAutoCADLT 2018для построения выходной диаграммы и её визуального изучения [15].

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

В случае тестов для квадратной сетки, рассматривается длина стороны квадрата предполагаемой сетки. В качестве тестовых случаев, были выбраны значения в 3, 10 и 25 элементов на стороне квадрата, и, соответственно, 9, 100 и 625 элементов (сайтов). Также, значение имеет вариация расстояния между узлами сетки. Так как метод требует точных вычислений, возможно составление диапазона значений, в которых он будет работать безотказно, а также диапазона, где могут случаться ошибки округления, вследствие дискретности арифметического процессора.

В случае тестов для точек на окружности, были выбраны варианты с 4 точками, лежащими в вершинах вписанного в окружность квадрата, и с 16 точками, лежащими в известных точках единичной окружности: и так далее, до значения , не включая его. Нужно учесть, что в данном случае не гарантируется появление одной единственной вершины Вороного в центре окружности - исследование существующих моделей алгоритма Форчуна показало, что дискретность современных процессоров в таких случаях может не позволить произвести математически верное построение. Координаты точки на единичной окружности, выражаемой как . Число - иррациональное [16], его нельзя представить как конечную десятичную дробь.

2.5.2 Интеграционное тестирование

Интеграционное тестирование уже будет включать в себя как тестирование на правильность, так и тестирование на скорость исполнения.

Тестирование на правильность предполагается совершать по результатам модульного тестирования, сверяя данные в выходном файле с данными на построенных в AutodeskAutoCADLT 2018 диаграммах. Интерфейсный модуль только изменит вид выходной информации, но не её содержание.

Отчасти, интеграционное тестирование основано на результатах модульного тестирования и диапазонах значений количества сайтов и расстояния между ними, так как заранее известна дискретность арифметического процессора. Данная дискретность может вызывать ошибки округления чисел, когда фактическое количество знаков после запятой у некоего числа, полученного в процессе расчётов, больше, чем может иметь переменная.

2.6 Интерфейс для включения в программный комплекс по автоматизации поиска способа модуляции

В дальнейшем программный модуль реализации алгоритма Форчуна будет включён, поэтому возникает вопрос о реализации интерфейса. Известны следующие детали:

Ввод производится через файл.

Вывод производится через файл.

Оба файла являются текстовыми.

После изучения файлов, предоставленными Алышевым Ю. В., можно сделать набор выводов.

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

Входной файл является текстовым.

Входной файл имеет несколько строк.

На каждой строке записаны координаты отдельного сайта.

Рис 2.7 Пример входного файла

Каждая координата представлена двумя целыми или дробными числами.

Выходной файл имеет более сложную структуру. Его можно разделить на два блока записей.

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

Второй блок - списки вершин Вороного и опорных точек для каждого из сайтов. Этот блок разделяется на под-блоки, структура каждого из которых одинакова и количество которых равно количеству сайтов диаграммы. Под-блоки состоят из числа вершин и опорных точек, задающих эту область диаграммы. На первой строчке находится число, модуль которого равен количеству точек, относящихся к одной из областей. Знак этого числа зависит от того, является ли область ограниченным многоугольником, или нет. Далее следует список точек: две координаты точки записываются каждая на отдельной строке. Также, точки идут в определённом порядке - следуя рёбрам области диаграммы и не повторяясь. То есть, для закрытой области, обход может начинаться с любой вершины области, тогда как для открытой области есть только два варианта - одна из опорных точек рёбер-лучей. Следовательно, требования к выходному файлу следующие:

Выходной файл является текстовым.

Выходной файл состоит из нескольких строк.

Выходной файл можно разделить на два блока.

Первый блок содержит число количества сайтов на первой строке.

На остальных строках содержатся координаты каждого сайта в соответствующем количестве.

Каждая координата описывается двумя дробными или целыми числами.

Второй блок содержит информацию об областях диаграммы.

Второй блок состоит из набора под-блоков, каждый из которых имеет соответствие с одним из сайтов.

Под-блок содержит число, по модулю равное количеству последующих точек. Знак числа определяет факт открытости области.

На следующих строках содержатся координаты вершин области в соответствующем количестве.

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

Если область открытая, первой точкой может быть только опорная точка одного из рёбер-лучей.

...