0

I am trying to determine whether a line drawn connecting a number of points is convex or not. The points can be plotted on x,y coordinates. Can this be done in a way other than essentially connecting each point to every other point and seeing if all of those lines lie above the curve? Thanks! Here are sample points:

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
4

1 回答 1

0

凸函数

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

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

伪代码：

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 是单调递增的。

于 2015-04-29T01:26:06.873 回答