Функция площади выпуклой оболочки к точек через координаты на плоскости

Предыдущий
вопрос Следующий
вопрос

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

Алгоритм Грэхема:

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

Алгоритм Джарвиса:

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

Оба алгоритма работают за время O(n*log(n)), где n - количество точек на плоскости.

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

P = 0.5 |(x1y2 + x2y3 + ... + xny1) - (y1x2 + y2x3 + ... + yn*x1)|

где (x1, y1), ..., (xn, yn) - координаты вершин многоугольника.