Область наук:
  • Математика
  • Рік видавництва: 1998
    Журнал: Известия Південного федерального університету. Технічні науки

    Наукова стаття на тему 'Аналіз алгоритмів розбиття геодезичної карти на елементи'

    Текст наукової роботи на тему «Аналіз алгоритмів розбиття геодезичної карти на елементи»

    ?ня сервера геоінформаційної системи. У їх функції входить отримання уявлення (1) при зміні параметрів виразів (3) і (4), знаходження сукупності ЕК, "покриває" задану область карти.

    Наведені результати можуть використовуватися для одиночних ЕОМ. Роль клієнта і сервера в цьому випадку грає графічний редактор ГІС. Параметри, що входять в (3) і (4), можуть бути визначені експериментальним шляхом.

    ЛІТЕРАТУРА

    1. Малишев С. Новий картографічний порядок. Комп'ютер-прес, 8/96.

    2. Міллер С., Сорокін А. Вибір програмних і технічних засобів ГІС. Компьютерра. 21/96.

    УДК 519.85

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

    АНАЛІЗ алгоритму розбивки ГЕОДЕЗИЧНОЇ КАРТИ НА ЕЛЕМЕНТИ

    Геоінформаційні системи (ГІС) знаходять все більш широке застосування в областях контролю і управління - будь то система міського господарства або пожежна служба. ГІС - це програмно-апаратний комплекс, призначений для збору, управління, аналізу і відображення просторово-розподіленої інформації [1]. За характером домінуючих запитів все ГІС класифікуються на:

    - ГІС з неравновероятнимі зверненнями до різних частин геодезичної карти;

    - ГІС, в яких переважають запити вибору семантично пов'язаних примітивів (об'єктів);

    - ГІС, в яких переважають запити вибору семантично незв'язаних примітивів;

    - ГІС з рівноімовірними зверненнями до різних частин геодезичної карти.

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

    Нехай Рк - число примітивів карти, тоді необхідно розбити геодезичну карту на N елементів таким чином, щоб:

    1) число примітивів Ре, що належать кожному елементу, не перевищувало Рк / ^ т. Е. ( "Ре) (Ре? Рк / ^;

    2) ніякі два елементи і Ej (1Ф], 1,] = 1, N) не перетиналися б між собою, т. Е. ( "Е1,1 = 1, N) (" Е],] = 1, N) (1 Ф] ® (Е1П Е] = 0));

    3) всі безліч елементів покривало б геодезичну карту, тобто.

    якщо прийняти весь простір геодезичної карти за G, то Ei = G.

    і = 1, N

    У даній статті аналізуються алгоритми, вирішальні завдання розбиття.

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

    - пористі алгоритми;

    - об'єктні алгоритми;

    - адаптивні алгоритми.

    До пористих алгоритмам відносяться алгоритми розбиття геодезичної карти на елементи, в основу яких покладено поняття осередку. Осередок - це семантично незалежна частина геодезичної карти, що отримується в результаті розмітки всього простору геодезичної карти на N1 рядів по N2 осередків в кожному. Прикладом осередків виступають геодезичні планшети в масштабі 1: 500. Осередки можуть об'єднуватися для отримання макроячеек-елементів. Перевага таких алгоритмів полягає в простоті їх опису, відносно малому числі точок, що описують елементи, і в якості обробки.

    Для прикладу наведемо два пористих алгоритму - алгоритм, який визначає розмір комірки по найбільш щільному ділянці карти (алгоритм 1.1) і алгоритм адаптивного визначення макроячейки (алгоритм 1.2). В алгоритмі 1.1 спочатку задається розмір sd сітки щільності. Потім, визначивши центр "C" найбільш щільного (з точки зору числа примітивів на одиницю площі) ділянки геодезичної карти і розмір осередку з центром "C", що містить P ^ P ^ N примітивів, алгоритм 1.1 розмічає всю карту на осередки. Далі цей алгоритм об'єднує сусідні осередки так, щоб кожна з отриманих таким чином макроячеек неохоплювала більш P ^ Pg / N примітивів, і формує елементи.

    алгоритм 1.1.

    Begin

    Dm = 0

    У = 0

    yy = sd / 2

    While yy< ymax do x = 0, xx = sd / 2 While xx< xmax do

    D = BибopCeкOкнo x, yy, x + sd, yy)

    D = D + BибopCeкOкнo xx, y, xx, y + sd)

    If D>Dm then Dm = D

    C- xx, yy) x = x + sd xx = xx + sd y = y + sd yy = yy + sd

    Визначити розмір осередку dxd), oхвативающeй P ^ P ^ N прими-тівoв, з цeнтpoм C y = 0, x = 0 ВЕ = Pк / N

    While y< ymax do

    Б = ВиборСекОкно x, y, x + d, y + d) x = x + d

    While x< xmax) and Б Ф 0) do Т = ВиборСекОкно x, y, x + d, y + d)

    If Т + Б< Ре

    then Б = Б + Т x = x + d

    else Сформувати елемент Б Б = 0

    If БФ 0 then Сформувати елемент Б x = 0 y = y + d

    End

    Тут xmax - довжина геодезичної карти, а ymax - ширина (висота) геодезичної карти. Операція "ВиборСекОкно (х1, у1, Х2, у2)" означає вибір примітивів, що потрапляють у вікно (xi, yi, Х2, У2) або перетинають його. Операція "Визначити розмір осередку, що охоплює Ре = Рк / М примітивів (dxd) з центром C» не деталізується.

    Алгоритм 1.2 визначає макроячейки без попереднього формування осередків.

    алгоритм 1.2.

    Begin

    y = 0

    dmin ymax Ре = Рк / М

    While dmin< ymax do

    x = 0

    While x< xmax do

    Визначити розміри осередку x, y, x + d, y + d), що охоплює Ре примітивів

    Б = ВиборСекОкно x, y, x + d, y + d)

    Сформувати елемент Б If dmin>d then dmin = d x = x + d y = y + dmin

    If dmin< ymax then dmin = ymax

    End

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

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

    алгоритм 2.1.

    Begin

    ВЕ = Pк / N

    type = 1

    While typeФ 3 do

    While O - Bli6op не пустили) do K - ^ нтур O)

    If K- замкнутий) and type = 1)) or K- незамкнутого) and type = 2))

    then

    B = Oб'eм K)

    While B< P.3 do

    Oпpeдeліть No - чіcлo oб'eктoв Oi, i = 1, No, що перетинаються кoнтypoм K i = 1

    If i < No then Ki - Koнтyp Oi)

    Ki - Ki / Ki П K)

    T = Oб'eм Ki)

    If B + T<ВЕ then K - K U Ki B = B + T i = i + 1 K '- K + d T = Oб'eм K')

    If T< ВЕ then K - K '

    B = T

    else

    Cфopміpoвать елемент B B = B + 1

    Виключити oб'eкт O з pаccмoтpeнія type = type + 1

    Oтмeніть виняток oб'eктoв If $ примітив) then ал ^ ритм 1 2 End

    Операція "Вибір" здійснює вибір першого-ліпшого об'єкта. Операція "Контур ^)" означає визначення контуру об'єкта x. Операція "Обсяг ^)" означає підрахунок числа примітивів, що входять або

    перетинають контур x. Операція "A U B" означає об'єднання списків A і B, а операція "A Про B" - перетин списків A і B.

    Адаптивні алгоритми застосовуються тільки на етапі експлуатації ГІС. Під адаптацією розуміється виділення найбільш часто запитуваних ділянок геодезичної карти в окремі цілісні елементи. Прикладом алгоритмів даного типу є сенсорний алгоритм (3.1). Ідея цього алгоритму полягає в наступному. На весь простір геодезичної карти "накидається" сенсорна мережа. Під ij-сенсором розуміється прямокутник i-го ряду j-й колонки (i = 1, N1, j = 1, N2) сенсорної мережі, що відображає частину геодезичної карти, до якої користувач звертається із запитом. Після R звернень до ГІС сенсорний алгоритм приступає до переразбіеніе геодезичної карти. Прийнявши максимальний по числу звернень сенсор за материнський, алгоритм 3.1 приєднує до материнського найбільш часто використовувані сусідні сенсори до тих пір, поки число належать формованому елементу примітивів не досягне Ре = Рк / №

    алгоритм 3.1.

    Begin

    NR = NR + 1

    If mod NR / R) Ф0 then Sxmin = \ X1 • N 2]

    Sxmax = \ X2 ^ N21 Symax = \ У2 ^ N11 Sy = \ yi • Ni1 While Sy < Symax do

    j Sxmin

    While j < Sxmax do

    S Sy] j] = S Sy] j] +1 j = j + 1 Sy = Sy + 1

    else D - S SN = 0

    SS - SSS - порожній список While SN<N ^ N2 do

    DD - порожній список

    SN = SN + 1

    SS - Вибір D)

    Б = Обсяг SS)

    While Б< Pк / N) and D не пустили) do SSS - ВиборСосед D)

    Т = Обсяг SSS)

    If Т + Б< Pк / N then SS - SS U SSS

    Б = Б + Т SN = SN + 1 else

    DD - DD U SSS Сформувати елемент SS DD U DD

    End

    Тут x1, У1, x2, У2 - координати вікна вибору користувача, S - матриця сенсорів. Операція "mod (x / y)" означає взяття залишку від ділення x на у. Операція "Вибір ^)" означає вибір максимального за значенням сенсора зі списку x з подальшим записом -1 як значення обраного сенсора в список x. Операція "ВиборСосед ^)" означає вибір максимального за значенням сенсора, сусіднього з сенсорами списку x, з подальшим записом -1 як значення обраного сенсора в список x. Операція "A і B" означає об'єднання списків A і B.

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

    1

    q = tp:

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

    q3.1 > q1.1, q3.1 > qo, q3.1 > q2.1.

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

    q2.1 > q1.1, q2.1 > q1.2, q2.1 > q3.1.

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

    З точки зору часу роботи все алгоритми є алгоритмами з поліноміальних часом, т. Е. Час виконання кожного алгоритму, залежне від заданих Рк і N, обмежена зверху деяким поліномом ^ P ^ N). Нехай часи роботи алгоритмів обмежуються зверху полиномами:

    - для алгоритму 1.1

    !0 (РКД, в ^ = j (sd) + tяч + tLrN, (1)

    де j (sd) - час пошуку центру найбільш щільного (з точки зору числа примітивів на одиницю площі) ділянки геодезичної карти;

    tOT - час визначення розміру осередку;

    t1.1 - середній час формування осередку алгоритмом 1.1;

    - для алгоритму 1.2

    ^ .2 (РКД) = t1.2 * N, (2)

    де ^ .2 - середній час формування осередку алгоритмом 1.2;

    - для алгоритму 2.1

    {; І (РКД) = ^ Гі, (3)

    де ^ 2.1 - середній час формування осередку алгоритмом 2.1;

    - для алгоритму 3.1

    !З.1 (РКД) = 1з.1гІ, (4)

    де ^ З.1 - середній час формування осередку алгоритмом 3.1.

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

    Нш / 1.1 (Рк, N, sd) ® ?.

    й ® 0

    Порівняльний аналіз часу роботи алгоритмів, як видно з формул (1) - (4), потрібно виробляти за величинами 1 - часу формування осередку. Так як, в свою чергу, час формування осередку

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

    цього параметра алгоритмів, співвідношення між значеннями величин 1 наступне:

    11.1 < 13.1 << 11.2 < 12.1.

    Якщо інтервал між вузлами сітки щільності в алгоритмі 1.1 приблизно дорівнює ширині осередку, то ф (б ^ »^. ^ І. З огляду на, що 1яч = ^ 1.2, можна отримати наступне співвідношення:

    !3.1 (Рк, І) < !1.1 (Рк, І, ва) < !про (РКД) < !2.1 (Рк, І).

    З точки зору використовуваної оперативної пам'яті, алгоритми знаходяться в наступній залежності:

    ^ 3.1 < ^ .2 < ^ 2.1 < ^ 1.1.

    Алгоритм 3.1 менше інших використовує оперативну пам'ять через те, що це найбільш простий, з точки зору числа операторів, алгоритм. За даними, що використовуються алгоритмами, найбільш вимогливі адаптивні, що збирають специфічну інформацію під час експлуатації ГІС. Алгоритми 1.2 і 2.1 аналогічні за винятком того, що об'єктні алгоритми додатково використовують семантику примітивів.

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

    1. якщо створюється система з неравновероятнимі зверненнями до елементів, то необхідно спочатку використовувати алгоритм 1.2 (або 2.1) для розбиття геодезичної карти, а під час експлуатації ГІС використовувати сенсорний алгоритм.

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

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

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

    ЛІТЕРАТУРА

    1. Малишев С. Новий картографічний порядок. Комп'ютер-ПРЕСС. № 8. 1996. УДК 512.85

    АН. Цілих, Р.П. Тимошенко ОЦІНКА ЕКОЛОГІЧНОЇ ОБСТАНОВКИ НАВКОЛИШНЬОГО СЕРЕДОВИЩА НА ОСНОВІ АНАЛІЗУ ЗНАНЬ ЕКСПЕРТІВ

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

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

    Перед експертами ставиться умова опитування, згідно з яким вони повинні оцінювати навколишню обстановку. Як приклад умови вибираємо "дуже небезпечна ділянка". Експерт повинен самостійно, на підставі власного досвіду і знань оцінити екологічну обстановку на ділянці і прийняти рішення про адекватність ділянки умові опитування. Експертам пропонувалося для кожної ознаки ділянки провести оцінку важливості цієї ознаки при виборі ділянки, що відповідає умові опитування. Наступним кроком є ​​оцінка сумісності ознаки з ділянкою дослідження. Один і той самий ознака може мати різні значення при заданому умови для різних експертів. Це залежить від знань експерта. Використання експертів обумовлено тим, що інформація представлена ​​в нечіткій формі. Використовується кілька експертів для виключення отримання узгодженої оцінки стану об'єкта. Для даної моделі вважаємо, що експерти мають однакову кваліфікацію і їх знань можна довіряти з рівною мірою достовірності. Це припущення робиться для того, щоб при оцінці об'єкта думки експертів мали однакову вагу. Основу методу дослідження становить теорія нечітких множин. У статті використано математичний аппа-


    Завантажити оригінал статті:

    Завантажити