1#include "internal/graph.h"
3#include "internal/bezier.h"
4#include "internal/Pixel.h"
5#include "internal/shared_contours.h"
23void Graph::hash_node_ids() {
24 for (int32_t i {0}; i < m_nodes->size(); i++) {
25 const int32_t key {m_nodes->at(i)->id()};
30bool Graph::add_edge(int32_t node_id1, int32_t node_id2) {
31 auto end_node_ids {m_node_ids.end()};
32 auto node1_it {m_node_ids.find(node_id1)};
33 auto node2_it {m_node_ids.find(node_id2)};
35 if (node1_it == end_node_ids || node2_it == end_node_ids) {
39 const int32_t idx1 {node1_it->second};
40 const int32_t idx2 {node2_it->second};
42 m_nodes->at(idx1)->add_edge(m_nodes->at(idx2));
43 m_nodes->at(idx2)->add_edge(m_nodes->at(idx1));
47bool Graph::merge_nodes(
const Node_ptr& node_to_keep,
const Node_ptr& node_to_remove) {
48 auto end_node_ids {m_node_ids.end()};
49 auto node1_it {m_node_ids.find(node_to_keep->id())};
50 auto node2_it {m_node_ids.find(node_to_remove->id())};
52 if (node1_it == end_node_ids || node2_it == end_node_ids) {
56 const int32_t idx_k {node1_it->second};
57 const int32_t idx_r {node2_it->second};
60 for (Node_ptr n : m_nodes->at(idx_r)->edges()) {
61 if (n->id() != node_to_keep->id()) {
63 n->remove_edge(node_to_remove);
64 n->add_edge(node_to_keep);
65 node_to_keep->add_edge(n);
69 node_to_keep->add_pixels(node_to_remove->get_pixels());
71 node_to_remove->clear_all();
76void Graph::clear_unconnected_nodes() {
77 std::vector<Node_ptr>& nodes {*m_nodes};
81 nodes.begin(), nodes.end(), [](
const Node_ptr& n) { return n->area() == 0; }
89void Graph::discover_edges(
90 const std::vector<int32_t>& region_labels,
const int32_t width,
const int32_t height
93 constexpr int8_t dirs[8][2] {{1, 0}, {-1, 0}, {0, 1}, {0, -1},
94 {1, 1}, {-1, -1}, {-1, 1}, {1, -1}};
98 for (int32_t y {0}; y < height; ++y) {
99 for (int32_t x {0}; x < width; ++x) {
100 const int32_t idx {y * width + x};
101 const int32_t rid {region_labels[idx]};
103 for (int32_t k {0}; k < 8; ++k) {
104 const int32_t nx {x + dirs[k][0]};
105 const int32_t ny {y + dirs[k][1]};
107 if (nx >= 0 && nx < width && ny >= 0 && ny < height) {
108 rneigh[k] = region_labels[ny * width + nx];
114 for (int32_t r : rneigh) {
123void Graph::compute_contours() {
133 std::vector<int32_t> labels(
static_cast<size_t>(m_width) * m_height, -1);
134 for (
const Node_ptr& n : get_nodes()) {
137 for (
auto& p : n->get_pixels())
138 labels[static_cast<size_t>(p.position.y) * m_width + p.position.x] = n->id();
141 auto loops = build_shared_loops(labels, m_width, m_height, eps);
143 for (
const Node_ptr& n : get_nodes()) {
147 auto it = loops.find(n->id());
148 if (it == loops.end())
152 for (std::vector<QuadBezier>& curve : it->second) {
153 std::vector<Point> anchors;
154 anchors.reserve(curve.size() + 1);
156 anchors.push_back(q.p0);
158 anchors.push_back(curve.back().p2);
159 n->m_contours.contours.push_back(std::move(anchors));
160 n->m_contours.curves.push_back(std::move(curve));
161 n->m_contours.colors.push_back(col);
162 n->m_contours.hierarchy.push_back({-1, -1, -1, -1});
163 n->m_contours.is_hole.push_back(
false);
172void dt_1d(
const std::vector<float>& f, std::vector<float>& d,
int n) {
173 constexpr float INF = 1e20f;
174 std::vector<int> v(n);
175 std::vector<float> z(n + 1);
180 for (
int q = 1; q < n; ++q) {
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) {
197 for (
int q = 0; q < n; ++q) {
198 while (z[k + 1] <
static_cast<float>(q))
200 const float dq =
static_cast<float>(q - v[k]);
201 d[q] = dq * dq + f[v[k]];
210float max_inscribed_radius(
const Node_ptr& n) {
211 std::vector<uint8_t> mask;
212 const std::array<int, 4> xywh = n->create_binary_image(mask);
213 const int w = xywh[2];
214 const int h = xywh[3];
215 if (w <= 0 || h <= 0)
220 const int pw = w + 2;
221 const int ph = h + 2;
222 constexpr float INF = 1e20f;
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;
234 std::vector<float> in, out(std::max(pw, 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];
240 for (
int y = 0; y < ph; ++y)
241 grid[
static_cast<size_t>(y) * pw + x] = out[y];
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];
249 for (
int x = 0; x < pw; ++x)
253 return std::sqrt(max_d2);
258void Graph::merge_small_area_nodes(
const int32_t min_area,
const int32_t min_thickness) {
263 bool merged_any =
true;
267 for (
const Node_ptr& n : get_nodes()) {
271 bool needs_merge = n->area() <
static_cast<size_t>(min_area);
272 if (!needs_merge && min_thickness > 0) {
274 needs_merge = 2.0f * max_inscribed_radius(n) <
static_cast<float>(min_thickness);
281 Node_ptr best_neighbor =
nullptr;
282 float best_score = std::numeric_limits<float>::max();
283 for (
const Node_ptr& ne : n->edges()) {
284 if (ne->area() > 0) {
286 float score =
static_cast<float>(ne->area()) + 10.f * cdist;
287 if (score < best_score) {
295 if (!best_neighbor) {
299 if (best_neighbor->area() >= n->area()) {
300 merge_nodes(best_neighbor, n);
302 merge_nodes(n, best_neighbor);
307 clear_unconnected_nodes();