5. Контрольні запитання та завдання

1. Які порядки сканування растрів Ви знаєте?

2. Дайте визначення, що таке «гомогенний блок».

3. Як відбувається розбиття растра на гомогенні блоки?

4. Наведіть приклад кодування квадродеревом.

5. У чому суть оверлейних операцій на квадродеревах?

6. Наведіть приклад індексування цифрової карти квадродеревом.

4 Алгоритми обчислювальної геометрії

План лекції. Перетин ліній. Операції з полігонами. Оверлей полігонів

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

1. Перетин ліній

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

Розглянемо найпростіший приклад: потрібно визначити, чи перетинається відрізок AB (4, 2) – (2, 0) з відрізком CD (0, 4) – (4, 0) і якщо так, то в якій точці? Для цього потрібно знайти рівняння прямих AB і CD і вирішити їх спільно (рис. 4.1, а). Рівняння прямої може бути знайдено за двома точками, через які вона проходить. Коефіцієнт нахилу прямої . Використовуючи будь-яку з точок, через які проходить пряма, знайдемо . Рівняння першої лінії , а другої лінії . Склавши два рівняння, отримаємо точку перетину (3, 1).

Рисунок 4.1– Точка перетину прямих: а) всередині відрізків; б) зовні

У загальному вигляді дві лінії, задані рівняннями та перетинаються в точці ; . Проте у такий спосіб можна знайти тільки точку перетину непаралельних ліній нескінченної довжини. Можливо, що відрізки не перетинаються, а перетинаються продовжені за цими відрізкам прямі (рис. 4.1, б). Відрізки перетинаються, якщо для точки перетину і точок A, B, C, D виконані умови:

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

Розглянемо тепер способи визначення перетину поліліній. Нехай є дві полілінії із та сегментами відповідно. Найпростішим способом знаходження їх точок перетину є послідовна перевірка перетину кожного сегмента першої лінії з кожним сегментом другої лінії. Складність цього алгоритму, пропорційна добутку , може бути зменшена за допомогою різноманітних евристичних алгоритмів. Хоча в цих алгоритмах потрібні додаткові кроки обробки і, можливо, структури даних, загальна трудомісткість алгоритму знижується. Розглянемо деякі з таких методів. Складність алгоритму обчислення перетину поліліній може бути знижена, якщо попередньо перевіряти на перетин мінімальні обмежуючі прямокутники поліліній. Ці прямокутники визначаються мінімальними і максимальними координатами x і y. Дві полілінії не перетинаються, якщо не перетинаються їх обмежують прямокутники. Можна застосувати цей підхід і для визначення перетину окремих сегментів поліліній. Два відрізка AB і CD не перетинаються, якщо не перетинаються інтервали і чи не перетинаються інтервали і .

Наступний метод, вперше використаний в ГІС ArcInfo, заснований на розбитті полілінії на секції, в яких лінія монотонно зростає або зменшується за x та за y (рис. 4.2, а). Розбиття відбувається в точках локального мінімуму або максимуму за x або за y. Горизонтальна або вертикальна лінія перетинає таку секцію тільки в одній точці. Це дає можливість зменшити трудомісткість алгоритму пошуку перетину поліліній. Якщо для двох секцій знайдена точка перетину, не потрібно перевіряти пари точок, що залишилися, тому що цей перетин єдиний за умови, що другі похідні в секціях не змінюють знак. Це обмеження може бути вирішено або розбивкою секції в критичних точках, або повним перебором пар сегментів для таких секцій.

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

Рисунок 4.2 – Оптимізація алгоритму визначення перетину поліліній, заснована на розбитті на монотонні секції: а) розбивка на секції, б) різні варіанти перетину секцій; в) схема визначення точки перетину секцій