Курсовая работа: Поиск кратчайшего пути в многоугольнике
Выполнил: Матвеев А.В.
Владивосток 2009
Введение
Условие решаемой задачи дословно по заданию звучит следующим образом: «В заданном m-угольнике найти кратчайший путь между стартом, лежащим в одной из его вершин, и финишем, находящимся на одной из его сторон».
Для большей эффективности положим старт и финиш произвольными точками внутри m-угольника, выбираемыми пользователем. Предоставим возможность выбирать размерность поля N на N для дальнейшего построения внутри неё, создаваемого пользователем, m-угольника. Графически покажем один из кратчайших путей между стартом финишем.
Перед началом вычисления пользователь должен указывать в программе следующую информацию
- размер поля;
- кол-во опорных точек, для построения m-угольника
- местоположение вершин m-угольника(с помощью мыши)
-место положение финиша и старта внутри m-угольника(также с помощью мыши)
После установки опорных точек программа должна определять принадлежность той или иной точки к внутренней области m-угольника, после чего просчитывать кратчайший путь с учётом доступности(внутри m-угольника) и не доступности(вне m-угольника) точек и, в соответствии с этим, отбирать те из них, которые задействованные в пути.
Программа должна отображать поле, область(m-угольник) и путь между стартом и финишем.
Необходимо предусмотреть контроль целостности вводимых данных, таких как размер поля и кол-во опорных точек.
Не допустить совпадения финиша и старта или установку их вне области а так же дать возможность в заранее построенной области изменять их положение.
Формальная постановка задачи
Положим поле двумерным массивом Shape’ов, основные функции которого дать пользователю возможность задания вершин m-угольника, старта и финиша, а также графическое отображение работы программы. В соответствии ему поставим двумерный булевый массив(доступные и недоступные точки).
Используя булевую матрицу и координаты старта и финиша вычисляем точки кратчайшего пути, которые далее отображаем с помощью массива Shape’ов.
Методы решения задачи
Локализация точек
Существует довольно много различных методов решения подобной задачи, каждый из которых основывается на своих принципах и приемах, имеет уникальные преимущества и, соответственно, недостатки. В данной работе был использован наиболее простой и менее громоздкий с учётом того, что на поле между точками имеется некоторое расстояние.
Суть используемого метода в следующем. По заданным вершинам строится полигон и заливается цветом, отличным от цвета фона. Далее для каждой точки идёт проверка цвета канвы. Если цвет канвы в данной точке совпадает со цветом заливки полигона то точка принадлежит заданной области.
Построениеполигона:
with canvas do begin
setlength(tochka,m);
for i:=0 to m-1 do begin
tochka[i].X:=integer(vershina[i].x^)+round(h/(4*n));
tochka[i].Y:=integer(vershina[i].y^)+round(h/(4*n));
end;
Pen.Color:=clred;
--> ЧИТАТЬ ПОЛНОСТЬЮ <--