Img2Num C++ (Internal Developer Docs) dev
API Documentation
Loading...
Searching...
No Matches
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 172 of file graph.cpp.

172 {
173 constexpr float INF = 1e20f;
174 std::vector<int> v(n);
175 std::vector<float> z(n + 1);
176 int k = 0;
177 v[0] = 0;
178 z[0] = -INF;
179 z[1] = INF;
180 for (int q = 1; q < n; ++q) {
181 float s;
182 while (true) {
183 s = ((f[q] + static_cast<float>(q) * q) - (f[v[k]] + static_cast<float>(v[k]) * v[k])) /
184 (2.0f * static_cast<float>(q - v[k]));
185 if (s <= z[k] && k > 0) {
186 --k;
187 } else {
188 break;
189 }
190 }
191 ++k;
192 v[k] = q;
193 z[k] = s;
194 z[k + 1] = INF;
195 }
196 k = 0;
197 for (int q = 0; q < n; ++q) {
198 while (z[k + 1] < static_cast<float>(q))
199 ++k;
200 const float dq = static_cast<float>(q - v[k]);
201 d[q] = dq * dq + f[v[k]];
202 }
203}

◆ max_inscribed_radius()

float anonymous_namespace{graph.cpp}::max_inscribed_radius ( const Node_ptr &  n)

Definition at line 210 of file graph.cpp.

210 {
211 std::vector<uint8_t> mask;
212 const std::array<int, 4> xywh = n->create_binary_image(mask); // tight bbox
213 const int w = xywh[2];
214 const int h = xywh[3];
215 if (w <= 0 || h <= 0)
216 return 0.0f;
217
218 // Pad by one pixel so the region's boundary against the exterior is treated
219 // as background by the distance transform.
220 const int pw = w + 2;
221 const int ph = h + 2;
222 constexpr float INF = 1e20f;
223
224 std::vector<float> grid(static_cast<size_t>(pw) * ph);
225 for (int y = 0; y < ph; ++y) {
226 for (int x = 0; x < pw; ++x) {
227 const bool inside = x >= 1 && x <= w && y >= 1 && y <= h &&
228 mask[static_cast<size_t>(y - 1) * w + (x - 1)];
229 grid[static_cast<size_t>(y) * pw + x] = inside ? INF : 0.0f;
230 }
231 }
232
233 // Separable two-pass transform: columns first, then rows.
234 std::vector<float> in, out(std::max(pw, ph));
235 in.resize(ph);
236 for (int x = 0; x < pw; ++x) {
237 for (int y = 0; y < ph; ++y)
238 in[y] = grid[static_cast<size_t>(y) * pw + x];
239 dt_1d(in, out, ph);
240 for (int y = 0; y < ph; ++y)
241 grid[static_cast<size_t>(y) * pw + x] = out[y];
242 }
243 in.resize(pw);
244 float max_d2 = 0.0f;
245 for (int y = 0; y < ph; ++y) {
246 for (int x = 0; x < pw; ++x)
247 in[x] = grid[static_cast<size_t>(y) * pw + x];
248 dt_1d(in, out, pw);
249 for (int x = 0; x < pw; ++x)
250 if (out[x] > max_d2)
251 max_d2 = out[x];
252 }
253 return std::sqrt(max_d2);
254}