Tutorialspoint.dev

Minimum area of a Polygon with three points given

Given three points of a regular polygon( n > 3), find the minimum area of a regular polygon (all sides same) possible with the points given .

Examples:

Input : 0.00 0.00
        1.00 1.00
        0.00 1.00
Output : 1.00
By taking point (1.00, 0.00) square is 
formed of side 1.0 so area = 1.00 .



One thing to note in question before we proceed is that the number of sides must be at least 4 (note n > 3 condition)..

Here, we have to find the minimum area possible for a regular polygon, so to calculate minimum possible area, we need calculate required value of n . As the side length is not given, so we first calculate circumradius of the triangle formed by the points. It is given by the formula
R = abc / 4A
where a, b, c are the sides of the triangle formed and A is the area of the traingle. Here, the area of triangle can be calculated by Heron’s Formula .

After calculating circumradius of the triangle, we calculate the area of the polygon by the formula

A = nX ( sin(360/n) xr2 /2 )

Here r represents the circumradius of n-gon ( regular polygon of n sides ) .
But, first we have to calculate value of n . To calculate n we first have to calculate all the angles of triangle by the cosine formula
cosA = ( b2+c2-a2 ) / 2bc
cosB = ( a2+c2-b2 ) / 2ac
cosC = ( a2+b2-c2 ) / 2ab

Then, n is given by
n = pi / GCD (A , B, C )
where A, B and C are the angles of the triangle . After calculating n we substitute this value to the formula for calculating area of polygon .

Below is the implementation of the given approach :

C++

// CPP program to find minimum area of polygon of
// number of sides more than three with given three points.
#include <bits/stdc++.h>
using namespace std;
  
// assigning pi value to variable
const double pi = 3.14159265359;
  
// calculating gcd value of two double values .
double gcd(double x, double y)
{
    return fabs(y) < 1e-4 ? x : gcd(y, fmod(x, y));
}
  
// Calculating minimum area of polygon through this function .
double min_area_of_polygon(double Ax, double Ay, double Bx, 
                            double By, double Cx, double Cy)
{
    double a, b, c, Radius, Angle_A, Angle_B, Angle_C, 
                              semiperimeter, n, area;
  
    // calculating the length of the sides of the triangle 
    // formed from given points a, b, c represents the 
    // length of different sides of triangle .
    a = sqrt((Bx - Cx) * (Bx - Cx) + (By - Cy) * (By - Cy));
    b = sqrt((Ax - Cx) * (Ax - Cx) + (Ay - Cy) * (Ay - Cy));
    c = sqrt((Ax - Bx) * (Ax - Bx) + (Ay - By) * (Ay - By));
  
    // here we have calculated the semiperimeter of a triangle .
    semiperimeter = (a + b + c) / 2;
  
    // Now from the semiperimeter area of triangle is derived
    // through the heron's formula .
    double area_triangle = sqrt(semiperimeter * (semiperimeter - a)
                                * (semiperimeter - b)
                                * (semiperimeter - c));
  
    // thus circumradius of the triangle is derived from the 
    // sides and area of the triangle calculated .
    Radius = (a * b * c) / (4 * area_triangle);
  
    // Now each angle of the triangle is derived from the sides
    // of the triangle .
    Angle_A = acos((b * b + c * c - a * a) / (2 * b * c));
    Angle_B = acos((a * a + c * c - b * b) / (2 * a * c));
    Angle_C = acos((b * b + a * a - c * c) / (2 * b * a));
  
    // Now n is calculated such that area is minimum for
    // the regular n-gon .
    n = pi / gcd(gcd(Angle_A, Angle_B), Angle_C);
  
    // calculating area of regular n-gon through the circumradius
    // of the triangle .
    area = (n * Radius * Radius * sin((2 * pi) / n)) / 2;
  
    return area;
}
  
int main()
{
    // three points are given as input .
    double Ax, Ay, Bx, By, Cx, Cy;
    Ax = 0.00;
    Ay = 0.00;
    Bx = 1.00;
    By = 1.00;
    Cx = 0.00;
    Cy = 1.00;
  
    printf("%.2f", min_area_of_polygon(Ax, Ay, Bx, By, Cx, Cy));
    return 0;
}

Python3

# Python3 program to find minimum area of 
# polygon of number of sides more than three
# with given three points. 
  
# from math lib import every function
from math import *
  
# assigning pi value to variable 
pi = 3.14159265359
  
# calculating gcd value of two double values . 
def gcd(x, y) :
  
    if abs(y) < 1e-4 :
        return x
    else :
        return gcd(y, fmod(x, y))
  
  
# Calculating minimum area of polygon 
# through this function . 
def min_area_of_polygon(Ax, Ay, Bx, 
                        By, Cx, Cy) :
  
    # calculating the length of the sides of 
    # the triangle formed from given points 
    # a, b, c represents the length of different
    # sides of triangle
    a = sqrt((Bx - Cx) * (Bx - Cx) +
             (By - Cy) * (By - Cy))
    b = sqrt((Ax - Cx) * (Ax - Cx) + 
             (Ay - Cy) * (Ay - Cy))
    c = sqrt((Ax - Bx) * (Ax - Bx) +
             (Ay - By) * (Ay - By)) 
  
    # here we have calculated the semiperimeter 
    # of a triangle . 
    semiperimeter = (a + b + c) / 2
  
    # Now from the semiperimeter area of triangle 
    # is derived through the heron's formula 
    area_triangle = sqrt(semiperimeter * 
                        (semiperimeter - a) * 
                        (semiperimeter - b) * 
                        (semiperimeter - c))
  
    # thus circumradius of the triangle is derived 
    # from the sides and area of the triangle calculated
    Radius = (a * b * c) / (4 * area_triangle)
  
    # Now each angle of the triangle is derived 
    # from the sides of the triangle
    Angle_A = acos((b * b + c * c - a * a) / (2 * b * c))
    Angle_B = acos((a * a + c * c - b * b) / (2 * a * c))
    Angle_C = acos((b * b + a * a - c * c) / (2 * b * a))
  
    # Now n is calculated such that area is 
    # minimum for the regular n-gon 
    n = pi / gcd(gcd(Angle_A, Angle_B), Angle_C)
  
    # calculating area of regular n-gon through 
    # the circumradius of the triangle
    area = (n * Radius * Radius * 
            sin((2 * pi) / n)) / 2
  
    return area
  
# Driver Code
if __name__ == "__main__" :
  
    # three points are given as input . 
    Ax = 0.00
    Ay = 0.00
    Bx = 1.00
    By = 1.00
    Cx = 0.00
    Cy = 1.00
  
    print(round(min_area_of_polygon(Ax, Ay, Bx, 
                                    By, Cx, Cy), 1))
  
# This code is contributed by Ryuga 


Output:

1.00


This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter