El volumen del casco convexo 3D de puntos pequeños establece todo en el casco

11

Tengo una pregunta que es similar a esta antes, excepto en 3D, y solo necesito el volumen, no la forma real del casco.

Más precisamente, se me da un pequeño conjunto de puntos (digamos, 10-15) en 3D, todos los cuales se sabe que se encuentran en el casco convexo del conjunto de puntos (por lo que todos "importan" y definen el casco). Solo quiero calcular el volumen del casco, no me importa calcular el poliedro real. ¿Existe un algoritmo eficiente para hacer esto?

algorithms reference-request computational-geometry Victor Liu
fuente

Sabes que los puntos son vértices del poliedro. ¿Conoces las caras (polígonos en el casco)? Si es así, puede calcular el volumen con bastante facilidad (como una suma de volúmenes "cono").

hardmath

1

Una forma perezosa sería triangular primero, luego sumar los volúmenes del tetraedro (muy fácil de calcular).

Shuhao Cao

@hardmath: No. Sé que si supiera las formas de las facetas, sería fácil.

Victor Liu

@Shuhao Cao: ¿Existe un algoritmo de triangulación simple para este caso especial? En general, los algoritmos de tetraédricación 3D son bastante complicados, y espero tener que resolver este problema miles o millones de veces.

Victor Liu

5

$O(n^2)$ $n^4$ $n=15$ $v$ $T$ $v$ $4 \times 4$

Joseph O'Rourke
fuente

2

$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

$10^6$

convhull

$4\times 4$ $N=10^5$

time_elapse =
              3.244278
Vol =
     0.998068316875714

$\approx 7\times 10^5$ $1$ $[0,1]^3$

Shuhao Cao
fuente

Por cierto, la prueba se realiza en mi viejo Core 2 T61p 2007.

Shuhao Cao

2

De las preguntas frecuentes sobre cálculo poliédrico de Komei Fukuda :

$R^d$

Se sabe que calcular el volumen de un V-polytope (o H-polytope) es # P-hard, ver [DF88] y [Kha93]. Existen algoritmos aleatorios teóricamente eficientes para aproximar el volumen de un cuerpo convexo [LS93], pero parece que no hay implementación disponible. Existe un estudio comparativo [BEF00] de varios algoritmos de cálculo de volumen para politopos convexos. Indica que no existe un algoritmo único que funcione bien para muchos tipos diferentes de politopos.

[DF88] ME Dyer y AM Frieze. La complejidad de calcular el volumen de un poliedro. SIAM J. Comput. 17: 967-974, 1988.

[Kha93] LG Khachiyan. Complejidad del cómputo del volumen del politopo. En J. Pach, editor, Nuevas tendencias en geometría discreta y computacional , páginas 91-101. Springer Verlag, Berlín, 1993.

[LS93] L. Lovasz y M. Simonovits. Paseos aleatorios en un cuerpo convexo y un algoritmo de volumen mejorado. Estructuras y algoritmos aleatorios , 4: 359-412, 1993.

[BEF00] B. Bueler, A. Enge y K. Fukuda. Cálculo de volumen exacto para politopos convexos: un estudio práctico. En G. Kalai y GM Ziegler, editores, Polytopes - Combinatorics and Computation , DMV-Seminar 29, páginas 131-154. Birkhauser, 2000.

Esto puede parecer enterrar los detalles específicos del problema 3D entre las dificultades de dimensiones superiores, a pesar del título del artículo de Dyer y Frieze. De su resumen: "Mostramos que calcular el volumen de un poliedro dado como una lista de facetas o como una lista de vértices es tan difícil como calcular el permanente de una matriz".

$P$ $P$ $N_v$ $v$ $P$ $P$ $P$ $P = \{x \in \mathbb{R}^3 : Ax \le b \}$

$P$

hardmath
fuente

El volumen del casco convexo 3D de puntos pequeños establece todo en el casco

Respuestas: