Я хочу вычислить площадь случайного многоугольника и объем случайного многогранника. Поиск в Google привел меня к тесселяции и методу Монте-Карло. Однако я только интересует точный расчет, а не приближение через сближение. Может ли кто-нибудь знать точные формулы наизусть или иметь ссылку на страницу, где описаны такие формулы?
Формулы не нужны для применения к экзотическим многоугольникам или многогранникам. Я уже удовлетворен, если они относятся к просто (непересекающиеся ребра) выпуклый формы. Я не хотел бы использовать ничего кроме списка координат вершин [(x1, y1), ..., (xn, yn)]
или же [(x1, y1, z1), ..., (xn, yn, zn)]
Возможна организация в определенном порядке.
Я умею читать Fortran
, C/C++
, Python
а также MATLAB
, Следовательно, алгоритм, написанный на любом из этих языков или написанный в псевдокоде, хорошо принят.
Для простых полигонов вы можете использовать формулу Грина-Римана, как объяснено там: 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#Volume
Вы можете найти обзор вышеупомянутого метода для вычисления объемов там: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.3873&Rep = REP1&тип = PDF
Других решений пока нет …