Page 101 - 4204

ЛЕКЦІЯ 7. ЕЛЕМЕНТИ ОБЧИСЛЮВАЛЬНОЇ ГЕОМЕТРІЇ.

чення найкоротшої відстані між пунктами та побудови діаграми

Вороного розроблені спеціальні алгоритми.

Для кількісної оцінки та порівняння впливу центрів діаграми

Вороного обчислюють площі полігонів (областей близькості) по-

передньо визначивши координати їх вершин.

7.2. Обчислення площ полігонів за координатами вер-

шин

Площу многокутника, заданого вершинами A i (x i , у i ) обчислю-

ють за формулою

1 n
S   x(  x )  y(  y ) .
2 i 1 i i 1 i
i 1

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

x  x , y  y .
n  1 1 n  1 1

Структуру формули розглянемо на прикладі п’ятикутника.

Будь-який многокутник можна розбити на трапеції утворені дво-

ма послідовними вершинами і їх проекціями на вісь Ox. Площа

y  y
кожної з таких трапецій буде S  (x i  1  x i ) i  1 i . При-
i
2

чому, якщо x  x то S  0, а якщо x  x то S  0. Тоді
i 1 i i i 1 i i

n
очевидно, що сума таких площ S   S буде рівна площі мно-
i
i 1

гокутника, яку отримаємо із знаком «+», якщо вершини нумеру-

вати за годинниковою стрілкою та із знаком «–», якщо вершини

100