Візуалізація в ГІС при наявності просторових обмежень

Л.К. Самойлов, С.Л. Беляков, М.П. Сидоренко

Взаємодія користувача з геоінформаційної системи (ГІС) здійснюється найчастіше в діалоговому режимі. Суть діалогу полягає у формуванні запитів серверу ГІС і отриманні відповідей у вигляді картографічних зображень. Ефективність діалогу визначається швидкістю регенерації зображення на екрані при переході між локальними ділянками електронної карти. Дана швидкість в значній мірі залежить від числа примітивів, що описують відповідь на запит користувача. Тут передбачається, що електронна карта представлена в векторному форматі, найбільш поширеному в ГІС.

Як показав аналіз, відповіді сервера ГІС містять надлишкові примітиви. Їх поява обумовлена тим, що результат виконання запиту є картою, яка містить крім безпосередньо примітивів обраних об'єктів опис навколишнього їх простору. Наскільки широко останнім опис (і відповідне кількість примітивів) залежить від подання карти. У простому випадку відповідь включає в себе повністю карту, в складних ГІС - набір фрагментів (наприклад, стандартних геодезичних планшетів), що становлять загальну карту системи.

Питання про те, які примітиви у відповіді сервера вважати надлишковими, вирішується користувачем. ГІС повинна надавати кошти опису примітивів, які є суттєвими в відповіді сервера на запит користувача. У даній роботі аналізується один з можливих варіантів опису суттєвості - через просторові обмеження.

У загальному вигляді під завданням візуалізації будемо розуміти наступне: є безліч примітивів вихідної карти G, в результаті виконання деякої процедури отримано безліч R G примітивів відповіді на запит. Потрібно знайти безліч примітивів E GR таке, що | E | < img src = "http://localhost/uploads/posts/2009-10/1255892767_Vizualizaciya_v_GIS_pri_nalichii_prostranstvennyh_ogranicheniiy_1.gif" alt = "" width = "20" height = "16" /> min.

Всі просторові обмеження можна класифікувати за кількома ознаками. Так з точки зору користувача просторові обмеження описують:

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

просторову околиця для кожного примітиву gi R, попадання в яку будь-якого іншого примітиву gk R, ( k i) є критерієм віднесення його до безлічі E. Даний вид обмежень ефективний, наприклад, в задачах, пов'язаних з комунікаціями: просторова околиця трубопроводу, дороги, енергомережі значно менше простору, які вони охоплюють;

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

просторову околиця для об'єктів - деяких смислових об'єднань примітивів. Прикладом можуть служити будівлі і споруди, території, землі. Кордон околиці в цьому випадку визначається як описує багатокутник об'єкта;

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

З точки зору способу уявлення описують контурів, всі просторові обмеження можна класифікувати на:

1) обмеження, задаються окружностями:

Як видно з рис.1 координати примітивів безлічі E для кола повинні задовольняти умові:

, (1.а)

. (1.б)

де x0, y0-центр кола, навколо якого вводиться просторова околиця, r - радіус кола, d -- довжина просторової околиці, x, y -- координати розглянутого примітиву.

примітив, який потрапив у просторову околиця заданого об'єкта (примітиву) може мати більшу просторову протяжність. Отже, має сенс розрізати його у точці перетину з обмежує колом. Тому пропонується наступний порядок відбору примітивів. Спочатку координати примітиву аналізуються на виконання відповідної умови (1.а) або (1.б). Якщо умова виконується, то вважається, що примітив належить безлічі E. В іншому випадку аналізується варіант перетину примітиву та кола, отриманої за нерівності (1.а) або (1.б) відповідно. Якщо і ця умова не виконується, то примітив виключається з розгляду, інакше примітив розрізається в точці його перетину з обмежує колом, і залишилася в просторової околиці частина примітиву приписується до безлічі E. Відповідний алгоритм розрізання описаний в [3].

2) обмеження, задаються еліпсами:

Координати примітивів безлічі E для еліпса повинні задовольняти таким умовам:

, 2.а)

. (2.б)

де x0, y0 -- центр кола, навколо якого вводиться просторова околиця, a, b -- велика і фокальна півосі описуваного еліпса відповідно, d -- довжина просторової околиці, x, y -- координати розглянутого примітиву.

Як видно з порівняння формул (1.а, 1.б) і формул (2.а, 2.б), завдання просторових обмежень еліпсами аналогічно попередньому випадку, тому тут все справедливо вищесказане по відношенню до обмежень колами.

3) обмеження, задаються дугами кіл:

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

, (3)

де C = (x0, y0) - центр дуги, навколо якій вводиться просторова околиця,

r - радіус дуги,

d-довжина просторової околиці,

x, y -- координати розглянутого примітиву,

A - точка, розташована на початку дуги,

B - точка, розташована в кінці дуги,

D - точка, розташована на одній осі з точкою 'C' зі зміщенням

вправо, наприклад (x0 1, y0).

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

4) обмеження, задаються довільними багатокутниками:

