Многоугольник определяется как часть плоскости, ограниченная какой-то замкнутой ломаной.
Многоугольник называется простым, если граничная ломаная не имеет точек самопересечения. На картинке все многоугольники кроме последнего являются простыми.
Многоугольник называется выпуклым, если для любых его двух точек, все точки на отрезке между ними тоже принадлежат многоугольнику. Первые два многоугольника являются выпуклыми.
Выпуклый многоугольник называется правильным, если у него равны все стороны и все углы. Все правильные многоугольники также можно вписать в окружность, но обратное неверно.
В трёхмерном пространстве обобщением многоугольника является многогранник.
#Площади
В самом простом случае — для треугольника — площадь можно посчитать по готовым формулам через основание и высоту, а можно воспользоваться свойством векторного произведения:
$$ V = \frac{1}{2} (B-A) \times (C-A) $$В случае произвольного многоугольника, заданного последовательностью вершин в порядке обхода, можно поступить так: пройдемся по всем ребрам и для каждого добавим в сумму его ориентированную площадь треугольника, заданного этим ребром и началом координат.
На примере из картинки, площадь будет равна такой сумме векторных произведений:
$$ S = - \frac{1}{2} \cdot (\sum_{i=1}^{5} A_i \times A_{i+1} + A_6 \times A_1) $$Все пары вершин, идущие по часовой стрелке, учтутся с отрицательным знаком, а против часовой — с положительным, и поэтому отменят лишнюю площадь.
Формула верна в случае любых многоугольников без самопересечений, даже невыпуклых. Чтобы убедиться в этом, попробуйте зафиксировать какую-нибудь точку на плоскости и проверить, сколько раз и с какими знаками она учтется в сумме.
Отметим, что знак итогового результата зависит от того, в каком порядке обходить многоугольник (чтобы про это не думать, можно взять его по модулю).
double area(vector<r> p) {
int n = (int) p.size();
double s = 0;
for (int i = 0; i < n; i++)
s += p[i] ^ p[(i + 1) % n];
return abs(s) / 2;
}
Также существует возможно более интуитивный, но и более громоздкий метод трапеций, где мы так же проходимся по всем ребрам и складываем ориентированные площади, но не треугольников относительно начала координат, а трапеций с основанием на оси $x$, в котором «нижние» трапеции аналогично отменяют лишнюю площадь «верхних».
Вне зависимости от метода подсчета площадей, заметим, что из формулы для площади треугольника следует, что если все координаты целочисленные, то площадь любой фигуры будет либо целым числом, либо рациональным с двойкой в знаменателе. Часто в задачах все входные данные целочисленные, и чтобы оставаться в целых числах, иногда имеет смысл умножить все входные числа на $2$ — тогда все площади будут целыми (и более того, чётными).
#Принадлежность точки
Опять же, начнём с треугольников. Требуется определить, находится ли точка точка $P$ в треугольнике $ABC$, заданном против часовой стрелки. Тогда она должна лежать слева от всех трёх отрезков $AB$, $BC$ и $CA$. Это условие задаст пересечение трёх полуплоскостей, которое и будет нужным треугольником.
$$ \text{P лежит внутри ABC} \iff \begin{cases} (B-A) \times (P-A) \geq 0 \\ (C-B) \times (P-B) \geq 0 \\ (A-C) \times (P-C) \geq 0 \\ \end{cases} $$Подобную проверку можно обобщить на случай выпуклых многоугольников. Для этого нужно пройтись по вершинам против часовой стрелки и проверить, что точка $P$ лежит «слева» от всех ребер.
Чтобы проверить, что многоугольник выпуклый, можно пройтись по ребрам многоугольника и проверять векторным произведением, что мы «поворачиваем» всегда в одну сторону, то есть для всех последовательных точек $a$, $b$, $c$ проверить, что $(b-a)\times(c-a) > 0$.
В постановке задачи, когда у нас многоугольник фиксирован, и поступают запросы проверки вхождения, задачу можно решить быстрее чем за линейное время.
#Произвольный многоугольник
В более общем случае есть два популярных подхода, оба за $O(n)$.
Первый заключается в подсчете углов. Пройдемся по всем вершинам в порядке обхода и будем последовательно рассматривать углы с вершиной в точке $P$ и лучами, проходящими через соседние вершины многоугольника. Если просуммировать эти ориентированные углы, то получится какая-то величина $\theta$. Если точка $P$ лежит внутри многоугольника, то $\theta = \pm 2 \pi$, иначе $\theta = 0$.
Второй заключается в подсчете, сколько раз луч, выпущенный из $P$, пересекает ребра многоугольника.
Если из произвольной точки пустить любой луч, и если этот луч пересечет многоугольник, то он рано или поздно выйдет из этого многоугольника — потому что луч бесконечный, а многоугольник нет.
Если посчитать число пересечений с многоугольником, то для точки, находящейся внутри, это число будет нечетным («наружу-внутрь-наружу», 3 пересечения), в противном случае — четным.
Чтобы не обрабатывать отдельно случаи, когда луч пересекает вершину (сразу 2 ребра), его можно делать случайным — вероятность, что действительнозначное направление совпадет с конечным числом точек пренебрежимо мала.