Курсовая работа по дисциплине «Программирование» на тему «Выявление квадратов созданных точками на плоскости»

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

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

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

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

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

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

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

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

на тему

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

Студентка группы ЗВП-12

Руководитель

Рыбинск, 2013



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

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

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

- Ввод данных с клавиатуры и из файла.

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

- Вывод результата на экран и в файл.

- Использование графического режима.

- Использование динамических структур данных.

- Использовать манипулятор «мышь».

Введение

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

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

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

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

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

Модуль 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) – при отпускании кнопки мыши происходит запись координат точки и добавление ее в список.

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

tz3 : = tz3^.Next

 

tz4 : = listRoot^.Next

 
Блок-схема: решение: (Длинна вектора >E) и (векторы между точками 1и 2 и точками 2 и 3 ортоональны)?

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

 
Блок-схема: решение: Пока tz3<>nil

tz3 : = listRoot^.Next

 
Блок-схема: решение: Длинна больше E?

tz2 : = tz2^.Next

 

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

 

tz1 : = tz1^.Next

 
Овал: Конец


Блок-схема: решение: (Длинна вектора >E) и (векторы между точками 4 и 1 и точками 1 и 2 ортоональны)?Блок-схема: решение: Пока tz4<>nil

tz4 : = tz4^.Next

 

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

 

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

 
Блок-схема:

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

search_squares.exe.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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);

*****n;

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;

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;

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;

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;

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;

end;

tz4 := tz4^.Next;

end;

end;

tz3 := tz3^.Next;

end;

end;

tz2 := tz2^.Next;

end;

tz1 := tz1^.Next;

end;

result := Squares;

end;

end.



Подпишитесь на рассылку:




 Курсы:

Подготовительные курсыДистационное образование и курсыПодготовительные курсыДневные курсыВечерние курсыКонкурсы профессиональныеЗаочные конкурсыКурсовые работыПрограммы курсовКурсы МЭОКурсы лекций

Студенты: Для студентов I курсаДля студентов II курсаДля студентов III курсаДля студентов IV курсаДля студентов V курсаДля студентов VI курса

Основные темы

Проекты по теме:

Основные порталы, построенные редакторами

Домашний очаг

ДомДачаСадоводствоДетиАктивность ребенкаИгрыКрасотаЖенщины(Беременность)СемьяХобби
Здоровье: • АнатомияБолезниВредные привычкиДиагностикаНародная медицинаПервая помощьПитаниеФармацевтика
История: СССРИстория РоссииРоссийская Империя
Окружающий мир: Животный мирДомашние животныеНасекомыеРастенияПриродаКатаклизмыКосмосКлиматСтихийные бедствия

Справочная информация

ДокументыЗаконыИзвещенияУтверждения документовДоговораЗапросы предложенийТехнические заданияПланы развитияДокументоведениеАналитикаМероприятияКонкурсыИтогиАдминистрации городовПриказыКонтрактыВыполнение работПротоколы рассмотрения заявокАукционыПроектыПротоколыБюджетные организации
МуниципалитетыРайоныОбразованияПрограммы
Отчеты: • по упоминаниямДокументная базаЦенные бумаги
Положения: • Финансовые документы
Постановления: • Рубрикатор по темамФинансыгорода Российской Федерациирегионыпо точным датам
Регламенты
Термины: • Научная терминологияФинансоваяЭкономическая
Время: • Даты2015 год2016 год
Документы в финансовой сферев инвестиционнойФинансовые документы - программы

Техника

АвиацияАвтоВычислительная техникаОборудование(Электрооборудование)РадиоТехнологии(Аудио-видео)(Компьютеры)

Общество

БезопасностьГражданские права и свободыИскусство(Музыка)Культура(Этика)Мировые именаПолитика(Геополитика)(Идеологические конфликты)ВластьЗаговоры и переворотыГражданская позицияМиграцияРелигии и верования(Конфессии)ХристианствоМифологияРазвлеченияМасс МедиаСпорт (Боевые искусства)ТранспортТуризм
Войны и конфликты: АрмияВоенная техникаЗвания и награды

Образование и наука

Наука: Контрольные работыНаучно-технический прогрессПедагогикаРабочие программыФакультетыМетодические рекомендацииШколаПрофессиональное образованиеМотивация учащихся
Предметы: БиологияГеографияГеологияИсторияЛитератураЛитературные жанрыЛитературные героиМатематикаМедицинаМузыкаПравоЖилищное правоЗемельное правоУголовное правоКодексыПсихология (Логика) • Русский языкСоциологияФизикаФилологияФилософияХимияЮриспруденция

Мир

Регионы: АзияАмерикаАфрикаЕвропаПрибалтикаЕвропейская политикаОкеанияГорода мира
Россия: • МоскваКавказ
Регионы РоссииПрограммы регионовЭкономика

Бизнес и финансы

Бизнес: • БанкиБогатство и благосостояниеКоррупция(Преступность)МаркетингМенеджментИнвестицииЦенные бумаги: • УправлениеОткрытые акционерные обществаПроектыДокументыЦенные бумаги - контрольЦенные бумаги - оценкиОблигацииДолгиВалютаНедвижимость(Аренда)ПрофессииРаботаТорговляУслугиФинансыСтрахованиеБюджетФинансовые услугиКредитыКомпанииГосударственные предприятияЭкономикаМакроэкономикаМикроэкономикаНалогиАудит
Промышленность: • МеталлургияНефтьСельское хозяйствоЭнергетика
СтроительствоАрхитектураИнтерьерПолы и перекрытияПроцесс строительстваСтроительные материалыТеплоизоляцияЭкстерьерОрганизация и управление производством

Каталог авторов (частные аккаунты)

Авто

АвтосервисАвтозапчастиТовары для автоАвтотехцентрыАвтоаксессуарыавтозапчасти для иномарокКузовной ремонтАвторемонт и техобслуживаниеРемонт ходовой части автомобиляАвтохимиямаслатехцентрыРемонт бензиновых двигателейремонт автоэлектрикиремонт АКППШиномонтаж

Бизнес

Автоматизация бизнес-процессовИнтернет-магазиныСтроительствоТелефонная связьОптовые компании

Досуг

ДосугРазвлеченияТворчествоОбщественное питаниеРестораныБарыКафеКофейниНочные клубыЛитература

Технологии

Автоматизация производственных процессовИнтернетИнтернет-провайдерыСвязьИнформационные технологииIT-компанииWEB-студииПродвижение web-сайтовПродажа программного обеспеченияКоммутационное оборудованиеIP-телефония

Инфраструктура

ГородВластьАдминистрации районовСудыКоммунальные услугиПодростковые клубыОбщественные организацииГородские информационные сайты

Наука

ПедагогикаОбразованиеШколыОбучениеУчителя

Товары

Торговые компанииТоргово-сервисные компанииМобильные телефоныАксессуары к мобильным телефонамНавигационное оборудование

Услуги

Бытовые услугиТелекоммуникационные компанииДоставка готовых блюдОрганизация и проведение праздниковРемонт мобильных устройствАтелье швейныеХимчистки одеждыСервисные центрыФотоуслугиПраздничные агентства

Блокирование содержания является нарушением Правил пользования сайтом. Администрация сайта оставляет за собой право отклонять в доступе к содержанию в случае выявления блокировок.