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

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

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

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

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

У загальному вигляді під завданням візуалізації будемо розуміти наступне: є безліч примітивів вихідної карти G, в результаті виконання деякої процедури отримано безліч R G примітивів відповіді на запит. Потрібно знайти безліч примітивів E GR таке, що | E | < img src = "http://localhost/uploads/posts/2009-10/1255913826_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

де Tурi - Час формування рівнянь обмежень i-м () способом уявлення описують контурів.

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

Tа1

де Tаi - Час аналізу та розрізання примітивів для формування просторової околиці i-м () способом представлення описують контурів.

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

Tпр

де Tпр - час аналізу та розрізання примітивів для формування контуру просторової околиці представленої прямокутником.

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

Tпр

Нерівності (4) і (7) описують співвідношення часів, що складають процес формування просторової околиці:

Tф = Tур + Tа. (8)

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

Tпр + Tур4

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

Tф.пр

де Tфi - Час формування просторової околиці i-м () способом уявлення описують контурів,

Tф.пр - час формування просторової околиці за допомогою прямокутника,

Tф.мн - час формування просторової околиці за допомогою довільного багатокутника.

Як видно з (10), найбільш переважними з точки зору часу формування просторової околиці є перші три способи представлення описують контурів (див. класифікацію за способами подання описують контурів) і особливо спосіб формування просторової околиці за допомогою прямокутника, сторони якого паралельні осям координат. Виходячи з цих позицій, надзвичайно привабливо апроксимувати контур об'єкта прямокутником, колом або еліпсів і задати просторові обмеження за допомогою відповідних рівнянь. Але це "огрубіння" в результаті веде до появи примітивів, які не повинні потрапляти в безліч E примітивів просторової околиці. Тобто апроксимація контуру об'єкта приводить до появи надмірності результату, яка напряму залежить від "ступеня огрублення "цього контуру. Завдання полягає в тому, щоб визначити: чи можна апроксимувати контур об'єкта таким чином, щоб час формування результату з аппроксіміруемим контуром не перевищувало часу формування результату з початковим (неаппроксімірованним) контуром. Таку постановку завдання можна узагальнити наступним чином: необхідно визначити, чи не перевищить час формування результату заданого значення:

Tдоп = Tф + Tпр, (11)

де Tдоп - передбачуваний час формування результату при побудові обмежень для об'єкта з початковим контуром,

Tпр, - час, що витрачається системою на пошук об'єкта, промальовування і пр.

Поставлену задачу пропонується вирішити через визначення передбачуваного часу формування просторової околиці заданого об'єкту:

Tф Tдоп-Tпр, (12)

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

,

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

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

Таким чином, на підставі проведеного аналізу можна стверджувати, що найбільш ефективними способами подання описують контурів є обмежень, що задаються прямокутниками, колами і еліпсами. За допомогою обмежень, що задаються довільними багатокутниками, можливо гнучке опис просторової околиці будь-якої форми. Апроксимація ж прямокутником, колом і еліпсів дозволяє істотно знизити тимчасові витрати на формування околиці. Апроксимація можлива тільки в тих випадках, коли час формування просторової околиці (визначене за формулою 8) задовольняє умові (12).

Список літератури

Павлідіс Т. Алгоритми машинної графіки та обробки зображень: Пер. З англ. - М.: Радіо і зв'язок, 1986.

Фолі Дж., ДЕМ А. Основи інтерактивної машинної графіки: У 2-х книгах. Пер з англ. - М.: Світ, 1985.

Егрон Ж. Синтез зображень. Базові алгоритми: Пер. з франц. - М.: Радіо і зв'язок, 1993.

Бугров Я.С., Никольский С.М. Елементи лінійної алгебри та аналітичної геометрії: Підручник для студентів інж.-техн. спец. вузов .- 3-е изд., испр. і доп., М.: Наука, 1988.