Алгоритми на квадродеревах
Розглянемо тепер деякі алгоритми ГІС на квадродеревах: обчислення площі, оверлейний алгоритм і алгоритми визначення суміжності комірок. Щоб визначити площу комірок з деяким значенням в растровому шарі, необхідно обійти дерево і підрахувати кількість комірок, кодованих цим значенням, зважене площею комірки на даному рівні дерева. Обчислимо, наприклад, на карті 1 (рис. 3.6) площу комірок зі значенням "A". Площа SA = 1 * (Count leaf (00,02,03,32)) 4 * (Count leaf (2)) = 8.
Рисунок 3.6 – Оверлейна операція на квадродереві
Оверлейна задача на квадродереві полягає в поєднанні квадродерев двох карт і отриманні нового квадродерева. Для цього потрібно одночасно обійти обидва дерева, слідуючи гілкам, існуючим в обох деревах. У тих вузлах, де в одного з дерев буде відсутнє розгалуження, значення атрибуту переноситься на всі наступні підрівні. У результаті утворюється "широке" дерево, що містить обидва атрибуту (рис. 3.6). Багато операцій ГІС, що працюють з ієрархічними структурами даних, вимагають наявності способів визначення суміжності комірок. Для цього будемо використовувати представлення координат комірок у системі числення з основою 4 і розділяти біти так, як це робилося в скануванні растру за Мортоном. При цьому використовується tesseral-арифметика, в якій перенесення між розрядами здійснюється через дві позиції. Наприклад, різниця 1000 – 1 = 0010, а сума 1 + 0001 = 0100. Будемо розрізняти два випадки: коли комірки, які перевіряються мають коди однакової і різної довжини. Блоки однакового розміру є суміжними, якщо їх подання до tesseral – арифметики відрізняються на 1 або 10. Наприклад, блоки 01 і 03 є суміжними, так як 0011 – 0001 = 10. Блоки 033 і 211 також суміжні, так як 001 111 + 10 = 100 101. Блоки 01 і 30 не є суміжними, так як 1100 – 0001 = 1001. Для визначення суміжності блоків різного розміру коди приводяться до основи 2. Далі з кодом більшої довжини підсумовуються ± 01 і ± 10. З одержаних чотирьох кодів відкидаються як неможливі всі негативні (за переносом). Решта кодів переносом вправо зводяться до меншої довжини. Два блоки є суміжними, якщо трансформований і обрізаний код більшої довжини дорівнює короткому коду. Наприклад, потрібно визначити, є комірки 02 і 2 суміжними. Наведемо коди в двійковій системі 024 = 00102 , 24 = 102. Додамо до довгого коду ± 01 і ± 10. Отримаємо 0010 +1 = 0001, 0010 +10 = 1000, 0010-10 = 0000. Різниця 0010-1 негативна, ця комбінація відкидається як неможлива. Вибравши два старших розряди з решти результатів, отримаємо коди 002=04 и 102=24. Один з одержаних кодів дорівнює короткому коду, тому комірки 2 і 02 є суміжними.
Просторові індекси
У векторних ГІС просторові індекси використовуються для більш швидкого доступу до об'єктів на певній ділянці карти. Індексування просторових об'єктів дозволяє зменшити обчислювальну складність процедур пошуку вкладених об'єктів та об'єктів, що перетинаються, тому індекси є важливою частиною алгоритмів оверлея полігонів. Процес побудови індексу для цифрової карти включає наступні кроки. Спочатку для кожного об'єкта бази даних знаходиться найменший лист квадродерева, що повністю включає об'єкт. Деякі великі об'єкти можуть лежати більш ніж в одному квадранті першого рівня квадродерева. У цьому випадку об'єкти позначаються значенням "NULL". Інші об'єкти позначаються кодом листа, який належить квадродереву. Потім об'єкти сортуються за зростанням отриманого ключа, а сам індексний файл у свою чергу індексується звичайним способом (рис. 3.7). Побудовані таким способом індекси використовуються для пошуку об'єктів, які перетинають заданий полігон або лінію. Для цього визначається мінімальний лист квадродерева, що включає заданий об'єкт. Піднявшись з отриманого вузла до вершини дерева і виконавши обхід піддерева, коренем якого є цей вузол, отримуємо список листя дерева, всередині яких об'єкти можуть перетинатися із заданим об'єктом. Очевидно, просторові індекси, побудовані на квадродеревах, більш ефективні в порівнянні з незалежним впорядкуванням об'єктів по x та y, так як в цьому випадку враховується просторовий характер даних. Індексування квадродеревами найбільш доцільно для дрібних об'єктів (особливо для точок). Великим об'єктам зазвичай відповідають великі блоки. Для них часто потрібно визначати перетин з іншими об'єктами.
Рисунок 3.7 – Індексування цифрової карти квадродеревом
Проблему індексації великих об'єктів можна вирішити з використанням R-дерев (R – rectangle, прямокутник), в яких також використовується концепція мінімального прямокутника, який вміщує об’єкт. Тобто потрібно знайти два таких прямокутника, всередині яких розташоване максимально можлива кількість об'єктів. При цьому потрібно прагнути, щоб кількість об'єктів у прямокутнику має була приблизно однаковою. Прямокутники можуть перетинатися, але площа перетину повинна бути настільки малою, наскільки можливо. Далі ця процедура рекурсивно повторюється (рис. 3.8).
Рисунок 3.8 – Індексування цифрової карти R-деревом