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

До задач обчислювальної геометрії що застосовуються в ГІС відносять аналіз близькості та зонування території

Аналіз близькості – це пошук об'єктів, що лежать на визначеній відстані від початкового об'єкта або знаходження найближчих об’єктів до объекту – джерела.

1) Класична задача про поштові відділення є однією з перших задач обчислювальної геометрії.

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

2) Є план міста з нанесеними на нього місцями розміщення пожежних частин. Знайти найближчу до кожного дому пожежну частину.

Зонування території – встановлення області обслуговування (інш. сл. поділ на сфери впливу)

Наприклад,

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

2) визначення ареалів поширення даних спостережень мережі метеорологічних станцій, нерівномірно розміщеній у межах розглянутої території.

Математично подібні задачі формулюються так.

На площині задано множину з точок «центрів». Потрібно для кожної точки визначити область таку, що для будь-якої точки -ї області відстань до була менша ніж до будь-якої іншої з множини .

Такі задачі розв’язуються шляхом розбиття території на полігони Тіссена – Вороного.

Полігони Вороного розділяють територію на області близькості до заданих точок.

Діаграма Вороного.

Діаграма Вороного (полігони Тіссена) для системи точок – це многокутник, утворений відрізками перпендикулярів, проведених до середин сторін, що сполучають дві найближчих сусідніх точки.

Наприклад для двох точок–«центрів», області найближчих точок буде розділяти пряма відстань від якої до «центрів» буде однакова. Очевидно, що пряма буде проходити через середину відрізка і до нього. (Рис). Для 3-х центрів отримаємо вже 1-ну точку перетину. Для більшої кількості точок отримаємо щось схоже на (нерегулярну) стільникову структуру.

Всі ми дивуємося коли дивимось на рамку з сотами як бджоли їх ліплять з такою точністю.

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

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

Крім того диаграмма Вороного позволяет создавать максимально крепкие структуры с использованием минимального количества материала. Тому метод этот часто используется в инженерных справах

Діаграму Вороного будувати просто, якщо перед цим була виконана тріангуляція Делоне.

(нагадаємо означення)

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

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

Кожна область Вороного будується з'єднанням серединних перпендикулярів у вихідних трикутниках тріангуляції. В цьому розумінні діаграма Вороного і тріангуляція Делоне є взаємно двоїстими. Рис.

Таким чином кожна вершина многокутника є перетином серединних перпендикулярів трикутника тобто є центром описаного кола. Це є внутрішні вершини діаграми Вороного. Зовнішні вершини діаграми Вороного (ті, що лежать на границі області) утворені перетином серединних перпендикулярів із границею області.

Визначення сторін діаграми Вороного.

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

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

Координати середини відрізка будуть , а к-ти вектора нормалі . Отже рівняння сторони діаграми що проходить між точками та буде ,

або розписавши

Значення координат внутрішніх вершин полігона (діаграми) знаходимо як координати точок перетину серединних перпендикулярів. Наприклад для 3-х точок тріангуляції , , отримаємо систему рівнянь

Тут , – координати вектора , а , – к-ти середини відрізка .

Приклад.

Задано точки тріангуляції , , .

1) Знаходимо середини відрізків ,

2) Знаходимо к-ти векторів ,

3) Розв’язуємо систему рівнянь

Тобто внутрішня вершина діаграми що відповідає точкам , , буде .

Зауважимо що через точку буде проходити і третя сторона діаграми (Рис.)

.

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

звідки легко шукається значення

По аналогії легко знайти координати вершини на перетині сторони діаграми, що проходить наприклад, між точками та з межею

Так з попереднього прикладу, точки перетину сторін діаграми з осями координат будуть

З віссю :

З віссю :

Крім того слід пам’ятати про існування кутових точок області, що утворені перетином межових ліній.

Якщо наприклад всі точки тріангуляції , , попадають в середину квадрата , то зовнішніми вершинами діаграми ще будуть точки (0, 0), (10, 0), (10, 10), (0, 10).

Обчислення площі полігонів

Площу полігонів обчислюють за формулою

При цьому слід пам’ятати, що

.

Структуру формули розглянемо

на прикладі п’ятикутника

A1(x1,y1); A2(x2,y2); A3(x3,y3); A4 x4,y4; A5(x5,y5)

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

причому, якщо то , а якщо то . Тоді очевидно, що сума таких площ буде рівна площі многокутника, яку отримаємо із знаком «+» якщо вершини нумерувати за годинниковою стрілкою та із знаком «–» якщо вершини нумерувати у протилежному напрямку. Отже у будь-якому випадку

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

