Поиск кратчайшего пути в многоугольнике

Агентство по образованию

Тихоокеанский государственный экономический университет

Экономический институт

Поиск кратчайшего пути в многоугольнике

Выполнил: Матвеев А.В.

Владивосток 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;

Polygon(tochka);

brush.color:=clred;

end;

end;

Здесьздесь vershina[].хи vershina[].ууказателина Top и Left Shape’ов, tochka[]-массивкоординатцентровэтих Left Shape’ов.

Проверкацвета:

for i:=0 to n-1 do

for j:= 0 to n-1 do

if canvas.Pixels[a[i,j].Left+round(h/(4*n)),a[i,j].Top+round(h/(4*n))]=clred then

a[i,j].Brush.Color:=clgreen;

Также приведём пример решения этой задачи в более общем случае. Его суть в том, что вначале строится контур области, а потом для каждой точки идет подсчёт кол-ва пересечений горизонтали, проведённой через эту точку, с контурами области слева от определяемой точки. Если кол-во нечётно то она принадлежит области, иначе не принадлежит.

Приведём текст такого метода:

dx:=(bx-ax)/m;

расстояние по горизонтали между двумя соседними точками ребра

dy:=(by-ay)/m;//по вертикали

{Локализация}

x:=ax+dx/2;

for i:=1 to m do begin

y:=ay+dy/2;

//WriteLn(fout);

for j:=1 to m do begin

//Write(fout,'(',x:0:1,',',y:0:1,')',' ');

{(x,y)-локализация}

L:=0; {Число пересечений слева}

for k:=1 to n-1 do begin

x1:=xv[k]; y1:=yv[k]; {Ребро}

x2:=xv[k+1]; y2:=yv[k+1];

if ((y1<y2) and (y1<y) and (y<y2)) or

((y2<y1) and (y2<y) and (y<y1)) then begin

{Уравнение прямой через 2 точки}

x3:=(y-y1)/(y2-y1)*(x2-x1)+x1;

if x3<x then L:=L+1;

end;

end;

y:=y+dy;

//WriteLn(fout,'L=',L);

if (L mod 2) =0 then b[m-j+1,i]:=0 else b[m-j+1,i]:=1;

end;

x:=x+dx;

end;

for i:=1 to m do begin

WriteLn(fout);

for j:=1 to m do begin

Write(fout,b[i,j]);

end;

end;

Поиск кратчайшего пути

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

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать