Курсовая работа "Разработка прикладного программного обеспечения для проверки принадлежности точки контуру с программной реализацией в среде C++" (артикул 0010835)

Категория:

Описание

ВВЕДЕНИЕ    5
1.1 Обзор методов (Сумма углов многоугольника)    7
1.2 Метод Секущей Линии    8
1.3 Проверка принадлежности точки «простым» и «сложным» контурам    12
2. РЕАЛИЗАЦИЯ МЕТОДА В СРЕДЕ С++    17
2.1 Алгоритм реализации метода    17
2.2 Примеры, результаты    19
ЗАКЛЮЧЕНИЕ    24
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ    25
ПРИЛОЖЕНИЕ 1: Листинг программного кода    27
Полностью рабочий программный Project С++ содержится в архиве в отдельной папке

ВВЕДЕНИЕ
Проверка принадлежности точки многоугольнику или многограннику необходима во многих алгоритмах, например, в булевых операциях над многоугольниками или многогранниками. Для простых многоугольников, определенных замкнутым контуром без самопересечений и без «дыр»; известно несколько алгоритмов [4, 5, 11]. Все они предназначены или для выпуклых многоугольников или для многоугольников, у которых контур представляет собой упорядоченную последовательность ребер.
1. ПОСТАНОВКА ЗАДАЧИ ПРИНАДЛЕЖНОСТИ ТОЧКИ К КОНТУРУ
Кратко напомним известные алгоритмы определения принадлежности точки Q(x, y) многоугольнику.
Для простого односвязного многоугольника алгоритм может быть следующим. Вершины vi многоугольника последовательно нумеруются от 1 до п. Для каждой пары вершин вычисляется разность углов лучей, проведенных из точки Q. Разности суммируются. Если сумма равна нулю, то делается вывод о том, что заданная точка лежит вне заданного многоугольника.
Этот алгоритм требует большого объема вычислений с использованием обратных тригонометрических функций и, поэтому, непригоден для компьютерных интерактивных графических приложений, в которых многоугольник имеет большое число вершин.
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
1.    Бояринов A.И., Кафарова B.B. Методы оптимизации в химической технологии. — M.: Химия, 1975.
2.    Бэстен Д.-Э., ванн ден Берг В.-М., Вуд Д. Нейронные сети и финансовые рынки: принятие решений в торговых операциях. – М.: ТВП, 1997.-236с.
3.    Круглов В.В., Борисов В.В. Искусственные нейронные сети. Теория и практика. – М.: Горячая линия – Телеком, 2002. – 382с.: ил.
4.    Ласло, М. Вычислительная геометрия и компьютерная графика на C++ / М. Ласло. — М. : БИНОМ, 1997. — 304 с.
5.    Препарата Ф. Вычислительная геометрия: введение / Ф. Препарата, М. Шеймос. — М. : Мир, 1989. — 478 с.
6.    Пучков Е.В., Лила В.Б. Применение градиентных методов оптимизации для обучения искусственных нейронных сетей на примере задачи прогнозирования временного ряда. – Нечеткие системы и мягкие вычисления: сб. ст.  Третьей Всероссийской научной конференции: В 2.т. Т. I / Волгоград. гос. техн. ун-т; редкол.: А.В. Заболеева-Зотова (отв. ред.) [и др.]. – Волгоград, 2009. – 214с.  с.109-116.
7.    Тархов Д.А. Нейронные сети. Модели и алгоритмы. Кн.18. Справочное издание. (Серия «Нейрокомпьютеры и их применение»): – М.: Радиотехника, 2005. – 256с.
8.    Хайкин С. Нейронные сети: полный курс,  2-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс»,  2006. – 1104 с.: ил. – Парал. тит. англ.
9.    Химмельблау Д. Прикладное нелинейное программирование.- М.: Мир, 1975. — 535 с.
10.    Численные методы условной оптимизации / М.Дж.Д.Пауэлл, Ф.Гилл, У.Мюррей и др. — М.: Мир, 1977. — 290 с.
11.    Шикин, Е.В. Компьютерная графика. Полигональные модели / Е.В. Ши- кин, А.В. Боресков. — М. : ДИАЛОГ-МИФИ, 2005. — 223 с.
12.    Проверка принадлежности точки невыпуклому многоугольнику – https://habrahabr.ru/post/161237/
13.    Задача об определении принадлежности точки многоугольнику – https://www.pvsm.ru/algoritmy/27079/print/