Приклад.

Обчислимо площу отриманого чотирикутника з діаграми Вороного з вершинами

, , , .

Формулу обчислення площі найзручніше було б запрограмувати на комп’ютері, однак якщо обчислення проводяться вручну, то результати доцільно заносити у таблицю

Таблиця 1. Полігон 1

№ вершини	0	1	2	3	Сума
	0	0	5	3
	0	6	6	0
	0	5	-2	3
	6	12	6	0
	0	60	-12	0	2S = 48

Отже площа чотирикутника буде одиниці.

Зауважимо що тут легко зробити перевірку оскільки маємо трапецію .

Завдання на самост. розрах. роботу.

Виконати графічну побудову тріангуляції Делоне і діаграми Вороного для заданої системи 3-х точок у заданому квадраті. Визначити сторони діаграми (записати їх рівняння). Визначити координати вершин діаграми (внутрішні та зовнішні). Обчислити площу кожного з 3-х полігонів та їх сумарну площу.

Задачі мережевого аналізу

Мережевий аналіз спрямований на опрацювання даних лінійних об’єктів, які мають розгалужену (деревоподібну) структуру.

Класичні задачі мережного аналізу: оптимізація маршрутів (Знаходження найкоротшого чи найбільш вигідного маршруту) та обчислення “зон досяжності” в мережі.

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

Граф - множина об'єктів довільної природи, називаних вершинами, зв'язаних між собою відношеннями які назив. ребрами графа.

Геометрично граф подається у формі схеми, що складається з вершин, вузлів, ребер, дуг. 

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

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

Вузол (англ. Node) – це вершина, загальна для двох і більшого числа дуг. У вузлах сходяться дуги.

Дуга (англ. Arc) – це ребро з певною орієнтацією (напрямком) відносно її кінцевих вершин.

Кількість вершин графа називають його порядком.

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

Маршрутом (або шляхом) у графі називається послідовність вершин v_i і ребер e_i така, що кожні два сусідні ребра в цій послідовності мають спільну вершину, отже, e_i=(v_i,v_i +1), i=1,2,…,k.

Вершина v₁ називається початком шляху, а вершина v_k +1  кінцем шляху. Всі інші вершини цього шляху називаються проміжними, або внутрішніми, вершинами.

Кількість k ребер у маршруті називається довжиною маршруту. Кажуть, що цей маршрут з’єднує вершини v₁ і v_k +1 або веде з вершини v₁ у вершину v_k +1.

Маршрут, в якому всі ребра попарно різні, називається ланцюгом. Маршрут, в якому всі проміжні вершини попарно різні, називається простим ланцюгом.

Маршрут називається замкненим (або циклічним), якщо v₁=v_k +1. Замкнений ланцюг називається циклом, а замкнений простий ланцюг  простим циклом.

Граф, довільні дві вершини якого можуть бути з’єднані деяким маршрутом називається зв’язним. Інакше граф називається незв’язним.

Зв’язний граф що немає циклів називається деревом.

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

Цю задачу можна сформулювати ще так:

Нехай у місті М знаходиться кур’єрська служба і кур’єр повинен розвести листи в інші міста. Ясно, що є багато маршрутів об’їхати всі міста. Який з них буде найкоротший?

(тут розв’язок очевидний спочатку треба поїхати на пиво, а потім будь-який маршрут буде найкоротшим :)

Розглянемо граф що відповідає 5-ти населеним пунктам і кожні два пункти сполучені дорогою. Такий граф називають повним. Числа на лініях вказують відстані між пунктами по цих дорогах.

Для знаходження відповіді найпростіше проаналізувати всі варіанти за допомогою нового графу. Вверху вершина М – початок маршруту, з неї є 4 варіанти почати маршрут, далі для кожного з них буде по 3 варіанти продовження шляху, потім 2 потім в останнє місто і назад до М. Всього варіантів.

Запишемо біля кожного ребра відстань між пунктами а в кінці кожного маршруту їх суму – тобто його довжину. Тепер видно, що з отриманих 24-х варіантів два М-В-Б-А-Г-М та М-Г-А-Б-В-М будуть найменшими по 28 км. По суті це один і той же маршрут, пройдений у протилежних напрямках. (6+6+7+5+4=28).

(недоліком такого методу є швидке зростання кількості варіантів із збільшенням кількості міст) 5! = 120, 6! = 720, 10! = 3 628 800, а 20! – число що містить 19 позицій.

Тому для великих задача розв’язується наближеними методами за допомогою комп. програм.

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

Задача про найдешевшу дорожну мережу (Побудова графа найменшої довжини)

