C语言如何根据输入的N边形顶点坐标判断其是否为凸多边形

凸多边形判断功能实现方案 #

判断逻辑 #

• 凸多边形所有相邻边的转向保持一致，我们可以通过连续三个顶点的向量叉积的符号判断转向：
  • 取连续三个顶点a、b、c，构造向量ab = (b.x - a.x, b.y - a.y)，bc = (c.x - b.x, c.y - b.y)
  • 叉积计算公式为 cross = ab.x * bc.y - ab.y * bc.x
  • cross>0代表逆时针转向，cross<0代表顺时针转向，cross=0代表三点共线
• 遍历所有相邻的三个顶点（首尾顶点需要相连，最后两组顶点为p[n-2],p[n-1],p[0]和p[n-1],p[0],p[1]），所有叉积的符号必须完全一致（如果允许边共线可兼容cross=0的情况），否则为凹多边形。

完整实现代码 #

#include <stdio.h> 
#include <math.h> 

typedef struct point 
{
    float x;    
    float y; 
} TPoint; 

// 计算三个点的叉积
float cross(TPoint a, TPoint b, TPoint c) {
    return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}

// 判断是否为凸多边形，返回1为凸，0为凹，-1为输入不合法
int isConvex(TPoint p[], int n) {
    if (n < 3) return -1; // 至少3个顶点才构成多边形
    int i;
    float cur_cross;
    // 先拿到第一个叉积的符号作为基准
    int sign = 0; 
    for (i = 0; i < n; i++) {
        // 取连续三个点，超出边界的取模回到开头
        TPoint a = p[i];
        TPoint b = p[(i+1)%n];
        TPoint c = p[(i+2)%n];
        cur_cross = cross(a, b, c);
        if (fabs(cur_cross) < 1e-6) { // 浮点误差处理，认为是共线
            continue; // 允许共线的情况保留这行，不允许的话直接return 0
        }
        int cur_sign = cur_cross > 0 ? 1 : -1;
        if (sign == 0) {
            sign = cur_sign; // 初始化基准符号
        } else if (cur_sign != sign) {
            return 0; // 符号不一致，为凹多边形
        }
    }
    return 1;
}

int main( void ) 
{ 
    TPoint p[20]; 
    int n, i; 
        
    printf("Number of sides ?\n"); 
    scanf("%d",&n); 
    if (n <3 || n>20) {
        printf("输入边数不合法，需为3~20之间的整数\n");
        return 0;
    }

    for(i=0;i<n;i++) 
    {
        printf("Point %d (x,y) ?\n",i+1); 
        scanf("%f", &p[i].x); 
        scanf("%f", &p[i].y); 
    } 

    int res = isConvex(p, n);
    if (res == -1) {
        printf("输入顶点数不足，无法构成多边形\n");
    } else if (res == 1) {
        printf("该多边形是凸多边形\n");
    } else {
        printf("该多边形是凹多边形\n");
    }
    
    return 0; 
}

说明 #

• 代码中对浮点计算做了误差处理，避免精度问题导致判断错误，阈值1e-6可根据需求调整
• 目前代码默认允许三点共线的情况，如果要求严格凸多边形（无共线边），把continue改为return 0即可
• 限制了最大顶点数为20，和你定义的数组长度p[20]保持一致

内容的提问来源于stack exchange，提问作者Marasha