Volume do casco 3D convexo de pequenos conjuntos de pontos no casco

Tenho uma pergunta semelhante à que foi feita anteriormente, exceto em 3D, e só preciso do volume, não da forma real do casco.

Mais precisamente, recebi um pequeno conjunto de pontos (digamos, 10 a 15) em 3D, que são conhecidos por estar no casco convexo do conjunto de pontos (para que todos "importem" e definam o casco). Eu só quero calcular o volume do casco, não me importo em calcular o poliedro real. Existe um algoritmo eficiente para fazer isso?

Eu ficaria surpreso se você pudesse superar a sugestão de Shuhao Cao: calcule o casco e depois o volume depois de ter uma triangulação do casco. Você pode calcular o casco com o algoritmo incremental ou com o algoritmo de embrulho para presente. Se você realmente deseja um código fácil, basta escrever um loop sobre todos os triângulos possíveis para ver se estão no casco. Para , isso ainda é bastante rápido e você pode implementar facilmente atalhos. Depois de ter todas as faces do triângulo, escolha um vértice faça um tetraedro com cada triângulo e . Seu volume é um determinante nas coordenadas do vértice.n 4 n = 15 v T v 4 × $O(n^2)$$n^4$$n=15$$v$$T$$v$$4 \times 4$

Um pequeno teste no MATLAB, para número de vértices , cada componente é um número aleatório uniforme em :[ 0 , 1 $N = 100$$[0,1]$

N = 100;
p=rand(N,3);
tic;
T = delaunayTri(p(:,1),p(:,2),p(:,3));
t = T.Triangulation;
e1 = p(t(:,2),:)-p(t(:,1),:);
e2 = p(t(:,3),:)-p(t(:,1),:);
e3 = p(t(:,4),:)-p(t(:,1),:);
V = abs(dot(cross(e1,e2,2),e3,2))/6;
Vol = sum(V);
time_elapse = toc;

Resultado:

time_elapse =
              0.014807
Vol =
      0.67880219135839

Eu diria que é razoavelmente rápido, se você quiser executá-lo vezes, leva apenas menos de 3 horas. Aqui está o que é:$10^6$

Também quero mencionar que no post do professor O'Rourke ele mencionou o uso de determinante para calcular os volumes do tetraedro, mas aqui eu prefiro usar o produto triplo. É uma operação vetorizada naturalmente, mais escalável que a rotina interna do determinante (ou você pode expandir um determinante manualmente: p). Aqui está outro teste para , o resultado éN = 10 $4\times 4$$N=10^5$

time_elapse =
              3.244278
Vol =
     0.998068316875714

com número de tetraedros . Observe que o volume total está bem fechado para pois há muitos pontos agrupados em . 1 [ 0 , 1 ] $\approx 7\times 10^5$$1$$[0,1]^3$

Das Perguntas frequentes sobre computação poliédrica de Komei Fukuda :

2.23 Existe algum algoritmo eficiente para calcular o volume de um polítopo convexo em ?$R^d$

Sabe-se que a computação do volume de um politopo V (ou politopo H) é difícil de P, veja [DF88] e [Kha93]. Existem algoritmos aleatoriamente teoricamente eficientes para aproximar o volume de um corpo convexo [LS93], mas nenhuma implementação parece estar disponível. Existe um estudo comparativo [BEF00] de vários algoritmos de computação de volume para pólipos convexos. Indica que não existe um algoritmo único que funcione bem para muitos tipos diferentes de politopos.

[DF88] ME Dyer e AM Frieze. A complexidade de calcular o volume de um poliedro. SIAM J. Comput. 17: 967-974, 1988.

LG Khachiyan. Complexidade do cálculo do volume de politopo. Em J. Pach, editor, New Trends in Discrete and Computational Geometry , páginas 91-101. Springer Verlag, Berlim, 1993.

L. Lovasz e M. Simonovits. Passeios aleatórios em um corpo convexo e um algoritmo de volume aprimorado. Random Structures & Algoritmos , 4: 359-412, 1993.

B. BEeler, A. Enge e K. Fukuda. Cálculo de volume exato para pólipos convexos: um estudo prático. Em G. Kalai e GM Ziegler, editores, Polytopes - Combinatorics and Computation , DMV-Seminar 29, páginas 131-154. Birkhauser, 2000.

Isso pode parecer enterrar as especificidades do problema 3D entre dificuldades de dimensões mais altas, apesar do título do artigo de Dyer and Frieze. De seu resumo: "Mostramos que calcular o volume de um poliedro dado como uma lista de facetas ou como uma lista de vértices é tão difícil quanto calcular a permanente de uma matriz".

Um artigo de 1991 de Jim Lawrence, Polytope Volume Computation , pode ser lido on-line e tem algumas referências para o caso especificamente em 3D. Ele escreve: "O método no presente artigo evita a triangulação de ou de seus limites". Além disso, o algoritmo descrito nesse artigo parece apropriado para sua situação, pois expressa "o volume de como uma soma dos números , um para cada vértice de Esses números são fáceis de calcular, portanto a dificuldade do procedimento é principalmente enumerando os vértices de ". A dificuldade provavelmente se traduz em sua situação em encontrar uma expressão para como a solução de um sistema de desigualdades linearesP N v v P P P P = { x ∈ R 3 : A x ≤ b $P$$P$$N_v$$v$$P$$P$$P$$P = \{x \in \mathbb{R}^3 : Ax \le b \}$ .

Se você já conhece essa expressão de "interseção de meios espaços" para , talvez isso permita uma computação bastante rápida.$P$