Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Рыбинский государственный авиационный технический университет им. П. А. Соловьева

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

курсач / КУРСАЧ ПОЗДНЕЕ

.doc

Скачиваний:

Добавлен:

08.03.2015

Размер:

348.16 Кб

Скачать

☆

МИНИСТЕРСТВО ОБРАЗОВАНИЯ и науки РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное Государственное бюджетное образовательное учреждение высшего профессионального образования

«РыбинскИЙ государственнЫЙ авиационнЫЙ технологическИЙ УНИВЕРСИТЕТ имени П.А. Соловьева»

Факультет радиоэлектроники и информатики

Кафедра МПО ЭВС

КУРСОВАЯ РАБОТА

по дисциплине

«Программирование»

на тему

«Выявление квадратов созданных точками на плоскости»

Студентка группы ЗВП-12 Сухов А. Н.

Руководитель Паламарь И. Н.

Рыбинск, 2013

Задание на курсовую работу

Имеется множество точек на плоскости. Выявить все квадраты, которые могут быть образованны этими точками.

Программа должна обеспечивать:

Ввод данных с клавиатуры и из файла.
Обработку данных в соответствии с заданием.
Вывод результата на экран и в файл.
Использование графического режима.
Использование динамических структур данных.
Использовать манипулятор «мышь».

Введение

Анализ задания

Необходимо разработать программу, выявляющую все квадраты, которые могут быть построены из множества точек на плоскости.

Входными данными являются множество точек. Выходными данными являются графически изображенные квадраты и их количество.

В программе должен присутствовать графический интерфейс, должны быть использованы динамические структуры.

Обоснование выбора и разработка структур данных

Модуль DynStruct.

function InitPointList : pPointNode – возвращает ссылку на начальный элемент списка точек.

procedure DestroyPointList ( var root : pPointNode ) – производит удаление всего списка точек.

procedure AddPointNode ( root: pPointNode; X, Y : integer ) – производит добавление точки в конце списка точек.

function InitSquareList : pSquareNode – возвращает ссылку на начальный элемент списка квадратов.

procedure DestroySquareList( var root : pSquareNode ) – производит удаление всего списка квадратов.

procedure AddSquareNode( root: pSquareNode; P1, P2, P3, P4 : tPoint ) – производит добавление точки в конце списка квадратов.

Модуль SquareFinder.

function FindSquares( listRoot : pPointNode ) : pSquareNode – передаем ссылку на корень списка точек и возвращаем ссылку на квадрат.

function vecLength( v : tPoint ) : real – значение длинны вектора между двумя точками. Передает координаты вектора.

Модуль Unit 1.

procedure TForm1.FormPaint(Sender: TObject) – прорисовка найденных квадратов различными цветами.

procedure TForm1.FormDestroy(Sender: TObject) – очистка формы и списков.

procedure TForm1.img1MouseUp(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer) – при отпускании кнопки мыши происходит запись координат точки и добавление ее в список.

Разработка алгоритмов

tz1 : = tz1^.Next

Вычисление длинны вектора между первой и второй точками

tz2 : = tz2^.Next

tz3 : = listRoot^.Next

Вычисление длинны вектора между второй и третьей точками

tz4 : = listRoot^.Next

tz3 : = tz3^.Next

Вычисление длинны вектора между третьей и четвертой точками

Вычисление длинны вектора между четвертой и первой точками

Добавление квадрата в список квадратов

tz4 : = tz4^.Next

4 Тестирование программы

Для проверки корректности работы программы проведем несколько тестов.

Создадим в программе 4 точки расположенные как показано на рисунке 3.1.

Рисунок 3.1. Расположение точек.

Точки находятся на одной окружности, на одинаковом расстоянии от ее центра. После нажатия на кнопку найти квадраты программа должна выдать нам результат о наличии одного квадрата в поле.

Рисунок 3.2. Результат работы программы.

Программа произвела правильный расчет и в результате своей работы нашла квадрат (см. Рисунок 3.2).

Произведем проверку работы алгоритма создания случайных точек. Для этого запускаем программу и нажимаем на кнопку «Случайные точки». Получившийся результат представлен на Рисунке 3.3.

Рисунок 3.3. Результат работы программы

Результат поиска квадратов – 0, так как нет 4 точек удовлетворяющих определению квадрата.

Производим повторное нажатие на копку « Случайные точки».

Рисунок 3.4. Повторное нажатие кнопки «Случайные точки»

Рисунок 3.5. Выявление квадратов.

Нажав «Найти квадраты» программа выдает нам 2 квадрата выделенные в поле (Рисунок 3.5.).

Руководство пользователя.

Для запуска программы необходимо открыть папку КР_Сух и запустить приложение

search_squares.exe.

Рисунок 4.1. Начальное окно.

