Поиск кратчайшего пути в многоугольнике (стр. 2 из 2)
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;
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;
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;
end;
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.Построим вогнутый многоугольник. Выберем начало и конец так, чтобы по прямой между ними имелись точки, не принадлежащие области.
Сменим начальную и конечную точки.
