Рубрики

Площадь многоугольника с заданными n упорядоченными вершинами

Даны упорядоченные координаты многоугольника с n вершинами. Найдите площадь многоугольника. Здесь упорядоченное означает, что координаты задаются либо по часовой стрелке, либо против часовой стрелки от первой вершины до последней.

Примеры :

Input :  X[] = {0, 4, 4, 0}, Y[] = {0, 0, 4, 4};
Output : 16

Input : X[] = {0, 4, 2}, Y[] = {0, 0, 4}
Output : 8

Мы можем вычислить площадь многоугольника, используя формулу Шнеласа .

Area

 = | 1/2 [ (x1y2 + x2y3 + ... + xn-1yn + xny1) -
           (x2y1 + x3y2 + ... + xnyn-1 + x1yn) ] |

Ниже приведена реализация вышеприведенной формулы.

CPP

// C ++ программа для оценки площади многоугольника с использованием
// формула шнурка
#include <bits/stdc++.h>

using namespace std;

  
// (X [i], Y [i]) - координаты i-й точки.

double polygonArea(double X[], double Y[], int n)

{

    // Initialze area

    double area = 0.0;

  

    // Рассчитать значение формулы шнурка

    int j = n - 1;

    for (int i = 0; i < n; i++)

    {

        area += (X[j] + X[i]) * (Y[j] - Y[i]);

        j = i;  // j - предыдущая вершина i

    }

  

    // Возвращаем абсолютное значение

    return abs(area / 2.0);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    double X[] = {0, 2, 4};

    double Y[] = {1, 3, 7};

  

    int n = sizeof(X)/sizeof(X[0]);

  

    cout << polygonArea(X, Y, n);

}

Джава

// Java-программа для оценки области
// многоугольника по формуле шнурка

import java.io.*;

  

class GFG 

{

    // (X [i], Y [i]) - координаты i-й точки.

    public static double polygonArea(double X[], double Y[], 

                                                       int n)

    {

        // Initialze area

        double area = 0.0;

      

        // Рассчитать значение формулы шнурка

        int j = n - 1;

        for (int i = 0; i < n; i++)

        {

            area += (X[j] + X[i]) * (Y[j] - Y[i]);

              

            // j - предыдущая вершина i

            j = i; 

        }

      

        // Возвращаем абсолютное значение

        return Math.abs(area / 2.0);

    }

  

    // Драйвер программы

    public static void main (String[] args)

    {

        double X[] = {0, 2, 4};

        double Y[] = {1, 3, 7};

      

        int n = 3;

        System.out.println(polygonArea(X, Y, n));

    }

  
}
// Этот код предоставлен Sunnnysingh

python3

# python3 программа для оценки
# площадь многоугольника, использующего
# формула шнурка

  
# (X [i], Y [i]) - координаты i-й точки.

def polygonArea(X, Y, n):

  

    # Начальная область

    area = 0.0

  

    # Рассчитать значение формулы шнурка

    j = n - 1

    for i in range(0,n):

        area += (X[j] + X[i]) * (Y[j] - Y[i])

        j = i   # j - предыдущая вершина i

      

  

    # Вернуть абсолютное значение

    return int(abs(area / 2.0))

  
# Программа драйвера для проверки вышеуказанной функции

X = [0, 2, 4]

Y = [1, 3, 7]

n = len(X)

print(polygonArea(X, Y, n))

  
# Этот код предоставлен
# Смита Динеш Семвал

C #

// C # программа для оценки площади
// многоугольника по формуле шнурка

using System;

  

class GFG {

      

    // (X [i], Y [i]) - координаты i-й точки.

    public static double polygonArea(double[] X,

                               double[] Y, int n)

    {

          

        // Initialze area

        double area = 0.0;

  

        // Рассчитать значение формулы шнурка

        int j = n - 1;

          

        for (int i = 0; i < n; i++) {

            area += (X[j] + X[i]) * (Y[j] - Y[i]);

  

            // j - предыдущая вершина i

            j = i;

        }

  

        // Возвращаем абсолютное значение

        return Math.Abs(area / 2.0);

    }

  

    // Драйвер программы

    public static void Main()

    {

        double[] X = { 0, 2, 4 };

        double[] Y = { 1, 3, 7 };

  

        int n = 3;

        Console.WriteLine(polygonArea(X, Y, n));

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP программа для оценки площади
// полигон, использующий формулу шнурка

  
// (X [i], Y [i])
// координаты i-й точки.

function polygonArea($X, $Y, $n)

{

    // Initialze area

    $area = 0.0;

  

    // Рассчитать значение

    // формула шнурка

    $j = $n - 1;

    for ($i = 0; $i < $n; $i++)

    {

        $area += ($X[$j] + $X[$i]) * 

                 ($Y[$j] - $Y[$i]);

                   

        // j - предыдущая вершина i

        $j = $i

    }

  

    // Возвращаем абсолютное значение

    return abs($area / 2.0);

}

  
// Код драйвера

$X = array(0, 2, 4);

$Y = array(1, 3, 7);

  

$n = sizeof($X);

  

echo polygonArea($X, $Y, $n);

  
// Этот код предоставлен ajit
?>


Выход :

2

Почему это называется формула шнурка?
Формула называется так из-за того, как мы ее оцениваем.

Пример :

Let the input vertices be
 (0, 1), (2, 3), and (4, 7). 

Evaluation procedure matches with process of tying
shoelaces.

We write vertices as below
  0    1
  2    3
  4    7
  0    1  [written twice]

we evaluate positive terms as below
  0  \  1
  2  \  3
  4  \  7
  0     1  
i.e., 0*3 + 2*7 + 4*1 = 18 

we evaluate negative terms as below
  0     1
  2  /  3
  4  /  7
  0  /  1  
i.e., 0*7 + 4*3 + 2*1 = 14

Area = 1/2 (18 - 14) = 2 

See this for a clearer image.

Как это работает?
Мы всегда можем разделить многоугольник на треугольники. Формула площади получается путем взятия каждого ребра AB и вычисления (подписанной) площади треугольника ABO с вершиной в начале O, путем получения перекрестного произведения (которое дает площадь параллелограмма) и деления на 2. Как один обернут вокруг полигона, эти треугольники с положительной и отрицательной области будут перекрываться, и области между началом координат и полигона будет отменен, и сумма в 0, в то время как только область внутри опорного треугольника остается. [Источник: Wiki ]

Статьи по Теме :
Минимальная стоимость полигональной триангуляции
Найти простой замкнутый путь для заданного набора точек

Эта статья предоставлена Уткаршем Триведи. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Площадь многоугольника с заданными n упорядоченными вершинами

0.00 (0%) 0 votes