Алгоритмы

  • 25 сент. 2011 г.
  • 2462 Слова
Югорский государственный университет
Институт прикладной математики, информатики и управления
Кафедра компьютерного моделирования и
информационных технологий

Курсовая работа по предмету
«Структуры и алгоритмы обработки данных»
на тему: Алгоритмическое решение задач

Выполнил студент группы 1170

Проверил преподаватель

«___» _______________ 2011 года

Оценка_______________________

Подпись ______________________

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

Входные данные
Представляют собой массив строк текстового файла data.txt. Первая строка - количество вершин, последующие строки - координаты вершин, в порядке обхода по часовой стрелке,записанные через пробел (x y). Количество вершин 3 < N < 50000. Размерность координат -12000 < x,y < 12000

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

Примеры
№ | data.txt | Диалоговое окно программы |
1 | 6-4 1-1 35 26 -11 -4-3 -2 | 44 |
2 | 5-3 21 43 12 -2-2 -3 | 26 |
3 | 73 45 36 -23 -3-2 -2-4 2-1 4 | 48 |Разбор и анализ алгоритмов

В ходе выполнения задания курсового проекта было разработано 3 разных алгоритма, выполняющих решение поставленной задачи. Каждый алгоритм имеет свои особенности в быстродействии и потребности в ресурсах системы. Алгоритмы были реализованы посредством программирования на языке C++

Алгоритм №1: Формула Пика
Если вершины многоугольника расположены в точках сцелочисленными координатами, то выполнено следующее равенство:
S = K + M/2 – 1
где S — площадь многоугольника
K — число целых точек, лежащих внутри многоугольника,
M — число целых точек, лежащих на границе многоугольника.
Зная координаты вершин многоугольника, мы можем подсчитать S и M, а значит можем найти K, то есть ответ к задаче, по формуле Пика. Чтобы найти площадь многоугольника, мыищем векторное произведение треугольников и суммируем результаты. Что касается нахождения числа M, то эта задача сводится к такой: зная координаты концов отрезка (целые числа), найти, сколько на нем целых точек. Ответом на последний вопрос будет НОД(Δx, Δy) + 1, где НОД(A,B) — наибольший общий делитель чисел A и B, а Δx и Δy — разности абсцисс и ординат концов отрезка соответственно. А тогда число M —просто сумма НОД(Δx, Δy) для всех сторон многоугольника.

Псевдокод:
Функция main:
Загрузка данных с файла
Расчет M (точки на сторонах)
Расчет S (площадь многоугольника)
K = S - M/2 + 1 //количество точек
Расчет M:
Цикл от 1 до n-1 (кол-во вершин многоугольника)
Разность абсцисс и ординат концов отрезка
Результат = сумма НОД разности абсцисс и ординат концов отрезка
Для 0 - ой иточки n производится единичный просчет
Расчет S:
Цикл от 1 до n-1
Результат = сумма векторных произведений
Единичный просчет для 0 - ой точки и точки n
Функция возвращает половину абсолютной величины (площадь)

Алгоритм №2 Триангуляция
Данный алгоритм осуществляет перебор точек в прямоугольнике, в который вписан многоугольник. Далее определяется принадлежность точки многоугольнику. Дляпринадлежности точки многоугольнику вершины последовательно нумеруются от 1 до n. Вершина с условным номером 1 соединяется отрезками со всеми другими вершинами. Осуществляется проверка принадлежности заданной точки хотя бы одному из этих треугольников. Заданная точка соединяется отрезками с вершинами треугольника. Если площадь исходного треугольника равна сумме площадей образовавшихся трёх треугольников, тосчитается, что точка принадлежит треугольнику.

1

S2
S1

S

S3

Псевдокод:
Функция main:
Расчет области перебираемых точек (определение maxx, minx, maxy, miny)
Цикл от minx+1 до maxx-1
Цикл от miny+1 до maxy-1
Если точка принадлежит многоугольнику, то увеличиваем значение счетчика
Функция Polygon (определение принадлежности точки)
Цикл от 0 до n-1...
tracking img