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

Агентство по образованию Тихоокеанский государственный экономический университет Экономический институт

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

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

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

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

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

if x3

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;

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

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

end;

end;

end;

end;

end;

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;

end;

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;

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

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;

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

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;

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;

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

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

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