Як видно з рис.4-5 багатокутник, що описує просторову околиця, не може бути отриманий простим масштабуванням вихідного контуру (контуру, що описує заданий об'єкт) з двох причин:

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

b) сторони багатокутника, що описує просторову околицю, як демонструють рис.4 і рис.5, обмежені дугами кіл на внутрішніх кутах, менших .

Виходячи з цих причин, пропонується наступний алгоритм, який враховує всі особливості перетворення контурів. Суть алгоритму полягає в наступному:

З вихідного безлічі вершин P (| P | = N) контуру, що описує заданий об'єкт, будуються рівняння прямих (відповідні формули широко висвітлюються в усіх друкованих виданнях з машинної графіки та аналітичної геометрії, наприклад, в [1-4 ]).

Згідно з результатами, отриманими в попередньому пункті, будуються рівняння прямих багатокутника, задає просторові обмеження. Дані прямі зміщені в напрямку від контуру об'єкта (див. випадок, зображений на рис. 5) і до контуру об'єкта (див. 4). Рівняння прямих, паралельних ребрах багатокутною контуру, можна побудувати за [4].

За формулою, аналогічною (1.б), визначаються нерівності, що обмежують відрізки отриманого багатокутника в його кутах.

Визначається безліч V1 точок перетину сусідніх відрізків і безліч V2 точок перетину відрізків і відповідних кіл, отриманих з нерівностей на кроці 3.

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

У результаті, будь-який примітив, потрапляє в околиці об'єкта, повинен задовольняти хоча б одній з умов:

примітив потрапляє або перетинає багатокутник, складений з вершин множини V;

координата примітиву задовольняє одному з умов нерівностей, отриманих з нерівностей на кроці 3.

Якщо примітив перетинає контур просторової околиці, то його необхідно розрізати в точках перетину, користуючись узагальненими на випадок розрізає примітиву алгоритмами розрізання довільної прямої довільним багатокутників. Дані алгоритми описані в [1] і [2], а більш повний аналіз наведено в [3]. Уявімо результати аналізу таких алгоритмів, наведені в [3].

Таблиця 1.

Розрізання відрізків прямий багатокутний вікном             

Назва методу            

Вікно            

Елементарна операція            

Складність                 

Сазерленд (дихотомічний варіант)         

Прямокутне         

Порівняння положення точки та контуру (з   кодуванням)   

Обчислення середини відрізка         

O (Log2 (розмір відрізка))             

Сазерленда-Коена         

Прямокутне і опукле         

Кодування точки щодо контуру   

Обчислення точки перетину відрізків прямих         

O (2n),   

де n - число ребер контуру             

Павлідіса         

Прямокутне і опукле         

Порівняння точка-відрізок (однорідні   координати)   

Обчислення точки перетину відрізків прямих         

O (n)             

Простежування контуру         

довільної форми         

Порівняння положення точки по відношенню до   прямий   

Перетин прямої з відрізком другий прямий         

O (n)     

Як видно з таблиці 1, при розрізанні відрізка багатокутний довільним контуром необхідно користуватися алгоритмом простежування контуру. Ж. Егрон відзначає, що в приватному випадку, коли вікно має форму прямокутника, метод Сазерленд (дихотомічний варіант) найкращим чином пристосований для реалізації на жорсткій логіці. У іншому випадку апаратна реалізація на програмованому пристрої краще узгоджується з алгоритмом Павлідіса, причому ступінь переваги визначається характеристиками сцени (вмістом у ній вершин і горизонтальних ліній). Отже, якщо багатокутник опуклий, то доцільно користуватися більш спеціалізованими алгоритмами, наприклад алгоритмом Павлідіса [2,3]. Якщо ж багатокутник являє собою прямокутник, сторони якого паралельні осях координат (далі по тексту просто "прямокутник"), то процес визначення факту знаходження примітиву в багатокутнику просторової околиці зводиться до елементарних операцій порівняння координат і обчислення середини відрізка.

Проведемо порівняльний аналіз варіантів опису просторової околиці. Оцінку способів уявлення описують контурів будемо проводити з точки зору часу формування просторової околиці Tф. Процес формування просторової околиці можна розділити на кілька складових:

побудова рівнянь обмежень;

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

Час Tур, що витрачається на ГІС побудова рівнянь обмежень, розрізняється для кожного із способів. Так при побудові рівнянь кіл (1.а, 1.б) витрати часу мінімальні по порівнянні з іншими методами. Для другого і третього способів витрати часу майже не відрізняються від перших, тому що кількість проведених обчислень (ініціалізації відповідних коефіцієнтів у рівняннях 2.а, 2.б, 3) зневажливо мало. По-іншому йде справа з формуванням рівнянь обмежень довільними багатокутниками. Як видно із запропонованого алгоритму, процес формування багатокутників контуру просторової околиці займає деякий, що значно перевищує для перших трьох випадків, час. І чим більше вершин містить описуваний контур, тим більший проміжок часу займає цей процес. Таким чином, співвідношення часів, що витрачаються на побудову рівнянь обмежень, має такий вигляд:

Tур1