Function dt

dep/agg/include/agg_span_gradient_contour.h:151–191

DT algorithm by: Pedro Felzenszwalb

    // DT algorithm by: Pedro Felzenszwalb
    void dt(float* spanf, float* spang, float* spanr, int* spann, int length)
    {
        int k = 0;
        float s;

        spann[0] = 0;
        spang[0] = -FLT_MAX;
        spang[1] = FLT_MAX;

        for (int q = 1; q <= length - 1; q++)
        {
            s = ((spanf[q] + square(q)) -
                    (spanf[spann[k]] + square(spann[k]))) /
                (2 * q - 2 * spann[k]);

            while (s <= spang[k])
            {
                k--;
                s = ((spanf[q] + square(q)) -
                        (spanf[spann[k]] + square(spann[k]))) /
                    (2 * q - 2 * spann[k]);
            }

            k++;
            spann[k] = q;
            spang[k] = s;
            spang[k + 1] = FLT_MAX;
        }

        k = 0;

        for (int q = 0; q <= length - 1; q++)
        {
            while (spang[k + 1] < q)
            {
                k++;
            }

            spanr[q] = square(q - spann[k]) + spanf[spann[k]];
        }
    }

    // DT algorithm by: Pedro Felzenszwalb
    int8u* gradient_contour::contour_create(path_storage* ps)