Хочу почати з деяких відомостей про історію Delphi щоб пояснити саме такий вибір мови програмування. Turbo Pascal (який ми вивчали на першому курсі) та Borland Pascal були дешевими 16-бітними компіляторами. За роки свого існування, вони пройшли через багато релізів, і в основному використовувалися для створення програм, що виводили інформацію у текстовому режимі. Коли використання графічного інтерфейсу користувача стало необхідним у Microsoft Windows 3.1, було представлено Delphi, розроблене на основі Borland Pascal. Delphi була першою так званою системою швидкої розробки, випущеною у 1995-ому році для 16-бітної Windows 3.1 Delphi 2, представлена роком пізніше, підтримувала 32-бітне Windows-середовище, a версія, що використовувала мову C++ (яку я не використовував у даному проекті), під назвою C++ Builder побачила світ іще кількома роками пізніше. Delphi 7 (на якому власне написаний мій проект), випущена у серпні 2002, навіть зараз вона активно використовується. В Delphi 7 додано підтримку для тем Windows XP (із деяким патчем може бути застосована на Windows 7 якою я власне і користуюся). Також це була остання версія Delphi, яка могла використовуватися без активації. Вона мала лише необов'язкову реєстрацію, яку можна було просто проігнорувати. Delphi 7 є найбільш оціненим програмним середовищем, створеною Borland завдяки своїй стабільності, швидкості і низькими вимогами до апаратного забезпечення. Незважаючи на це у цій версії Delphi, як і у всіх інших, була велика кількість відомих помилок, так і ніколи не виправлених Borland. Завдання виправлення цих помилок компанія залишила на спільноту Delphi (саме один з таких "аматорських" патчів допоміг мені вирішити проблему з деякими функціями BitMap, які не працювали коректно до цього). Ще я характеризую Delphi, як найзручніше і "найпривітніше" щодо користувача у візуальному плані програмне середовище, яке також має не таку високу складність через те,що бере основу з Pascal.

Я також хотів би розповісти і детально пояснити про саме графи. Що таке граф? Це власне можна назвати будь-яку (карту, електричний коло) що складається з точок (вершин графу) та поєднано лініями (ребрами графу). Степеню вершин називається число ребер, кінцем яких і є ця вершина. Давайте підкреслимо що граф - це деяка множина точок та способи їх з'єднання а також, що для нашої цілі ці способи є суттєві.

Два графи можуть бути ізоморфні якщо існують взаємно однозначне співпадання з їх вершинами, які мають такі самі властивості,що і дві вершини з'єднанні ребром в одному графі, тоді і тільки тоді, коли такі самі вершини з'єднанні одним ребром в другому графі. Нижче (мал. 1) нам наведений неорієнтований граф з 6тьма вершинами. Орієнтований граф або орграф - це граф у якому ребрам присвоєний певний напрямок. Такий граф показаний нижче на малюнку 2. і він може бути описаний матрицею. Орієнтований граф ми активно застосовували на дискретній математиці коли вивчали відношення на множинах. Також по графу можна дізнатися яке це відношення - (анти) рефлексивне, (анти\а) симетричне, зв'язне транзитивне або монотонне.

1 2.

Існують 2 типи матриць за допомогою яких можна детально описати орієнтований граф: матриця суміжності та матриця інциндентності.1) Матриця суміжності графа G зі скінченною кількістю вершин n (пронумерованих числами від 1 до n) - це квадратна матриця A розміру n, в якій значення елементу aij рівне числу ребер з i-ї вершини графа в j-у вершину.

Іноді, особливо у разі неорієнтованого графа, петля (ребро з i-ї вершини в саму себе) вважається за два ребра, тобто значення діагонального елементу aii в цьому випадку рівне подвоєному числу петель навколо i-ї вершини.

Матриця суміжності простого графа (що не містить петель і кратних ребер) є бінарною матрицею і містить нулі на головній діагоналі.

Приклад:

Також на цьому графі ми бачимо петлю - з'єднання ребром однієї і тієї ж вершини.

Матриця суміжності повного графа Kn містить одиниці у всіх своїх елементах, окрім головної діагоналі, на якій розташовані нулі. Матриця суміжності порожнього графа, що не містить жодного ребра, складається лише з нулів.

