НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ“
ЛЬВІВСЬКА ПОЛІТЕХНІКА”
БАСЮК ТАРАС МИХАЙЛОВИЧ
УДК 004.942: 004.915
МОДЕЛІ ТА МЕТОДИ ВІЗУАЛІЗАЦІЇ ГРАФІВ
ДЛЯ КОМП’ЮТЕРНИХ ВИДАВНИЧИХ СИСТЕМ
01.05.02 – математичне моделювання
та обчислювальні методи
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук
Львів 2007
Дисертацією є рукопис
Робота виконана в Українській академії друкарства Міністерства освіти і науки України
Науковий керівник: доктор технічних наук, доцент
Дунець Роман Богданович,
Національний університет “Львівська політехніка”,
професор кафедри електронно-обчислювальних машин.
Офіційні опоненти: доктор технічних наук, професор
Матвійчук Ярослав Миколайович,
Національний університет “Львівська політехніка”,
професор кафедри теоретичної радіоелектроніки та радіовимірювання
кандидат технічних наук, старший науковий співробітник
Опир Наталія Василівна,
Фізико-механічний інститут ім. Г.В. Карпенка НАН України,
старший науковий співробітник відділу обчислювальних методів та
систем перетворення інформації.
Провідна установа: Харківський національний університет радіоелектроніки
Міністерства освіти і науки України,
кафедра автоматизації проектування обчислювальної техніки.
Захист відбудеться 16.04.2007 р. о год. на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті "Львівська політехніка" (79013, м. Львів-13, вул. С. Бандери, 12).
З дисертацією можна ознайомитися в науково-технічній бібліотеці Національного університету “Львівська Політехніка” (79013, м. Львів, вул. Професорська, 1).
Автореферат розісланий 14.03.2007 р.
Вчений секретар
спеціалізованої вченої ради,
доктор технічних наук, професор Бунь Р.А.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. При проектуванні комп’ютерних систем, в основному, застосовуються такі форми візуалізації результатів: графи для відображення структур зв’язків між елементами системи, алгоритми роботи для опису функціонування системи, часові діаграми для відображення вхідних та вихідних сигналів елементів системи впродовж певного часу їх роботи. Якщо візуалізація часових діаграм, чи алгоритмів роботи, що забезпечується системами проектування комп’ютерної техніки, наприклад: VHDL, Verilog, Protel, OrCAD не викликає принципових труднощів, то візуалізація графів є більш трудомістким процесом, оскільки їх початкові моделі, що представляються для візуалізації, а це найчастіше матриці суміжності, таблиці зв’язаності тощо, не містять інформації стосовно взаємного розташування вершин графів на площині. Така ситуація приведе до того, що можна отримати практично необмежену кількість зображень графів, еквівалентних за структурою зв’язків і різних за виглядом, які мають різну наочність сприйняття. З іншого боку, візуалізовані на екрані монітора зображення потребують подальшого документування на паперовому носію у вигляді науково-технічних видань до яких висуваються певні вимоги, що викладені в Державних стандартах з оформлення видань. Очевидно, що було б найкраще, коли візуалізовані зображення відразу відповідали б встановленим вимогам. Проте програм, які б здійснювали перетворення матричних моделей структур зв’язків між елементами комп’ютерних видавничих систем у графові з використанням поліграфічно-орієнтованого матема-тичного апарату, на теперішній час немає.
Відображення та візуалізація даних, як процес перетворення матриць суміжностей у зображення графів, придатних для комп’ютерних видавничих систем, поділяється на два етапи. На першому етапі здійснюється розташування вершин на площині, а на другому – відображення дуг між ними. Важливість першого етапу полягає в тому, що його результат є основою для створення зображення графів, що в подальшому може лише коригуватися для підвищення наочності. Відомі методи відображення, які часто застосовуються на практиці не в повній мірі придатні при візуалізації матричних моделей у вигляді графів з багатьма вершинами, оскільки, по-перше, вони не враховують обмеження по ширині і висоті площі, що відводиться для зображення на шпальтах видань, а приймають її необмеженою; по-друге, вони не враховують вимоги до поліграфічного оформлення зображень на шпальтах видань; і, по-третє, основну увагу приділяють мінімально-можливій довжині дуг, а не розташуванню вершин таким чином, щоб зображення мало високу наочність сприйняття.
Інші відомі методи відображення структурних зв’язків, не повною мірою придатні для комп’ютерного підготування зображення як елемента видання тому, що, по-перше, у більшості з них відсутній механізм безсітковості рисування та обходу перепон, що ускладнює гнучкість моделювання структурних зв’язків, а це в свою чергу значно знижує сприйняття та розпізнаваність ілюстрації; по-друге, растрове подання рисунку спричиняє виникнення ефекту елайзінгу при подальшому опрацюванні графічного об’єкта; по-третє, вони в процесі візуалізації не враховують співвідношення між розмірами вершин графа та кеглем видання і не передбачена можливість автоматизованого редагування підготовленого до друку зображення згідно з технологічними вимогами поліграфічного оформлення науково-технічних видань. Виходячи з цього, актуальною є наукова задача розроблення математичних моделей комп’ютерних видавничих систем у вигляді графів та методів відображення структурних зв’язків між елементами систем для підвищення якості поліграфічної продукції.
Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана за планом науково-дослідних робіт Української академії друкарства в рамках наукового напряму кафедри автоматизації та комп’ютерних технологій “Розробка засобів автоматизації і комп’ютерних технологій друкарства” та відповідно до документу „Про затвердження пріоритетних напрямків діяльності технологічного парку „Яворів” (Львівська обл.), ухваленого Постановою Президії НАН України від 22.06.2005 року за №135. Результати дисертаційної роботи впроваджено в ТОВ „Центр розвитку новітніх технологій”, Фонді підтримки науки, ТОВ „Науково-технологічний парк – „Яворів” та в навчальний процес Української академії друкарства.
Мета і задачі дослідження. Метою роботи є розроблення математичних моделей комп’ютерних видавничих систем у вигляді графів та методів відображення структурних зв’язків між елементами систем для підвищення якості поліграфічної продукції. Для досягнення поставленої мети у роботі вирішено такі основні задачі:
· проведення аналізу та класифікації відомих методів і програмних засобів моделювання структурних зв’язків між елементами комп’ютерних видавничих систем та їх відображення графами;
· формулювання критеріїв відображення графових моделей структур зв’язків між елементами комп’ютерних видавничих систем та ознак вибору форм графічних примітивів зображень візуалізованих графів;
· розроблення методів перетворення матричних моделей у графові і забезпечення високих вимог поліграфічного оформлення;
· розроблення операцій редагування зображень графових моделей і відображення структур зв’язків між елементами комп’ютерних видавничих систем при їх розташуванні на екрані чи на шпальті видання;
· розроблення структури та алгоритмів прикладної програми відображення графових моделей.
Об’єкт дослідження – структурні зв’язки між елементами комп’ютерних видавничих систем.
Предмет дослідження – математичні моделі структурних зв’язків між елементами комп’ютерних видавничих систем та методи їх перетворення і відображення.
Методи дослідження. При розв’язанні поставлених задач використовувалися методи теорії матриць і теорії графів, які забезпечили вибір внутрішнього представлення графових моделей зв’язків між елементами комп’ютерних видавничих систем; методи аналізу – при розгляді алгоритмів візуалізації та об’єктно-орієнтованих середовищ для роботи з графами; алгебри логіки, які дали змогу зменшити обчислювальну складність розроблених методів; математичного моделювання, з допомогою яких отримано способи відображення вершин, дуг графа та текстових міток; прикладного програмування, використаних для реалізації прикладної програми візуалізації матричних моделей структур зв’язків між елементами комп’ютерних видавничих систем.
Наукова новизна одержаних результатів. На основі виконаних досліджень розв’язана наукова задача розроблення математичних моделей комп’ютерних видавничих систем у вигляді графів та методів відображення структурних зв’язків між елементами систем для підвищення якості поліграфічної продукції. При цьому отримано такі наукові результати:
· удосконалено способи відображення вершин графових моделей шляхом врахування кеглю основного шрифту видання, що дозволяє після їх візуалізації відразу отримувати зображення, які є придатними для комп’ютерних видавничих систем;
· удосконалено графові моделі структур зв’язків між елементами комп’ютерних видавничих систем шляхом рівновіддаленого розташування як вершин у рядках, так і сусідніх рядків на величину кратну діаметрові вершин, що забезпечило вищу наочність та відповідність поліграфічним вимогам;
· вперше запропоновано метод розташування вершин графових моделей, згідно з яким у кожному рядку зображення вершини розташовуються з центру до країв по мірі зменшення кількості дуг кожної вершини, що забезпечує вищу наочність зображень як на екрані монітора, так і на шпальті видання;
· удосконалено метод парних перестановок, в якому пари вершин в межах кожного рядка графових моделей вибираються з врахуванням кількості дуг та наявності взаємних перетинів, що потребує меншої кількості перестановок, ніж у відомих методах;
· удосконалено метод реалізації обходів вершин графових моделей шляхом знаходження положення точок обходу на основі аналізу координат перетину дуг і вершин, що підвищує наочність отриманих зображень.
Практичне значення одержаних результатів. Практична цінність роботи полягає у наступному:
· сформульовано критерії оцінювання функціональних можливостей основних модулів програм візуалізації графових моделей, за допомогою яких можна здійснити порів-няльний аналіз та вибір оптимального програмного засобу комп’ютерного відображення;
· побудовані алгоритми відображення графових моделей, представлених матрицями суміжності, на основі розроблених моделей та методів дозволяють проектувати програмні модулі для організації об’єктно-орієнтованих програмних продуктів;
· розроблено спеціалізований формат файлу, який враховує топологічні і стильові особливості відображення графової моделі, що забезпечує можливість редагування й збереження візуалізованого зображення та його конвертування з метою інтеграції створеного рисунка в публікацію за допомогою комп’ютерно-видавничої системи;
· на основі розроблених моделей та методів обґрунтовано структуру програмного засобу VISUAL, який дає можливість отримувати високонаочні зображення графів із матриць суміжностей, що відповідають поліграфічним вимогам, і може бути включений як складовий елемент комп’ютерних видавничих систем чи інших систем, в яких повинна реалізуватися візуалізація графів.
Особистий внесок здобувача. Всі результати, що становлять основний зміст дисертації, автор отримав самостійно. За результатами наукових досліджень по темі дисертаційної роботи опубліковано 18 наукових праць. У роботах [1, ], надрукованих у співавторстві, здобувачем реалізовано підпрограму перетворення графів в ярусно-паралельну форму та запропоновано алгоритм візуалізації графів представлених матрицями.
Апробація результатів роботи. Основні результати роботи доповідалися та обговорювалися на Другій та Четвертій науково-технічних конференціях студентів і аспірантів „Друкарство молоде” (м. Київ, 2002, 2004), VII і VIII Міжнародних науково-технічних конференціях „Контроль і управління в складних системах” (КУСС-2003, ) (м. Вінниця, 2003, 2005), Міжнародній науковій конференції „Інформаційні технології друкарства: алгоритми, сигнали, системи „ДРУКОТЕХН – 2004” (м. Львів, 2004), VI Всеукраїнській науково-практичній конференції „Комп’ютерне моделювання та інформаційні технології в науці, економіці та освіті” (м. Кривий Ріг, 2005), ІІ Міжнародній конференції „Сучасні комп’ютерні системи та мережі: розробка та використання” (ACSN’2005) (м. Львів, 2005), звітних науково-технічних конференціях професорсько-викладацького складу наукових працівників та аспірантів Української академії друкарства (2002-2006 рр).
Публікації. За темою роботи опубліковано 18 наукових праць: 12 статей у наукових фахових виданнях, тези 6 доповідей науково-технічних конференцій (в тому числі 16 праць без співавторів).
Структура та обсяг дисертації. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, списку використаних джерел та додатків. Загальний обсяг роботи 184 сторінки. Основний зміст роботи викладено на 144 сторінках. Робота містить 70 рисунків, 9 таблиць, 4 додатки. Список використаних джерел нараховує 188 найменувань.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі розглянуто загальний стан досліджуваної задачі, її значу-щість у сучасних умовах, обґрунтовано актуальність роботи, сформульовано мету та основні задачі досліджень, викладено наукову новизну роботи і практичну цінність результатів. Наведено дані про впровадження результатів роботи, її апробацію та публікації.
У першому розділі здійснено огляд і аналіз джерел, присвячених перетворенню матричних моделей структур зв’язків між елементами комп’ютерно-видавничих систем у графові, та визначено структуру процесу візуалізації, на основі якої окреслено об’єкт дослідження та обґрунтовано необхідність його комп’ютерної візуалізації.
Сформульовано критерії оцінювання методів візуалізації графових моделей з огляду на застосування їх при підготуванні друкованої продукції, що дало змогу провести класифікацію застосовуваних в них методів візуалізації і виявити їх неефективність для розв’язання поставленої наукової задачі. Запропоновано критерії оцінювання програм візуалізації графів, як програми комп’ютерно-видавничої системи для підготування науково-технічних видань. Проаналізовано сучасні програмні засоби і виявлено їх невідповідність сформованим критеріям та неможливість їх інтеграції з наявними програмами верстання, а відтак і їх непридатність для вирішення наукової задачі.
Обґрунтовано необхідність розроблення методів та алгоритмів перетворення матричних моделей структур зв’язків між елементами комп’ютерних видавничих систем у графові моделі, що забезпечить оперативне виготовлення науково-технічних видань, які відповідатимуть вимогам підготування друкованої продукції.
У другому розділі сформульовано критерії відображення графових моделей структур зв’язків між елементами комп’ютерних видавничих систем, які забезпечують утворення рівномірного рисунку графів, а саме: рівномірність розташування вершин на екрані чи на шпальті видання, мінімальну кількість перетинів дуг, неприпустимість перетину вершин графа, мінімальну площу, яку займає зображення графа. Проаналізовано особливості застосування цих засобів при підготовленні технічних рисунків. Виконано дослідження структури графа, що дало змогу визначити основні елементи зображення та здійснити їх впорядкування для комп’ютерних видавничих систем (рис.1). Для опису зображення графа, при підготовленні технічного рисунку, використовуються три типи елементів: вершини, дуги та текстові блоки. Основну структуру графа формують інформативні вершин, у випадку не вміщення всього зображення на площині чи шпальті видання використовують вершини-з’єднувачі. Зазначені типи вершин можуть мати різну форму, яка визначається структурою видання.
Напрямок та особливості взаємодії між вершинами відображаються дугами. В ілюстраціях науково-технічних видань зустрічаються дуги, подані у вигляді прямих ліній та сплайнів, які у випадку орієнтованих графів містять стрілки, що вказують напрямок проходження інформації. Текстові блоки застосовуються для нумерування інформативних вершин та вершин-з’єднувачів (у випадку їх наявності), та з метою створення легенди (короткого опису вершин графа).
Рис. 1. Структурні елементи зображення графів
Проаналізовано різні форми представлення вершин і виявлено, що для відображення графів великих порядків (більше 30) доцільно застосовувати графічні примітиви у формі кола. З огляду на це, запропоновано та обґрунтовано залежність для визначення діаметрів інформативних вершин в залежності від кількості символів мітки (m) та кеглю шрифта (F):
, при
, при
де Ед – величина англійського дюйма;
Fд – кегель основного шрифта видання (8, 10, 12 ...);
Кв – коефіцієнт візуалізації, що враховує значення роздільної здатності та шрифтові особливості.
Відповідно до технологічних вимог розташування міток вершин, а саме, відсутності накладань, недвозначності та наочності сприйняття запропоновано здійснювати їх розташування відповідно до абсолютних координат, які змінюватимуться в залежності від координат центрів інформативних вершин та від основного кегля видання:
(2)
де Хм, Yм – координати розташування мітки;
Х, Y – координати центра вершини графа.
На основі проведених досліджень щодо забезпечення рівномірного розташування вершин на площині розроблено загальну схему рівновіддаленого розташування їх на шпальті видання. Координати центрів (Xi,Yi) при цьому визначаються за формулами:
, для непарних
, для парних
Yi =
де і -– номер стовпця;
j – -номер рядка.
Отримано залежності, за допомогою яких визначається максимальна кількість вершин на екрані монітора чи шпальті видання:
(4)
де – максимальна кількість вершин у парних рядках;
– максимальна кількість вершин у непарних рядках;
– максимальна кількість рядків.
Загальна кількість вершин що може розміститись на шпальті видання, рівна:
(5)
В табл. наведено максимальні кількості вершин, що можуть бути розташовані на шпальтах трьох різних форматів технічних видань для трьох варіантів значень кеглю основного шрифта.
Таблиця 1. Максимальна кількість вершин в рядках, кількість рядків та загальна кількість вершин на шпальтах окремих видань
Зроблено висновок про те, що на екрані монітора чи шпальті видання доцільно в якості моделі вершини застосовувати коло з діаметром від 7 до 10 мм, що забезпечить наочність візуалізованих графів в масштабі 1:1.
У третьому розділі описано розроблені методи перетворення матричних моделей структур зв’язків у графові для всіх типів ациклічних орієнтованих графів. Вибір методу визначається вмістом матриці суміжності, що їх представляє.
Для відображення графів типу „дерево” пропонується ярусний метод візуалізації. Вершини, згідно з ним, розташовуються ярусами, що відповідає ярусам графа „дерево”. Яруси графа розташовуються зверху вниз, або зліва направо. В цих напрямках в подальшому проводяться дуги графа. Запропонований метод відображення вершин графа на площині передбачає такі основні етапи:
· утворення матриці суміжності, що представляє граф множиною матриць-рядків, що відповідають ярусно-паралельній формі;
· визначення номера та координат опорної вершини;
· визначення порядку розташування вершин графа по ярусах;
· визначення координат вершин графа в кожному ярусі.
На першому етапі проводиться перетворення матриці суміжності в ярусно-паралельну форму. У результаті такого перетворення отримуються матриці рядки, одиничні елементи яких відповідають вершинам графа, що входять в даний ярус. Кількість отриманих матриць-рядків відповідає кількості ярусів ярусно-паралельної форми графа.
На другому етапі визначається опорна вершина та знаходяться її координати. Опорною вершиною в графі „дерево” завжди є вхідна вершина, яка до речі є єдиною. Її розташовують в першому рядку, а координати визначають згідно з виразом (3).
На третьому етапі визначають порядок розташування вершин кожного ярусу в рядках. Оскільки в другому та наступних ярусах графа може бути більше однієї вершини, то вони можуть займати або один або декілька рядків на екрані чи шпальті видання. Щоб визначити це, проводиться порівняння кількості вершин поточного ярусу Nj з кількістю вершин парного (непарного) ярусів ().
Якщо Nj ?(), то всі вершини ярусу розташовують в одному рядку таким чином, що посередині відображають вершини, які мають більше число зв’язків з вершинами наступного ярусу, а по краях – ті вершини, що мають мінімальне число таких зв’язків, або взагалі їх не мають, оскільки вони є кінцевими вершинами. Таке розташування вершин забезпечує не тільки менше число перетинів дуг між собою, але й менше число обходів вершин.
Якщо Nj > (), то визначається ще кількість рядків k, які займе j-й ярус. В цьому рядку розташовують вершини, що мають найбільшу кількість зв’язків, а далі в кожному попередньому рядку – вершини з меншою кількістю зв’язків. Таке розташування сприятиме підвищенню наочності візуалізованого графа, оскільки зменшується ймовірність перетину дуг між собою та потреба в обході вершин.
Для визначення кількості зв’язків кожної вершини графа пропонується застосовувати операцію множення введеної матриці суміжності А на одиничний вектор-стовпець В. Результатом операції є матриця-рядок С, елементами якої є цілі числа з діапазону [0, 1, 2, 3, …, N-1]. Величина чисел матриці С визначає кількість дуг відповідної вершини.
Далі у сформованому масиві чисел здійснюється процедура сортування за спаданням. Особливістю такого сортування є те, що в утвореному масиві даних М зберігаються номери та відповідні кількості дуг кожної з вершин, а це дає змогу оцінити їх взаємовідношення. При проведенні сортування можливі випадки, коли відбувається знаходження декількох вершин з однаковою кількістю дуг. У такому разі, вершини в масиві розташовують в порядку зростання їх номерів, що пояснюється зручністю їх сприйняття та формування відповідного зображення графа.
З утвореного масиву М вибираються вершини, що входять в даний ярус Mj, із збереженням порядку проведеного сортування. Номер позиції в рядку першої вершини із масиву М визначаємо як:
(6)
а номер місця в рядку кожної наступної вершини знаходимо за рекурсивною залежністю:
(7)
де f = 1,2,…, -1 – порядковий номер вершин в масиві М.
На четвертому етапі відбувається розташування вершин на площині з одночасним їх нумеруванням (присвоєнням міток) з використанням залежностей (2) та (3). В якості міток використовують порядкові номери вершин графа.
Що стосується вагового методу, то він використовується для відображення деревоподібних графів. Особливістю таких графів є те, що, по-перше, вони можуть містити альтернативні шляхи між двома вершинами і, по-друге, вони можуть мати декілька вхідних вершин. На відміну від ярусного методу, він допускає наявність зв’язків між вершинами одного ярусу. Ваговий метод передбачає поділ усіх вершин графа на групи. В кожній групі містяться лише ті вершини, які мають хоч би один зв’язок із попередньою групою, а також можуть мати зв’язки між собою. Опорною вершиною є одна із вершин першої групи, що має найбільшу кількість зв’язків із іншими вершинами. Далі розташування груп вершин проводиться за аналогічною процедурою, як в ярусному методі.
Після розташування вершин на площині здійснюється відображення зв’язків (дуг) між ними у відповідності до вмісту матриці суміжності. Спочатку зв’язки відображаються як відрізки прямих ліній, відповідно до сформульованих критеріїв візуалізації, далі перевіряємо чи мають місце перетини дуг між собою чи площиною вершини тощо.
Якщо такі перетини є, то в такому випадку пропонується застосовувати модифікований метод парних перестановок, який полягає в попарній заміні місцями вершин, що містять перетини дуг. А саме, на кожному кроці роботи спочатку вибирають вершини, які містять дуги, що взаємно перетинаються, тобто мають спільну точку і визначається загальна кількість таких перетинів. Далі, серед дуг, що перетинаються, вибирають ті, які мають максимум взаємоперетинань і здійснюється процедура заміни місць відповідних вершин рядка між собою. Фактично перестановка вершин зводиться до заміни координат їх центрів у загальному масиві, що отриманий після етапу розташування вершин. Потім виконують перевірку того, чи не збільшилась кількість перетинів дуг. Якщо кількість перетинів збільшилась, то здійснену перестановку вершин місцями відміняють і вибирають для перестановки іншу пару вершин. У випадку, якщо кількість перетинів не збільшилась, то проводять перестановку наступної пари вершин, дуги яких перетинаються. Процес завершується тоді, коли здійснено всі попарні перестановки вершин, дуги яких перетинаються. Далі значення координат вершин ярусу, над якими проводились перестановки, фіксують і вибирають вершини нижнього ярусу. Таким чином, виконується перестановка решти вершин графа. Запропонований підхід, на відміну від класичного методу, не здійснює загального переставлення вершин, а лише міняє між собою ті вершини, що мають зв’язки із взаємним перетинанням в межах одного рядка.
Після відображення дуг і парних їх перестановок може виникнути ситуація, коли одна із дуг перетинає площу іншої вершини або доторкається до неї, тобто такі вершини складають певну перепону для прокладання з’єднань у виді відрізків прямих ліній. У такому випадку необхідно забезпечити обхід даною дугою вершини графа. Очевидно, що для обходу зв’язок може бути реалізований у виді ламаної лінії чи сплайну для чого необхідно визначити координати точки обходу вершини, яку пропонується віддалити від площини вершини на відстань . Така відстань є достатньою для відображення зв’язку в обхід вершини і не займає додаткового місця навколо неї. У відповідності до запропонованих методів розташування вершин на рис. наведено можливі варіанти перетину вершини графа відрізком прямої лінії.
Пропонується точку обходу виносити за межі вершини в напрямку від її центру в бік дуги перпендикулярно до неї. Точки перетину лінії з границею вершини визначають відомими методами геометрії. Величину кута між віссю X та відрізком, що з’єднує точку обходу і центр кола вершини, визначаємо як:
(8)
Рис.2. Варіанти перетину вершин
Координати точки обходу (Xp, Yp) визначаємо як:
(9)
Після знаходження координат точки обходу відбувається остаточне відображення дуги графа. Особливістю процедури візуалізації дуг між вершинами графа є відображення стрілок-вказівників, які вказують напрям проходження інформації. Складність їх відображення полягає у тому, що розміри вершин не є сталими і залежать від кегля основного шрифту видання. Якщо збільшується кегель, то збільшується і діаметр вершин згідно формули), а відтак необхідно заново знаходити координати точок дотику.
(10)
де – кут нахилу дуги до осі Ох.
В разі, якщо зображення графа не вміщується на шпальту видання визначеного формату, а також при його насиченні елементами окремі лінії потоку розривають з перенесенням частини графа на незадруковану площу поточної шпальти, або на іншу шпальту видання. Місця таких обривів у роз’єднаних частинах графа зазначаємо з’єднувачами, які розгляда-ємо як своєрідні вершини графа зі специфічними параметрами. Специфіка полягає в особливому розмірі та формі з’єднувача, відмінному від інформативних вершин, та в застосуванні кегля шрифту мітки, меншого за кегель основного шрифта видання.
З огляду на це, запропоновано наступну залежність, яка визначає розмір вершини-з’єднувача у формі квадрата в залежності від кегля основного шрифту видання:
(11)
Розташування мітки зазначеної вершини графа визначаємо згідно виразу (2), а кегль шрифту згідно формули:
(12)
Отримана площа вершини-з’єднувача є приблизно на 25% менша за площу інформативної вершини, що дає змогу легко її ідентифікувати та розміщати на площині шпальти. Зазначені моделі та методи становлять математичний апарат процедурного модуля для відображення структурних зв’язків з дотриманням норм та правил оформлення видань.
У четвертому розділі описано архітектуру побудови прикладної програми відображення структурних зв’язків між елементами комп’ютерних видавничих систем. Розроблено функціональну схему, яка складається з трьох основних модулів (рис.3): модуль керування діалогом з користувачем (призначений для обміну інформацією між оператором та прикладним програмним продуктом), модуль моделювання та візуалізації (забезпечує створення графічної моделі та відображення графа) та модуль виведення зображення (призначений для коректної роботи на програмному рівні з драйверами пристроїв виведення (монітор, принтер) та підтримки процедур відображення).
Рис.3. Функціональна схема програми візуалізації
Створено компонентну модель (рис.4), яка визначає основні аспекти відображення структурних зв’язків між елементами комп’ютерних видавничих систем та представляє статичну структуру модуля формування зображення графа.
На основі розробленої компонентної моделі та функціональної схеми побудовано архітектуру програми відображення структурних зв’язків між елементами комп’ютерних видавничих систем, яка ґрунтується на модульному принципі побудови та обґрунтовано її реалізацію із застосуванням об’єктно-орієнтованого підходу.
Для збереження результатів візуалізації розроблено спеціалізований формат файлу, який запропоновано реєструвати під ім’ям *.viz. Формат *.viz складається з послідовності даних – тегів (рис. 5).
Як і в більшості засобів збереження комп’ютерних даних, теги *.viz _ формату впорядковано в певну базову структуру: заголовок, розділ даних, закінчення. Наведена структура забезпечує коректне зберігання даних прикладної програми та належне інтерпретування їх при візуалізації.
У відповідності до визначеної методології у середовищі Borland Delphi реалізовано прикладну програму VISUAL (VISual AnaLyze – візуальний аналіз) призначену для двовимірного відображення структурних зв’язків у вигляді орієнтованих графів, що представляються матрицями суміжності. При роботі з нею оператор може легко вводити потрібну інформацію, відпрацьовувати граничні ситуації та вирізняти, які дії з його боку потрібні для продовження роботи. Спроектована прикладна програма забезпечує візуалізацію результатів у багатовіконному режимі: в модальних вікнах здійснюються основні операції по введенню матриці, її редагуванню, введенню кегля видання, вибору форми представлення інформативних вершин та вершин-з’єднувачів тощо, а в головному власне – процес візуалізації.
Таким чином, побудована на основі запропонованої компонентної моделі та функціональної схеми, а також архітектури, прикладна програма відображення структурних зв’язків для комп’ютерних видавничих систем VISUAL значно полегшує процес відображення за вхідною матрицею суміжності довільного рангу, забезпечує простий спосіб збереження сформованого рисунку із використанням розробленого формату файлу. Застосування VISUAL при створенні технічних рисунків дало змогу скоротити час підготовлення науково технічних видань і підвищити їх поліграфічну якість.
У додатках наведено акти впровадження результатів роботи, вигляд основних вікон програми VISUAL, процедури відображення структурних зв’язків та приклади вікон програмних засобів з результатами візуалізації.
ВИСНОВКИ
У дисертаційній роботі розв’язано наукову задачу розроблення математичних моделей комп’ютерних видавничих систем у вигляді графів та методів відображення структурних зв’язків між елементами систем для підвищення якості поліграфічної продукції.
1. Проаналізовано процес відображення структурних зв’язків між елементами комп’ютерних видавничих систем, як трансформацію масиву цифрових даних у масив пікселів зображень і показано, що від якості отриманих зображень залежить сприйняття виведеної інформації, а також показано, що для перетворення матричних моделей у графові можна частково застосовувати методи машинної графіки та методи трасування електронних схем.
2. Виявлено особливості відображення структурних зв’язків між елементами комп’ютерних видавничих систем, а саме в матриці суміжності, що є початковою моделлю, не міститься інформація щодо просторового розташування вершин; в результаті відображення можна отримати безліч еквівалентних за суттю, але різних за графічним представленням графів з різною наочністю; візуалізовані структурні зв’язки у вигляді графів крім високої наочності повинні відповідати вимогам поліграфічного оформлення видань і бути придатні для застосування в комп’ютерних видавничих системах.
3. Сформульовано критерії відображення структурних зв’язків з використанням матриць суміжностей, дотримання яких забезпечує утворення рівномірного зображення та проаналізовано особливості їх застосування при підготуванні технічних рисунків, створено загальний алгоритм візуалізації графів для комп’ютерних видавничих систем, який забезпечує наочне зображення графів з мінімальною кількістю перетинів дуг.
4. Досліджено структурні елементи зображень візуалізованих графів і показано, що застосування моделі вершини „коло”, в порівнянні з іншими графічними примітивами, підвищує наочність візуалізованих графів, швидкодію роботи прикладної програми, а також спрощує задання місця розташування вершин графа. На основі обґрунтованих залежностей проведено аналіз вершин графа, що містять мітки, і показано, що значення діаметру вершини залежить лише від кегля основного шрифта видання при умові, що кількість символів мітки не більше трьох, і залежить від кегля символів мітки, коли їх кількість є більшою.
5. Розроблено загальний алгоритм рівновіддаленого відображення вершин візуалізованого графа і отримано залежності, за допомогою яких визначається максимальна кількість вершин на екрані монітора чи шпальті видання, зокрема при діаметрах кола від 7 до 10 мм, максимальна кількість вершин на екрані становить від 48 до 165 в залежності від діагоналі екрану, і від 17 до 154 для шпальт видань різних форматів.
6. Розроблено ярусний та ваговий методи відображення вершин графів на площині рядками, де в межах рядка вершини, які мають більшу кількість дуг розташовують в середині рядка, а з меншим числом дуг – на краях рядка, що забезпечує вищу наочність зображення як на екрані монітора, так і на шпальті видання.
7. Удосконалено метод парних перестановок вершин графів, в якому вибір пар здійснюється з врахуванням кількості дуг вершин та наявності взаємних їх перетинів, що в результаті зменшує кількість перетинів дуг, а кількість самих перестановок є меншою, ніж у відомих методах.
8. Розроблено метод відображення обходів вершини графа дугою, шляхом визначення координат точки обходу на основі аналізу координат точки перетину дуги і кола вершини та координат центру кола, що підвищує наочність отриманого зображення графів. Розглянуто умови застосування вершин-з’єднувачів при відображенні структурних зв’язків з огляду на особливості розташу-вання графа в оригінал-макеті науково-технічного видання та запропоновано спосіб визначення координат вершин-з’єднувачів, що забезпечує коректний поділ графа на частини, які розташовують на різних шпальтах видань.
9. Створено та ієрархічно впорядковано класи компонентів, що формують модель ядра програмного засобу відповідно до розроблених методів відображення структурних зв’язків, та визначено їх параметри і функції, а також розроблено функціональну схему прикладної програми візуалізації графів для комп’ютерних видавничих систем. Спроектовано архітектуру програми відображення структурних зв’язків між елементами комп’ютерних видавничих систем, яка базується на модульному принципі побудови із застосуванням об’єктно-орієнтованого підходу; створена програма дає змогу відображати структурні зв’язки складних об’єктів і систем у вигляді графів із забезпеченням високої якості підготовки поліграфічної продукції.
СПИСОК ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1. Дунець Р.Б., Басюк Т.М. Основні задачі візуалізації графів, що описують топології поліграфічних систем // Наукові записки Української академії друкарства – 2002. – Вип. 5. – С.93 – 96.
2. Дунець Р.Б., Басюк Т.М. Структура програми перетворення графів у ярусно-паралельну форму // Комп’ютерні технології друкарства - 2002. – №7. – С.97 – 102.
3. Басюк Т.М. Аналіз програмних продуктів для візуалізації графів та критерії їх оцінкиКомп’ютерні технології друкарства. – 2003. – №10. – С.109 – 115.
4. Басюк Т.М. Аналіз та класифікація методів візуалізації // Поліграфія і видавнича справа. –2003. – Вип. 40. – С. .
5. Басюк Т.М. Критерії відображення графів в процесі візуалізації // Наукові записки Української академії друкарства. – 2004. – Вип. 7. – С. 60 – 63.
6. Басюк Т.М. Проблема розміщення міток в процесі візуалізації графівКомп’ютерні технології друкарства. – 2004. – №12. – С.187–190.
7. Басюк Т.М. Метод розміщення вершин графа в процесі візуалізації // Вісник Національного університету „Львівська політехніка”. – 2004. №519. – С.3-10.
8. Басюк Т.М. Фактори вибору графічних примітивів для візуалізації топологій // Комп’ютерні технології друкарства. – 2004. - №11. - С.124 – .
9. Басюк Т.М. Метод зображення зв’язків між вершинами графа // Вісник Тернопільського державного технічного університету. – 2005. - №1. – С.144-150.
10. Басюк Т.М. Синтез об’єктної та функціональної моделей системи візуалізації графів // Комп’ютерні технології друкарства. – 2005. - №13. – С.156-160.
11. Басюк Т.М. Етапи проектування системи моделювання та візуалізації графів // Восточно-европейский журнал передовых технологий. – 2005 – №2/2(14). – C.65-67.
12. Басюк Т.М. Архітектура системи моделювання та візуалізації графівКомп’ютерні технології друкарства. – 2006. - №15. – С.72-77.
13. Басюк Т.М. Алгоритм програми візуалізації графів, що описують топології поліграфічних систем // Доп. Другої наук.-техн. конф. студентів і аспірантів “Друкарство молоде”. – Київ, 2002. – С. 67-71.
14. Басюк Т.М. Алгоритм розміщення вершин графа при візуалізації топологій поліграфічних систем // Доп. Четвертої наук.-техн. конф. студентів і аспірантів “Друкарство молоде”. – Київ, 2004. – С. 99-102.
15. Басюк Т.М. Критерії оптимального відтворення рисунків в процесі візуалізації // Тези доп. Сьомої міжнар. наук.-техн. конф. „Контроль і управління в складних системах (КУСС-2003)”. – Вінниця, 2003. – С. 229.
16. Басюк Т.М. Архітектура системи моделювання та візуалізації графів // Тези доп. Шостої всеукраїнської наук.-практ. конф. „Комп’ютерне моделювання та інформаційні технології в науці, економіці та освіті”. – Кривий Ріг, 2005. – С. 18-19.
17. Basyuk T. The basic task of architecture designing of system of modeling and visualization graphs // Тези доп. Другої міжнар. конф. „Сучасні комп’ютерні системи та мережі: розробка та використання (ACSN’2005)”. – Львів, 2005. – С. 136-137.
18. Басюк Т.М. Критерії ефективності методів візуалізації графів // Тези доп. Восьмої міжнар. наук.-техн. конф. „Контроль і управління в складних системах (КУСС-2005)”. – Вінниця, 2005. – С. 9.
АНОТАЦІЇ
Басюк Т.М. Моделі та методи візуалізації графів для комп’ютерних видавничих систем. - Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи. – Національний університет „Львівська політехніка”, Львів, 2007.
Дисертація присвячена розробленню моделей та методів відображення структурних зв’язків між елементами комп’ютерних видавничих систем. В результаті проведеного дослідження визначено основні елементи зображення графа та виконано їх впорядкування з метою створення ієрархічного опису компонентів прикладної програми візуалізації. Сформульовано критерії візуалізації графів, дотримання яких сприяє утворенню рівномірного рисунку графа, та проаналізовано особливості їх застосування при підготовленні технічних рисунків. Побудовано математичні моделі відображення вершин і міток, які враховують співвідношення діаметра області розташування вершини, значення кегля шрифту, технічні параметри пристроїв виведення, і дають змогу побудувати зображення графів у відповідності до поліграфічних вимог.
Розроблено методи відображення різних типів структурних зв’язків у вигляді графів з врахуванням обмежень на кількість вершин у рядку. Проаналізовано особливості моделювання дуг між вершинами графа й запропоновано метод їх візуалізації, який ґрунтується на розроблених математичних моделях обчислення точки обходу області вершини за параметрами розташування суміжних вершин.
На основі розроблених методів та моделей створено комп’ютерну програму відображення структурних зв’язків складних об’єктів і систем, яка забезпечує підготовку поліграфічної продукції високої якості.
Ключові слова: математична модель, структурний зв’язок, комп’ютерна видавнича система, граф, візуалізація, програмний засіб.
Басюк Т.М. Модели и методы визуализации графов для компьютерных издательских систем. - Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 – математическое моделирование и вычислительные методы. – Национальный университет „Львовская политехника”, Львов, 2007.
Диссертация посвящена разработке моделей и методов отображения структурных связей между элементами сложных объектов и систем, в частности для компьютерных издательских систем. Выполнен анализ источников и аргументировано отображение матричных представлений в виде графов с целью визуализации структуры связей между элементами компьютерных издательских систем. Определены критерии оценивания методов визуализации учитывая применение их при подготовке специализированной печатной продукции, что дало возможность осуществить классификацию применяемых в них методов визуализации графов и выявлено их неэффективность для решения поставленной научной задачи. Сформулированы критерии оценивания программных продуктов визуализации графов, как составляющих компьютерной издательской системы для подготовки научно-технических изданий, в результате чего осуществлены исследования современных прикладных программ и показано их несоответствие сформированным критериям, невозможность интеграции с имеющимися программами верстки, а соответственно и их непригодность для решения научной задачи.
В результате проведенного исследования определены структурные элементы, которые формируют изображение графа, что дало возможность выполнить их упорядочение с целью создания иерархического описания компонентов прикладной программы визуализации графов. Основную структуру графа формируют информативные вершины, а в случае невозможности помещения всего изображение на странице издания используют вершины-соединители. Эти вершины могут иметь разное начертание, которое определяется структурой издания. Направления и особенности взаимодействия между вершинами отображается дугами. В иллюстрациях научно-технических изданий встречаются дуги, представленные в виде прямых линий и сплайнов, которые в случае ориентированных графов содержат стрелки, указывающие направление прохождения информации.
Сформулированы критерии визуализации, соблюдение которых, способствует образованию равномерного изображения графов, и проанализированы особенности их применения при подготовке технических рисунков. Построены математические модели визуализации вершин и меток, которые учитывают соотношение диаметра области расположения вершины, значение размера шрифта, технические параметры устройств вывода, и дают возможность построить изображения графов для компьютерных издательских систем с соблюдением требований полиграфического оформления.
Разработаны методы преобразования матричных моделей в графы для всех типов ациклических ориентированных графов. Выбор метода определяется содержимым матрицы
