Web-интерфейс для демонстрации и тестирования системы полигональной аппроксимации
Вернуться к списку проектовНа главную страницу курсаЗаказчик
Богоявленская Ольга Юрьевна, доцент, к.т.н., кафедра Информатики и математического обеспечения. Эл.почта: olbgvl@cs.karelia.ru. Раб.тел.: 711015. 215 каб.Инструктор
Крышень Михаил Александрович. Эл.почта: kryshen@cs.karelia.ru. Раб.тел.: 711015. 215 каб.Аннотация проекта
Цель проекта - разработка web-интерфейса для демонстрации и тестирования системы полигональной аппроксимации. Задача полигональной аппроксимации впервые была поставлена в картографии. В настоящее время она стала актуальной в целом ряде областей информатики, иногда слабо связанных с друг другом (например компьютерная графика и производительность беспроводных технологий Интернет). Результаты проекта должны быть интегрированы с прототипом, реализующим оригинальный алгоритм полигональной аппроксимации, разработанные ранее.Первичные требования
Рассмотрим следующую задачу. Пусть определено множество прямых полос, одинаковой ширины s, произвольной длины и расположенных произвольным образом внутри некоторой площади так, что с любой точки одной полосы можно достичь любую точку другой (аналог - сеть городских улиц, полосы - дороги). Пусть некоторый объект непрерывно движется по произвольной траектории, находясь тем не менее всегда внутри одной из полос. Будем считать, что через некоторые промежутки времени нам сообщаются координаты объекта в некоторой фиксированной системе координат. Необходимо по этим данным восстановить ломаную, описывающую движение объекта по полосам. Вершины ломаной - точки перехода объекта с одной полосы на другую. Движение происходит на плоскости.Разработанное в проекте ПО должно обеспечивать web - интерфейс для демонстрации и тестирования алгоритма, реализующего эту задачу и интегрировано с одной из разработанных ранее реализаций этого алгоритма (C или Jаva). Мы ожидаем, что в проекте будут реализованы следующие функции:
- Генерация случайных траектории движения объекта по набору отрезков истинной траектории.
- Представление на экране обозревателя в системе координат, изображённой на графическом поле, траектории движения объекта, ломаной - результата полигональной аппроксимации и "идеальной траектории"
- Демонстрация и тестирование в интерактивном режиме. Здесь пользователь определяет новую точку траектории движения, а система определяет произошёл ли переход на новую полосу
- Вычисление разности между "идеальной траекторией" и результатами полигональной аппроксимации по мерам максимума разности расстояния и максимума разности по одной из координат
- Ведение архива тестовых примеров и результатов тестирования.
Набор функций может быть слабо изменён по результатам обсуждения с группой разработчиков.
Предметная область
Задача полигональной аппроксимации [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/index.php.ru
Разработчики
- Матвеева Полина Александровна, 22303, менеджер, зачтено
- Шеренкова Ольга Анатольевна, 22303, секретарь, зачтено
- Михайлова Анна Николаевна, 22303, зачтено
- Илюкевич Ольга Геннадьевна, 22303, зачтено
- Лукашенко Олег Викторович, 22303, зачтено
- Талбонен Виталий Юрьевич, 22303, зачтено
Презентация проекта (HTML)
Web-ресурс разработки (локальная копия web-ресурса 02.06.2006)
