Tetrahedral Shoelace Algorithm: Calculating Volume of Irregular Solids

Summary

Calculating the volume of regular and irregular solids is an important task in nearly all branches of science including Engineering, Mathematics, Computer Science, and Bioinformatics, and also in real world applications, such as calculating potential volume of reserve in mining, volume of dam design in valley, volume of mountain in Mars, or volume of tumor. 

We have been calculating volumes with different methods such as water displacement, convex polyhedron calculation, integration, and solving by parts however, all these methods have some limitations. Water displacement requires a lot of water for large objects. Moreover, it is required that the object is physical. Integration method works really fast for shapes with an easily integrable function that defines it, but most shapes are just random. Other volume measuring methods doesn’t work with every non-convex shape as some parts of the shape are calculated repeatedly. So, we need a new method that can calculate the volume of any polyhedron accurately.

This idea takes inspiration from The Shoelace Formula (Surveyor's area formula) which is a formula in 2D. In this research the formula is modified to work in 3D. This research has been mathematically proven and tested with calculation of different kinds of shapes, using computer programming based on the Tetrahedral Shoelace Method, the method that this research developed. 

It can be concluded that this method can calculate volumes of any solids that are physical/abstract, convex/non-convex, simple/complex, revolutional/non-revolutional, and shapes without/with hole(s) quickly. This method can be applied as a complement for the current methods.

Question / Proposal

Problem Statement

Since the story about Archimedes and the famous "Eureka", we have been calculating volumes with different methods such as water displacement, convex polyhedron calculation, integration, and solving by parts. All those methods have some limitations.

The problems are: Water displacement method is inefficient because it requires a lot of water for big objects. Moreover, it is required that the object is physical. Other current volume measuring method doesn’t work with every non-convex shape as some parts are calculated more than they are supposed to. Integration method works really fast for functions with an easily integrable function that defines it, but most shapes are just random. All these methods have their own limitations shown in the table. 

Research Goal

As a student of Mathematics, I have been challenged to try and find another effective way to calculate the volume of any solid with one formula. This research aims to specifically find a new method that can calculate the volume of any polyhedron.

Hypothesis

From looking at many geometric formulas such as Cavalieri’s principle, Pythagoras’ theorem, Euler’s formula (Euler characteristic), which works in any number of dimensions, I begin to think that the Shoelace formula, a formula for calculating the area of any polygon must also have a 3D counterpart. Moreover, I believe the 3D 'version' of this formula can calculate the volume of any polyhedron.

Research

Theorem: Shoelace Formula

Proposition 2D to 3D

Proof of Shoelace Formula

Method / Testing and Redesign

Research Method

This method takes inspiration from The Shoelace Formula, a method of calculating the area of a polygon given the Cartesian coordinates of the vertices, and applies it to 3D. The first task is to divide a given shape into 3D counterparts of triangles, tetrahedra, where taking a triangular surface and a common origin point forms each tetrahedron. The next step is to decide whether the tetrahedra should be added to (Ptet) or subtracted from (Ntet) the final result. We can intuitively tell that a ray emanating from the origin in The Shoelace Formula can tell what lengths will be calculated as area; as the ray goes through a side, it will start/stop counting area. The same goes for 3 dimensions. So if we set the sign of the volume to be the sign of the derivative of the points (facing in/out, can be told by the right-hand rule), we can instantly differentiate Ptet and Ntet. With this, we can see that a Shoelace Formula in 3D will need to have the same direction for all the surfaces. A polyhedron can be triangulated into tetrahedra whose volume can be calculated using The Tetrahedral Shoelace Method. If all the directions of the surfaces in the determinants are the same then two surfaces joining together (Ptet – Ntet) will cancel out, leaving only the surface of the polyhedron’s tetrahedra to be calculated. The volume of a single tetrahedron is given by the formula.

So the volume of any polyhedron can be given by the Tetrahedral Shoelace Formula

After all the math is checked, a computer program using those formulas can calculate the volume of any given polyhedron.

Proof of Tetrahedral Shoelace Method (My Method)

Calculation Test

Pseudo code of my program

The real code in C++ and some input file examples can be found here.

Diagram of Tetrahedral Shoelace Method

Results

The Tetrahedral Shoelace Method can calculate the volume of any irregular solid by making a polyhedral approximation and calculate that shape’s volume. For higher accuracy, more vertex coordinates are required. So, for simple shapes, small physical waterproof shapes, convex hulls, or shapes of revolution, we may still use recent methods. But for other objects where it is possible to find the Cartesian coordinates of the vertices, one may use the Tetrahedral Shoelace Method.

Results Table

To assure that this formula really works, I made a JavaScript & C++ program to test it out on some polyhedra.

It can be observed that for polyhedral shapes from a cube to a toroidal polyhedron, the program gives correct results. If we on the other hand try calculating the volume of a shape with curvature however, we get innaccurate results. This is because the program calculates the volume of the polyhedral approximation for the curved surfaces.

Convex and Concave Shapes (Error Analysis)

It can be seen that the areas with a positive curvature (curving inwards) will be underestimated by the program (as seen with the sphere) whilst the areas with a negative curvature (curving outwards) will be overestimated by the program (as seen with the cylinder with 2 semi-sphere concave caps)

Hexahedral and Tetrahedral Mesh Comparison (Error Analysis)

It can also be seen that despite the inaccuracy, the polyhedral approximation used by our program is more accurate than a hexahedral mesh used by numerical integration method, the method typically used for similar scenarios.

Program Complexity

In computer science, a program's complexity is given by how long or how much memory a program takes to deal with a certain input size and is typically written in Big-O notation. In here, we will be comparing the complexities of our Tetrahedral Shoelace Method Program with a numerical integration program. 

Numerical Integration Program's Complexity

Since numerical integration can produce more and more accurate as the number of slices increase, we can consider the number of slices to be n. The additional memory complexity of such program is O(e) where e is the number of edges, whilst the time complexity of such program is O(ne +e log e) for most test cases, and O(ne+e2 log e) in the worst-case. 

Tetrahedral Shoelace Method's Complexity

In the C++ program I made, the additional memory complexity is O(e), whilst the time complexity of my program is O(e) in most cases and O(e2 log e) in the worst-case. 

Had the faces of the polyhedron been given as inputs as well, The complexities of both programs would be:

Memory complexity of numerical integration: O(1)
Time complexity of numerical integration: O(ne + e log e)

Memory complexity of tetrahedral shoelace method: O(e)
Time complexity of tetrahedral shoelace method: O(e) for average-case, O(e log e) for worst-case

Note: One may also modify the tetrahedral shoelace method by adding O(e2) to the programs memory complexity to get rid of the log e factor in the time complexity. 

Conclusion

Analysis

For the calculation of simple shapes, waterproof small objects, or revolutional shapes, we can use the previous methods such as specific formulas, water displacement method, or a combination of shell method and washer method of integration. But for complex, non-physical/non-waterproof/large shapes, non-revolutional shapes, we can use the Tetrahedral Shoelace Method.

Limitations

There are, of course, several limitations of this method:

  • This method only works when we know the vertex coordinates (and edges) of a given shape’s polyh­edral approximation.
  • Higher Accuracy requires more vertex coordinates. 
  • The program used to implement such method is not as efficient as numerical integration in terms of memory complexity. 

Conclusion

The Tetrahedral Shoelace Method can calculate the volume of any irregular solid by making a polyhedral approximation. For higher accuracy, more vertex coordinates are required. It can be concluded that this method can calculate volumes of solids that are physical/non-physical, convex/non-convex, simple/complex, revolutional/non-revolutional, and shapes with/without hole(s). This method can calculate the volume of any solids with one formula and can be applied as a complement of current methods.

Future Work

Considering that this method is a 3D implementation of a 2D formula, it is reasonable to consider that this method should be implementable in higher dimensions. (See proof below).

About me

I'm Nicholas Patrick, 10th grade student from Cita Hati School, Surabaya, Indonesia. Since I was little, I have always been fascinated by geometric shapes and their unique properties. I am also interested in computer programming since I was in 4th grade, because I saw a video of Mitchel Resnick introducing block-line programming. Following that I began learning a few more "real" programming languages, namely Javascript and C++. I have also began joining competitive programming competitions and won a national gold medal recently. 

My family really supports me in my hobby in math and coding, as they too are very interested in the world of science and technology. Other than that, I am also very influenced by Leonhard Euler, a very important mathematician in shaping the world of mathematics that we know today because of his passion and way of thinking. 

For my future study, I can assure that I will be majoring in computer science. I really hope I may enter a top university so that I can collaborate with great minds to solve real world problems using programming. 

Winning Google Science Fair would further motivate me in research and exploring math with the aid of programming. By joining Google Science Fair I can have more exposure to share my idea with the world and learn more from other people. I really hope that I can continue this research and also make it to a top university.

Health & Safety

This research is done independently, mostly in the classroom, library, and home and does not involve any dangerous/hazardous material or equipment (only using pencil, paper, and my laptop).

Bibliography, references, and acknowledgements

References

- Varberg, D., Purcell, E., & Rigdon, S. (2006). Calculus (9th ed.). (pp. 574–578). London, UK: Pearson.

- Bart Braden (1986). The Surveyor's Area Formula (pp. 326–329) The College Mathematics Journal. 

- Schmaltz, Wolfgang. (2009). A Jordan–Brouwer Separation Theorem (PDF). (pp: 1–19). Chicago: University Paper. 

 

Acknowledgement

  • My mom Conny Wijaya for supporting me and making sure I stay on schedule for this research
  • My dad Jallson Surjo for mentoring and also helping with some of the illustrations
  • Ms. Nadya Pramita my Math teacher for allowing me to do this research during her class at school
  • Mr. Hokky Situngkir for advice in error analysis
  • Mr. Kim Siung for mentoring about mathematics research writing