He aquí una solución bastante sencilla para poliedros (3 dimensiones), con un tiempo de ejecución O(v+ve), donde v es el número de vértices y e es el número de aristas. Supongo que podría extenderse a dimensiones mayores, pero probablemente tendría un tiempo de ejecución mucho peor (me temo que más o menos exponencial como en O(v n ), siendo n el número de dimensiones).
Dejemos que nuestro poliedro tenga n vértices, definidos por sus coordenadas x,y,z: v 1 , v 2 , ..., v n y que el punto más bajo sea v 1 y el origen (modificando los valores de los demás en consecuencia), y que tenga e aristas, definidas por los vértices que conectan. Entonces, como tenemos coordenadas para los vértices (ya que así los hemos definido), debe haber un plano "a ras de suelo" p 0 que pasa por los ejes x y z (el eje y es la altura, y el suelo nunca tiene una elevación). Entonces, dejemos que v 2 sea el punto más cercano al plano del suelo (línea más corta perpendicular al plano), y que v 3 sea el siguiente más cercano, etc., hasta v n .
A través de cada uno de los puntos v 2 a través de v n , dibujar un plano perpendicular al suelo, y dejar que se numeren p m donde m es el subíndice del vértice por el que se ha dibujado. Entonces, el volumen de nuestro poliedro es igual a la suma de los volúmenes de las figuras entre los planos. Deberíamos tener algo parecido a esto:
![Polyhedron with 6 vertices and 12 edges]()
Sean las alturas entre los segmentos h 1 a través de h n-1 donde la altura h j es la altura entre los planos p j y p j+1 .
Ahora, a través de cada plano, tenemos un polígono (o más, si la figura es cóncava), cuyas coordenadas de los vértices se pueden calcular fácilmente como sigue:
Sea la arista que pasa por el plano p j tienen puntos finales v a y v b . Entonces, el vector de desplazamiento es v b - v a (suponiendo que las coordenadas de v están en forma de vector), y el porcentaje recorrido hacia arriba es $\frac{h_j-h_a}{h_{b-1}-h_a}$ . Multiplique esto por v b - v a y añadir a v a para calcular el nuevo punto de intersección de esa arista:
Punto de intersección = $(v_b-v_a)\frac{h_j-h_a}{h_{b-1}-h_a}+v_a$
El área de estos polígonos se puede determinar utilizando triángulos, o una simplificación de este mismo proceso en sólo 2 dimensiones.
PlanetMath dice que el volumen de un prismatoide (que es el tipo de figura contenida entre planos secuenciales) es $h\frac{B_1 + B_2 + 4M}{6}$ donde las Bs son las áreas de los polígonos paralelos y M es el área del polígono intermedio, que está exactamente a la mitad de ellos (y paralelo a ellos). Como ya conocemos el área de cada uno de los polígonos extremos, y podemos calcular fácilmente los vértices del polígono intermedio (utilizando el método del párrafo anterior), podemos calcular el volumen de los prismatoides resultantes. Al sumarlos se obtiene el volumen total del poliedro.
Supongo que el único problema real en este caso, entonces, es, a través del código, determinar qué aristas corren a través de cualquier plano en particular, pero si lo miráramos realmente, podríamos saberlo muy fácilmente.
Una versión más sencilla de esto se puede utilizar para calcular el área de cualquier polígono; basta con trazar líneas a través de los vértices paralelas al eje x y calcular el área de los trapecios resultantes como (b 1 +b 2 )/2
