Курсовая. Разработка алгоритма и программы решения задачи трассировки лучевым методом

Курсовая работа по программированию. Тема - Разработка алгоритма и программы решения
задачи трассировки лучевым методом

Институт компьютерных технологий и информационной безопасности, кафедра систем автоматизированного проектирования.
Программа написана на delphi, все работает, трассировка происходит.

Оформлено все по ГОСТу.

...

Введение 3
1 Задача трассировки 4
1.1 Постановка задачи трассировки 4
1.2 Способы трассировки 5
1.3 Алгоритмы трассировки 6
2 Лучевой алгоритм 7
2.1 Простейший одно-лучевой алгоритм 8
2.2 Двух-лучевой алгоритм 10
2.3 Структура алгоритма 11
3 Практическая часть 13
3.1 Описание программы 13
3.2 Руководство пользователя 14
3.2.1 Первый запуск программы 14
3.2.2 Интерфейс программы. 14
3.2.3 Работа с программой 16
Список использованных источников 18
Приложение А 19
Приложение Б 20

Одной из задач автоматизированного конструкторского проектиро-вания является задача трассировки, которая состоит в определении кон-кретной геометрии линий (печатного или проводного монтажа), соединя-ющих контакты. Задачей трассировки является прокладывание цепей та-ким образом, чтобы они имели ортогональное расположение (за исключе-нием цепей на печатных платах, на которых цепи могут прокладываться под углом 45°), не пересекали элементы, текст и точки соединений, длина цепей по возможности должна быть минимальной. Решение задачи опре-деления кратчайшего пути принадлежит к числу сложных комбинаторных задач, называемых трудно-решаемыми.
Для решения задачи трассировки разработано множество алгорит-мов, например, алгоритм Ли (волновой), его модификация (метод встреч-ной волны), лучевой, по маг истралям, канальный, эвристические. Но у каждого из этих алгоритмов есть свои особенности и недостатки. Путь, находимый лучевым алгоритмом, не всегда является кратчайшим. Канал — это область прямоугольной формы, на одной или нескольких сторонах которой расположены контакты с системой однонаправленных магистра-лей. Основная задача канальной трассировки — выбор наименьшей ши-рины канала, достаточной для размещения в нем всех соединений и назна-чения соединений на магистрали.

