How to determine the type of polygon

Question

The user inputs nth points. I need to check if a polygon exists and then to determine the type - concave or convex polygon. I know that a polygon is convex if every of it's angles is under 180 degrees. So the problem comes down to finding every inside corner of the polygon. I've been searching for the formula or algorithm but with no success.

Example:

Input: n = 4;

Point1: (5;6)

Point2: (4;-5)

Point3: (-5;4)

Point4: (-5;5)

Expected output: Polygon is convex

This is the code so far: Right now it only finds the max and minimum distance between the points in the plane.

#include "stdafx.h"
#include <iostream>
using namespace std;

int main()
{
    double a[15][2];
    int n;
    cin >> n;
    if (n <= 0 && n > 15)
        return 1;

    for (int i = 0; i < n; i++)
    {
        cout << "x" << i << " = , y" << i << " = ";
        cin >> a[i][0] >> a[i][1];
    }

    double maxDistance = 0.0;
    double minDistance = 0.0;
    double maxpoint1[2];
    double maxpoint2[2];
    double minpoint1[2];
    double minpoint2[2];

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (j != i)
            {
                double x1 = a[i][0];
                double x2 = a[j][0];
                double y1 = a[i][1];
                double y2 = a[j][1];
                double currentDistance = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));

                if (currentDistance > maxDistance)
                {
                    maxDistance = currentDistance;
                    maxpoint1[0] = x1;
                    maxpoint1[1] = y1;
                    maxpoint2[0] = x2;
                    maxpoint2[1] = y2;

                }

                if (minDistance > currentDistance)
                {
                    currentDistance = minDistance;
                    minpoint1[0] = x1;
                    minpoint1[1] = y1;
                    minpoint2[0] = x2;
                    minpoint2[1] = y2;
                }

                cout << "x1 = " << x1 << " y1 = " << y1 << " x2 = " << x2 << " y2 = " << y2;
                cout << endl << "Distance is " << currentDistance;
                cout << endl;
            }
        }
    }

    cout << "The max distance is: " << maxDistance << " between x1 = " << maxpoint1[0] << " y1 = " << maxpoint1[1] << " and x2 = " << maxpoint2[0] << " y2 = " << maxpoint2[1];
    cout << "The min distance is: " << minDistance << " between x1 = " << minpoint1[0] << " y1 = " << minpoint1[1] << " and x2 = " << minpoint2[0] << " y2 = " << minpoint2[1];


    return 0;
}

Answer 1

To find if polygon is convex or concave, just check signs of cross products for all sequential point triplets CrossProduct(P[0], P[1], P[2]) etc. As example

CrossProductSign(A, B, C) = 
               SignOf((B.X - A.X) * (C.Y - B.Y) - (B.Y - A.Y) * (C.X - B.X))

For convex one all cross products must have the same sign (+ or -).

How it works: for convex polygon every triplet makes turn in the same side (or CW, or CCW depending on walk direction). For concave one some signs will differ (where inner angle exceeds 180 degrees). Note that you don't need to calculate angle values.

Answer 2

If you want to find angle between two sides, use cross or dot product of vectors.

a dot b = |a||b| cos(angle_between_vectors) = a[0]*b[0] + a[1]*b[1] + a[2]*b[2]

inner angle would be (pi - angle_between_vectors)

Oh, by the way, polygon may intersect itself, that also detrimental issue in many use-cases. Your definition would fail to detect that.. e.g. complex quad would have all its angles to be less than 90 degrees.

That's not the only way to determine if polygon is convex, and probably one of most calculation rich ones? The problem with dot product that is that its sign would show if angle is less or greater than pi/2. The proper way to determine if your polygon is not complex or nonconvex is to check if direction of turn changes. For that you would need cross product. For 2d vectors result of their cross product got only z component (perpendicular to the plane), its sign determines which way rotation happened.

The question was here already.

How do determine if a polygon is complex/convex/nonconvex?