Abstract
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 other real world applications, such as volumetric estimation in coal reserve,[1] volume of dam design in a valley, volume of volcano on Mars, or estimating the volume of a tumour.[2]
Many methods of obtaining volumes have been found over the years. However, each of these methods have their own limitations and no known formula can calculate the volume of any polyhedron — a shape with only flat polygons as faces — without error. So there is a need for a new method that can calculate the exact volume of any polyhedron.
This research takes The Shoelace Formula (also known as Surveyor’s area formula) — a formula to find the area of a polygon in 2D (Braden, 1986)[3] — and modified it to work in 3D. This new formula has been mathematically proven and tested with a calculation of different kinds of shapes using a computer program. This method breaks apart the polyhedron into triangular pyramids known as tetrahedra (Figure 1), hence its name — Tetrahedral Shoelace Method.
It can be concluded that this method can calculate volumes of any polyhedron without error and any solid regardless of their complex shape via a polyhedral approximation.
Figure 1: Diagram of the Tetrahedral Shoelace Method
Introduction
Volume Calculating Methods
Since the story about Archimedes and the famous \”Eureka\”, many methods of obtaining volume have been found such as water displacement, convex polyhedron[4] [5] volume formula — dividing polyhedra[6] into pyramids, integration — slicing the polyhedron into thin slices and calculating the area of each slice, and solving by parts — partitioning the polyhedra into simpler shapes. All those methods have some limitations. Water displacement method is inefficient because it requires a lot of water for big objects. Moreover, it is required that the object is physical. Convex polyhedron volume calculating method does not work with every non-convex shape as some pyramids may overlap one another resulting in a miscalculation. Integration method works really fast for functions with an easily integrable function that defines it, but most shapes aren’t defined by a function that can be integrated this way. All these methods have their own limitations shown in the table (Figure 2).
Figure 2: Table of calculating volume method and limitation
The Shoelace Formula:
The shoelace formula (also known as the surveyor’s area formula) is a formula that can calculate the area of any polygon, given the cartesian coordinates (x, y) of each vertex.
Objective:
This research aims to find a new method that can calculate the volume of any polyhedron accurately. More specifically, this research aims to find a 3D implementation of the shoelace formula that can calculate the volume of any polyhedron.
Research Method
The method used to obtain the formula from the Shoelace Formula (in 2D) to compute volumes of 3D objects is mathematical deduction and reasoning. The process of proving is in the branch of Mathematics: Linear Algebra. After the formula has been obtained and proven, volumes of various simple shapes are calculated with their respective formulas and the formula obtained. Some calculations are done with the help of a computer program to speed up the process.
Theorem: Shoelace Formula
The Shoelace formula states that given any polygon, we have:
where:
- is the area of the polygon
- is the number of sides of the polygon
- for all validare the coordinates of the vertices of the polygon
Proposition 2D to 3D
- In 2 dimensions, the triangle’s area is half that of the corresponding parallelogram,
where , and
are vectors of the parallelogram. Or alternatively
- where
are the coordinates of the vertices of the triangle.
Note: this works because - In 3 dimensions, tetrahedron’s volume is times that of the corresponding parallelepiped (3-dimensional counterpart of the parallelogram),
where ,
, and
are vectors of the parallelepiped. Or alternatively
- whereare the coordinates of the vertices of the tetrahedron.
Note: this works because
Proof of Shoelace Formula
Given a triangle of coordinates,, and, the area calculated by the Shoelace Formula is
We can express any polygon as tessellating triangles by triangulation, where the points are all listed in the same rotational direction (counter-clockwise).
Figure 3: Polygon partitioned to triangles
Any two adjacent triangles (triangles with a common side) will have the determinants corresponding to that side cancel out (because ), leaving only the determinants whose corresponding triangles’ areas are calculated by the Shoelace Formula.
Proof of Tetrahedral Shoelace Method (TSM)
Given a tetrahedron of coordinates ,,, and , the volume calculated by the Tetrahedral Shoelace Formula is
Unlike in 2 dimensions, proving that we can express any polyhedron as tessellating tetrahedra is much harder since there exists polyhedra which can’t be tetrahedralized without the introduction of Steiner vertices (additional points that aid in tetrahedralization). This can, however, be done by a method similar to triangulation by trapezoidal decomposition. If we cut a given polyhedron by every plane passing through a vertex of the polyhedron that contains a line parallel to an axis, every piece is a convex polyhedron, which can always be tetrahedralized (note that partitioning is only necessary for the proof and not the actual algorithm). The points of each tetrahedron such that its vertices are all listed in the same rotational direction (Figure 4).
Figure 4: Polyhedra partitioned to tetrahedra (not using the partitioning method described above)
Any two adjacent tetrahedra (tetrahedra with a common surface) will have the determinants corresponding to that surface cancel out (because ), leaving only the surfaces whose corresponding tetrahedra’s volumes are calculated by the Tetrahedral Shoelace Formula.
Figure 5: The cancellation of volumes calculated by the determinants
where
,, and are the coordinates of the vertices of a triangular surface
Ptet are the positive determinants, representing surfaces facing in at the origin
Ntet are the negative determinants, representing surfaces facing out from the origin
Simple Shapes Calculation (Tetrahedron)
Figure 6: The sample tetrahedron
Vertex:
Faces:
Tetrahedral Shoelace Method:
Reference face:
Finding orientation of other faces from edges we get:
(This can be obtained by considering that directed edges 1->2, 2->3, and 3->1 cannot be used again)
Calculating volume:
Calculation with the standard formula:
It can be seen that the results match.
Simple Shapes Calculation (Triangular dipyramid)
Figure 7: The sample triangular dipyramid
Vertex:
Faces:
Tetrahedral Shoelace Method:
Reference face:
Finding orientation of other faces from edges of the first face we get:
(This can be obtained by considering that directed edges: 1->2, 2->4, and 4->1 cannot be used again)
Finding orientation of other faces from edges of the second group, we get:
(This can be obtained by considering that directed edges: 1->5 and 5->2 (and 2 others) cannot be used again)
Calculating volume:
Calculation with the standard formula:
It can be seen that the results match.
Result
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. This method certainly has its own limitations (e.g. this method is cumbersome to use without computer assistance) and when other methods are more practical, they may be used.
Results Table
A C++ computer program using this formula is implemented to assure that this formula works.
Figure 8: Table of results
Analysis
It can be observed that for polyhedral shapes from a cube to a toroidal polyhedron, the program gives correct results. However, calculating the volume of a shape with curvature gives inaccurate results. This is because the program calculates the volume of the polyhedral approximation for the curved surfaces.
Convex and Concave Shapes (Error Analysis)
Figure 9: Comparison of positive and negative curvature
It can be seen (Figure 9) that the areas with a positive curvature (curving inwards) will be underestimated by the program (as seen with the sphere on Figure 8) 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 on Figure 8).
Hexahedral and Tetrahedral Mesh Comparison (Error Analysis)
Figure 10: Comparison of positive and negative curvature
It can also be seen (Figure 10) that despite the inaccuracy, a 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.
Conclusions
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.
This method can be used to calculate the volume of abstract models such as the needed amount of concrete to build a building with an irregular shape. This method can also be implemented in higher dimensional spaces, calculating volumes of polytopes — higher-dimensional counterparts of polyhedra.
Limitations:
This method only works when the vertex coordinates (and edges) of a given shape’s polyhedral approximation are known. Higher Accuracy requires more vertex coordinates. The program used to implement such a method is not as efficient as numerical integration in terms of memory complexity.
Acknowledgements
- Jallson Surjo, for mentoring and also helping with some of the illustrations
- Janto Sulungbudi and Kim Siung, for mentoring about Mathematics research writing
- Nadya Pramita, my Math teacher for allowing me to do this research during her class at school
- Hokky Situngkir, for advice in error analysis
References
- Varberg, D., Purcell, E., & Rigdon, S, Calculus 9th edition, (London, UK: Pearson, 2006), 574-578
- Bart Braden, The Surveyor\’s Area Formula, (The College Mathematics Journal, 1986), 326-329
- Mostafijul Karim, Volumetric Estimation of Coal Resources in Seam VI for Require Backfill Materials of Barapukuria Coal Mine (Dinajpur, Earth Science, 2013), 113-119.
- National Aeronautics and Space Administration. (n.d.). Mars Atlas: Olympus Mons. Retrieved from https://mars.jpl.nasa.gov/gallery/atlas/olympus-mons.html
- Johanna Sápi, Tumor Volume Estimation and Quasi-Continuous Administration for Most Effective Bevacizumab Therapy. (PLoS ONE, 2015), 1-2
Appendix
Code in C++ and some input file examples from this research can be found here: http://bit.ly/TSMprogram
- Mostafijul Karim, Volumetric Estimation of Coal Resources in Seam VI for Require Backfill Materials of Barapukuria Coal Mine, (Dinajpur, Earth Science, 2013), 113-119. ↑
- Johanna Sápi, Tumor Volume Estimation and Quasi-Continuous Administration for Most Effective Bevacizumab Therapy, (PLoS ONE, 2015), 1-2 ↑
- Bart Braden, The Surveyor\’s Area Formula, (The College Mathematics Journal, 1986), 326-329 ↑
- Polyhedron: a solid made of only flat surfaces, such as a cube. ↑
- Convex polyhedron: a polyhedron that is formed by a convex hull of finitely many points ↑
- Polyhedra: plural of polyhedron ↑
About the Author
Nicholas Patrick is a high school student from SMA Cita Hati, Surabaya, Indonesia who enjoys joining Math Olympiads since he was 10 years old. This research was started in mid 2017 and made it as regional finalist in Google Science Fair 2019. Another research competition he joined included ICYS 2017 (International Conference for Young Scientists) Stuttgart, which got the best presentation award.
This is an interesting exercise and piece of information you provide Nicholas ina a lucid manner. I used this in developing a CFD based method for DEM implementation. Thanks a lot.