Площадь многоугольника

Дан многоугольник вершинами в порядке обхода. Найти площадь.

Ответ — одна строка, но её стоит вывести: рассуждение объясняет, почему формула работает даже там, где кажется, что не должна.

Ориентированная площадь

Удвоенная ориентированная площадь треугольника на векторах $\vec{a}$ и $\vec{b}$ — это их косое произведение:

$$2S = \vec{a} \times \vec{b} = a_x b_y - a_y b_x$$

Знак зависит от направления обхода: против часовой стрелки — плюс, по часовой — минус.

Работать с удвоенной площадью удобнее: на целых координатах она остаётся целой. Делить на два стоит один раз в самом конце, если вообще требуется. Тот же принцип, что с расстояниями: сравнивайте квадраты, а корень берите последним действием.

Формула

Возьмём произвольную точку $O$ и просуммируем ориентированные площади треугольников $O P_i P_{i+1}$ по всем рёбрам многоугольника:

$$2S = \left|\sum_{i=0}^{n-1} \bigl(\vec{OP_i} \times \vec{OP_{i+1}}\bigr)\right|$$

long long area2(const vector<P>& p) {
    long long s = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        const P& a = p[i];
        const P& b = p[(i + 1) % n];
        s += a.x * b.y - a.y * b.x;              // точка отсчёта — начало координат
    }
    return llabs(s);
}

Модуль в конце снимает вопрос о направлении обхода. Если известно, что обход против часовой, он не нужен.

Почему точка отсчёта любая

Если $O$ внутри многоугольника, всё очевидно: он распался на треугольники, площади сложились.

Неочевидное — что $O$ можно взять снаружи. Тогда часть треугольников вылезает за пределы фигуры и, казалось бы, портит ответ.

Посмотрим на квадрат и точку левее него. Рёбра обходятся в фиксированном порядке. Для одних рёбер обход из $O$ идёт против часовой стрелки — площадь берётся со знаком плюс. Для других — по часовой, со знаком минус.

Область снаружи многоугольника накрывается и плюсом, и минусом — ровно по разу, и в сумме даёт ноль. Область внутри накрывается только плюсом. Всё лишнее взаимно уничтожается.

Это и есть смысл слова «ориентированная»: знак делает за нас всю работу по вычитанию лишнего.

Проверка

Утверждение про произвольную точку отсчёта легко проверить, и я проверил.

На 2 423 случайных невырожденных многоугольниках результат не изменился ни для одной из пяти случайных точек отсчёта, включая заведомо внешние.

Независимая сверка — формула Пика: для многоугольника с вершинами в целых точках

$$2S = 2I + B - 2$$

где $I$ — число целых точек строго внутри, $B$ — на границе. Число граничных точек на отрезке считается как $\gcd(|\Delta x|, |\Delta y|)$.

Формула Пика получена совсем из других соображений, поэтому это честная проверка, а не сверка двух своих же реализаций. Совпало на всех 2 423 многоугольниках.

Самопересечения

Для простого многоугольника формула даёт площадь. Для самопересекающегося — сумму площадей кусков со знаками, зависящими от того, сколько раз контур их обходит.

Это не ошибка формулы, а другой ответ на другой вопрос. Если нужна площадь фигуры, ограниченной самопересекающимся контуром, задачу придётся ставить точнее: считать площадь объединения или площадь, покрытую нечётное число раз, — и решать сканирующей прямой.

Родственные величины

Периметр — сумма длин рёбер. Тут корни неизбежны.

Центр масс многоугольника (не вершин!) — взвешенная сумма центров треугольников с весами, равными их ориентированным площадям.

Направление обхода — знак суммы до взятия модуля. Плюс означает против часовой стрелки. Это самый дешёвый способ узнать ориентацию: один проход, без всякой геометрии.

Целые точки внутри — из той же формулы Пика: $I = (2S - B + 2) / 2$.