GCC Code Coverage Report

Directory: ./
File: tasks/peryashkin_v_binary_component_contour_processing/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 72 74 97.3%
Functions: 11 11 100.0%
Branches: 76 178 42.7%
Line Branch Exec Source
1 #include "peryashkin_v_binary_component_contour_processing/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <queue>
7 #include <ranges>
8 #include <utility>
9 #include <vector>
10
11 #include "peryashkin_v_binary_component_contour_processing/common/include/common.hpp"
12
13 namespace peryashkin_v_binary_component_contour_processing {
14
15 namespace {
16
17 inline bool InBounds(int x, int y, int w, int h) {
18 2968 return (x >= 0) && (y >= 0) && (x < w) && (y < h);
19 }
20
21 inline std::int64_t Cross(const Point &o, const Point &a, const Point &b) {
22 720 return (static_cast<std::int64_t>(a.x - o.x) * static_cast<std::int64_t>(b.y - o.y)) -
23 720 (static_cast<std::int64_t>(a.y - o.y) * static_cast<std::int64_t>(b.x - o.x));
24 }
25
26
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 inline std::vector<Point> ConvexHullMonotonicChain(std::vector<Point> pts) {
27
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (pts.empty()) {
28 ✗ return {};
29 }
30
31
9/78
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✓ Branch 67 taken 320 times.
✓ Branch 68 taken 88 times.
✓ Branch 69 taken 232 times.
✗ Branch 70 not taken.
✓ Branch 71 taken 88 times.
✓ Branch 72 taken 288 times.
✓ Branch 73 taken 320 times.
✓ Branch 74 taken 216 times.
✓ Branch 75 taken 104 times.
✗ Branch 76 not taken.
✓ Branch 77 taken 216 times.
 928 std::ranges::sort(pts, [](const Point &a, const Point &b) { return (a.x < b.x) || ((a.x == b.x) && (a.y < b.y)); });
32
33 const auto uniq =
34
3/8
✓ Branch 0 taken 216 times.
✓ Branch 1 taken 104 times.
✓ Branch 2 taken 216 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 320 std::ranges::unique(pts, [](const Point &a, const Point &b) { return (a.x == b.x) && (a.y == b.y); });
35 pts.erase(uniq.begin(), pts.end());
36
37
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 48 times.
 56 if (pts.size() == 1) {
38 return pts;
39 }
40
41
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 std::vector<Point> lower;
42
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 lower.reserve(pts.size());
43
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 48 times.
 416 for (const auto &p : pts) {
44
4/4
✓ Branch 0 taken 360 times.
✓ Branch 1 taken 240 times.
✓ Branch 2 taken 232 times.
✓ Branch 3 taken 128 times.
 600 while ((lower.size() >= 2) && (Cross(lower[lower.size() - 2], lower[lower.size() - 1], p) <= 0)) {
45 lower.pop_back();
46 }
47 lower.push_back(p);
48 }
49
50
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 std::vector<Point> upper;
51
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 upper.reserve(pts.size());
52
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 48 times.
 416 for (std::size_t i = pts.size(); i-- > 0;) {
53 const auto &p = pts[i];
54
4/4
✓ Branch 0 taken 360 times.
✓ Branch 1 taken 240 times.
✓ Branch 2 taken 128 times.
✓ Branch 3 taken 232 times.
 600 while ((upper.size() >= 2) && (Cross(upper[upper.size() - 2], upper[upper.size() - 1], p) <= 0)) {
55 upper.pop_back();
56 }
57 upper.push_back(p);
58 }
59
60 lower.pop_back();
61 upper.pop_back();
62
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 lower.insert(lower.end(), upper.begin(), upper.end());
63 return lower;
64 }
65
66 inline std::size_t Idx(int x, int y, int w) {
67
5/6
✓ Branch 0 taken 376 times.
✓ Branch 1 taken 1528 times.
✓ Branch 3 taken 56 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 800 times.
✓ Branch 6 taken 624 times.
 3384 return (static_cast<std::size_t>(y) * static_cast<std::size_t>(w)) + static_cast<std::size_t>(x);
68 }
69
70
2/2
✓ Branch 0 taken 1464 times.
✓ Branch 1 taken 40 times.
 1504 inline void TryPush4(const BinaryImage &img, int w, int h, int nx, int ny, std::vector<std::uint8_t> &vis,
71 std::queue<Point> &q) {
72
2/2
✓ Branch 0 taken 1424 times.
✓ Branch 1 taken 40 times.
 1464 if (!InBounds(nx, ny, w, h)) {
73 return;
74 }
75 const std::size_t nid = Idx(nx, ny, w);
76
4/4
✓ Branch 0 taken 800 times.
✓ Branch 1 taken 624 times.
✓ Branch 2 taken 320 times.
✓ Branch 3 taken 480 times.
 1424 if ((img.data[nid] == 1) && (vis[nid] == 0U)) {
77 320 vis[nid] = 1U;
78 320 q.push(Point{.x = nx, .y = ny});
79 }
80 }
81
82 56 inline std::vector<Point> BfsComponent4(const BinaryImage &img, int w, int h, int sx, int sy,
83 std::vector<std::uint8_t> &vis) {
84 56 std::vector<Point> pts;
85
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 pts.reserve(128);
86
87 std::queue<Point> q;
88
89 const std::size_t sid = Idx(sx, sy, w);
90 56 vis[sid] = 1U;
91
92
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 q.push(Point{.x = sx, .y = sy});
93
94
2/2
✓ Branch 0 taken 376 times.
✓ Branch 1 taken 56 times.
 432 while (!q.empty()) {
95 376 const Point p = q.front();
96 q.pop();
97
98 pts.push_back(p);
99
100
1/2
✓ Branch 1 taken 376 times.
✗ Branch 2 not taken.
 376 TryPush4(img, w, h, p.x + 1, p.y, vis, q);
101
1/2
✓ Branch 1 taken 376 times.
✗ Branch 2 not taken.
 376 TryPush4(img, w, h, p.x - 1, p.y, vis, q);
102
1/2
✓ Branch 1 taken 376 times.
✗ Branch 2 not taken.
 376 TryPush4(img, w, h, p.x, p.y + 1, vis, q);
103
1/2
✓ Branch 1 taken 376 times.
✗ Branch 2 not taken.
 376 TryPush4(img, w, h, p.x, p.y - 1, vis, q);
104 }
105
106 56 return pts;
107 }
108
109 56 inline std::vector<std::vector<Point>> ExtractComponents4(const BinaryImage &img) {
110 56 const int w = img.width;
111 56 const int h = img.height;
112
113 56 std::vector<std::vector<Point>> comps;
114
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if ((w <= 0) || (h <= 0)) {
115 return comps;
116 }
117
118 56 const std::size_t n = static_cast<std::size_t>(w) * static_cast<std::size_t>(h);
119
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 std::vector<std::uint8_t> vis(n, 0U);
120
121
2/2
✓ Branch 0 taken 304 times.
✓ Branch 1 taken 56 times.
 360 for (int yy = 0; yy < h; ++yy) {
122
2/2
✓ Branch 0 taken 1904 times.
✓ Branch 1 taken 304 times.
 2208 for (int xx = 0; xx < w; ++xx) {
123 const std::size_t id = Idx(xx, yy, w);
124
4/4
✓ Branch 0 taken 376 times.
✓ Branch 1 taken 1528 times.
✓ Branch 2 taken 320 times.
✓ Branch 3 taken 56 times.
 1904 if ((img.data[id] == 0) || (vis[id] != 0U)) {
125 1848 continue;
126 }
127
1/4
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 112 comps.push_back(BfsComponent4(img, w, h, xx, yy, vis));
128 }
129 }
130
131 return comps;
132 ✗ }
133
134 56 inline OutType SolveSTL(const BinaryImage &img) {
135 56 auto comps = ExtractComponents4(img);
136
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 OutType hulls;
137
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 hulls.resize(comps.size());
138
139
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 std::vector<std::size_t> indices(comps.size());
140
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 56 times.
 112 for (std::size_t i = 0; i < indices.size(); ++i) {
141 56 indices[i] = i;
142 }
143
144
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 112 std::ranges::for_each(indices, [&](std::size_t i) { hulls[i] = ConvexHullMonotonicChain(std::move(comps[i])); });
145
146 56 return hulls;
147 56 }
148
149 } // namespace
150
151
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 PeryashkinVBinaryComponentContourProcessingSTL::PeryashkinVBinaryComponentContourProcessingSTL(const InType &in) {
152 SetTypeOfTask(GetStaticTypeOfTask());
153 GetInput() = in;
154 GetOutput().clear();
155 56 }
156
157 112 bool PeryashkinVBinaryComponentContourProcessingSTL::ValidationImpl() {
158 const auto &in = GetInput();
159
2/4
✓ Branch 0 taken 112 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 112 times.
✗ Branch 3 not taken.
 112 if ((in.width <= 0) || (in.height <= 0)) {
160 return false;
161 }
162 112 const std::size_t need = static_cast<std::size_t>(in.width) * static_cast<std::size_t>(in.height);
163 112 return in.data.size() == need;
164 }
165
166
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 bool PeryashkinVBinaryComponentContourProcessingSTL::PreProcessingImpl() {
167 local_out_.clear();
168 56 return true;
169 }
170
171 56 bool PeryashkinVBinaryComponentContourProcessingSTL::RunImpl() {
172
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 if (!ValidationImpl()) {
173 return false;
174 }
175
176 56 local_out_ = SolveSTL(GetInput());
177 56 return true;
178 }
179
180 56 bool PeryashkinVBinaryComponentContourProcessingSTL::PostProcessingImpl() {
181 56 GetOutput() = local_out_;
182 56 return true;
183 }
184
185 } // namespace peryashkin_v_binary_component_contour_processing
186