теорема на Pick

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

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

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

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

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

За конкретния случай проверката на твърдението се извършва чрез сума от лица на следните фигури: триъгълник (AHB, HGF, FED), правоъгълен триъгълник DCK, равнобедрен триъгълник BIC, квадрат HBJF, и правоъгълник  IJDK.

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

Алгоритмизиране на построителната задача теорема на Pick не е обосновано. Валидизиране на входните данни при машинна обработка изисква имплементация на алгоритъм за изпъкнала обвивка, на алгоритъм за проверка принадлежност на точка с определени координати: не принадлежи на контура, е инцидентна със страна/връх на многоъгълника, е от многоъгълника и т.н.

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

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

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

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