Велике практичне значення має слiдуюча задача, котру можна зформулювати у виглядi задачи про проведення дорiг. Маємо декiлька мiст M1, M2, М3,... Мп, котрi потрiбно з'єднати мiж собою мережею дорiг. Для кожної пари мiст (i,j) знаємо вартiсть l_ij будiвництва з'єднуючої їх дороги. Задача у тому, щоб побудувати саму дешеву з можливих мереж дорiг.

Замiсть мережи дорiг можна розглядати мережу лiнiй електропередач, мережу нафтопроводiв тощо.

Називаючи в графi, який зображує мережу дорiг, величину l_ij довжиною ребра d_ij, приходимо до задачі про побудову графа найменшої довжини. Тому далi в якостi вартостi дорiг примемо довжину ребер графа.

Якщо маємо всього три вершини (а,b,с), то достатньо побудувати один з з'єднуючих ланцюгiв аbс, асb, bас, причому якщо bс-саме довге ребро, то саме його i потрiбно виключити, побудувавшив ланцюг bас.

Для більшої кількості вершин граф найменшої довжини можна побудувати, за слiдуючим правилом. (алгоритм Пріма – Краскала)

1) З'єднуємо двi вершини з найбiльш коротким ребром u1.

2)На кожному з слiдуючих крокiв добавляемо саме коротке з ребер u_i якщо при цьому не виходить циклу. Якщо мається декiлька ребер однакової довжини, то вибираємо любе з них.

Cума довжин ребер такого графа буде найменшою:

Рисунок 10 - До побудови дерева найменшої довжини

Завдання.

1. Дев’ять населених пунктів задані у прямокутній декартовій системі координат їх координатами X,Y (Таблиця 6). Необхідно:

   1. розрахувати матрицю відстаней між пунктами мережі за формулою

( 10 )

(значення відстаней заокруглювати з точністю до десятих);

2. використовуючи матрицю відстаней, згідно з алгоритмом Пріма-Краскала запроектувати найдешевшу дорожну мережу і побудувати план дорожної мережі, вказавши номери населених пунктів і довжини з’єднуючих їх доріг. Вказати загальну довжину мережі.

16.3. Приклад розв’язування.

Розглянемо мережу, яка складається з дев’яти населених пунктів (вершин), заданих їхніми декартовими координатами на площині.

x	5	36	43	14	17	35	19	12	21
y	29	24	11	28	8	38	23	39	12

Перший етап. Розрахуємо матрицю відстаней між вершинами, використовуючи формулу (1).

Перш за все врахуємо, що d₁₁ = d₂₂ = d₃₃ = … = d₉₉ = 0. Крім того, слід мати на увазі, що матриця відстаней – симетрична. Отже, нам необхідно вирахувати 9*8/2 = 36 відстаней.

;

;

;

. . . . . . .

.

В результаті виконаних розрахунків отримуємо матрицю відстаней у вигляді:

	1	2	3	4	5	6	7	8	9
1	0	31.4	42.0	9.1	24.2	31.3	15.2	12.2	23.3
2		0	14.8	22.4	24.8	14.0	17.0	28.3	19.2
3			0	33.6	26.2	28.2	26.8	41.8	22.0
4				0	20.2	23.3	7.1	11.2	17.5
5					0	35.0	15.1	31.4	5.7
6						0	21.9	23.0	29.5
7							0	17.5	11.2
8								0	28.5
9									0

Другий етап. Застосовуємо алгоритм Пріма – Краскала.

1. Вибираємо ще не розглянуте ребро мінімальної довжини. У нашому випадку це ребро d(5,9)= 5,7 . Обводимо кружечком дане число у матриці відстаней (помічаємо розглянуте ребро). Сполучаємо на схемі відповідні вершини

2. Вибираємо ще не розглянуте ребро мінімальної довжини. d(4,7) = 7,1 (цикл не утв.)

3. Вибираємо не розглянуте ребро мінімальної довжини. d(1,4) = 9,1 (цикл не утв.)

4. Далі маємо два ребра мінімальної довжини. d(4,8) = d(7,9) = 11,2 (цикл не утв.)

5. Ребро d(1,8) = 12,2 утв. цикл тому його не розгл.

6. Далі йдуть ребра d(2,6) = 14,0, d(2,3) = 14,8 (цикл не утв.)

7. Ребро d(1,7) = 15,2 утв. Цикл, тому вибираємо Ребро d(2,7) = 17,0.

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

Рис.7. Схема найкоротшої дорожної мережі.

Висновок. Побудована найкоротша дорожна мережа загальною довжиною 90.1 кілометра.