площадь выпуклого многоугольника

[photon]

Имеется массив точек на плоскости, заданный своими координатами $(x_i,y_i)$. Необходимо найти площадь выпуклого многоугольника, который покрывает все эти точки (Вершинами многоугольника являются данные точки. Часть точек может не являться вершинами, а лежать внутри многоугольника.).

Я реализовал алгоритм, решающий данную задачу, следующим образом (опуская подробности алгоритма): нашел точки - вершины многоугольника и триангулировал.
Поиск точек-вершин не очень сложный, но несколько более громоздкий, чем хотелось бы.
Отсюда вопрос: можно ли сразу посчитать, например, площади всех возможных треугольников и из них получить площадь многоугольника, учтя каким-то образом (каким?) перекрытие этих треугольников?

[mihailm]

В Maple насколько помню есть команда выпуклая оболочка точек, в качестве результата дает некий минимальный набор точек из исходных
А у почти всех команд можно посмотреть код

[photon]

У меня сейчас нет возможности посмотреть содержимое команд коммерческого софта, да и с установкой free софта несколько проблемно.

[Sender]

Известны алгоритмы нахождения выпуклой оболочки, имеющие сложность $O(n\log h)$, где $n$ - общее число точек, а $h$ - число точек в выпуклой оболочке. Далее площадь ищется за $O(h)$. Если же считать площадь всех треугольников, это уже $O(n^3)$. Кроме того, триангулировать вовсе не обязательно, есть же известная формула для площади многоугольника.

[photon]

За алгоритм вычисления площади без триангуляции спасибо, а вот площадь через площади всех треугольников меня всё равно интересует - не взирая на сложность алгоритма

[Urnwestek]

photon в сообщении #778451 писал(а):

У меня сейчас нет возможности посмотреть содержимое команд коммерческого софта, да и с установкой free софта несколько проблемно.

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

[photon]

Urnwestek в сообщении #778605 писал(а):

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

Да я уже написал, и оно работает. Мне просто интересно, можно ли реализовать не через поиск вершин, а в лоб, через площади фигур.