После открытия программы перед нами открывается окно, в котором мы видим поле для задания точек (см. Рисунок 4.1). Справа от него находятся кнопки:

Открыть файл.

При нажатии на данную кнопку перед нами появляется окно выбора загружаемого файла (см. Рисунок 4.2).

Рисунок 4.2. Окно для загрузки файла.

Сохранить файл.

При нажатии на данную кнопку перед нами появляется окно выбора места и имени сохраняемого файла (см. Рисунок 4.3)

Рисунок 4.3. Сохранение файла.

Случайные точки.

При нажатии на данную кнопку происходит случайная генерация множества точек расположенных хаотично на поле (см. Рисунок 4.4). При повторном нажатии на данную кнопку количество точек увеличивается.

Рисунок 4.4. Случайная генерация точек.

Очистить поле.

При нажатии на данную кнопку происходит очистка поля от любых элементов находящихся на нем (см. Рисунок 4.5).

Рисунок 4.5. Поле после очистки.

Найти квадраты.

При нажатии на данную кнопку происходит поиск всех возможных квадратов из точек заданных на поле. Ниже данной кнопки выводится количество квадратов, найденное на поле. Квадраты на поле выделяются цветом и прорисовываются.

Рисунок 4.6. Поиск квадратов.

Выход.

При нажатии на кнопку выход происходит закрытие окна программы.

Заключение

Список использованных источников

Приложение А. Листинг программы

uses

Forms,

Unit1 in 'Unit1.pas' {Form1},

DynStruct in 'DynStruct.pas',

SquareFinder in 'SquareFinder.pas';

{$R *.res}

begin

Application.Initialize;

Application.CreateForm(TForm1, Form1);

Application.Run;

end.

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls, Buttons;

type

TForm1 = class(TForm)

img1: TImage;

btn1: TButton;

btn2: TButton;

btn3: TButton;

btn4: TButton;

btn5: TButton;

btn6: TBitBtn;

lbl1: TLabel;

dlgOpen1: TOpenDialog;

dlgSave1: TSaveDialog;

procedure FormPaint(Sender: TObject);

