Вернуться к списку проектовНа главную страницу курса
Заказчик
Богоявленская Ольга Юрьевна, доцент, к.т.н., кафедра Информатики и математического обеспечения. Эл.почта: olbgvl@cs.karelia.ru. Раб.тел.: 711015. 215 каб.Консультант:
Матвеева Полина Александровна, студентка группы 22403. pmatveev@cs.karela.ru
Аннотация проекта
Цель проекта - развитие web-интерфейса для демонстрации и тестирования системы полигональной аппроксимации. Задача полигональной аппроксимации впервые была поставлена в картографии. В настоящее время она стала актуальной в целом ряде областей информатики, иногда слабо связанных с друг другом (например компьютерная графика и производительность беспроводных технологий Интернет). Результаты проекта должны быть интегрированы с прототипом, реализующим web-интерфейс для оригинального алгоритма, разработанный ранее.Первичные требования
Рассмотрим следующую задачу. Пусть определено множество прямых полос, одинаковой ширины s, произвольной длины и расположенных произвольным образом внутри некоторой площади так, что с любой точки одной полосы можно достичь любую точку другой (аналог - сеть городских улиц, полосы - дороги). Пусть некоторый объект непрерывно движется по произвольной траектории, находясь тем не менее всегда внутри одной из полос. Будем считать, что через некоторые промежутки времени нам сообщаются координаты объекта в некоторой фиксированной системе координат. Необходимо по этим данным восстановить ломаную, описывающую движение объекта по полосам. Вершины ломаной - точки перехода объекта с одной полосы на другую. Движение происходит на плоскости.Разработанное в проекте ПО должно расширить web-интерфейс для демонстрации и тестирования различных алгоритмов полигональной аппроксимации. В настоящий момент в проекте реализованы следующие функции:
- Генерация случайных траектории движения объекта по набору отрезков истинной траектории.
- Представление на экране обозревателя в системе координат, изображенной на графическом поле, траектории движения объекта, ломаной - результата полигональной аппроксимации и "идеальной траектории".
- 1.Демонстрация и тестирование в интерактивном режиме. Здесь пользователь определяет новую точку траектории движения, а система определяет произошел ли переход на новую полосу.
- Вычисление разности между "идеальной траекторией" и результатами полигональной аппроксимации по мерам максимума разности расстояния и максимума разности по одной из координат.
- Расширен набор алгоритмов аппроксимации, алгоритмами известными в литературе, (в частности алгоритм [1].)
- Сравнение результатов обработки различными алгоритмами одной и той же траектории
- Ведение архива тестовых примеров и результатов тестирования.
- Модернизация реализованных ранее функций системы.
Набор функций может быть слабо изменен по результатам обсуждения с группой разработчиков.
Предметная область
Задача полигональной аппроксимации [1-3] впервые была поставлена в картографии, когда по результатам проведенных на местности измерений картограф должен был построить ломанную и нанести ее на карту. При большом объеме измерений задача удаления "лишних точек" представляла значительные трудности. Для ее решения Дугласом и Пекером был разработан алгоритм дающий решение с точностью заданной ширины полосы. Постановка рассматриваемая в проекте актуальна для решения задач производительности сетей технологии Wi-Fi. Программное обеспечение, реализующее услуги для мобильного использования Интернет предполагает возможность предсказания производительности сети и адаптации к ней. С этой целью необходимо выявлять типичные траектории мобильных пользователей в условиях городского трафика.Ссылки
- Line Simplification Algorithms.
http://www.sli.unimelb.edu.au/gisweb/LGmodule/LGSimplification.htm - Douglas-Peucker line simplification algorithm implementation by Jack Snoeyink
http://www.cs.sunysb.edu/~algorith/implement/DPsimp/implement.shtml - Efficient Algorithms for Polygonal Approximation - Dr. Alexander Kolesnikov, Professor Pasi Franti (University of Joensuu, Finland)
http://www.cs.karelia.ru/fdpw/2004/kolesnikov.pdf
