Р Б Дунець, Т М Басюк - Знаходження шляху обходу вершин дугами при візуалізації топологій на площині - страница 1

Страницы:
1 

завад контрольованих сигналів при перевищенні швидкості їхнього наростання деякого заданого граничного значення.

1. Цветков Э.И. Процессорные измерительные средства. - Л.: Энергоатомиздат, 1989. - 224 с. 2. Дороніна О., Лавров Г., Хомич С. Підвищення точності системи контролю енергетичних параметрів електромережі.// Системы контроля окружающей среды. Сборник научных трудов. -Севастополь: МГИ, 2004. - С. 96-98. 3. Доронина О.М., Хомич С.В. Особенности автоматического выбора диапазонов измерения системы мониторинга энергетических параметров электросети // Системы контроля окружающей среды. Средства и инфрмационные технологии: Сб. науч. тр. -Севастополь: МГИ, 2006. - С. 98-80. 4. Guery A., Kitchin Ch. 16-bit ADC provides 19-bit resolution.// Analog Devices, EDN. - 2002. - №2. 5. Дороніна О.М., Лавров Г.М., Хомич С.В. Підвищення точності вимірювальних каналів комп 'ютеризованої системи контролю та діагностики енерго­об'єктів //Вісн. Нац. ун-ту "Львівська політехніка". - 2003. - № 492. - C. 54-58. 6. Пат. 54718А Україна. Аналого-цифровий перетворювач інтегральних характеристик електричних величин / О.М. Дороніна, Г.М. Лавров, С.В. Хомич (Україна). - Опубл. в Бюл., 2003. - № 3. 7. Голуб В. Измерительные трансформаторы тока для счётчиков электроэнергии // Электронные компо­ненты и системы. - 2002. - № 12. - С. 32-35. 8. Валентик А. Прецизионные измерительные трансформаторы тока для электронных счётчиков электроэнергии // Электронные компоненты и системы. - 2004. - № 1. - С. 39-41. 9. Дороніна О.М., Лавров Г.М., Хомич С.В. Особливості контролю імпульсних сплесків та провалів сигналів промислової електромережі // Вісн. Нац. ун-ту "Львівська політехніка ". - 2004. - № 523. - C. 51-53.

УДК 004.92

Р.Б. Дунець, Т.М. Басюк

Національний університет "Львівська політехніка", кафедра електронних обчислювальних машин

ЗНАХОДЖЕННЯ ШЛЯХУ ОБХОДУ ВЕРШИН ДУГАМИ ПРИ ВІЗУАЛІЗАЦІЇ ТОПОЛОГІЙ НА ПЛОЩИНІ

© Дунець Р.Б., Басюк Т.М., 2007

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

In article the basic aspects which findings of points of detour concern at visualization of topology of computer's systems are analysed and the algorithm of their display in the graphs form is offered.

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

Топології комп' ютерних систем візуалізуються в системах автоматизованого проектування, як правило, у вигляді графів. Проблема полягає в тому, що одне й те саме зображення графа можна представити еквівалентними рисунками, різними за наочністю, проте однаковими за структурою зв'язків, яке суб'єктивно по-різному може сприйматися оператором [2, 3, 9]. Прийнято вважати [4], що зображення графів топологій комп'ютерних систем мають вищу наочність тоді, коли вони не містять перетинів дуг, або ж цих перетинів є мінімальна кількість, а самі дуги відображаються відрізками прямих.

Постановка задачі. Задача візуалізації графів складається з двох основних частин - роз­міщення вершин на площині та відображення дуг між ними, причому кожна з них безпосередньо впливає на вигляд майбутнього зображення графа, тобто на їх наочність [2, 3, 9]. Традиційно більше уваги було приділено розміщенню вершин на площині, і сьогодні вже створено достатньо ефективні методи та алгоритми [1, 5, 9]. Прокладанню дуг приділялася значно менша увага. Якщо, наприклад, дугами є відрізки кривих, то тоді, залежно від маршруту їх прокладання на площині від одної вершини до іншої, може змінюватися загальна кількість перетинів дуг.

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

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

Метод обходу вершин дугами. Після розташування вершин графу на площині та проведення парних їх перестановок [1], з метою зменшення кількості взаємних перетинань дугами, проводяться необхідні з'єднання вершин графу відрізками прямих. У результаті може виникнути ситуація, коли певна кількість дуг перетинає площу вершин, що не пов' язані з цими дугами або доторкаються до них. Очевидно, що такі вершини становлять певну перепону для прокладання з'єднань у вигляді відрізків прямих ліній. У таких випадках необхідно забезпечити обхід цими зв' язками вершин графу, замінивши відрізок прямої ламаною лінією чи сплайном (власне дугою), попередньо визначивши необхідні координати точки обходу вершини поза її межами. Тут виникає запитання - на якій відстані від границі зображення вершини графу повинна знаходитися точка обходу? З одного боку, ця відстань повинна бути не великою, щоб не виникало нових взаємних перетинів дуг, а з іншого боку, вона повинна бути достатньою, щоби візуально обхід не сприймався як торкання дуги краю площини вершини. Враховуючи, що найчастіше вершини графу топологій зображаються у вигляді кругів [3, 4], а також погляд вимог щодо

поліграфічного оформлення видань [8], у розробленому методі вважають, що ця відстань дорівнює ,

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

Як би не проходив перетин, точка обходу в розробленому методі виноситься за межі площі вершини в напрямку від центру кола вершини в бік відрізка прямої, причому перпендикулярно до того відрізка. У цьому випадку координати точки перетину визначаються відомими методами

геометрії, для чого необхідно просто задати кути і, ОС2 між горизонтальною віссю X та радіусом

