Материал: 252_337

Визначення площі багатокутника

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

Площу трикутника, прямокутника, ромба можна визначити за відомими з математики формулами. А як бути, коли задано багатокутник на площині як опуклий, так і неопуклий? Коли опуклий, його можна розбити на трикутники, провівши діаго­ налі з будь-якої вершини до всіх решти, не суміжних з нею, визначити їхні площі, наприклад за формулою Герона, і знай­ ти їхню суму (мал. 143, а). А якщо він неопуклий, то такий підхід до розв'язання поставленої задачі не дасть позитивного результату (мал. 143, б). Спробуємо розв'язати задачу про ви­ значення площі багатокутника за допомогою тих ідей, які вже були розглянуті вище.

Мал. 143

Розглянемо довільний чотирикутник з вершинами у точках (Хі, ух), (х2; у2), (х3; у3), (*4; у4) (мал. 144). Якщо з кожної вер­ шини опустити вертикальні лінії на вісь Ох, то отримаємо точ­ ки (х\; 0), (х2; 0), (х3; 0), (х4; 0). Неважко помітити, що шукану площу заданого чотирикутника можна отримати так: від суми площ трапецій, зображених на малюнку 144, а, відняти суму площ трапецій, зображених на малюнку 144, б.

А чи достатньо для цього інформації про заданий чотирикут­ ник у вигляді координат його вершин? Виявляється, що так. Ос­ нови трапеції, що утворюються точками (хй; 0), (хх; ух), (х2; у2), (х2; 0) (мал. 144, а), мають довжини ух та у2, а висота дорівнює (х2 - хх). Площу цієї трапеції можна буде визначити за форму-

252

(x„; y2)

(x„; ya)

(0;0J

Мал. 144

с

Як бачимо, у них використана певна послідовність розгляду вершин заданого чотирикутника: в порядку їх обходу за годин­ никовою стрілкою. Перші два вирази даватимуть у результаті обчислення додатні значення (х2 - хг > 0, х3 - х2 > 0), а другі два - від'ємні (х4 - х3 < 0, хг - х4 < 0). Отже, немає необхідності в інформації про те, площі яких трапецій необхідно додавати, а яких - віднімати. Всі їх треба лише додавати - це обумовлено порядком обходу вершин заданого багатокутника.

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

Виконавши алгебраїчні перетворення, отримаємо:

±((Уі+У2)(Х2-Хі) , (Уі+Уз)(Х3-Х2) J (У8 +У4)(*4-*з) , (У4+Уі)(хі-Х4)) =

= ± 2 К*гУі -*i%)+(хзУ2 - хгуг ) + (хіу3-х3у4) + (xty4 - хіу1 ))\

Чи не схожі доданки отриманої формули з виразами, що ви­ значають напрям повороту при обході багатокутника від кожної вершини {хі + j; г/. + -^ до його попередньої вершини (xt; yt)? Усі,

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

253

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

Отриману формулу можна представити у більш компактно­ му вигляді для я-кутника:

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

!/V.

S = ±2- І УМУІ + УіУп

Переходячи до мови програмування, представимо фрагмент Pascal-програми, що обчислює площу багатокутника, який за­ даний координатами своїх вершин у порядку їх обходу:

read(f_in, х[і], у[і]);

s:=x[1]*y[n]-x[n]*y[1]; {Визначення початкового значення результату.}

for і := 1 to n - 1 do {Покрокове визначення площі багатокутника.}

s := s + (x[i + 1] * y[i] - x[i] * y[i + 1]);

Оцінка роботи описаного алгоритму зрозуміла: для визна­ чення площі заданого багатокутника необхідно послідовно двічі розглянути всі його п вершин. Тому оцінка ефективності запропонованого алгоритму 0{п).

При тестуванні алгоритму обчислення площі багатокутни­ ка необхідно передбачити різні види багатокутників - опуклі, неопуклі, з невеликою кількістю вершин та з кількістю вер­ шин, близькою до 100. Для зручності перевірки правильності роботи алгоритму можна задати правильні багатокутники (мал. 145, в), починаючи з квадратів, площі яких неважко ви­ рахувати вручну (мал. 145, а, б). У якості неопуклого багато­ кутника можна дослідити багатокутник, сторони якого зуб­ часті (мал. 145, г), або подібні до такого.

254

Цікавою є задача визначення напряму обходу опуклого багатокутника, заданого координатами своїх вершин. Відпо­ відь випливає із визначення напряму повороту при переході від точки (xt; yt) до точки (л;;.; і/;.).

А чи можна впорядкувати задані в довільному порядку вер­ шини опуклого багатокутника за певним напрямом його обхо­ ду? Так, можна, якщо підібрати таку їх послідовність, щоб знак виразу (xtyl+1 - xi+lyt) для будь-якої пари сусідніх вершин (xt; yt) і (хі+1; уі+і) не мінявся на протилежний.

Завдання

1.Розробити та реалізувати у вигляді програми алгоритм ви­ значення коефіцієнтів загального рівняння прямої, заданої двома точками (дсх; уг) і (х2; у2).

2.Розробити та реалізувати у вигляді програми алгоритм визна­ чення довжини відрізка, заданого двома точками (д:1; уг) і (х2; у2).

3.Розробити та реалізувати у вигляді програми алгоритм ви­ значення взаємного розміщення двох точок (Xj; у2) та (х2; у2).

4.Розробити та реалізувати у вигляді програми алгоритм ви­ значення взаємного розміщення двох прямих, кожна з яких задана координатами двох точок.

5.Розробити та реалізувати у вигляді програми алгоритм ви­ значення взаємного розміщення двох точок і прямої, також заданої координатами двох точок.

6.Розробити та реалізувати у вигляді програми алгоритм ви­ значення взаємного розміщення точки і відрізка.

7.Розробити та реалізувати у вигляді програми алгоритм ви­

значення напряму повороту від заданої точки {хг; уг) до ін­ шої заданої точки (х2; у2) у разі, коли спостереження ведеть­ ся з початку координат (0; 0).

8.Розробити та реалізувати у вигляді програми алгоритм ви­

значення напряму повороту від заданої точки (лгх; у^) до ін­ шої заданої точки (х2; у2) у разі, коли спостереження ведеть­ ся з довільної точки (х0; у0).

9.Розробити та реалізувати у вигляді програми алгоритм ви­ значення площі багатокутника, заданого координатами вер­ шин у порядку їх обходу.

10.Виконати завдання 9 для опуклого багатокутника з кількістю вершин N < 10. Результат виконання програми вивести у файл.

11.Виконати завдання 9 для неопуклого багатокутника з кількістю вершин N ^ 10. Результат виконання програми вивести у файл.

12.Виконати завдання 9 для опуклого багатокутника з кіль­ кістю вершин N ^ 100. Результат виконання програми ви­ вести у файл.

255