лице на многоъгълник

Познати са различни алгоритми за изчисляване лице на многоъгълник.

Под лице на многоъгълник ще разбираме затворена част от равнината, ограничена от начупена линия. 

В правилен многоъгълник: всички страни имат равни дължини; всички вътрешни ъгли имат една и съща стойност, всички диагонали имат равни дължини.

Формула за лице на правилен многоъгълник S = n*b*a/2, където n е брой страни; b - дължина на страна; а - апотема на многоъгълника. Идеята е да се разбие многоъгълника на n еднакви равнобедрени триъгълника имащи бедро (= радиус на описаната окръжност) и височина към основата - апотема на многоъгълника.

Възможният брой диагонали в изпъкнал многоъгълник може да бъде представен с емпиричната формула m=n*(n-3)/2 или рекурентно с числа на пръстена.

Свойство на изпъкналия многоъгълник е, че всеки вътрешен ъгъл е по-малък от 180°. Ако през произволна страна на изпъкналия многоъгълник се построи права, то всички върхове на многоъгълника са в една и съща полуравнина. Относително лесен алгоритъм за изчисляване лице на изпъкнал многоъгълник е чрез разбиване на триъгълници.

Алгоритъм за лице на многоъгълник чрез  разбиване на триъгълници:

в цикъл последователно се посочват координати за върхове на многоъгълника;

избира се посока за обхождане на многоъгълника и изискването е да не се променя през изчислителния процес;

изчислява се лице на триъгълника с върхове първите три въведени точки - по формула на Херон;

в цикъл последователно се се изчислява лице на триъгълник с върхове - избраната начална точка, връх от последно разглеждания триъгълник и следващата поредна точка;

сумата от изчислените лица на триъгълниците представя търсеното лице на многоъгълника.

Алгоритъм за лице на многоъгълник имащ целочислени координати за всички свои върхове е описан в теорема на Pick.

Теоремата извежда твърдението: лице на равнинен многоъгълник с върхове възли на квадратна решетка може да бъде представено чрез формулата:

S = K + 0.5*(M + N) - 1, където

K - брой възли на квадратната мрежа затворени в контура - на чертежа със син цвят;

M - брой възли на квадратната мрежа, през които минава страна на многоъгълника - на чертежа с оранжев цвят

N - брой върхове на многоъгълника - на чертежа с черен цвят.

Чрез алгоритъма на Pick е възможно да се изчислява лице и за не изпъкнал многоъгълник.

Алгоритъмът за изчисляване лице на многоъгълник по метода на трапеците решава може да се приложи също и при не изпъкнал многоъгълник и съдържа следните стъпки.

в цикъл последователно се посочват  координати за поредната точка  връх на многоъгълника;

избира се посока за обхождане на многоъгълника, като се спазва същото изискване тя да не се променя през изчислителния процес;

изчислява се лице на правоъгълен трапец с върхове поредните две точки (използват се техните декартови координати) - изчисляване дължините на всяка от двете основи на правоъгълния трапец е като се отчете стойността на тяхната ордината - проекцията им по ординатната ос, дължината на височината на правоъгълния трапец се изчислява от разликата на стойностите на проекцията на двете точки по абсцисната ос;

от съществено значение е да се отчита знака пред изчислената стойност;

обхождайки всички върхове на многоъгълника и изчислявайки сумата от лицата на всеки трапец се получава сума от събираеми с различен знак - така се елиминира значението на вече изчислена частична площ на многоъгълника;

за стойност на търсеното лице на многоъгълника се взема абсолютната стойност от получената сума.

Алгоритъмът не налага изискването за изчисляване координати на проекция върху координатните оси.

Разгледайте други основни типове примерни проекти, за чиято реализация се използват теореми от изчислителна геометрия. Потърсете допълнителен материал за: триъгълник, четириъгълник, права, дистанция, ориентирано лице.