dfm}{ TPlata }//------------------Методы класса TPlata--------------------// КОНСТРУКТОР КЛАССА TPlataconstructor TPlata.Create(x, y: string);begin inherited Create; fSize.w:= StrToInt(x)*4; // умножение на 4 необходимо для выравнии компонента линейка fSize.h:= StrToInt(y)*4;end;// ДЕСТРУКТОР КЛАССА TPlatadestructor TPlata.Destroy;begin inherited Destroy;end;//*************РАЗЛИЧНЫЕ ПРОЦЕДУРЫ КЛАССА TPLATA****************// ЧЕРТИМ СЕТКУprocedure TPlata.SetGrid(n, m: byte);var i: integer;begin MainForm.Image1.Canvas.Pen.Color := clBlack; // устнавливаем цвет карандашу {n - ширина (ось X); m - длина (Ось У) } for i := 0 to m do begin // горизонтальные линии MainForm.Image1.Canvas.MoveTo(0,i*r); // черитм горизонтальные линии MainForm.Image1.Canvas.LineTo(n*r,i*r); mainForm.Image1.Refresh; end; for i:= 0 to n do begin // вертикальные линии MainForm.Image1.Canvas.MoveTo(i*r,0); // изменяем текущую позиц. пера и чертим вертикальные линии MainForm.Image1.Canvas.LineTo(i*r,m*r); // рисуем прямую линию начин с текущ позиции end; SetLength(arr, n, m); // устнавливаем размер динамического массиваend;// ОПРЕДЕЛЯЕМ РАЗМЕРЫ ПЛАТЫprocedure TPlata.ScanImage(var n: Tsize);var i,j: integer;begin j:= 0; n.w:= 0; // ширина n.h:= 0; // длина {Здесь я взял приблизительно 80 ячеек сетки что равняется 20 сантиметрам} for i:= 0 to 80 do begin if (MainForm.Image1.Canvas.Pixels[i*r+8, 8] = clWhite) or (MainForm.Image1.Canvas.Pixels[i*r+8, 8] = clBlack) then n.w:= n.w + 1 ; {если использовать оператор break (прерывает цикл), то необходимо использовать два цикла for ... do, что бы изображение, при разных размерах длины и высоты, не теряло часть изображения} { else break;} if (mainForm.Image1.Canvas.Pixels[8,i*r+8] = clWhite) or (MainForm.Image1.Canvas.Pixels[8,i*r+8] = clBlack) then n.h:= n.h + 1;{ else break;} end; MainForm.Image1.SetBounds(25,25, n.w*r, n.h*r);end;// ЗАПИСЫВАЕМ РАЗМЕР ПЛАТЫ В ПЕРЕМЕННУЮprocedure TPlata.SetSize(a: TSize);begin if plata <> nil then begin fsize.w:= a.w; fsize.h:= a.h; end else begin setka:= TSetka.Create(IntToStr(a.w),IntToStr(a.h)); Plata:= TPlata.Create(IntToStr(a.w), IntToStr(a.h)); end;end;//************ОСНОВЫНЫЕ ПРОЦЕДУРЫ ТРАССИРОВКИ****************// ЗАПОЛНЯЕМ МАССИВ ДАННЫМИprocedure TPlata.LoadArray;var i, j: integer; // Циклbegin for i :=0 to plata.PSize.w-1 do for j :=0 to plata.PSize.h-1 do begin // смотрим каждую клетку в определенном пикселе и взависимости от цвета // заносим данные в массив case MainForm.Image1.Canvas.Pixels[i*r+8,j*r+8] of clBlack : arr[i][j] := 255; //непроходимо clWhite : arr[i][j] := 254; //проходимо clRed : begin arr[i][j] := 253; //старт X_s := i; Y_s := j; end; clGreen : begin arr[i][j] := 0; //финиш x_end:= i; y_end:= j; end; end; end;end;// ЧЕРТИМ ДОРОЖКУ ПЕЧАТНОЙ ПЛАТЫprocedure TPlata.WaveWrite;var p: Trect;begin MainForm.Image1.Canvas.Brush.Color:= clBlack; MainForm.Image1.Canvas.Ellipse(X_s*r+2, Y_s*r+2, X_s*r+r, Y_s*r+r); MainForm.Image1.Canvas.Ellipse(X_end*r+2, Y_end*r+2, X_end*r+r, Y_end*r+r); {в этой процедуре я рисую дорожку начиная с начала, просматриваю все ячейки массива и на каждом шаге сравниваю номер шага с каждым значением в массиве если они равны черчю линию и продолжаю дальнейший просмотр} while arr[x_s,y_s] <> 0 do begin if x_s+1 < plata.PSize.w then if arr[x_s+1,y_s] = Ni1 then begin x_s:= x_s + 1; {если черта идет вправо, то ЛЕВЫЙ КРАЙ должен выступать (перекрывать) за пределы квадрата | | левый край ______|______________| | | | | | | | | | |______|______________| | | | | } p:= rect(x_s*r-8, Y_s*r+8, X_s*r+13, Y_s*r+13); end; if x_s-1 >= 0 then if arr[x_s-1,y_s] = Ni1 then begin x_s:= x_s - 1; {если черта идет влево, то ПРАВЫЙ КРАЙ должен выступать за пределы квадрата | | |________________|______ правый край | | | | | | | | | |________________|______| | | | | } p:= rect(X_s*r+8, Y_s*r+8, X_s*r+31, Y_s*r+13); end; if y_s+1 < plata.PSize.h then if arr[x_s, y_s+1] = Ni1 then begin y_s:= y_s + 1; {если черта идет вниз, то ВЕРХНИЙ КРАЙ должен выступать за пределы квадрата X_s |-----------| верхний край _____|___________|_____ | | | | | | | | | | _____|___________|_____ y_end} p:= rect(x_s*r+8, y_s*r-8, x_s*r+13, y_s*r+13); end; if y_s >= 0 then if arr[x_s, y_s - 1] = Ni1 then begin y_s:= y_s - 1; {если черта идет вверх, то НИЖНИЙ КРАЙ должен выступать за пределы квадрата} p:= rect(x_s*r+8, y_s*r+8, x_s*r+13, y_s*r+30); end; Ni1:= Ni1 - 1; MainForm.Image1.Canvas.FillRect(p); // rect(X*15, Y*15+6, X*15+15, Y*15+10) MainForm.Image1.Update; end;end;{ TSetka }//-------------------МЕТОДЫ КЛАССА TSetka---------------------// КОНСТРУКТОР КЛАССА TSETKAconstructor TSetka.Create(l, m: string);begin inherited Create(l,m); ColorE:= clWhite;end;// ДЕСТРУКТОР КЛАССА TSETKAdestructor TSetka.Destroy;begin inherited Destroy;end;//**************ПЕРЕОПРЕДЕЛЯЕМЫЙ МЕТОД КЛАССА********************// УДАЛЯЕМ СЕТКУ С ПЛАТЫprocedure TSetka.SetGrid(n,m: byte);var i: integer;begin MainForm.Image1.Canvas.Pen.Color := ColorErase; // устнавливаем цвет карандашу {n - ширина (ось X); m - длина (Ось У) } for i := 0 to m do begin // горизонтальные линии MainForm.Image1.Canvas.MoveTo(0,i*r); // черитм горизонтальные линии MainForm.Image1.Canvas.LineTo(n*r,i*r); end; for i:= 0 to n do begin // вертикальные линии MainForm.Image1.Canvas.MoveTo(i*r,0); // изменяем текущую позиц. пера и чертим вертикальные линии MainForm.Image1.Canvas.LineTo(i*r,m*r); // рисуем прямую линию начин с текущ позиции end;end;//*******************СТУЧИМ ПО КНОПКАМ*********************// КНОПКА - НОВЫЙ ФАЙЛprocedure TMainForm.ButtonNewClick(Sender: TObject);begin if NewForm.ShowModal = mrOk then begin NewForm.ControlSize; setka:= TSetka.Create(NewForm.Edit1.Text, NewForm.Edit2.Text); Plata:= TPlata.Create(NewForm.Edit1.Text, NewForm.Edit2.Text); end else exit; MainForm.Image1.SetBounds(25,25, plata.PSize.w*r, Plata.PSize.h*r); MainForm.Image1.Canvas.Brush.Color:= clWhite; // кисть белого цвета MainForm.Image1.Canvas.FillRect(rect(0,0, Plata.PSize.w*r, Plata.PSize.h*r)); // заливаем прямоугольни белым цветом Plata.SetGrid(Plata.PSize.w, Plata.PSize.h); // чертим сеткуend;// КНОПКА - УСТАНОВКА/УДАЛЕНИЕ СЕТКИprocedure TMainForm.ButtonGridClick(Sender: TObject);begin if plata = nil then begin MessageDlg('Не задан размер печатной платы!', mtError, [mbOk], 0); exit; end; if ButtonGrid.Down then setka.SetGrid(plata.psize.w, plata.PSize.h) // удаляем сетку else plata.SetGrid(plata.PSize.w, plata.PSize.h); // рисуем сеткуend;// КНОПКА - ЗАПУСТИТЬ ТРАССИРОВКУ ПЕЧАТНОЙ ПЛАТЫprocedure TMainForm.ButtonRunClick(Sender: TObject);var c: TWave;begin if plata = nil then begin MessageDlg('Не задан размер печатной платы!', mtError, [mbOk], 0); exit; end; plata.LoadArray; // загружаем массив данными c.HandlingArray(plata.PSize.w, plata.PSize.h, arr, ni1); if Ni1 > max then begin MessageDlg('Ошибка! Данные точки не соеденить.', mtError, [mbOk], 0); Image1.Canvas.Brush.Color := clWhite; Image1.Canvas.FillRect(rect(Plata.x_s*r+1, Plata.y_s*r+1, Plata.x_s*r+r, Plata.y_s*r+r)); Image1.Canvas.FillRect(rect(Plata.x_end*r+1, Plata.y_end*r+1, Plata.x_end*r+r, Plata.y_end*r+r)); Exit; end; Plata.WaveWrite; // проводим дорожку он старта до финишаend;// КНОКА РЕДАКТИРОВАТЬ: РЕДАКТИРОВАТЬ и ТРАССИРОВКАprocedure TMainForm.Image1MouseDown(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer);begin// Режим РЕДАКТИРОВАТЬ if ButtonEdit.Down then case Button of mbLeft: begin FNowDraw := True; Image1.Canvas.Brush.Color := clWhite; end; mbRight: begin FNowDraw := True; Image1.Canvas.Brush.Color := clBlack; end; end// Режим ТРАССИРОВКА else case Button of mbLeft: // левая клавиша begin Image1.Canvas.Brush.Color := clRed; Image1.Canvas.Ellipse((X div r) *r+2,(y div r) *r+2,(X div r) *r+r,(y div r) *r+r); {Image1.Canvas.FillRect(rect((X div r) *r+3,(y div r) *r+3,(X div r) *r+r-3,(y div r) *r+r-3));} end; mbRight: // правая клавиша begin Image1.Canvas.Brush.Color := clGreen; Image1.Canvas.Ellipse((X div r) *r+2,(y div r) *r+2,(X div r) *r+r,(y div r) *r+r); {Image1.Canvas.FillRect(rect((X div r) *r+3,(y div r) *r+3,(X div r) *r+r-3,(y div r) *r+r-3));} end; end;end;// КНОПКА - ОТКРЫТЬ ПРОЕКТprocedure TMainForm.ButtonOpenClick(Sender: TObject);var a: TSize;begin if OpenDialog1.Execute then begin Image1.Picture.LoadFromFile(OpenDialog1.FileName); Image1.Top:= 25; Image1.Left:= 25; Image1.Height:= Image1.Picture.Height; Image1.Width:= Image1.Picture.Width; end; Plata.ScanImage(a); plata.SetSize(a); SetLength(arr, Plata.PSize.w, Plata.PSize.h);end;// КНОПКА - СОХРАНИТЬ ПРОЕКТprocedure TMainForm.ButtonSaveClick(Sender: TObject);begin if SaveDialog1.Execute then Image1.Picture.SaveToFile(SaveDialog1.FileName);end;//****************СТУЧИМ ПО МЕНЮ*****************// МЕНЮ-НОВЫЙ ФАЙЛprocedure TMainForm.NewFileClick(Sender: TObject);begin ButtonNewClick(nil);end;// МЕНЮ - ФАЙЛ ОТКРЫТЬ ПРОЕКТprocedure TMainForm.OpenFileClick(Sender: TObject);begin ButtonOpenClick(NIL);end;// МЕНЮ - ФАЙЛ СОХРАНИТЬ ПРОЕКТprocedure TMainForm.SaveFileClick(Sender: TObject);begin ButtonSaveClick(NIL);end;// МЕНЮ - ПЕЧАТЬprocedure TMainForm.PrintFileClick(Sender: TObject);var x1,x2,y1,y2: integer; PointX, PointY: double;begin if PrintDialog1.Execute then begin// начинаем новый документ Printer.BeginDoc; Printer.Canvas.Refresh;// Получаем информацию о разрешении принтера PointX:= GetDeviceCaps(Printer.Canvas.Handle, LOGPIXELSX) /70; PointY:= GetDeviceCaps(Printer.Canvas.Handle, LOGPIXELSY) / 70;// Расчитвываем размеры изображения X1:= round((Printer.PageWidth-Image1.Picture.Bitmap.Width* pointX)/2); y1:= round((Printer.PageHeight-Image1.Picture.Bitmap.Height* pointy)/2); x2:= round(x1+Image1.Picture.Bitmap.Width*PointX); y2:= round(y1+Image1.Picture.Bitmap.Height*PointY);// Выводим изображение на печать Printer.Canvas.CopyRect(Rect(x1,y1,x2,y2), Image1.Picture.Bitmap.Canvas, rect(0,0,Image1.Picture.Bitmap.Width, Image1.Picture.Bitmap.Height)); Printer.EndDoc; end;end;// МЕНЮ - ФАЙЛ - ЗАКРЫТЬprocedure TMainForm.CloseFileClick(Sender: TObject);begin MainForm.Close;end;// МЕНЮ - РЕДАКТИРОВАТЬprocedure TMainForm.EditProjectClick(Sender: TObject);begin if ButtonEdit.Down then ButtonEdit.Down:= False else ButtonEdit.Down:= True;end;// МЕНЮ - ЗАПУСТИТЬ ТРАССИРОВКУprocedure TMainForm.RunProjectClick(Sender: TObject);begin ButtonRunClick(nil);end;// МЕНЮ - ВЫЗОВ СПРАВКИprocedure TMainForm.Call_HelpClick(Sender: TObject);begin application.HelpFile:= 'D:\2\1\4.hlp'; application.HelpCommand(help_context, 1);end;//*************ПРОЦЕДУРЫ ДЛЯ МЫШКИ*******************// ПЕРЕМЕЩАЕМ ПО ЭКРАНУprocedure TMainForm.Image1MouseMove(Sender: TObject; Shift: TShiftState; X, Y: Integer);begin if FNowDraw and ButtonEdit.Down then Image1.Canvas.FillRect(rect((X div r) *r+1,(y div r) *r+1, (X div r) *r+r,(y div r) *r+r));end;// ОТПУСТИЛ КНОПКУprocedure TMainForm.Image1MouseUp(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer);begin FNowDraw := false; // запрещаем редактированиеend;//******************ПРОЦЕДУРЫ ДЛЯ ФОРМЫ***********************// ЗАКРЫЛИ ФОРМУprocedure TMainForm.FormClose(Sender: TObject; var Action: TCloseAction);var res: word;begin // сохраним проект if plata <> nil then begin res:= MessageDlg('Сохранить проект перед закрытием?', mtConfirmation, [mbYes, mbNo], 0); if res = mrYes then ButtonSaveClick(NIL); end; // освобождаем память if setka <> nil then begin Setka.Destroy; Plata.Destroy; end; {Можно ли сдесь обойтись одним методом Destroy? Ведь сетка дочерний класс от TPlata и при вызове Setka.Destroy она вызовет метод предка}end;// ПОКАЗАЛИ ФОРМУprocedure TMainForm.ShowHint(Sender: TObject);begin StatusBar1.SimpleText:= Application.Hint; // вывели потсказкуend;// ПОДСКАЗКА В СТРОКЕ СТАТУСАprocedure TMainForm.FormShow(Sender: TObject);begin Application.OnHint:= ShowHint;end;// СОЗДАЕМ ФОРМУprocedure TMainForm.FormCreate(Sender: TObject);var t: longint;begin // выводим заставку t:= GetTickCount div 1000; while (GetTickCount div 1000) < t + 3 do; // Drag & Drop для файла DragAcceptFiles(handle, true);end;//***************DRAG AND DROP ФАЙЛА********************// Процедура Drag and Drop для файлаprocedure TMainForm.WMDropFiles(var Msg: TMessage);var FileName: array[0..256] of char; a: TSize;begin DragQueryFile(THandle(msg.WParam), 0, FileName, SizeOf(FileName)); Image1.Picture.LoadFromFile(FileName); DragFinish(THandle(msg.WParam)); // операции с изображением Plata.ScanImage(a); // определяем размер платы plata.SetSize(a); // заносим размер в переменные SetLength(arr, Plata.PSize.w, Plata.PSize.h); // устанавливаем размер массиваend;procedure TMainForm.ControlSize;beginend;end.unit Unit2;interfaceuses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Buttons;type TNewForm = class(TForm) Label1: TLabel; Edit1: TEdit; Label2: TLabel; Edit2: TEdit; BitBtn1: TBitBtn; procedure FormShow(Sender: TObject); procedure Edit1KeyPress(Sender: TObject; var Key: Char); procedure Edit2KeyPress(Sender: TObject; var Key: Char); procedure Label1Click(Sender: TObject); private { Private declarations } public procedure ControlSize; end;var NewForm: TNewForm;implementation{$R *.dfm}procedure TNewForm.FormShow(Sender: TObject);begin Edit1.SetFocus;end;procedure TNewForm.Label1Click(Sender: TObject);beginend;procedure TNewForm.Edit1KeyPress(Sender: TObject; var Key: Char);begin Case Key of '0'..'9': ; #8: ; #13: Edit2.SetFocus; else Key:= chr(0); end;end;procedure TNewForm.Edit2KeyPress(Sender: TObject; var Key: Char);begin Case Key of '0'..'9': ; #8: ; #13:; else Key:= chr(0); end;end;procedure TNewForm.ControlSize;begin if (StrToInt(Edit1.Text) > 15) or (StrToInt(Edit1.Text) = 0)then begin MessageDlg('Размер печатной платы не должен превышать 15x15 см!', mtWarning, [mbOk],0); NewForm.ShowModal; controlSize; end; if (StrToInt(Edit2.Text) > 15) or (StrToInt(Edit2.Text) = 0) then begin MessageDlg('Размер печатной платы не должен превышать 15х15 см!', mtWarning, [mbOk],0); NewForm.ShowModal; controlSize; end;end;end.unit Unit2;interfaceuses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Buttons;type TNewForm = class(TForm) Label1: TLabel; Edit1: TEdit; Label2: TLabel; Edit2: TEdit; BitBtn1: TBitBtn; procedure FormShow(Sender: TObject); procedure Edit1KeyPress(Sender: TObject; var Key: Char); procedure Edit2KeyPress(Sender: TObject; var Key: Char); procedure Label1Click(Sender: TObject); private { Private declarations } public procedure ControlSize; end;var NewForm: TNewForm;implementation{$R *.dfm}procedure TNewForm.FormShow(Sender: TObject);begin Edit1.SetFocus;end;procedure TNewForm.Label1Click(Sender: TObject);beginend;procedure TNewForm.Edit1KeyPress(Sender: TObject; var Key: Char);begin Case Key of '0'..'9': ; #8: ; #13: Edit2.SetFocus; else Key:= chr(0); end;end;procedure TNewForm.Edit2KeyPress(Sender: TObject; var Key: Char);begin Case Key of '0'..'9': ; #8: ; #13:; else Key:= chr(0); end;end;procedure TNewForm.ControlSize;begin if (StrToInt(Edit1.Text) > 15) or (StrToInt(Edit1.