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

Материал из Algocode wiki
Перейти к: навигация, поиск

Нахождение площади многоугольника без самопересечений

Рассмотрим два самых популярных способа — метод трапеций и суммирование ориентированных площадей треугольников.

Метод трапеций

рисунок 1

Будем рассматривать вершины и стороны многоугольника в порядке обхода по или против часовой стрелке. Допустим, будем обходить по часовой стрелке.

Опустим из каждой вершины перпендикуляр на ось OX. Если рассмотреть сторону (например, $AB$), то ей можно сопоставить прямоугольную трапецию, у которой одна боковая сторона лежит на оси OX, а другая совпадает со стороной многоугольника. Например, для стороны AB будет трапеция $ABHG$.

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

Как проводить суммирование: пусть $x[i]$ и $y[i]$ - координаты точки $i$. Прибавляться будет величина $$ \Delta S = \dfrac{(x[i + 1] - x[i]) \cdot (y[i] + y[i + 1])}{2} $$ При движении от точки A по верхней огибающей вправо у нас будет появляться изюбток площади, потому что координаты по $x$ увеличивались (допускаем, что весь многоугольник лежит в верхней полуплоскости). То есть мы будем прибавлять лишнюю площадь под фигурой. Этот избыток будет компенсирован при движении по нижней огибающей от точки $D$ влево. При этом движении $\Delta S < 0$, в чем легко убедиться.

Если смотреть на пример, то площади трапеций $DLJE$, $EJIF$ и $IFAG$ будут идти со знаком <<минус>> и <<уберут>> лишнюю площадь, добавленную до этого.

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

Очевидно, что для вычисления площади достаточно одного прохода по всем точкам, поэтому время работы составит $O(n)$, где $n$ - число вершин в многоугольнике.

Метод треугольников

рисунок 2

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

Рассмотрим самую левую, а если таких несколько, то самую нижнюю среди таких, точку многоугольника. На рисунке 2 это точка $A$. Теперь в порядке обхода от точки $A$ будем суммировать ориентированные площади треугольников, у которых одна вершина общая - точка $A$, а две другие - вершины $i$ и $i+1$ многоугольника. Прибавлять к общей площади будем: $$ \Delta S = \left[ OP_{i}, OP_{i+1} \right] $$ под квадратными скобками подразумеавем векторное произведение первого вектора на второй.

Здесь опять в каких-то местах будет суммироваться лишняя площадь, где-то будет недостаток, но в силу замкнутости фигуры и отсутствия самопересечений в итоге мы получим площадь нашего многоугольника.

Распишем, какие площади будут суммироваться на примере:

$$ S = \Delta ABC + \Delta ACD - \Delta ADE + \Delta AEF $$ Когда мы прибавили площадь $ACD$, то была прибавлена лишняя площадь, но так как поворот от $AD$ к $AE$ идет в противоположную сторону (по часовой стрелке), то эта площадь вычтется. Но вычтется и немного лишнего - часть треугольника $AEF$, эту его часть уже прибавили на этапе $ACD$, в итоге выши в ноль. Последним шагом прибалвяем весь треугольник $AEF$.

Надо понимать, что на деле (в коде) у нас будет только прибавление площадей, но площади ориентированные, вычитание будет делаться "само по себе".

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



Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko