确定图形是否凸

Question

我正在尝试确定连接多个点的线是否是凸的。 这些点可以绘制在 x，y 坐标上。 这是否可以以一种方式完成，而不是基本上将每个点连接到每个其他点，并查看所有这些线是否都在曲线上方？ 谢谢！以下是示例点：

X           Y
1191.06     0.9655265 
1192.36     0.9644738 
1193.75     0.9633508 
1194.98     0.9623592 
1196.49     0.9611447 
1197.78     0.9601095
1199.02     0.9591166 
1200.29     0.9581017 
1201.56     0.9570891 
1202.77     0.9561263 
1204.01     0.9551415 
1205.26     0.9541510  

Answer 1

凸

函数

一个变量的可微函数在区间上是凸的，当且仅当它的导数在该区间上单调不递减时。如果一个函数是可微的和凸的，那么它也是连续可微的。对于从实数（子集）到实数的可微函数的基本情况，"凸"等价于"以递增的速度增加"。

您可以遍历这些点，并检查序列中每对连续点之间的斜率是否严格不减小。您不必将每个点连接到每个其他点。

伪代码：

boolean isConvex(float[] x, float[] y, int length)
{
    float previousSlope = 0;
    for(int i = 1; i < length; i++)
    {
        if(x[i] == x[i-1])
        {
            // handle infinite gradients to avoid div by zero
            // if you are not going to exclude this case from your data
        }
        float slope = (y[i] - y[i-1]) / (x[i] - x[i-1]);
        // only compare the slope after the first iteration:
        if((i > 1) && (slope < previousSlope))
            return false;
        previousSlope = slope;
    }
    return true;
}

这假设 y 是 x 的函数，并且数组中的值根据 x 按升序排序，并且 x 单调递增。