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


Полнотекстовый поиск по базе:

Главная >> Курсовая работа >> Информатика, программирование


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




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

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

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

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

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

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

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

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

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;

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

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

Похожие работы:

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

    Курсовая работа >> Информатика, программирование
    ... темы разработки “Поиск кратчайшего пути”. 1.2 Назначение разработки Программа “Поиск кратчайшего пути” предназначается для нахождения кратчайшего пути между входом ... данными должны быть координаты вершин многоугольника. Координаты рациональней не вводить, ...
  • Геометрические задачи на олимпиадах по информатике

    Реферат >> Информатика, программирование
    ... 1; i + 1 вычисляется по модулю n. Выпуклость многоугольника (задача 6.2) с вершинами p0, p1, …, ... + 1 и i + 2 вычисляются по модулю n. В случае выпуклого многоугольника знаки у всех указанных произведений совпадают ... из них — поиск кратчайшего пути в графе (см ...
  • VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

    Реферат >> Информатика, программирование
    ... массиве B. Тогда точки, образующие многоугольник I, занимают в массиве B ... список многоугольников. Каждый многоугольник ... путей. Другие задачи поиска кратчайшего маршрута Описанные выше алгоритмы поиска кратчайшего маршрута вычисляли все кратчайшие пути ...
  • Эйлеровы и гамильтоновы графы

    Реферат >> Информатика, программирование
    ... M = (1, 2, 3, 4, 5, 6, 7, 8, 1) §3. Задачи связанные с поиском гамильтоновых циклов В ряде отраслей промышленности ... или смешанной сети найти кратчайший путь между двумя заданными ... в тур в виде выпуклого многоугольника все центральные города с минимальными ...
  • Решение задач на построение в курсе геометрии основной школы как средство развития логического мышления школьников

    Дипломная работа >> Педагогика
    ... на нахождение кратчайшего пути. Также имеется ... психический процесс поисков и открытия ... Многоугольники” (12 ч): Ломаная. Выпуклые многоугольники. Сумма углов выпуклого многоугольника. Правильные многоугольники. Окружность, вписанная в правильный многоугольник ...
  • Развитие логического мышления учащихся при решении задач на построение

    Дипломная работа >> Педагогика
    ... крат­чайшие пути ее достижения. Наличие у школьников этого качества мышления особенно важно при поиске ... коэффициенту подобия этих многоугольников» описывает имеющиеся подобные многоугольники, т. е. является их свойством. Рассмотрим ...
  • Пьер де Ферма

    Реферат >> Математика
    ... минимумов на примере задачи о кратчайшем пути светового луча, уточняя и дополняя ... относительно возможности построения правильных многоугольников и сэкономила массу времени ... поклонников математики на бесплодные поиски доказательства или опровержения теоремы. ...
  • Пьер де Ферма

    Реферат >> Математика
    ... минимумов на примере задачи о кратчайшем пути светового луча, уточняя и дополняя ... относительно возможности построения правильных многоугольников и сэкономила массу времени ... поклонников математики на бесплодные поиски доказательства или опровержения теоремы. ...
  • Задачи математического программирования

    Курсовая работа >> Математика
    ... программирования о выборе оптимального пути в транспортной сети) Заключение ... оборудования и его замены; поиск кратчайших расстояний на транспортной сети и ... Решение: Графический метод. Для построения многоугольника решений преобразуем исходную систему , ...
  • MS Office '95

    Реферат >> Информатика, программирование
    ... две точки и кривизну. Многоугольник - рисует многоугольник, замыкая линиями расстояния между ... всем этапам построения диаграммы кратчайшим путем. Использование механизма связи и ... данные, содержащие русский текст (поиск и сортировка данных выполняются правильно ...