Нахождение объема шестигранника

[tsiberev]

Привет
Имеется шестигранная ячейка (8 узлов). В общем случае грани не являются плоскостями.
Подскажите пожалуйста БЫСТРЫЙ алгоритм вычисления объёма такой ячейки.
Именно быстрый, потому как таких вычислений нужно сделать миллиарды на каждом из 100000 шагов

[maxal]

tsiberev писал(а):

Имеется шестигранная ячейка (8 узлов). В общем случае грани не являются плоскостями.

А чем тогда являются грани?
И вообще в каком виде эта ячейка задана?

[tsiberev]

maxal писал(а):

tsiberev писал(а):

Имеется шестигранная ячейка (8 узлов). В общем случае грани не являются плоскостями.

А чем тогда являются грани?
И вообще в каком виде эта ячейка задана?

В общем случае - просто поверхностями Есть мнение, что проходящими через геометрический центр грани.
Это обычная трехмерная регулярная сетка.
Задана 3-я массивами X (i,j,k) , Y (i,j,k) , Z (i,j,k).

[maxal]

tsiberev писал(а):

В общем случае - просто поверхностями Есть мнение, что проходящими через геометрический центр грани.
Это обычная трехмерная регулярная сетка.
Задана 3-я массивами X (i,j,k) , Y (i,j,k) , Z (i,j,k).

Ну у ячеек регулярной сетки все грани плоские, не так ли?
То есть, задача - вычислить объем шестигранника, заданого координатами его (восьми) вершин?

[tsiberev]

maxal писал(а):

tsiberev писал(а):

Ну у ячеек регулярной сетки все грани плоские, не так ли?

Конечно же НЕТ.
Через 3 точки грани плоскость проходит, да. А вот четвертая может и не лежать в этой плоскости.

[maxal]

tsiberev писал(а):

maxal писал(а):

Ну у ячеек регулярной сетки все грани плоские, не так ли?

Конечно же НЕТ.
Через 3 точки грани плоскость проходит, да. А вот четвертая может и не лежать в этой плоскости.

И как это противоречит тому, что все грани плоские?

[незваный гость]

Господа, а не проще ли привести пример ячейки (в числах)? Восемь вершин, 24 числа, и всем все понятно.

[Someone]

maxal писал(а):

tsiberev писал(а):

maxal писал(а):

Ну у ячеек регулярной сетки все грани плоские, не так ли?

Конечно же НЕТ.
Через 3 точки грани плоскость проходит, да. А вот четвертая может и не лежать в этой плоскости.

И как это противоречит тому, что все грани плоские?

Какой же это тогда шестигранник, если у него будет 12 граней?

[maxal]

Someone писал(а):

Какой же это тогда шестигранник, если у него будет 12 граней?

Читайте самое первое сообщение в этой теме: "Имеется шестигранная ячейка (8 узлов)."
И вообще видите, какой у этой темы заголовок?

[Someone]

maxal писал(а):

Someone писал(а):

Какой же это тогда шестигранник, если у него будет 12 граней?

Читайте самое первое сообщение в этой теме: "Имеется шестигранная ячейка (8 узлов)."
И вообще видите, какой у этой темы заголовок?

Вижу. Также вижу и то, что обсуждение постепенно пришло к двенадцатиграннику с плоскими треугольными гранями, который почему-то по-прежнему называется шестигранником. Вы ведь хотите считать грани плоскими, а тогда их будет 12 (иногда меньше).

А вообще, давайте не будем разжигать страсти на пустом месте.

[Brukvalub]

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

[worm2]

Видимо, имеется в виду некоторая "наиболее простая" поверхность, проходящая через 4 заданные точки. Например, для 3-х точек наиболее простой поверхностью, проходящей через них, очевидно, является плоскость. Для 4-х точек, заданных векторами $\mathbf{r}_1$, $\mathbf{r}_2$, $\mathbf{r}_3$, $\mathbf{r}_4$ можно привести следующее параметрическое уравнение этой поверхности:

$$\mathbf{r}_1 + u(\mathbf{r}_2-\mathbf{r}_1) + v(\mathbf{r}_4-\mathbf{r}_1) + uv(\mathbf{r}_1+\mathbf{r}_3-\mathbf{r}_2-\mathbf{r}_4)$$

,
где u, v --- действительные числа.
Можно показать, что поверхность, задаваемая этим уравнением, не зависит от порядка следования векторов, если только "диагональность" $\mathbf{r}_1$---$\mathbf{r}_3$ и $\mathbf{r}_2$---$\mathbf{r}_4$ сохраняется. О чём это говорит? Это говорит о том, что если у нас есть две смежные ячейки, мы выписываем уравнение смежной грани как грани 1-й ячейки и уравнение смежной грани как грани 2-й ячейки, то эти два уравнения обязательно зададут одну и ту же поверхность.

[worm2]

Если ввести обозначение:

$$\mathbf{r}(u,v,w)=\sum\limits_{i,j,k=0}^1 \mathbf{r}_{ijk}(2ui-u-i+1)(2vj-v-j+1)(2wk-w-k+1)$$

,
где $\mathbf{r}_{ijk}$ --- вершины шестигранника, i, j и k могут принимать значения 0 или 1, то объём можно вычислить по формуле

$$\int\limits_0^1\int\limits_0^1\int\limits_0^1\left(\frac{\partial \mathbf{r}}{\partial u}, \frac{\partial \mathbf{r}}{\partial v}, \frac{\partial \mathbf{r}}{\partial w}\right)du dv dw$$

,
где (a,b,c) --- векторное произведение a, b и c.
По моим прикидкам, при вычислении этого интеграла можно обойтись всего 144 умножениями, одним делением (на константу 216), и 336 сложениями/вычитаниями.

[tsiberev]

Brukvalub писал(а):

Поэтому без уточнения геометрии граней шестигранника ответить на Ваш вопрос, как мне кажется, просто невозможно

Ну, я там выше писал, что например поверхность, проходящая через 4 точки грани и их геометрический центр. А в этом случае есть теорема, которая говорит, что поверхность, натянутая на 4 точки и их геометрический центр единственна и является гиперболическим параболоидом.
В этом случае вычисление объема ячейки сводится к вычислению 6 определителей 3-го порядка.
Интересны другие идеи о быстром вычислении этого объема.

[незваный гость]

tsiberev писал(а):

А в этом случае есть теорема, которая говорит, что поверхность, натянутая на 4 точки и их геометрический центр единственна и является гиперболическим параболоидом.

Ужели? Через пять точек можно провести любое количество поверхностей.

Так что скажите уж прямо, что Вы рассматриваете, скажем, поверхности второго порядка. И каким образом их определяете.