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

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

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

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

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

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

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

Здесь здесь 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;

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;

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

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

procedure Tgraph.find(var z:Tmatrix;a,b:Txy;n:Integer);

var i,j,i1,j1:integer;

c:Integer;//для записи значений в метки

yyy:Boolean;//используется как условие выхода из цикла

LABEL LBL;

begin

ny:=0;//длина пути

//зополнение матрицы меток бесконечностями

for i:=0 to n-1 do

for j:=0 to n-1 do metka1[i,j]:=$7fff;

metka1[b.x,b.y]:=0;//метка соответствующая финишу

//процедура записывает в конкретную метку кол-во ходов,

//необходимых чтобы попасть в неё с финиша

c:=-1;

while 1000>=c do begin

c:=c+1;

for i:=0 to n-1 do begin

for j:=0 to n-1 do begin

if metka1[i,j]=c then begin

for i1:=-1 to 1 do begin

for j1:=-1 to 1 do begin

if (i1=0) and (j1=0) then continue;//что бы не проверять саму точку

if not z[i+i1,j+j1] or (metka1[i+i1,j+j1]<>$7fff) then continue;//точка не доступ- //на или путь к ней отсутствует

metka1[i+i1,j+j1]:=c+1;

if (i+i1=a.x) and (j+j1=a.y) then begin//попали на старт

goto LBL;

end;

//запись полученной матрицы меток в текстовый файл

LBL:

//процедура двигаясь от старта к финишу по полученным меткам

//заносит пройденные точки в массив точек пути

if metka1[a.x,a.y]=$7fff then begin

exit;

end;

c:=metka1[a.x,a.y];//кол-во ходов от старта до финиша

i:=a.x;

j:=a.y;

yWay[1]:=a;

ny:=1;//кол-во точек, использованных в пути

while c>0 do begin

c:=c-1;

yyy:=False;

for i1:=-1 to 1 do begin

for j1:=-1 to 1 do begin

if (i1=0) and (j1=0) then continue;//чтобы не проверять саму точку

if metka1[i+i1,j+j1]<>c then continue;

ny:=ny+1;//увеличение длины пути

yWay[ny].x:=i+i1;//добавление точки

yWay[ny].y:=j+j1;// в путь

if (i+i1=b.x) and (j+j1=b.y) then exit;

i:=i+i1;

j:=j+j1;

yyy:=TRUE;//используется для выхода из первого цикла “FOR”

break;

end;

if yyy then break;

end;

Текст программы

В данном пункте приводятся тексты основного модуля без текста модуля для расчёта пути, так как его главная часть приведена выше.

unit MainUnit;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ExtCtrls, StdCtrls,Sgraph;

Const

nMaxShape=25;

type

coordinate=record

x:pointer;

y:pointer

end;

razmetka=array[0..nMaxShape,0..nMaxShape] of TShape;

TForm1 = class(TForm)

Panel1: TPanel;

btnstroi: TButton;

btnfinish: TButton;

btnstart: TButton;

btnnew: TButton;

Edit1: TEdit;

Edit2: TEdit;

btnGraph: TButton;

Label1: TLabel;

Label2: TLabel;

procedure matriza();

procedure btnstroiClick(Sender: TObject);

procedure btnnewClick(Sender: TObject);

