Точные формулы для площади многоугольников и объема многогранников

Question

Я хочу вычислить площадь случайного многоугольника и объем случайного многогранника. Поиск в Google привел меня к тесселяции и методу Монте-Карло. Однако меня интересует только точный расчет, а не приближение путем сходимости. Может ли кто-нибудь знать точные формулы наизусть или иметь ссылку на страницу, где описаны такие формулы?

Формулы не нужны для применения к экзотическим многоугольникам или многогранникам. Я уже удовлетворен, если они применяются к простым (непересекающимся краям) выпуклым формам. Я бы не хотел использовать ничего другого, кроме списка координат вершин [(x1, y1), ..., (xn, yn)] или же [(x1, y1, z1), ..., (xn, yn, zn)] Возможна организация в определенном порядке.

Я умею читать Fortran, C/C++, Python а также MATLAB, Следовательно, алгоритм, написанный на любом из этих языков или написанный в псевдокоде, хорошо принят.

Answer 1

Для простых полигонов вы можете использовать формулу Грина-Римана, как описано здесь: http://www.math.unl.edu/~mbrittenham2/classwk/208s04/inclass/areas_of_polygons.pdf

Это равносильно суммированию (алгебраических) областей треугольников M_iOM_j, где O - начало (или любая точка), и где алгебраическая область треугольника BOA положительна, если угол BOA положительный.

Для многогранников вы можете использовать формулу Остроградского для обобщения вышеизложенного. См. Например там: http://en.wikipedia.org/wiki/Polyhedron

Вы можете найти обзор вышеупомянутого метода для вычисления томов там: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.3873&rep=rep1&type=pdf