Polygons are basic shapes in geometry and can have many sides. Finding the Area of a Polygon is a complex task, So to perform this complex task we have a method called Triangulation. Triangulation is a method of dividing a polygon into triangles and then finding the area of each triangle to get the total area of the polygon. In this article, we’ll check the methods of how to find the area of any polygon using triangulation in Java.
Methods to Find Area of Polygon
There are a couple of methods to find the area of a Polygon as mentioned below:
- Break the polygon into triangles
- Using the shoelace formula
1. Break the Polygon into Triangles
We can divide the polygon into smaller triangles and then find the area of each triangle. The triangulation algorithm can be implemented using different methods, such as the Delaunay triangulation method, the ear clipping method, etc.
Implementation of the above approach:
Java
// Java Program to implement// Break the polygon into trianglesimport java.util.Scanner; // Main Classpublic class GFG { public static void main(String[] args) { // number of sides of the polygon int n = 4; // x-coordinates of the vertices of the polygon int[] xCoords = { 0, 1, 0, 1 }; // y-coordinates of the vertices of the polygon int[] yCoords = { 0, 0, 2, 2 }; // initialize the area double area = 0.0; // the three vertices of the triangle for (int i = 0; i < n - 2; i++) { // first vertex is always the same int v1 = 0; // second vertex moves from 1 to n-2 int v2 = i + 1; // third vertex moves from 2 to n-1 // calculate the area of the triangle using // Shoelace formula int v3 = i + 2; // add the area of the triangle to the total // area double triangleArea = Math.abs( 0.5 * (xCoords[v1] * (yCoords[v2] - yCoords[v3]) + xCoords[v2] * (yCoords[v3] - yCoords[v1]) + xCoords[v3] * (yCoords[v1] - yCoords[v2]))); area += triangleArea; } // print the final result System.out.println("Area of Polygon: " + area); }} |
Area of Polygon: 2.0
In this code, n is the number of sides of the polygon, and xCoords and yCoords are the arrays containing the x and y coordinates of the vertices of the polygon, respectively. The main method calculates the area of the polygon by triangulating it into smaller triangles and summing the areas of each triangle. The formula for calculating the area of a triangle is 0.5 * base * height.
Time complexity: O(n) Space Complexity: O(n)
2. Using the Shoelace Formula
The shoelace formula is a mathematical formula that can be used to find the area of a polygon. It works by adding the areas of the triangles formed by connecting the vertices of the polygon to a common point.
Implementation of the above approach:
Java
// Java Program to implement// Using shoelace formulaimport java.io.*; // Main Classclass GFG { public static void main(String[] args) { // number of vertices in the polygon int n = 4; // array to store x coordinates of the vertices int[] xCoords = { 0, 1, 1, 0 }; // array to store y coordinates of the vertices int[] yCoords = { 0, 0, 2, 2 }; // variable to store the area of the polygon double area = 0.0; // loop to calculate the area of the polygon for (int i = 0; i < n - 1; i++) { // add the area of the current triangle area += xCoords[i] * yCoords[i + 1] - xCoords[i + 1] * yCoords[i]; } // add the area of the last triangle area += xCoords[n - 1] * yCoords[0] - xCoords[0] * yCoords[n - 1]; // divide the total area by 2 to get the final // answer area = Math.abs(0.5 * area); // print the area of the polygon System.out.println("Area of Polygon: " + area); }} |
Area of Polygon: 2.0
In this code, n is the number of sides of the polygon, and xCoords and yCoords are the arrays containing the x and y coordinates of the vertices of the polygon, respectively. The main method calculates the area of the polygon using the Shoelace formula by summing the areas of each triangular component formed by the vertices and the origin. The formula is 0.5 * (sum of (x_i * y_i+1 – x_i+1 * y_i)) where x_i and y_i are the x and y coordinates of the ith vertex.
Time Complexity: O(n) Space Complexity: O(n)
