Название: Поиск кратчайшего пути в многоугольнике
Вид работы: курсовая работа
Рубрика: Информатика и программирование
Размер файла: 159.56 Kb
Скачать файл: referat.me-135871.docx
Краткое описание работы: Разработка программы в среде Delphi для нахождения кратчайшего пути между стартом, лежащим в одной из вершин многоугольника, и финишем, находящимся на одной из сторон. Установка опорных точек, контроль целостности вводимых данных, методы решения задачи.
Поиск кратчайшего пути в многоугольнике
Агентство по образованию
Тихоокеанский государственный экономический университет
Экономический институт
Поиск кратчайшего пути в многоугольнике
Выполнил: Матвеев А.В.
Владивосток 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.Построим вогнутый многоугольник. Выберем начало и конец так, чтобы по прямой между ними имелись точки, не принадлежащие области.
Сменим начальную и конечную точки.
Похожие работы
-
Решение транспортной задачи
Определение оптимального плана перевозок однородного груза из k-пунктов отправления в m-пункты назначения. Описание алгоритма нахождения потока минимальной стоимости. Решение транспортной задачи вручную и в среде MathCad, сравнение полученных результатов.
-
Определение связности графа на Лиспе
Двоичные деревья в теории информации. Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Обоснование выбора, описание алгоритма и структур данных. Обоснование набора тестов. Построение оптимального кода. Сущность алгоритма Хаффмана.
-
Визуализация в ГИС при наличии пространственных ограничений
Взаимодействие пользователя с геоинформационной системой (ГИС) осуществляется чаще всего в диалоговом режиме. Суть диалога заключается в формировании запросов сер-веру ГИС и получении ответов в виде картографических изображений.
-
Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог
Информационная карта 5013 Информационная 5418 Исходящий 7992 Инвентарный 5436 Инвентарный карта АИП номер, дата номер ФАП номер ВНТИЦ ИКАП ———— —————————————— ——————————————— ———————————————
-
Вычисления площади произвольного многоугольника
АННОТАЦИЯ В курсовом проекте решается задача вычисления площади произвольного многоугольника итерационным алгоритмом. ЗАДАНИЕ. Многоугольник (не обязательно выпуклый) задан на плоскости пересечением координат вершин в порядке обхода его границ. Определить площадь многоугольника.
-
Геометрические задачи на олимпиадах по информатике
Элементарные подзадачи, на решение которых опираются решения задач вычислительной геометрии. Основные формулы и алгоритмы. Олимпиадные задачи, связанные с геометрическими понятиями. Подробные численные решения геометрических разных задач с пояснениями.
-
Экспертная система для решения задачи о коммивояжере
Разработка, макетирование и реализация экспертной системы для решения задачи о коммивояжере, используя возможности языка Prolog. Составление графа "Карта Саратовской области" и решение проблемы поиска кратчайшего пути между двумя пунктами на карте.
-
Динамическое программирование, алгоритмы на графах
Алгоритмы, использующие решение дополнительных подзадач. Основные определения теории графов. Поиск пути между парой вершин невзвешенного графа. Пути минимальной длины во взвешенном графе. Понятие кратчайшего пути для графов с помощью алгоритма Флойда.
-
Алгоритмы сортировки, поиска кратчайшего пути в графе и поиска покрытия, близкого к кратчайшему
Алгоритм сортировки Шейкер: математическое описание задачи и описание алгоритма. Алгоритм покрытия: построение одного кратчайшего покрытия. Описание схемы и работы алгоритма на графах: нахождение кратчайшего пути. Контрольные примеры работы алгоритмов.
-
Алгоритмы сортировки, поиска длиннейшего пути во взвешенном графе и поиска покрытия, близкого к кратчайшему
Описание алгоритма сортировки с двоичным включением, выбор структур данных. Пример сортировки массива, отсортированного случайным образом. Алгоритм покрытия по методу "Построение одного кратчайшего покрытия". Волновой алгоритм поиска длиннейшего пути.