Общая формула для расчета объема многогранника

Question

Учитывая список вершин (v) и список ребер, соединяющих вершины (e), и список поверхностей, соединяющих ребра (s), как рассчитать объем Многогранник

Answer 1

1. Возьмите многоугольники и разбейте их на треугольники.
2. Рассмотрим тетраэдр, образованный каждым треугольником и произвольной точкой (началом координат).
3. Суммируйте подписанные объемы этих тетраэдров.

Примечания:

1. Это будет работать только в том случае, если вы сможете соблюдать постоянный порядок CC или CCW для треугольников, если смотреть со стороны.
2. Объем тетраэдра со знаком равен 1/6 определителя следующей матрицы:

[x1 x2 x3 x4]
[y1 y2 y3 y4]
[z1 z2 z3 z4]
[1 1 1 1]

где столбцы - это однородные координаты вершин (x, y, z, 1).

Это работает, даже если фигура не заключает в себе источник, вычитая этот объем, а также добавляя его, но это зависит от наличия последовательного порядка.

Если вы не можете сохранить порядок, вы все равно можете найти способ разбить его на тетраэдры и суммировать 1/6 абсолютного значения определителя каждого из них.

Answer 2

Аналогично многоугольнику, где мы можем разбить его на треугольники и суммировать площади,
Вы могли бы разделить многогранник на пирамиды и суммировать их объемы. Но я не уверен, насколько сложно реализовать алгоритм для этого.

(Я полагаю, что существует математический способ / формула, например, использование векторов и матриц.
Предлагаю опубликовать свой вопрос также на http://mathoverflow.net)

Answer 3

Я делал это раньше, но сетка поверхности, которую я использовал, всегда имела треугольные грани. Если ваша сетка имеет не треугольные грани, вы можете легко разбить их на треугольные грани. Затем я подал его на TetGen , чтобы получить тетраэдризацию внутреннего пространства. Наконец, я сложил все объемы тетраэдров. TetGen достаточно прост в использовании и является единственной библиотекой, отличной от CGAL , которую я знаю, которая может обрабатывать сложные сетки. CGAL довольно прост в использовании, если вы не против установить гигантскую библиотеку и использовать такие шаблоны, как сумасшедшие.

Answer 4

Сначала разбейте каждую грань на треугольники, рисуя новые ребра.

Теперь посмотрите на один треугольник и предположим, что он находится на «верхней» поверхности (некоторые из этих деталей позже окажутся неважными). Посмотрите на объем ниже треугольника, вниз до некоторой горизонтальной плоскости ниже многогранника. Если {h1, h2, h3} - высоты трех точек, а A - площадь основания, то объем твердого тела будет A (h1 + h2 + h3) / 3. Теперь мы должны сложить объемы этих твердых тел для верхних граней и вычесть их для нижних граней, чтобы получить объем многогранника.

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

Итак, нам нужен (1) способ расчета площади основания и (2) способ отличить «верхнюю» грань от «нижней». Первое легко, если у вас есть декартовы координаты точек, второе легко, если точки упорядочены, и вы можете объединить их и убить двух зайцев одним выстрелом. Предположим, что для каждого лица у вас есть список его углов в направлении против часовой стрелки. Тогда проекция этих точек на плоскость x-y будет против часовой стрелки для верхней грани и по часовой стрелке для нижней. Если вы используете этот метод для расчета площади основания, он будет положительным для верхней грани и отрицательным для нижней, так что вы можете сложить их все вместе и получить ответ.

Так как вы получаете упорядоченные списки углов? Начните с одного треугольника, выберите порядок, и для каждого ребра сосед, который разделяет это ребро, должен перечислить эти две точки в обратном порядке. Переходите от соседа к соседу, пока у вас не будет списка для каждого треугольника. Если объем многогранника становится отрицательным, просто умножьте на -1 (это означает, что вы выбрали неправильный порядок для этого первого треугольника, и многогранник был наизнанку).

EDIT: Я забыл лучшую часть! Если вы проверите алгебру для суммирования этих объемов, вы увидите, что многие термины отменяются, особенно при объединении треугольников обратно в исходные грани. Я не проработал это подробно, но похоже, что конечный результат может быть удивительно простой функцией.

Answer 5

Вот потенциальная реализация этого в Python. Может кто-нибудь проверить, если это правильно? Я считаю, что мне не хватает сочетаний точек, потому что мой второй тест (куб) дает 0,666, а не 1. Идеи кто-нибудь?

Приветствие EL

class Simplex(object):
    '''
    Simplex
    '''


    def __init__(self,coordinates):
        '''
        Constructor
        '''

        if not len(coordinates) == 4:
            raise RuntimeError('You must provide only 4 coordinates!')

        self.coordinates = coordinates



    def volume(self):
        '''
        volume: Return volume of simplex. Formula from http://de.wikipedia.org/wiki/Tetraeder
        '''
        import numpy

        vA = numpy.array(self.coordinates[1]) - numpy.array(self.coordinates[0])
        vB = numpy.array(self.coordinates[2]) - numpy.array(self.coordinates[0])
        vC = numpy.array(self.coordinates[3]) - numpy.array(self.coordinates[0])

        return numpy.abs(numpy.dot(numpy.cross(vA,vB),vC)) / 6.0  


class Polyeder(object):

    def __init__(self,coordinates):
        '''
        Constructor
        '''

        if len(coordinates) < 4:
            raise RuntimeError('You must provide at least 4 coordinates!')

        self.coordinates = coordinates


    def volume(self):

        pivotCoordinate = self.coordinates[0]

        volumeSum = 0

        for i in xrange(1,len(self.coordinates)-3):

            newCoordinates = [pivotCoordinate]

            for j in xrange(i,i+3):
                newCoordinates.append(self.coordinates[j])

            simplex = Simplex(newCoordinates)
            volumeSum += simplex.volume()

        return volumeSum


coords = []

coords.append([0,0,0])
coords.append([1,0,0])
coords.append([0,1,0])
coords.append([0,0,1])

s = Simplex(coords)
print s.volume()

coords.append([0,1,1])
coords.append([1,0,1])
coords.append([1,1,0])
coords.append([1,1,1])

p = Polyeder(coords)
print p.volume()