procedure img1MouseUp(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure FormCreate(Sender: TObject);

procedure FormDestroy(Sender: TObject);

procedure btn5Click(Sender: TObject);

procedure btn3Click(Sender: TObject);

procedure btn4Click(Sender: TObject);

procedure btn1Click(Sender: TObject);

procedure btn2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

uses DynStruct, SquareFinder;

const

PointW = 10;

PointH = 10;

GridRows = 40;

GridCols = 40;

var

pointListRoot : pPointNode;

squareListRoot : pSquareNode;

procedure TForm1.FormPaint(Sender: TObject);

const Colors : array[ 1..5 ] of TColor = ( clRed, clLime, clYellow, clFuchsia, clAqua );

var i : integer;

tz : pPointNode;

dz : pSquareNode;

SCnt : integer;

begin

form1.Canvas.Brush.Color := clSilver;

form1.Canvas.Pen.Width := 1;

form1.Canvas.Pen.Color := clBlack;

form1.Canvas.FillRect( Rect( img1.Left, img1.Top, img1.Left + img1.Width, img1.Top + img1.Height ) );

form1.Canvas.Rectangle( img1.Left, img1.Top, img1.Left + img1.Width, img1.Top + img1.Height );

for i := 1 to GridCols - 1 do

begin

form1.Canvas.MoveTo( img1.Left + i * PointW, img1.Top );

form1.Canvas.LineTo( img1.Left + i * PointW, img1.Top + img1.Height );

end;

for i := 1 to GridRows - 1 do

begin

form1.Canvas.MoveTo( img1.Left, img1.Top + i * PointH );

form1.Canvas.LineTo( img1.Left + img1.Width, img1.Top + i * PointH );

end;

form1.Canvas.Brush.Color := clBlue;

tz := pointListRoot^.next;

while tz <> nil do

begin

form1.Canvas.FillRect( Rect(

img1.Left + ( tz^.Point.X - 1 ) * PointW + 1,

img1.Top + ( tz^.Point.Y - 1 ) * PointH + 1,

img1.Left + tz^.Point.X * PointW,

img1.Top + tz^.Point.Y * PointH ) );

tz := tz^.Next;

end;

form1.Canvas.Pen.Width := 3;

dz := squareListRoot^.Next;

SCnt := 0;

while dz <> nil do

begin

form1.Canvas.Pen.Color := Colors[ SCnt mod 5 + 1 ];

form1.Canvas.MoveTo( img1.Left + dz^.Square[ 1 ].X * PointW - PointW div 2,

img1.Top + dz^.Square[ 1 ].Y * PointH - PointH div 2 );

form1.Canvas.LineTo( img1.Left + dz^.Square[ 2 ].X * PointW - PointW div 2,

img1.Top + dz^.Square[ 2 ].Y * PointH - PointH div 2 );

form1.Canvas.LineTo( img1.Left + dz^.Square[ 3 ].X * PointW - PointW div 2,

img1.Top + dz^.Square[ 3 ].Y * PointH - PointH div 2 );

form1.Canvas.LineTo( img1.Left + dz^.Square[ 4 ].X * PointW - PointW div 2,

img1.Top + dz^.Square[ 4 ].Y * PointH - PointH div 2 );

form1.Canvas.LineTo( img1.Left + dz^.Square[ 1 ].X * PointW - PointW div 2,

img1.Top + dz^.Square[ 1 ].Y * PointH - PointH div 2 );

dz := dz^.Next;

inc( SCnt );

end;

lbl1.Caption := 'Квадратов ' + IntToStr( SCnt );

end;

procedure TForm1.img1MouseUp(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

var iX, iY : integer;

begin

iX := X div PointW + 1;

iY := Y div PointH + 1;

AddPointNode( pointListRoot, iX, iY );

DestroySquareList( squareListRoot );

squareListRoot := InitSquareList;

Invalidate;

Update;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

pointListRoot := InitPointList;

squareListRoot := InitSquareList;

end;

procedure TForm1.FormDestroy(Sender: TObject);

begin

DestroyPointList( pointListRoot );

DestroySquareList( squareListRoot );

end;

procedure TForm1.btn5Click(Sender: TObject);

begin

DestroySquareList( squareListRoot );

squareListRoot := FindSquares( pointListRoot );

Invalidate;

Update;

end;

procedure TForm1.btn3Click(Sender: TObject);

var i, X, Y : integer;

begin

for i := 1 to 50 do

begin

X := random( GridCols ) + 1;

Y := random( GridRows ) + 1;

AddPointNode( pointListRoot, X, Y );

end;

Invalidate;

Update;

end;

procedure ClearAll;

begin

DestroyPointList( pointListRoot );

DestroySquareList( squareListRoot );

pointListRoot := InitPointList;

squareListRoot := InitSquareList;

end;

procedure TForm1.btn4Click(Sender: TObject);

begin

ClearAll;

Invalidate;

Update;

end;

procedure TForm1.btn1Click(Sender: TObject);

var f : TextFile;

X, Y : integer;

begin

if dlgOpen1.Execute then

begin

ClearAll;

AssignFile( f, dlgOpen1.FileName );

Reset( f );

while not eof( f ) do

begin

readln( f, X );

readln( f, Y );

AddPointNode( pointListRoot, X, Y );

end;

CloseFile( f );

end;

Invalidate;

Update;

end;

procedure TForm1.btn2Click(Sender: TObject);

var f : TextFile;

tz : pPointNode;

begin

if dlgSave1.Execute then

begin

AssignFile( f, dlgSave1.FileName );

Rewrite( f );

tz := pointListRoot^.Next;

while tz <> nil do

begin

Writeln( f, tz^.Point.X );

Writeln( f, tz^.Point.Y );

tz := tz^.Next;

end;

CloseFile( f );

end;

end.

unit DynStruct;

interface

type

tPoint = record

X, Y : integer;

end;

tSquare = array[ 1..4 ] of tPoint;

// POINTS ////////////////////////////

pPointNode = ^tPointNode;

tPointNode = record

Next : pPointNode;

Point : tPoint;

end;

// SQUARES ///////////////////////////

pSquareNode = ^tSquareNode;

tSquareNode = record

Next : pSquareNode;

Square : tSquare;

end;

// POINTS ////////////////////////////

function InitPointList : pPointNode;

procedure DestroyPointList( var root : pPointNode );

procedure AddPointNode( root: pPointNode; X, Y : integer );

// SQUARES ///////////////////////////

function InitSquareList : pSquareNode;

procedure DestroySquareList( var root : pSquareNode );

procedure AddSquareNode( root: pSquareNode; P1, P2, P3, P4 : tPoint );

implementation

function InitPointList : pPointNode;

var root : pPointNode;

begin

new(root);

root^.Next := nil;

result := root;

end;

procedure DestroyPointList( var root : pPointNode );

var tz : pPointNode;

begin

while root^.Next <> nil do

begin

tz := root^.Next;

root^.Next := tz^.Next;

dispose( tz );

end;

dispose( root );

root := nil;

end;

procedure AddPointNode( root : pPointNode; X, Y : integer );

var tz : pPointNode;

equalityFlag : boolean;

begin

tz := root;

equalityFlag := false;

while ( tz^.Next <> nil ) and ( not equalityFlag ) do

begin

if ( tz^.Point.X = X ) and ( tz^.Point.Y = Y ) then equalityFlag := true;

tz := tz^.Next;

end;

if ( not equalityFlag ) then

begin

new( tz^.Next );

tz := tz^.Next;

tz^.Point.X := X;

tz^.Point.Y := Y;

tz^.Next := nil;

end;

function InitSquareList : pSquareNode;

var root : pSquareNode;

begin

new(root);

root^.Next := nil;

result := root;

end;

procedure DestroySquareList( var root : pSquareNode );

var tz : pSquareNode;

begin

while root^.Next <> nil do

begin

tz := root^.Next;

root^.Next := tz^.Next;

dispose( tz );

end;

dispose( root );

root := nil;

end;

function SquaresAreEqual( pts1, pts2 : tSquare ) : boolean;

var i, j : integer;

equal : boolean;

begin

result := true;

for i := 1 to 4 do

begin

equal := false;

for j := 1 to 4 do

if ( pts1[ i ].X = pts2[ j ].X ) and ( pts1[ i ].Y = pts2[ j ].Y ) then equal := true;

result := result and equal;

end;

procedure AddSquareNode( root: pSquareNode; P1, P2, P3, P4 : tPoint );

var tz : pSquareNode;

pts : tSquare;

equalityFlag : boolean;

begin

pts[ 1 ] := P1;

pts[ 2 ] := P2;

pts[ 3 ] := P3;

pts[ 4 ] := P4;

tz := root;

equalityFlag := false;

while ( tz^.Next <> nil ) and ( not equalityFlag ) do

begin

if ( tz <> root ) and SquaresAreEqual( tz^.Square, pts ) then

equalityFlag := true;

tz := tz^.Next;

end;

equalityFlag := equalityFlag or SquaresAreEqual( tz^.Square, pts );

if not equalityFlag then

begin

new( tz^.Next );

tz := tz^.Next;

tz^.Square := pts;

tz^.Next := nil;

end;

end.

unit SquareFinder;

interface

uses DynStruct;

function FindSquares( listRoot : pPointNode ) : pSquareNode;

implementation

const

eps = 0.001;

function vecLength( v : tPoint ) : real;

begin

result := sqrt( v.X * v.X + v.Y * v.Y );

end;

function vecOrth( v1, v2 : tPoint ) : boolean;

begin

result := ( v1.X * v2.X + v1.Y * v2.Y ) = 0;

end;

function FindSquares( listRoot : pPointNode ) : pSquareNode;

var tz1, tz2, tz3, tz4 : pPointNode;

v1, v2, v3, v4 : tPoint;

v1l, v2l, v3l, v4l : real;

Squares : pSquareNode;

begin

Squares := InitSquareList;

tz1 := listRoot^.Next;

while tz1 <> nil do

begin

tz2 := listRoot^.Next;

while tz2 <> nil do

begin

v1.X := tz2^.Point.X - tz1^.Point.X;

v1.Y := tz2^.Point.Y - tz1^.Point.Y;

v1l := vecLength( v1 );

if ( v1l > eps ) then

begin

tz3 := listRoot^.Next;

while tz3 <> nil do

begin

v2.X := tz3^.Point.X - tz2^.Point.X;

v2.Y := tz3^.Point.Y - tz2^.Point.Y;

v2l := vecLength( v2 );

if ( vecOrth( v1, v2 ) ) and ( v1l - v2l <= eps ) then

begin

tz4 := listRoot^.Next;

while tz4 <> nil do

begin

v3.X := tz4^.Point.X - tz3^.Point.X;

v3.Y := tz4^.Point.Y - tz3^.Point.Y;

v3l := vecLength( v3 );

if ( vecOrth( v2, v3 ) ) and ( v2l - v3l <= eps ) then

begin

v4.X := tz4^.Point.X - tz1^.Point.X;

v4.Y := tz4^.Point.Y - tz1^.Point.Y;

v4l := vecLength( v4 );

if ( vecOrth( v3, v4 ) ) and ( v3l - v4l <= eps ) then

begin

AddSquareNode( Squares, tz1^.Point, tz2^.Point, tz3^.Point, tz4^.Point );

end;

tz4 := tz4^.Next;

end;

tz3 := tz3^.Next;

end;

tz2 := tz2^.Next;

end;

tz1 := tz1^.Next;

end;

result := Squares;

end;

end.

Соседние файлы в папке курсач

#
08.03.201551 б17Unit1.ddp
#
08.03.20152.44 Кб17Unit1.dfm
#
08.03.20155.75 Кб18Unit1.pas
#
08.03.20152.44 Кб17Unit1.~dfm
#
08.03.20155.75 Кб17Unit1.~pas
#
08.03.2015348.16 Кб20КУРСАЧ ПОЗДНЕЕ.doc
#
08.03.2015383.49 Кб25курсач.doc
#
08.03.2015176.13 Кб19Руководство пользователя.doc