procedure vershini(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure FormCreate(Sender: TObject);

procedure btnstartClick(Sender: TObject);

procedure btnfinishClick(Sender: TObject);

procedure FormPaint(Sender: TObject);

procedure FormResize(Sender: TObject);

procedure btnGraphClick(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

function min(x,y:integer):integer;

procedure DrawWay;

procedure myShape;

public

k:integer;

a:razmetka;

end;

var

index1,index2:boolean;//проверка возможности расчёта

Form1: TForm1;

n,h,m:integer;

vershina: array of coordinate;

tochka:array of Tpoint;

matr: TMatrix;

nachialo,konez:Txy;

implementation

{$R *.dfm}

//выбор и отображение нужного кол-ва Shape'ов

procedure TForm1.myShape;

var i,j:integer;

begin

for i:=0 to n-1 do

for j:=0 to n-1 do begin

a[i,j].Shape:=stcircle;

a[i,j].Parent:=self;

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

a[i,j].Height:=round(h/(2*n));

a[i,j].Width:=round(h/(2*n));

a[i,j].Top:=round(i*h/n);

a[i,j].Left:=round(j*h/n);

a[i,j].Show;

end;

//создание массива шейпов

procedure TForm1.btnstroiClick(Sender: TObject);

var i,j:integer;

begin

try

m:=strtoint(edit2.Text);//кол-во опорных точек

n:=strtoint(edit1.Text);//размерность

if (n<=nMaxShape)and(m<n)then begin

setlength(vershina,m); myShape();btnStroi.Enabled:=False

end

else begin

application.MessageBox ('введите кол-во точек<размерность <'+'25','ошибка');

edit1.Clear;edit2.clear; edit1.SetFocus;

end;

except

application.MessageBox('введите целое число','ошибка');

edit1.Clear;edit1.Clear;edit1.SetFocus;

end;

procedure TForm1.btnnewClick(Sender: TObject);

var j,i:integer;

begin

wGraph.ny:=0; //Нет пути

k:=0;

for i:=0 to n-1 do

for j:=0 to n-1 do a[i,j].Hide;

invalidate;

edit1.Clear;

edit1.SetFocus;

edit2.Clear;

index1:=false;index2:=false;

btnStroi.Enabled:=True;

end;

//создание области по выбранным вершинам(ShapeClick)

procedure TForm1.vershini(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

var i,j:integer;

begin

if k<m then

begin //получение массива точек для полигона

vershina[k].x:=@(sender as TShape).left;

vershina[k].y:=@(sender as TShape).top;

(sender as TShape).brush.Color:=clgreen;

k:=k+1;

if k=m then

begin formpaint(self);//закраска области

//определение принадлежности точки области

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;

btnstart.Enabled:=true;

btnfinish.Enabled:=true;

invalidate

end;

//изменение начала

if ((btnstart.Tag=1)and((sender as tshape).Brush.Color=clyellow))

then index2:=false;

if (btnstart.Tag=1)and((sender as tshape).Brush.Color=clgreen)

or((btnstart.Tag=1)and((sender as tshape).Brush.Color=clyellow))

then begin(sender as tshape).Brush.Color:=clblue;index1:=true;

btnstart.Tag:=0 end;

//изменение конца

if ((btnfinish.Tag=1)and((sender as tshape).Brush.Color=clblue))

then index1:=false;

if (btnfinish.Tag=1)and((sender as tshape).Brush.Color=clgreen)

or((btnfinish.Tag=1)and((sender as tshape).Brush.Color=clblue))

then begin btnfinish.Tag:=0;index2:=true;

(sender as tshape).Brush.Color:=clyellow end;

if (index1=true) and (index2=true) then btnGraph.Enabled:=true;

end;

procedure TForm1.FormCreate(Sender: TObject);

var i,j,n:integer;

begin

k:=0;

panel1.Tag:=0;

btnstart.Enabled:=false;

btnfinish.Enabled:=false;

btnGraph.Enabled:=false;

n:=nMaxShape;

//self.WindowState:=wsMaximized;

for i:=0 to n-1 do

for j:=0 to n-1 do begin

a[i,j]:=tshape.Create(self);

a[i,j].Shape:=stcircle;

a[i,j].Parent:=self;

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

a[i,j].Height:=41;

a[i,j].Width:=41;

a[i,j].Top:=round(i*100/n);

a[i,j].Left:=round(j*100/n);

a[i,j].onmousedown:=form1.vershini;

WriteLn(wgraph.fout,i:3,j:3);

a[i,j].Hide;

end;

//постановка начала

procedure TForm1.btnstartClick(Sender: TObject);

var i,j:integer;

begin

index1:=false;

btnstart.Tag:=1;

for i:=0 to n-1 do

for j:= 0 to n-1 do

if a[i,j].Brush.Color=clblue then

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

end;

//постановка конца

procedure TForm1.btnfinishClick(Sender: TObject);

var i,j:integer;

begin

index2:=false;

btnfinish.Tag:=1;

for i:=0 to n-1 do

for j:= 0 to n-1 do

if a[i,j].Brush.Color=clyellow then

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

end;

procedure TForm1.FormPaint(Sender: TObject);

var i:integer;

begin

if k=m then begin

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;

DrawWay();//вызов рисования кратчайшего пути

end;

function TForm1.min(x,y:integer):integer;

begin

if x<y then result:=x else result:=y;

end;

procedure TForm1.FormResize(Sender: TObject);

var i,j:integer;

begin

h:=form1.min(Form1.ClientWidth-Panel1.Width,Form1.ClientHeight);

for i:=0 to n-1 do

for j:=0 to n-1 do begin

a[i,j].Top:=round(i*h/n);

a[i,j].Left:=round(j*h/n);

end;

Invalidate;

end;

//создание матрицы для графа

procedure TForm1.matriza();

var i,j:integer;

begin

for i:=-1 to n do

for j:=-1 to n do matr[i,j]:=False;

for i:=0 to n-1 do

for j:=0 to n-1 do begin

if a[i,j].Brush.Color=clWhite then matr[i,j]:=false

else matr[i,j]:=true;

if a[i,j].Brush.Color=clBlue then begin

nachialo.x:=i;

nachialo.y:=j;

end;

if a[i,j].Brush.Color=clYellow then begin

konez.x:=i;

konez.y:=j;

end;

procedure TForm1.btnGraphClick(Sender: TObject);

var i,j:integer;

begin

matriza();

wGraph.find(matr,nachialo,konez,n);

for i:=0 to n-1 do

for J:=0 to n-1 do

if a[i,j].Brush.Color=rgb(0,255,0)

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

Invalidate;

end;

//процедура рисования кратчайшего пути

procedure TForm1.DrawWay;

var i,ik,jk:integer;

begin

for i:=1 to wGraph.ny do begin

ik:=wGraph.yWay[i].x;

jk:=wGraph.yWay[i].y;

a[ik,jk].Brush.Color:=RGB(0,255,0);

end;

Интерфейс(руководство пользователю)

При разработке приложения применялся принятый в среде Delphi объектно-ориентированный подход реализации интерфейса. При реализации алгоритмов обработки данных использовался структурный подход при проектировании к написании программ приложения.

Окно интерфейса приложения представлено на рисунке. Прежде всего заполняются поля размер и кол-во опорных точек.

Далее по нажатию кнопки старт формируется поле Shape’ов заданной размерности. Кликами мыши выбираются опорные Shape в кол-ве заданном в поле «кол-во опорных точек».

После выбора всех опорных точек отображается построенная на них область. Теперь необходимо установить начало и конец сначала нажав на соответствующую кнопку а затем на нужный Shape.Повторным нажатием на одну из этих кнопок можно изменить положение начала и конца.

По нажатию кнопки «Расчёт» будет построен кратчайший путь, но только если между данным началом и концом он вообще существует. Для перерасчёта с изменением начала и конца следует их заново установить и нажать кнопку «Расчёт». Для изменения области нужно нажать кнопку «Новый» и приступить ко всем изложенным операциям сначала.

Тестовый пример программы

Положим размер поля равным 20 и кол-во опорных точек 10.Построим вогнутый многоугольник. Выберем начало и конец так, чтобы по прямой между ними имелись точки, не принадлежащие области.

Сменим начальную и конечную точки.