кола, що з'єднують центр з точками перетину. Величина кута в між віссю X та відрізком, що з'єднує точку обходу і центр кола вершини, визначиться як:а2 -а,

а1 +—---, якщо 0 < а2 - а1 <п

а2 - а,

п + а1 +—--L, якщо п <а2 -а1 < 2п

(1)

(Xp, Yp)

Рис. 1. Варіанти перетину вершин

Після цього координати точки обходу (Xp, Yp) визначаться як:

Xp = X + d cose;

(2)

Yp = Y - d sin Є

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

Розглянемо конкретний приклад, який ілюструє роботу методу. Нехай маємо деяке зобра­ження графу в певній системі координат (рис. 2), в якому після розташування вершин та про­ведення всіх зв'язків відрізками прямих виявилося, що вершина за номером "3" перетинається одним зв'язком. Діаметр кола вершин цього графу дорівнює 7 мм.

3

Можна зауважити, що відрізок прямої перетинає центр вершини "3" під кутом —п до осі X,

4

а координати центру цієї вершини дорівнюють: X3 = 45,5 мм, Y3 = 24,5 мм.

3 7

Відповідно кути а1 та а2 дорівнюють: а1 = — п, а2 = 4 п . Враховуючи різницю цих кутів

3      1 5

а2 - а1 = п , визначимо згідно з (1) значення кута в , що дорівнюватиме: в = — п + — п = — п . Координати точки обходу визначаться згідно з виразом (2), а саме:

45,5 + 7 cos[^—J = 45,5 - 4,95 = 40,55 (мм), Yp = 24,5 - 7 sinf—) = 24,5 - (-4,95) = 29,45 (мм).

в

3,5    14   24,5    35   45,5    56    66,5   77 \(мм)

3,5

24,5

45,5 У

Y (мм)

Рис. 2. Приклад графу з перетином площини вершини Очевидно, обчислені координати точки обходу для зручності можна заокруглити до цілих

чисел.

Після проведення зв'язку у вигляді ламаної лінії через визначені координати точки обходу вершини зображення графу набуде вигляду, наведеного на рис. 3.

3,5 14 24,5 35 45,5 56 66,5 77 XjMM) п-1-1-7™^-г-7™^-1-1-

І-1

-1----1

І І І І І І

1-1

d

7

) J-

\o

-►Л

Л

 

"Y-

і—«

і—

~ 1 І

І І

і (X

І

S

Y )

У

 

 

/

 

 

"1 1 1

1

 

 

V

 

 

 

 

f

Y (mm)

Рис. 3. Граф після обходу вершини "3"

Треба зауважити, що після організації обходу вершини "3" з'явився новий взаємний перетин дуг, що є допустимим у зображенні графу.

Алгоритм відображення дуг графів. На рис. 4 наведено блок-схему алгоритму відобра­ження дуг графу, в основу якого покладено розроблений метод знаходження точок обходу дугами вершин графу та метод парних перестановок [1]. Тут також передбачається, що зв'язки графу топологій комп'ютерних систем описуються матрицею суміжності, а вершини розташовуються по ярусах так, як описано в роботах [1, 5].

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

Потрібно зазначити, що перетини вершин можуть бути відразу після проведення зв' язків відрізками прямих. Після проведення парних перестановок такі перетини можуть зникнути,

 

 

 

___ft

 

►Tf

 

 

 

 

----

—0.

vv

\

?

 

 

 

----

s

\

 

 

7

 

 

 

 

 

У

 

 

 

 

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

Г Початок 1

-1-2

Моделювання дугграфу відрізками прямих ліній

-*-3 -

Застосування методу парних перестановок

Так

Чи перетинають 4 ^ Ні дуги вершини ?

Визначеннякількості таких дуг граф а (p) i=1

6

Визначення координат точки „обходу" вершини і-ю дугою

І

Вилучення і-їдуги

І

8

Моделювання і-ї дуги як ламаної лінії чи сплайну

- 11

Виведеннясформованого зображення

12

Кінець

Рис. 4. Блок-схема алгоритму відображення дуг графу

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

5

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

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

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

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

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

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

1. Дунець Р.Б., Басюк Т.М. Метод розташування вершин деревоподібних графів на площині в процесі їхньої візуалізації//Вісн. Нац. ун-ту "Львівська політехніка". - 2006. - № 573. - С. 77-82. 2. Басюк Т.М. Аналіз та класифікація методів візуалізації // Поліграфія і видавнича справа. - 2003. -Вип. 40. - С. 109-114. 3. Дунець Р.Б. Аналіз та синтез топологій комп 'ютерних видавничо-полігра­фічних систем: НВФ "Українські технології". Львів, 2003. - 192 с. 4. Басюк Т.М. Критерії відобра­ження графів в процесі візуалізації // Наукові записки УАД. - 2004. - Вип. 7. - С. 60-63. 5. Басюк Т.М. Метод розміщення вершин графа в процесі візуалізації // Вісн. Нац. ун-ту "Львівська політехніка". -2004. - № 519. - С. 3-10. 6. Басюк Т.М. Метод зображення зв'язків між вершинами графа //Вісн. Тернопільського держ. техн. ун-ту. - 2005. - № 1. - С. 144-150. 7. ДСТУ 3018-95. Видання. Поліграфічне виконання. Терміни та визначення. - К.: Держстандарт України, 1995. - 30 с. 8. ДСТУ3772-98. Оригінали для поліграфічного відтворення. Загальні технічні вимоги. - К.: Держстандарт України, 1998. - 54 с. 9. Касьянов В.Н., Евстегнеев В.А. Графы в программи­ровании: обработка, визуализация и применение. - СПб. : БХВ, 2003. - 1104 с.

Страницы:
1 


Похожие статьи

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