Геометрия · объяснение и практика
Как внутренние и граничные узлы решётки определяют площадь
Как находить площадь простого решётчатого многоугольника по внутренним и граничным узлам, учитывать промежуточные точки сторон и проверять масштаб клеток.

В теме Векторы и координаты · Учебная карта
В маршруте Выпуклость и геометрия решётки · 10 тем
Главная мысль
Для простого многоугольника без отверстий с целочисленными вершинами площадь в единицах решётки равна S=I+B/2−1, где I — число внутренних узлов, B — число всех граничных узлов.
Считаются узлы, а не закрашенные клетки
Выбираем единичную квадратную решётку и простой замкнутый контур без самопересечений и отверстий. Его вершины должны находиться в узлах. Внутренние узлы считаются целиком, граничные входят в отдельное число B. Последнее включает не только углы многоугольника, но и все промежуточные узлы на его сторонах.
Теорема Пика утверждает S=I+B/2−1. Это точная формула для указанного класса фигур, включая невыпуклые. Она не означает, что каждый граничный узел сам по себе содержит половину клетки: углы и примыкания различаются. Формула описывает общий баланс площади после разбиения на простейшие решётчатые части.
Диагональная сторона тоже может содержать узлы
Возьмём треугольник с вершинами (0,0),(6,0),(0,4). На нижней стороне шесть единичных шагов, на вертикальной четыре, а на наклонной два примитивных решётчатых шага. Сумма даёт B=12 без двойного счёта углов. Промежуточный наклонный узел находится в (3,2), хотя сторона не идёт по линиям клеток.
Строго внутри при y=1 лежат четыре узла с x от одного до четырёх, при y=2 — два, при y=3 — один. Поэтому I=7 и S=7+12/2−1=12. Независимая проверка через прямоугольный треугольник даёт половину произведения катетов, также 12.
Пример
Что получится, если в этом треугольнике принять B за число вершин, то есть за три?
Вышла бы площадь 7+3/2−1=7,5 вместо 12. Ошибка возникла из-за пропущенных узлов на всех сторонах, а не из-за неприменимости теоремы к треугольникам.
Условия и единицы сохраняют смысл ответа
Если шаг решётки по осям составляет p и q единиц длины, координатная клетка имеет площадь pq. Сначала формула считает число таких единиц площади, затем результат умножают на pq. Например, счёт узлов не меняется при равномерном увеличении рисунка вместе с сеткой, но физическая площадь увеличивается.
Для фигуры с отверстием поправка уже другая, а самопересекающийся контур требует сначала определить, какую область считать внутренней. Дробные координаты вершин относительно выбранной сетки также не удовлетворяют исходному условию. Подбирать I и B по похожей картинке вместо проверки решётки опасно: точная формула не исправляет неточно заданный контур.
От чтения к действию
А теперь — вы
Частые вопросы
Входит ли вершина в B дважды как конец двух сторон?
Нет. B считает разные граничные узлы. При суммировании по сторонам нужно исключить двойной счёт общих концов.
Нужна ли выпуклость?
Нет, достаточно простого контура без отверстий и решётчатых вершин. Для самопересечений и отверстий исходная форма требует пересмотра.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему НОД приращений считает узлы на решётчатом отрезке
Как НОД координатных приращений определяет число узлов на наклонном отрезке и почему при суммировании по замкнутой границе нужно брать НОД без дополнительной единицы.
Открыть темуКак триангулировать вогнутый многоугольник последовательным отсечением ушей
Как выбирать допустимый треугольник-ухо у вогнутого контура, почему одного выпуклого угла мало и какие проверки повторяются после удаления вершины.
Открыть тему