如何判断给定的多边形是否为凸多边形

给定一个二维数组 point[][]，其中每一行的格式为 {X, Y}，代表了一个按顺时针或逆时针顺序排列的 多边形 的坐标。我们的任务是检查该多边形是否为 凸多边形。如果是，则打印 “Yes”，否则打印 “No”。

> 在凸多边形中，所有内角都必须小于或等于 180 度。

示例：

> 输入： arr[] = { (0, 0), (0, 1), (1, 1), (1, 0) }

> 输出： Yes

> 解释：

> !image

> 因为该多边形的所有内角都小于 180 度。因此，要求的输出是 Yes。

>

> 输入： arr[] = {(0, 0), (0, 10), (5, 5), (10, 10), (10, 0)}

> 输出： No

> 解释：

> !image

> 因为该多边形并非所有内角都小于 180 度。因此，要求的输出是 No。

方法： 我们可以按照以下步骤来解决这个问题：

• 遍历数组，并检查多边形任意两条相邻边的 叉积 方向是否相同。如果相同，则打印 “Yes”。
• 否则，打印 “No”。

下面是上述方法的实现：

C++

// C++ program to implement
// the above approach

#include 
using namespace std;

// Utility function to find cross product
// of two vectors
int CrossProduct(vector<vector >& A)
{
    // Stores coefficient of X
    // direction of vector A[1]A[0]
    int X1 = (A[1][0] - A[0][0]);

    // Stores coefficient of Y
    // direction of vector A[1]A[0]
    int Y1 = (A[1][1] - A[0][1]);

    // Stores coefficient of X
    // direction of vector A[2]A[0]
    int X2 = (A[2][0] - A[0][0]);

    // Stores coefficient of Y
    // direction of vector A[2]A[0]
    int Y2 = (A[2][1] - A[0][1]);

    // Return cross product
    return (X1 * Y2 - Y1 * X2);
}

// Function to check if the polygon is
// convex polygon or not
bool isConvex(vector<vector >& points)
{
    // Stores count of
    // edges in polygon
    int N = points.size();

    // Stores direction of cross product
    // of previous traversed edges
    int prev = 0;

    // Stores direction of cross product
    // of current traversed edges
    int curr = 0;

    // Traverse the array
    for (int i = 0; i < N; i++) {

        // Stores three adjacent edges
        // of the polygon
        vector<vector > temp
            = { points[i],
                points[(i + 1) % N],
                points[(i + 2) % N] };

        // Update curr
        curr = CrossProduct(temp);

        // If curr is not equal to 0
        if (curr != 0) {

            // If direction of cross product of
            // all adjacent edges are not same
            if (curr * prev < 0) {
                return false;
            }
            else {
                // Update curr
                prev = curr;
            }
        }
    }
    return true;
}

// Driver code
int main()
{
    vector<vector > points
        = { { 0, 0 }, { 0, 1 }, 
            { 1, 1 }, { 1, 0 } };

    if (isConvex(points)) {
        cout << "Yes"
             << "
";
    }
    else {
        cout << "No"
             << "
";
    }
}

“

// Java program to implement

// the above approach

class GFG

{

// Utility function to find cross product

// of two vectors

static int CrossProduct(int A[][])

{

// Stores coefficient of X

// direction of vector A[1]A[0]

int X1 = (A[1][0] – A[0][0]);

// Stores coefficient of Y

// direction of vector A[1]A[0]

int Y1 = (A[1][1] – A[0][1]);

// Stores coefficient of X

// direction of vector A[2]A[0]

int X2 = (A[2][0] – A[0][0]);

// Stores coefficient of Y

// direction of vector A[2]A[0]

int Y2 = (A[2][1] – A[0][1]);

// Return cross product

return (X1 Y2 – Y1 X2);

}

// Function to check if the polygon is

// convex polygon or not

static boolean isConvex(int points[][])

{

// Stores count of

// edges in polygon

int N = points.length;

// Stores direction of cross product

// of previous traversed edges

int prev = 0;

// Stores direction of cross product

// of current traversed edges

int curr = 0;

// Traverse the array

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

// Stores three adjacent edges

// of the polygon

int temp[][]= { points[i],

points[(i + 1) % N],