Как вычислить объём выпуклой фигуры заданной точками?

Question

[becks]

Есть набор точек в пространстве образующий выпуклую фигуру. Какие существуют методы для нахождения её объёма? Возможно существуют какие-то готовые реализации (библиотеки), буду очень признателен за подсказки.

Знают про метод тетраэдров - любая фигура разбивается на тетраэдры, после у каждого находим объём. Но во-первых, сложность O(n^4), а во-вторых, та реализация, что есть, сбоит на сложных фигурах, ошибку не могу отловить уже 2 дня.

Comments

[Денис Загаевский]

могу вам и так сказать - объём будет 0

[becks]

Денис Загаевский: Описался на не плоскости, а в пространстве, конечно

Answer 1

[x67]

Если не нужна высокая точность или нужно красивое решение, можно использовать метод Монте Карло. Для этого нужно знать, находится ли точка внутри фигуры или нет. Вот первая ссылка про это А вот про Монте Карло
Есть еще способ - численное интегрирование. Если вы знаете как просто получить проекцию разреза фигуры в любом месте на плоскость, то тут тоже ничего сложного нет.