Mathematics

Tetrahedral Shoelace Method: Calculating Volume of Irregular Solids

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).

Macintosh HD:Users:patricknicholas:Desktop:Screen Shot 2018-03-17 at 9.49.00 AM.png

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).

Macintosh HD:Users:patricknicholas:Desktop:dont open:New Folder With Items:New Folder With Items 2:New Folder With Items:New Folder With Items:New Folder With Items:just don't open this folder:I told you not to:stop what you're doing:files:competition files:LPB CYS 2017:Pembinaan 2:resources:cancel_out.png

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.

Macintosh HD:Users:patricknicholas:Desktop:Ptet_Ntet.png

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)

Macintosh HD:Users:patricknicholas:Desktop:dont open:New Folder With Items:New Folder With Items 2:New Folder With Items:New Folder With Items:New Folder With Items:just don't open this folder:I told you not to:stop what you're doing:files:competition files:LPB CYS 2017:Pembinaan 2:resources:GAMBARutkPATRICK:primitive01.png

Figure 6: The sample tetrahedron

Vertex:

Faces:

Tetrahedral Shoelace Method:

Reference face:

Macintosh HD:Users:patricknicholas:Desktop:dont open:New Folder With Items:New Folder With Items 2:New Folder With Items:New Folder With Items:New Folder With Items:just don't open this folder:I told you not to:stop what you're doing:files:competition files:LPB CYS 2017:Pembinaan 2:resources:GAMBARutkPATRICK:123.png

Finding orientation of other faces from edges we get:

Macintosh HD:Users:patricknicholas:Desktop:dont open:New Folder With Items:New Folder With Items 2:New Folder With Items:New Folder With Items:New Folder With Items:just don't open this folder:I told you not to:stop what you're doing:files:competition files:LPB CYS 2017:Pembinaan 2:resources:GAMBARutkPATRICK:214.png Macintosh HD:Users:patricknicholas:Desktop:dont open:New Folder With Items:New Folder With Items 2:New Folder With Items:New Folder With Items:New Folder With Items:just don't open this folder:I told you not to:stop what you're doing:files:competition files:LPB CYS 2017:Pembinaan 2:resources:GAMBARutkPATRICK:413.png Macintosh HD:Users:patricknicholas:Desktop:dont open:New Folder With Items:New Folder With Items 2:New Folder With Items:New Folder With Items:New Folder With Items:just don't open this folder:I told you not to:stop what you're doing:files:competition files:LPB CYS 2017:Pembinaan 2:resources:GAMBARutkPATRICK:432.png

(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)

Macintosh HD:Users:patricknicholas:Desktop:dont open:New Folder With Items:New Folder With Items 2:New Folder With Items:New Folder With Items:New Folder With Items:just don't open this folder:I told you not to:stop what you're doing:files:competition files:LPB CYS 2017:Pembinaan 2:resources:GAMBARutkPATRICK:primitive02.png

Figure 7: The sample triangular dipyramid

Vertex:

Faces:

Tetrahedral Shoelace Method:

Reference face:

Macintosh HD:Users:patricknicholas:Desktop:dont open:New Folder With Items:New Folder With Items 2:New Folder With Items:New Folder With Items:New Folder With Items:just don't open this folder:I told you not to:stop what you're doing:files:competition files:LPB CYS 2017:Pembinaan 2:resources:GAMBARutkPATRICK:124.png

Finding orientation of other faces from edges of the first face we get:

Macintosh HD:Users:patricknicholas:Desktop:dont open:New Folder With Items:New Folder With Items 2:New Folder With Items:New Folder With Items:New Folder With Items:just don't open this folder:I told you not to:stop what you're doing:files:competition files:LPB CYS 2017:Pembinaan 2:resources:GAMBARutkPATRICK:jajar3.png

(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:

Macintosh HD:Users:patricknicholas:Desktop:dont open:New Folder With Items:New Folder With Items 2:New Folder With Items:New Folder With Items:New Folder With Items:just don't open this folder:I told you not to:stop what you're doing:files:competition files:LPB CYS 2017:Pembinaan 2:resources:GAMBARutkPATRICK:jajar2.png

(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

  1. Mostafijul Karim, Volumetric Estimation of Coal Resources in Seam VI for Require Backfill Materials of Barapukuria Coal Mine, (Dinajpur, Earth Science, 2013), 113-119.
  2. Johanna Sápi, Tumor Volume Estimation and Quasi-Continuous Administration for Most Effective Bevacizumab Therapy, (PLoS ONE, 2015), 1-2
  3. Bart Braden, The Surveyor’s Area Formula, (The College Mathematics Journal, 1986), 326-329
  4. Polyhedron: a solid made of only flat surfaces, such as a cube.
  5. Convex polyhedron: a polyhedron that is formed by a convex hull of finitely many points
  6. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *