Area of a non-convex polygon

Problem: A polygon (not necessarily convex) is defined on the plane by listing the coordinates of the vertices in the order of traversing its boundary. Determine the area of the polygon.

I wrote code to calculate the area of a convex polygon (yes, with heap memory allocation). How can it be modified to calculate the area of a non-convex polygon and in general the algorithm for determining whether the entered polygon is convex or not? (If without splitting the polygon into shapes if not, then please write how to break it up and calculate each shape separately)

#include "stdafx.h"
#include <iostream>

using namespace System;
using namespace std;

int main()
{
    setlocale(0, "");
    int y, x, c, i = 0;
    cout << "Кол-во углов ";
    cin >> c;
    int(*coor)[2];
    coor = new int[c][2];
    while (i != c)
    {
        for (int j = 0; j < 2; j++)
        {
            cout << "Введите координаты " << endl;
            cout << "По X ";
            cin >> x;
            cout << "По Y ";
            cin >> y;
            coor[i][j] = x;
            j = 1;
            coor[i][j] = y;
            j = 2;
        }
        i++;
    };
    i = 0;
    int t = i + 1;
    double sum, pl = 0;
    for (i; t!= c; i++)
    {
        sum = ((coor[i][0] + coor[t][0])*(coor[i][1] - coor[t][1])) / 2;
        pl = pl + sum;
        t++;
    }
    cout << "Площадь " << abs(pl) << endl;
    system("pause");
    delete[]coor;
}

This is how the same program looks without arrays. Everything works right here. Apparently, I integrated the dynamic array here incorrectly... Please help me

int n, x, y, x1, x2, y1, y2;
    double sum = 0;
    cout << "Введите кол-во углов многоугольника: ";
    cin >> n;
    cout << "Введите координаты вершины многоугольника: ";
    cin >> x >> y;
    x1 = x;
    y1 = y;
    for (int i = 0; i < (n - 1); i++) 
    {
        cout << "Введите координаты следующей вершины: ";
        cin >> x2 >> y2;
        sum = sum + (x1 + x2)*(y2 - y1);
        x1 = x2;
        y1 = y2;
    }
    sum = sum + (x + x2)*(y - y2);
    sum = abs(sum) / 2;
    cout << fixed << setprecision(3) << sum << endl;
Author: llatibro, 2019-05-10

2 answers

You have some completely meaningless formula implemented in your code, which has no relation to any area, even for convex polygons.

Your formula seems vaguely similar to the "lacing" formula for calculating the area of a polygon. The "lacing" formula works perfectly for any simple polygon. There is no requirement for the convexity of the polygon in this formula. This is the formula you need.

That is: implement the correct formula. And remember that it involves all the edges of the polygon, including the edge from the last vertex to the first.


Your "pseudo-cycle" for (int j = 0; j < 2; j++) when entering coordinates is generally striking in its surreal nature. Why did you write theloop if you weren't going to do any loop there?


Your code "without arrays" is a variant of the correct implementation of the lacing formula.

 1
Author: AnT, 2019-05-10 19:13:52

Solved as follows, everything works correctly, even with non-convex triangles. Thank you for your comments, AnT.

#include "stdafx.h"
#include <iostream> 
#include <iomanip>
#include <cmath>

using namespace std;
int main()
{
    setlocale(0, "");
    int c, i = 0;
    cout << "Кол-во углов ";
    cin >> c;
    int(*coor)[2];
    coor = new int[c][2];
    while (i != c)
    {
        cout << "Введите координаты " << endl;
        cout << "По X ";
        cin >> coor[i][0];
        cout << "По Y ";
        cin >> coor[i][1];
        i++;
    };
    double sum = 0;
    i = 0;
    int t = 1;
    while (t != c) 
    {
        sum = sum + (coor[i][0] + coor[t][0])*(coor[t][1] - coor[i][1]);
        t++;
        i++;
    }
    t = c - 1;
    i = 0;
    sum = sum + (coor[i][0] + coor[t][0])*(coor[i][1] - coor[t][1]);
    cout << "Площадь " << fixed << setprecision(3) << abs(sum) / 2 << endl;
    system("pause");
    delete[]coor;
}
 0
Author: llatibro, 2019-05-11 10:03:07