anonymous_namespace{graph.cpp} Namespace Reference

Functions
void	dt_1d (const std::vector< float > &f, std::vector< float > &d, int n)
float	max_inscribed_radius (const Node_ptr &n)

Function Documentation

dt_1d()

void anonymous_namespace{graph.cpp}::dt_1d	(	const std::vector< float > &	f,
		std::vector< float > &	d,
		int	n
	)

Definition at line 313 of file graph.cpp.

                                                                  {
    constexpr float INF = 1e20f;
    std::vector<int> v(n);
    std::vector<float> z(n + 1);
    int k = 0;
    v[0] = 0;
    z[0] = -INF;
    z[1] = INF;
    for (int q = 1; q < n; ++q) {
        float s;
        while (true) {
            s = ((f[q] + static_cast<float>(q) * q) - (f[v[k]] + static_cast<float>(v[k]) * v[k])) /
                (2.0f * static_cast<float>(q - v[k]));
            if (s <= z[k] && k > 0) {
                --k;
            } else {
                break;
            }
        }
        ++k;
        v[k] = q;
        z[k] = s;
        z[k + 1] = INF;
    }
    k = 0;
    for (int q = 0; q < n; ++q) {
        while (z[k + 1] < static_cast<float>(q))
            ++k;
        const float dq = static_cast<float>(q - v[k]);
        d[q] = dq * dq + f[v[k]];
    }
}

max_inscribed_radius()

float anonymous_namespace{graph.cpp}::max_inscribed_radius

(

const Node_ptr &

n

)

Definition at line 351 of file graph.cpp.

                                              {
    std::vector<uint8_t> mask;
    const std::array<int, 4> xywh = n->create_binary_image(mask); // tight bbox
    const int w = xywh[2];
    const int h = xywh[3];
    if (w <= 0 || h <= 0)
        return 0.0f;
 
    // Pad by one pixel so the region's boundary against the exterior is treated
    // as background by the distance transform.
    const int pw = w + 2;
    const int ph = h + 2;
    constexpr float INF = 1e20f;
 
    std::vector<float> grid(static_cast<size_t>(pw) * ph);
    for (int y = 0; y < ph; ++y) {
        for (int x = 0; x < pw; ++x) {
            const bool inside = x >= 1 && x <= w && y >= 1 && y <= h &&
                                mask[static_cast<size_t>(y - 1) * w + (x - 1)];
            grid[static_cast<size_t>(y) * pw + x] = inside ? INF : 0.0f;
        }
    }
 
    // Separable two-pass transform: columns first, then rows.
    std::vector<float> in, out(std::max(pw, ph));
    in.resize(ph);
    for (int x = 0; x < pw; ++x) {
        for (int y = 0; y < ph; ++y)
            in[y] = grid[static_cast<size_t>(y) * pw + x];
        dt_1d(in, out, ph);
        for (int y = 0; y < ph; ++y)
            grid[static_cast<size_t>(y) * pw + x] = out[y];
    }
    in.resize(pw);
    float max_d2 = 0.0f;
    for (int y = 0; y < ph; ++y) {
        for (int x = 0; x < pw; ++x)
            in[x] = grid[static_cast<size_t>(y) * pw + x];
        dt_1d(in, out, pw);
        for (int x = 0; x < pw; ++x)
            if (out[x] > max_d2)
                max_d2 = out[x];
    }
    return std::sqrt(max_d2);
}