Д. Б. Богданов Многоугольником (в вычислительной геометрии также полигоном) называется замкнутая кривая на плоскости, образованная отрезками прямых линий. Многоугольники были известны ещё в Древней Греции. На сегодн



Скачать 25.02 Kb.
Дата15.10.2012
Размер25.02 Kb.
ТипДокументы
ЭФФЕКТИВНЫЙ АЛГОРИТМ ПРОВЕРКИ ПРИНАДЛЕЖНОСТИ ТОЧКИ
ЗВЕЗДЧАТОМУ МНОГОУГОЛЬНИКУ
Д.Б. Богданов
Многоугольником (в вычислительной геометрии также полигоном) называется замкнутая кривая на плоскости, образованная отрезками прямых линий. Многоугольники были известны ещё в Древней Греции. На сегодняшний день этот математический объект является одним из основных в элементарной и вычислительной геометрии, служит базовой моделью плоской фигуры в машинной графике.

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

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

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

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

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

Многоугольником называется замкнутая кривая на плоскости, образованная отрезками прямых линий. Многоугольник называется звездчатым, если существует такая его внутренняя точка, что из нее видны все точки многоугольника. Под принадлежностью точки многоугольнику подразумевается ее принадлежность внутренней части или границе.
Для данного звездчатого многоугольника требуется отвечать на запросы вида «принадлежит ли данная точка многоугольнику» (point-in-polygon problem).

Основные результаты

Рассмотрена задача определения принадлежности точки многоугольнику. Приведены и реализованы на языке программирования С++ два метода решения данной задачи − метод трассировки луча и метод двоичного поиска. Проведен сравнительный анализ быстродействия двух упомянутых методов. Показано преимущество по скорости метода двоичного поиска.

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




Рисунок 1 – Работа приложения Star

Богданов Дмитрий Борисович, 3 курс

Научный руководитель: Таранчук В.Б.

Похожие:

Д. Б. Богданов Многоугольником (в вычислительной геометрии также полигоном) называется замкнутая кривая на плоскости, образованная отрезками прямых линий. Многоугольники были известны ещё в Древней Греции. На сегодн iconТема 5: Многоугольники
Плоская фигура, образованная замкнутой цепочкой отрезков, называется многоугольником
Д. Б. Богданов Многоугольником (в вычислительной геометрии также полигоном) называется замкнутая кривая на плоскости, образованная отрезками прямых линий. Многоугольники были известны ещё в Древней Греции. На сегодн iconОсновные элементы треугольника abc
Треугольник – многоугольник с тремя сторонами, или замкнутая ломаная линия с тремя звеньями, или фигура, образованная тремя отрезками,...
Д. Б. Богданов Многоугольником (в вычислительной геометрии также полигоном) называется замкнутая кривая на плоскости, образованная отрезками прямых линий. Многоугольники были известны ещё в Древней Греции. На сегодн iconО наших координатах Н. С. Блинов
Географические координаты, широта и долгота, определяющие положение точки на земной поверхности, были известны еще в древней Греции....
Д. Б. Богданов Многоугольником (в вычислительной геометрии также полигоном) называется замкнутая кривая на плоскости, образованная отрезками прямых линий. Многоугольники были известны ещё в Древней Греции. На сегодн iconЛекция Многоугольники (полигоны). Тесты ориентации точки относительно полигона
Контур полигона определяется вершинами, которые соединены отрезками прямых. В векторной форме полигон задается перечислением своих...
Д. Б. Богданов Многоугольником (в вычислительной геометрии также полигоном) называется замкнутая кривая на плоскости, образованная отрезками прямых линий. Многоугольники были известны ещё в Древней Греции. На сегодн iconМногоугольник
Плоская фигура, образованная замкнутой цепочкой отрезков, называется многоугольником. В зависимости от количества углов многоугольник...
Д. Б. Богданов Многоугольником (в вычислительной геометрии также полигоном) называется замкнутая кривая на плоскости, образованная отрезками прямых линий. Многоугольники были известны ещё в Древней Греции. На сегодн iconДипломная работа студента 503 группы Таткина Антона Александровича
Множество прямых на плоскости называется плетенкой, если в точках пересечения прямых указано, какая из прямых проходит «выше», а...
Д. Б. Богданов Многоугольником (в вычислительной геометрии также полигоном) называется замкнутая кривая на плоскости, образованная отрезками прямых линий. Многоугольники были известны ещё в Древней Греции. На сегодн iconЛекции по дифференциальной геометрии Геометрия гладких многообразий. Пусть гладкое
Пусть – локальные координаты в окрестности точки. Тогда кривая в локальных координатах может быть записана в виде. Кривая называется...
Д. Б. Богданов Многоугольником (в вычислительной геометрии также полигоном) называется замкнутая кривая на плоскости, образованная отрезками прямых линий. Многоугольники были известны ещё в Древней Греции. На сегодн iconПараллельность прямых и плоскостей в пространстве
Прямая а параллельна плоскости α. Сколько прямых, лежащих в плоскости α, параллельна прямой а? Параллельны ли друг другу эти прямые,...
Д. Б. Богданов Многоугольником (в вычислительной геометрии также полигоном) называется замкнутая кривая на плоскости, образованная отрезками прямых линий. Многоугольники были известны ещё в Древней Греции. На сегодн iconПроисхождение богов по поэме Гесиода
Мифы древней Греции были частью религии в этом государстве. Современные ученые с интересом относятся к мифам и изучают их с целью...
Д. Б. Богданов Многоугольником (в вычислительной геометрии также полигоном) называется замкнутая кривая на плоскости, образованная отрезками прямых линий. Многоугольники были известны ещё в Древней Греции. На сегодн iconКонтрольная работа по геометрии за 1 полугодие учени 10 «а» класса Вариант 2 ( к задачам 1-4 выполните рисунок)
Через каждую из двух параллельных прямых проведена плоскость. Эти две плоскости пересекаются. Как расположена их линия пересечения...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org