2) Матриця інцендентності - це в матриця в якій вказується зв'язок між інцендетними елементами графу (ребрами (дугами) та вершинами). Стовпці матриці - це вершини,рядки - ребра. Ненульові значення в комірках матриці вказують на зв'язок між ребром там вершиною. Приклад:

Мультиграф (граф, в якому припускаються кратні ребра, тобто будь-які дві вершини можна з'єднати декількома ребрами. Псевдограф (мультиграф, який може мати петлі, тобто ребра, що з'єднують вершину саму з собою. Гіперграф (граф, в якому ребрами можуть бути не лише двоелементні, але довільні підмножини множини вершин. Нарешті, важливою для різноманітних практичних застосувань є модель, яка називається орієнтованим графом або орграфом. У цьому розділі дамо короткий огляд основних понять і результатів для орграфів.

Орієнтованим графом, або орграфом, G називається пара множин (V,E), де Е (V? V. Елементи множини V називаються вершинами орграфа G, а елементи множини Е (дугами орграфа G = (V,E). Отже, дуга (це впорядкована пара вершин. Відповідно, V називається множиною вершин і Е (множиною дуг орграфа G.

Якщо е= (v,w) (дуга, то вершина v називається початком, а вершина w (кінцем дуги е. Кажуть, що дуга е веде з вершини v у вершину w або виходить з v і заходить у w. Дугу е і вершини v та w називають інцедентними між собою, а вершини v i w суміжними.

Значна частина властивостей та тверджень стосовно звичайних графів може бути без змін сформульована і для орграфів. Зокрема, це стосується цілих на і для орграфів. Зокрема, це стосується цілих розділів, таких, наприклад, як планарність або розфарбування графів, в яких наявність орієнтації ребер не є суттєвою. Певні особливості в означеннях, постановках задач та методах їх розв'язування виникають при дослідженні проблем, пов'язаних з маршрутами, зв'язністю, обходами графів тощо.

Маршрутом або шляхом в орграфі G = (V,E) називається послідовність його вершин і дуг v1, e1, v2, e2, …, ek, vk +1 така, що ei = (vi,vi +1), i=1,2,.,k. Кажуть, що цей маршрут веде з вершини v1 у вершину vk +1. Число k дуг у маршруті називається його довжиною.

Маршрут, в якому всі дуги попарно різні, називається ланцюгом. Маршрут, в якому всі вершини попарно різні, називається простим ланцюгом. Маршрут називається замкненим (або циклічним), якщо v1=vk +1. Замкнений ланцюг називається циклом, а замкнений простий ланцюг - простим циклом, або контуром.

Орграф називається ациклічним (або безконтурним), якщо він не має жодного циклу. Якщо існує маршрут, який веде з вершини v у вершину w, то кажуть, що вершина w є досяжною з вершини v. У цьому випадку відстанню d (v,w) від вершини v до вершини w називається довжина найкоротшого маршруту, що веде з v y w. Відстань між вершиною v i вершиною w, яка є недосяжною зv, позначається символом.

1). Відношення досяжності на множині вершин орграфа є транзитивним.

2). Якщо в орграфі G вершина w є досяжною з вершини v, а вершина u є досяжною з вершини w, то d (v,w) +d (w, u)? d (v, u). Вершина v орграфа G називається джерелом, якщо з v є досяжною будь-яка інша вершина орграфа G. Вершина w називається стоком, якщо вона є досяжною з будь-якої іншої вершини орграфа G.

Повним орграфом (або турніром) називається орграф G, в якому будь-як ідві вершини є інцедентними одній і тільки одній дузі орграфа G. Для повних орграфів справедливі такі твердження.

Теорема 3.24. Для довільного повного орграфа G = (V,E) з n вершинами виконуються такі рівності (n (1 (? + (vi)) = |E |=n (n-1) /2; (? ( (vi)) 2.

Теорема 3.25. У будь-якому повному орграфі завжди є принаймні одне джерело і принаймні один стік.

Теорема 3.26. У будь-якому повному орграфі існує простий ланцюг, який приходить через усі вершини орграфа.

Послідовність (3.4) називається напівмаршрутом, якщо кожна дуга еі цієї послідовності є такою, що або еi = (vi,vi +1), або ei = (vi +1,vi). (Можна вважати, що при побудові напівмаршруту ми ігноруємо орієнтацію дуг орграфа). Аналогічно означаються напівланцюг, напівцикл і напівконтур.

Орграф називається сильно зв'язним, якщо будь-які дві його вершини є досяжними одна з одної. Орграф називається однобічно зв'язним, якщо для будь-яких двох його вершин принаймні одна з них є досяжною з іншої. Орграф називається слабо зв'язним, якщо для будь-яких двох його вершин існує напівмаршрут, що веде з однієї вершини в іншу.

Маршрут в орграфі G назвемо кістяковим, якщо він містить всі вершини орграфа G. Сформулюємо необхідні та достатні умови для кожного з типів а G. Сформулюємо необхідні та достатні умови для кожного з типів зв'язності.

Теорема 3.27. Орграф є сильно зв'язним тоді і тільки тоді, коли він має замкнений кістяковий маршрут.

Теорема 3.28. Орграф є однобічно зв'язним тоді і тільки тоді, коли він має кістяковий маршрут.

Теорема 3.29. Орграф є слабо зв'язним тоді і тільки тоді, коли він має кістяковий напівмаршрут.

Неважко переформулювати теореми 3.9 і 3.10, їхні наслідки та алгоритми пошуку вшир і вглиб на випадок різних типів зв'язності орграфів. Ці ж теореми й алгоритми можна пристосувати для обчислення відстаней між вершинами заданого орграфа.

Орграф, у якому є джерело і немає жодного напівконтура, називається кореневим деревом. Вхідне дерево - це орграф, який має стік і не має жодного напівконтура.

Орграф називається функціональним, якщо кожна його вершина має півстепінь виходу, рівний 1. Орграф називається ін'єктивним, якщо півстепінь заходу кожної його вершини дорівнює 1.

Тепер я хочу розповісти про Graphics Device Interface або простіше кажучи графіку в Delphi. Graphics Device Interface являє собою інтерфейс, який Windows використовує для малювання 2D графіки. Також це найповільніший спосіб відображення графіки з існуючих, проте найпростіший для розуміння основ. Отже, для початку, поговоримо про основні поняття і терміни у GDI.

Почнемо з того, що GDI зазвичай не використовують для створення крутих графічних ефектів, для цього є DirectX, OpenGL, або будь-які графічні бібліотеки (такі як: DelphiX, FastLib, DIBUltra, Graphics32.). Однак, для створення простих ефектів з мінімальними зусиллями GDI цілком згодиться.

З GDI тісно пов'язана ще одна абревіатура - DC ("Device Context" - контекст пристрою). Це те, на чому ми малюємо, і в Delphi контекст пристрою представлений як TCanvas. Ідея контексту пристрою полягає в тому, що це універсальний пристрій виводу, тому можна використовувати однакові функції як для екрану, так і для принтера.

Всі графічні функції в Delphi є надбудовами над стандартними GDI функціями Windows. Пізніше ми поговоримо про ці функції.

Pen Використовується для малювання простих ліній. Зазвичай застосовується для функції LineTo або при малюванні рамки для певної фігури (наприклад для функції Rectangle).

Brush Кисть використовується для заповнення області певним кольором. Застосовується у функціях Rectangle, FillRect або FloodFill.

Font Використовується для завдання шрифту, яким буде намальований текст. Можна вказати ім'я шрифту, розмір і т.д.

Region Дозволяє задати регіон (замкнутий простір). Регіоном може бути коло, квадрат або довільна фігура. Дозволяє так само робити дірки у фігурах.

Спершу необхідно чітко усвідомити, що координата (0,0) це верхній лівий кут екрану. Тобто значення по осі y збільшуються вниз екрану. Відповідно, координата (0, 50) означає, що ми просто відступили на 50 пікселів від верху екрана.

Найголовніше, що треба знати при малюванні ліній і фігур, це розходження між пером (Pen) і пензлем (Brush). Все дуже просто: перо (Pen) використовується при малюванні ліній чи рамок, а кисть (Brush) для заповнення фігури.

Нижче наведено дві функції, які використовуються для малювання ліній і обидві належать TCanvas: Ім'я Опис Приклад

MoveTo Переміщає точку початку малювання лінії у зазначені координати x і y Canvas. MoveTo (50, 100);

LineTo Малює лінію починаючи з поточної позиції (див. MoveTo) до зазначених координат x та y. Canvas. LineTo (50, 100);

Ефект переміщення точки початку малювання лінії так само досягається за допомогою установки своства PenPos в канвасе. наприклад, "Canvas. PenPos. x: = 20;", "Canvas. PenPos. y: = 50", або "Canvas. PenPos: = Point (20,50);".

За замовчуванням, точка початку малювання встановлена в (0,0), тобто, якщо відразу викликати "Canvas. LineTo (100,100); " то буде намальована лінія з точки (0,0) в точку (100, 100). Точка початку малювання автоматично переміститься в (100, 100), тобто, якщо виконати команду "Canvas. LineTo (200, 100);", то наступна лінія буде намальована з точки (100, 100) в (200, 100). Тому, якщо ми хочемо малювати лінії нез'єднаних один з одним, то доведеться скористатися методом MoveTo.

Лінія, намальована за допомогою LineTo використовує поточне перо в Сanvas (типу TPen). Основні властивості пера, це ширина - "Canvas. Pen. Width: = 4; " (за допомогою якого можна задавати різну ширину ліній), і колір "Canvas. Pen. Color: = clLime;".

Погляньмо на простий приклад безладного малювання різнокольорових ліній:

procedure TForm1. FormCreate (Sender: TObject);

begin

// инициализируем генератор

// случайных чисел Randomize;

end;

const NUM_LINES = 2000;

procedure TForm1. DrawLines;

var

i: Integer;

begin

for i: = 0 to NUM_LINES - 1 do

begin

Canvas. Pen. Color: = RGB (Random (256), Random (256), Random (256)); Canvas. LineTo (Random (ClientWidth),Random (ClientHeight));

end;

end;

Процедура DrawLines викликається з обробника кнопки OnClick. Кількість ліній задається в константі NUM_LINES. Між іншим, функція RGB, становить колір кожної лінії із трьох основних складових: червоного, зеленого і синього (значення від 0 до 255) і повертає нам колір у вигляді TColor.

Для малювання фігур, в TCanvas передбачені наступні функції:

Ellipse Малює еліпси, вписаний в невидимий квадрат з координатами верхнього лівого кута і правого нижнього. Якщо координати х і y у кутів будуть збігатися, то вийде коло. Canvas. Ellipse (0,0,50,50);

FillRect Заповнює прямокутник кольором поточної кисті (brush), але ніяк не за межами нього. Canvas. FillRect (Bounds (0,0,100,100));

FloodFill Заповнює дану область кольором поточної кисті, до тих пір поки не буде досягнутий край. Canvas. FloodFill (10, 10, clBlack, fsBorder);

Rectangle Малює прямокутник (або квадрат), заповнений кольором поточної кисті і обрамлений кольором поточного пера Canvas. Rectangle (Bounds (20, 20, 50, 50));

RoundRect Теж, що і Rectangle, але з загругленнимі кутами. Canvas. RoundRect (20, 20, 50, 50, 3,3);

Ще є дуже потрібна функція TextOut, яка дозволяє малювати текст, використовуючи шрифт, заданий в Canvas:

TextOut Малює дану рядок на канвасе починаючи з координат (x, y) - фон тексту заповнюється поточним кольором кисті. Canvas. TextOut (10, 10, 'Some text');

До речі, функція дозволяє малювати текст, не заповнюючи його фон. Якщо Вам необхідно змінити шрифт, використовуваний в TextOut, то необхідно змінити властивість Font Canvas (ця властивість має тип TFont) - наприклад "Canvas. Font. Name: = 'Verdana';", "Canvas. Font. Size: = 24; " або "Canvas. Font. Color: = clRed;".

Коротенько хотілося б звернути Вашу увагу на досить корисний клас TRect, який вміє зберігати в собі значення ліво, право, верху і низу (до речі, в Windows API це RECT). Те їсть, досить вказати ліву і верхню координату і ширину і висоту області, а TRect автоматично підставить у вигляді (ліво, верх, ліво + ширина, верх + висота). Ще є інша функція Rect (), яка робить те саме, але координати в ній задаються безпосередньо як ліво, право, верх і низ. Ну і за бажанням, можна використовувати API функцію SetRect.

Тепер давайте розберемося, чому в самому першому прикладі у нас стиралися лінії при переміщенні форми за межі екрану. А саме, нам потрібно з'ясувати різницю між "малюванням" і "перемальовуванням".

Малювання, це те, що ми робили вище. Тобто, малювали будь-які лінії і графічні фігури. Однак, малюнок зберігався до тих пір, поки вікно (форма) не було оновлено.

Перемальовування дещо відрізняється від поняття "малювання". Коли вікна необхідно перемальовувати, то Windows посилає певне повідомлення. Це повідомлення надходить в обробник події "OnPaint". Будь-який код, який помістити в обробник OnPaint буде викликаний кожен раз, коли формі необхідно оновитися.

Дескриптори, або як користуватися аналогічними API функціями.

Отже, ми навчилися малювати лінії, різні фігури, навчилися робити так, щоб наше творіння не стиралася при переміщенні форми, і виконали ми все це за допомогою стандартних функцій VCL (таких як Canvas. TextOut і т.д.). Однак, що робити, якщо Ви не хочете користуватися графічними функціями VCL, які всього на всього є надбудовами над аналогічними функціями з Windows API? Будь ласка! Ніхто нам не забороняє користуватися API функціями безпосередньо! Але постійте-ка, всі вони вимагають якогось HDC! Що таке HDC?

Майже все в Windows використовує "Дескриптор" (Handle). Дескриптор, це спосіб ідентифікації Вашого об'єкта в системі. У кожного вікна є свій дескриптор, у кожної кнопки теж є свій дескриптор і т.д. Саме тому всі наші об'єкти мають дескриптор в якості властивості - наприклад, "MyForm. Canvas. Handle".

Тип HDC це Дескриптор (Handle) Контексту Прилади (Device Context). Я вже говорив на самому початку, що TCanvas включає в себе більшість функцій DC. Тому, ми спокійно можемо підставляти властивість канвасе Handle скрізь, де нам це потрібно.

В API версії функції TextOut необхідно передавати рядок завершену нулем. Це означає, що замість того, щоб передати рядок у функцію безпосередньо, необхідно передати її як PChar. Так само не забувайте передавати у функцію довжину рядка. Для цього можна скористатися функцією Length.

Малювання ліній, це, звичайно, добре, але рано чи пізно Вам знадобиться намалювати більш реалістичну картинку у своєму додатку. Тому абсолютно необхідно навчитися працювати з растровими зображеннями, або як їх називають у середовищі програмістів - бітмапами.

Бітмапами, це графічний об'єкт, який містить заголовок, необхідну інформацію про зображення (таку як висота, ширина, кольору і т.д.) і, власне, саме зображення (великий масив, що містить колір кожної точки). У Delphi для цієї мети вже передбачений клас TBitmap.

Бітмапами можна малювати не тільки на формі, а й по всьому екрану. Може це і може здатися трохи дивним, але іноді це буває корисно, особливо при створенні скрінсейвера.

TCanvas має кілька корисних функцій, які працюють з типом TGraphic. Тип TGraphic є базовим класом для графічних об'єктів у Delphi, таких як: бітмапами (TBitmap), іконки (TIcon), метафайли (TMetafile) і JPEG-і (TJPEGImage). Всі вони використовують одні і ті ж функції.

Всі ці функції є методами TCanvas.

Draw Малює TGraphic на канвасе так як він є, не розтягуючи. Canvas. Draw (5,10, MyGraphic);

StrechDraw Малює TGraphic на Canvas, підганяючи (розтягуючи) його під задану область. Canvas. StretchDraw (Bounds (0,0,32,32), MyGraphic);

CopyRect Копіює частина TCanvas-а в іншій, при необхідності розтягуючи його. Canvas. CopyRect (Bounds (0,0,32,32), MyBmp. Canvas, Bounds (0, 0, 640, 480));

На цьому я хотів би закінчити з теоретичною і почати спеціальну частину

2. Спеціальна частина