2. Операції з полігонами

Перейдемо тепер до операцій з полігонами, заданими послідовністю вершин. Розглянемо завдання визначення площі полігону. Найчастіше застосовується алгоритм, заснований на розбитті багатокутника на трапеції, обмежені лінією сегмента полігону, перпендикулярами, опущеними з вершин сегмента на вісь ОХ (рис. 4.3, а). Для сегменту, що з'єднує вершини та , площа такої трапеції дорівнює . Обчислимо площі трапецій для всіх сегментів полігону і підсумуємо їх. Для сегментів, у яких , площа береться негативною (рис. 4.3-б). Слід зауважити, що полігон – замкнута фігура, тому потрібно враховувати сегмент, що з'єднує останню вершину з першої.

Рисунок 4.3 – Обчислення площі полігону: а) вихідна фігура;

б) розбиття на трапеції

Таким способом можна обчислити площі не тільки для опуклих багатокутників, але і для увігнутих, а також для полігонів, що мають дірки. Алгоритм непридатний для обчислення площ полігонів, що мають самоперетинання кордонів. Для полігонів, оцифрованих проти годинникової стрілки, площа виходить негативною. Проблеми виникають також при негативних значеннях координат y вершин полігону. У такому разі можна або додати до координат y досить велике число, або опускати перпендикуляри з вершин на пряму , де const менше самої малої y-координати в полігоні. Якщо використовується система координат з великими значеннями x і y (наприклад, в системі координат Гауса-Крюгера в районі Красноярська діють координати x = 6200000; y = 16500000), то при багаторазовому підсумовуванні площ трапецій буде накопичуватися обчислювальна помилка. Відносна похибка виходить особливо високою для малих полігонів. Ця проблема може бути вирішена лінійним перетворенням полігону до нової системи координат, в якій не буде настільки великих значень, і обчисленням в ній площі. Далі обчислюється площа у вихідній системі. У моделі "дуга-вузол" полігони формуються з дуг. При цьому кодується розташування полігону щодо направлення оцифрування дуги. Вочевидь, що для двох суміжних полігонів достатньо обчислити площу правого полігону. Потім для правих полігонів ця площа підсумовується зі знаком "плюс", а для лівих – зі знаком "мінус".

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

Рисунок 4.4 – Схема визначення приналежності точки полігону

Вертикальна лінія перетинає сегмент з кінцевими точками і тоді, коли ці точки розташовані по різні боки від вертикальної лінії. Рівняння прямої сегмента визначається за його кінцевим точкам, а перетинання сегменту з вертикальною прямою знаходиться в точці . Коли і , лінія і сегмент кордону не перетинаються. Коли і , додамо до кількості перетинів 0 або 2. Для збереження детермінованості алгоритму потрібно також перевіряти, розташована чи точка на границі полігону . Інакше алгоритм у різних випадках буде видавати різні результати (рис. 4.5).

2 перетини – точка зовні 3 перетини – точка всередині

Рисунок 4.5 – Невизначеність при розташуванні точки на кордоні об'єкта

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

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

Рисунок 4.6 – Розташування центроїду полігонів

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

У деяких програмах координати центроїда обчислюються як середнє значення x та y. Розглянемо наступну полігональну операцію – обчислення скелету полігона. Скелет полігона визначають як мережу ліній, побудованих таким чином, що кожна точка мережі розташована на рівній відстані від найближчих двох сегментів границі полігону. За допомогою цієї операції можна визначити оптимальні місця для підпису полігону. Скелет отримуємо шляхом "стиснення" полігону (рис. 4.7).

Рисунок 4.7 – Схема отримання скелета полігону

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