A simple algorithm for calculating the area of an arbitrary polygon
Computing the area of an arbitrary polygon is a popular problem in pure mathematics. The two methods used are Shoelace Method (SM) and Orthogonal Trapezoids Method (OTM). In OTM, the polygon is partitioned into trapezoids by drawing either horizontal or vertical lines through its vertices. The area of each trapezoid is computed and the resultant areas are added up. In SM, a formula which is a generalization of Green’s Theorem for the discrete case is used. The most of the available systems is based on SM. Since an algorithm for OTM is not available in literature, this paper proposes an algorithm for OTM along with efficient implementation. Conversion of a pure mathematical method into an efficient computer program is not straightforward. In order to reduce the run time, minimal computation needs to be achieved. Handling of indeterminate forms and special cases separately can support this. On the other hand, precision error should also be avoided. Salient feature of the proposed algorithm is that it successfully handles these situations achieving minimum run time. Experimental results of the proposed method are compared against that of the existing algorithm. However, the proposed algorithm suggests a way to partition a polygon into orthogonal trapezoids which is not an easy task. Additionally, the proposed algorithm uses only basic mathematical concepts while the Green’s theorem uses complicated mathematical concepts. The proposed algorithm can be used when the simplicity is important than the speed.
Keywords. Computational geometry, computer graphics programming, coordinate geometry, euclidian geometry, computer programming.
Hearn D, Baker MP. 1998. Computer Graphics, C Version, 2nd Edition, Prentice Hall, Inc., Upper Saddle River, pp. 305-309.
Kodituwakku SR, Wijeweera KR, Chamikara MAP. 2013. An Efficient Algorithm for Line Clipping in Computer Graphics Programming, Ceylon Journal of Science (Physical Sciences), Volume 17: 1-7.
O’Rourke J. 1998. Computational Geometry in C: 2nd Edition, Cambridge University Press 1-22.
Wijeweera KR. 2015. Finding the Area of an Arbitrary Polygon: Shoelace Formula and its Implementation in C Programming Language. Retrieved from http://www.academia.edu/9987996/Finding_the_Area_of_an_Arbitrary_Polygon_Shoelace_Formula_and_its_Implementation_in_C_Programming_Language.
- There are currently no refbacks.
Ruhuna Journal of Science by University of Ruhuna is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Print ISSN: 1800-279X (Before 2014)