Обобщение формулы Пика

Думаю, многие кто когда-то сдавал ЕГЭ хотя бы раз слышали о красивой формуле для подсчета площади фигуры по прямоугольной сетке по точкам. К сожалению, в дальнейшем про нее забывают и она нигде не возникает даже на мат факе, хотя эту формулу можно обобщить не только на прямоугольную решетку. Об этом и пойдет речь в заметке.

Рисунок 1 - пример фигуры на квадратной решетке

Базовая формула

где S - площадь многоугольника, I - внутренние точки многоугольника, а B - граничные точки многоугольника

Формула действительно позволяет легко и просто найти площадь фигуры на плоскости. Так, для фигуры с рисунка 1 площадь считается как S=7+8/2-1=10. Доказывается она тривиально - в начале через разбор частных случаев - прямоугольников и треугольников. Потом мы понимаем, что любой многоугольник можно представить как их склейку, а, следовательно, формула верна.

Обобщение формулы

Теперь представим, что у нас вдруг не прямоугольная сетка, а один вектор мы повернули - по сути мы получаем тоже сетку, но не прямоугольную, а, например, как на рисунку - треугольную.

Сочетание красной и фиолетовой стрелки дает треугольную сетку

Следовательно, мы можем выписать матрицу замены:

И если мы умножим исходную формулу Пика на определитель матрицы замены переменных, то получим формулу для обычной евклидовой площади фигуры в новой решетке. В случае треугольной решетки эта площадь выражается через количество внутренних и граничных узлов.

Если же мы хотим считать не обычную площадь, а количество элементарных треугольников, то нужно дополнительно разделить полученную площадь на площадь одного такого треугольника.

Применение формулы

Для полученной серой фигуры имеем 5 внутренних точек и 5 граничных точек.

По формуле получаем обычную евклидову площадь:

S = (5 + 5/2 - 1)*\sqrt(3)/2 = 13\sqrt(3)/4.

Поскольку площадь одного элементарного треугольника равна \sqrt(3)/4, данная фигура состоит из 13 элементарных треугольников. Эквивалентно, это 6,5 элементарных параллелограммов.

Для одного шестиугольника формула тоже верна: у него 1 внутренняя точка и 6 граничных точек, поэтому

S = (1 + 6/2 - 1)*\sqrt(3)/2 = 3\sqrt(3)/2.

Это соответствует 6 элементарным треугольникам, или 3 элементарным параллелограммам. Действительно, правильный шестиугольник в такой решетке естественно разбивается на 6 элементарных треугольников.