Как посчитать площадь произвольного многоугольника формулой шнуровки (Гаусса)?
Дан простой многоугольник как список вершин в порядке обхода. Нужно найти его площадь. Слышал про «формулу шнуровки», но не понимаю, откуда там сумма произведений координат и почему делят на 2. Как написать без ошибок?
2 ответа
Формула шнуровки (Гаусса) считает удвоенную ориентированную площадь как сумму косых произведений соседних вершин:
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.cross(b); // a.x*b.y - a.y*b.x
}
return s; // удвоенная ориентированная площадь
}
// настоящая площадь = abs(area2) / 2.0
Идея: каждое слагаемое a × b — это удвоенная площадь треугольника, образованного началом координат и ребром (a,b). Суммируя по всем рёбрам, площади «вне» многоугольника сокращаются (отсюда название — координаты сшиваются крест-накрест, как шнуровка), остаётся ровно площадь фигуры.
Возвращай удвоенную площадь как целое (long long) и дели на 2 только в самом конце — так избегаешь double до последнего момента. Знак суммы = ориентация обхода. Сложность O(n) по времени, O(1) доп. памяти.
Два важных нюанса. Во-первых, area2 без abs даёт ориентированную площадь: положительна при обходе против часовой стрелки, отрицательна — по часовой. Это полезно (см. вопрос про ориентацию обхода), но если нужна просто площадь — бери llabs.
Во-вторых, переполнение: при координатах до 1e9 и n до 1e5 сумма может дойти до ~1e23, что уже не влезает в long long. Тогда либо __int128 для накопителя, либо предварительный сдвиг всех точек на первую вершину (вычесть p[0]) — это уменьшает координаты, не меняя площадь. Сдвиг — самый простой приём против переполнения в шнуровке.