Поиск кратчайшего пути в многоугольнике - Программирование, компьютеры и кибернетика курсовая работа
Главная
Программирование, компьютеры и кибернетика
Поиск кратчайшего пути в многоугольнике
Разработка программы в среде Delphi для нахождения кратчайшего пути между стартом, лежащим в одной из вершин многоугольника, и финишем, находящимся на одной из сторон. Установка опорных точек, контроль целостности вводимых данных, методы решения задачи.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Тихоокеанский государственный экономический университет
Пои ск кратчайшего пути в многоугольнике
Условие решаемой задачи дословно по заданию звучит следующим образом: «В заданном m-угольнике найти кратчайший путь между стартом, лежащим в одной из его вершин, и финишем, находящимся на одной из его сторон».
Для большей эффективности положим старт и финиш произвольными точками внутри m-угольника, выбираемыми пользователем. Предоставим возможность выбирать размерность поля N на N для дальнейшего построения внутри неё, создаваемого пользователем, m-угольника. Графически покажем один из кратчайших путей между стартом финишем.
Перед началом вычисления пользователь должен указывать в программе следующую информацию
- кол-во опорных точек, для построения m-угольника
- местоположение вершин m-угольника(с помощью мыши)
-место положение финиша и старта внутри m-угольника(также с помощью мыши)
После установки опорных точек программа должна определять принадлежность той или иной точки к внутренней области m-угольника, после чего просчитывать кратчайший путь с учётом доступности(внутри m-угольника) и не доступности(вне m-угольника) точек и, в соответствии с этим, отбирать те из них, которые задействованные в пути.
Программа должна отображать поле, область(m-угольник) и путь между стартом и финишем.
Необходимо предусмотреть контроль целостности вводимых данных, таких как размер поля и кол-во опорных точек.
Не допустить совпадения финиша и старта или установку их вне области а так же дать возможность в заранее построенной области изменять их положение.
Положим поле двумерным массивом Shape'ов, основные функции которого дать пользователю возможность задания вершин m-угольника, старта и финиша, а также графическое отображение работы программы. В соответствии ему поставим двумерный булевый массив(доступные и недоступные точки).
Используя булевую матрицу и координаты старта и финиша вычисляем точки кратчайшего пути, которые далее отображаем с помощью массива Shape'ов.
Существует довольно много различных методов решения подобной задачи, каждый из которых основывается на своих принципах и приемах, имеет уникальные преимущества и, соответственно, недостатки. В данной работе был использован наиболее простой и менее громоздкий с учётом того, что на поле между точками имеется некоторое расстояние.
Суть используемого метода в следующем. По заданным вершинам строится полигон и заливается цветом, отличным от цвета фона. Далее для каждой точки идёт проверка цвета канвы. Если цвет канвы в данной точке совпадает со цветом заливки полигона то точка принадлежит заданной области.
tochka[i].X:=integer(vershina[i].x^)+round(h/(4*n));
tochka[i].Y:=integer(vershina[i].y^)+round(h/(4*n));
Здесь здесь vershina[].х и vershina[].у указатели на Top и Left Shape'ов, tochka[]-массив координат центров этих Left Shape'ов.
if canvas.Pixels[a[i,j].Left+round(h/(4*n)),a[i,j].Top+round(h/(4*n))]=clred then
Также приведём пример решения этой задачи в более общем случае. Его суть в том, что вначале строится контур области, а потом для каждой точки идет подсчёт кол-ва пересечений горизонтали, проведённой через эту точку, с контурами области слева от определяемой точки. Если кол-во нечётно то она принадлежит области, иначе не принадлежит.
расстояние по горизонтали между двумя соседними точками ребра
//Write(fout,'(',x:0:1,',',y:0:1,')',' ');
if ((y1$7fff) then continue;//точка не доступ- //на или путь к ней отсутствует
if (i+i1=a.x) and (j+j1=a.y) then begin//попали на старт
//запись полученной матрицы меток в текстовый файл
//процедура двигаясь от старта к финишу по полученным меткам
//заносит пройденные точки в массив точек пути
if metka1[a.x,a.y]=$7fff then begin
c:=metka1[a.x,a.y];//кол-во ходов от старта до финиша
ny:=1;//кол-во точек, использованных в пути
if (i1=0) and (j1=0) then continue;//чтобы не проверять саму точку
if metka1[i+i1,j+j1]<>c then continue;
yWay[ny].x:=i+i1;//добавление точки
if (i+i1=b.x) and (j+j1=b.y) then exit;
yyy:=TRUE;//используется для выхода из первого цикла “FOR”
В данном пункте приводятся тексты основного модуля без текста модуля для расчёта пути, так как его главная часть приведена выше.
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ExtCtrls, StdCtrls,Sgraph;
razmetka=array[0..nMaxShape,0..nMaxShape] of TShape;
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);
index1,index2:boolean;//проверка возможности расчёта
//выбор и отображение нужного кол-ва Shape'ов
procedure TForm1.btnstroiClick(Sender: TObject);
m:=strtoint(edit2.Text);//кол-во опорных точек
n:=strtoint(edit1.Text);//размерность
if (n<=nMaxShape)and(mПоиск кратчайшего пути в многоугольнике курсовая работа. Программирование, компьютеры и кибернетика.
Образец Рецензии На Дипломную
Реферат: Dolly Essay Research Paper DollyThe announcement in
Реферат: Унификация и стандартизация документов 2
Контрольная работа по теме Технологическая схема по выпуску кирпича обыкновенного
Курсовая работа по теме Организация материальной подготовки производства химического предприятия
Доклады На Тему Русская Журналистика Второй Половины Xviii Века
Сочинение На Тему Индивидуальность Обществознание 8 Класс
Реферат: Последствия землетрясений и наводнений
Курсовая работа по теме Разработка приборного оснащения беспилотных летательных аппаратов для контроля санитарно-гигиенических характеристик атмосферного воздуха в приповерхностном слое
Доклад: Об ухаживании и проявлении чувств во внешних признаках и поступках
Реферат по теме Основные социологические и экономические подходы к изучению домохозяйства
Реферат по теме Реформация Эхнатона
Реферат по теме Проект по восстановлению воздушной линии связи на железнодорожном участке
Реферат: Экономика Казахстана 3
Контрольная работа по теме Математические соревнования в четвертом классе
Контрольная работа по теме Философское знание средних веков
Сущность Предпринимательской Деятельности Реферат
Курсовая работа: Грабеж и его виды
Реферат по теме Анакреон в поэзии Ломоносова
Дипломная работа по теме Особенности преподавания психологии студентам инженерных специальностей
Методы исторической геологии и строение земной коры - Геология, гидрология и геодезия реферат
Історія культури як науки, культура стародавніх Греції і Риму - Культура и искусство лекция
Коллекторские свойства нефтеносных пластов - Геология, гидрология и геодезия презентация