GCC Code Coverage Report

Directory: ./
File: tasks/dorogin_v_bin_img_conv_hull/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 113 118 95.8%
Functions: 11 13 84.6%
Branches: 105 150 70.0%
Line Branch Exec Source
1 #include "dorogin_v_bin_img_conv_hull/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <array>
7 #include <cstddef>
8 #include <cstdint>
9 #include <functional>
10 #include <queue>
11 #include <ranges>
12 #include <utility>
13 #include <vector>
14
15 #include "dorogin_v_bin_img_conv_hull/common/include/common.hpp"
16 #include "oneapi/tbb/parallel_for.h"
17
18 namespace dorogin_v_bin_img_conv_hull {
19
20 namespace {
21
22 constexpr std::uint8_t kThreshold = 128;
23
24 constexpr std::array<std::pair<int, int>, 4> kNeighbours = {{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}};
25
26 bool CellInImage(int x, int y, int width, int height) {
27 732 return x >= 0 && x < width && y >= 0 && y < height;
28 }
29
30 bool IsForeground(std::uint8_t pixel) {
31 return pixel > kThreshold;
32 }
33
34 std::int64_t Orient(const Point &a, const Point &b, const Point &c) {
35 302 const std::int64_t x1 = static_cast<std::int64_t>(b.x) - static_cast<std::int64_t>(a.x);
36 302 const std::int64_t y1 = static_cast<std::int64_t>(b.y) - static_cast<std::int64_t>(a.y);
37 302 const std::int64_t x2 = static_cast<std::int64_t>(c.x) - static_cast<std::int64_t>(a.x);
38 302 const std::int64_t y2 = static_cast<std::int64_t>(c.y) - static_cast<std::int64_t>(a.y);
39 302 return (x1 * y2) - (y1 * x2);
40 }
41
42 5 std::vector<int> FlattenHulls(const std::vector<std::vector<Point>> &hulls) {
43
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 std::vector<int> buf;
44
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 buf.push_back(static_cast<int>(hulls.size()));
45
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 5 times.
 11 for (const auto &hull : hulls) {
46
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 buf.push_back(static_cast<int>(hull.size()));
47
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 6 times.
 19 for (const Point &p : hull) {
48
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 10 times.
 13 buf.push_back(p.x);
49
1/2
✓ Branch 0 taken 13 times.
✗ Branch 1 not taken.
 13 buf.push_back(p.y);
50 }
51 }
52 5 return buf;
53 }
54
55
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 std::vector<std::vector<Point>> RestoreHulls(const std::vector<int> &buf) {
56
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 if (buf.empty()) {
57 ✗ return {};
58 }
59 std::size_t pos = 0;
60 10 const int num_hulls = buf[pos++];
61
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 std::vector<std::vector<Point>> hulls;
62
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 hulls.reserve(static_cast<std::size_t>(std::max(0, num_hulls)));
63
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 10 times.
 22 for (int hull_index = 0; hull_index < num_hulls; ++hull_index) {
64
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (pos >= buf.size()) {
65 break;
66 }
67
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 const int point_count = buf[pos++];
68
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<Point> hull;
69
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 hull.reserve(static_cast<std::size_t>(std::max(0, point_count)));
70
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 12 times.
 38 for (int point_index = 0; point_index < point_count; ++point_index) {
71
1/2
✓ Branch 0 taken 26 times.
✗ Branch 1 not taken.
 26 if (pos + 1 >= buf.size()) {
72 break;
73 }
74
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 hull.emplace_back(buf[pos], buf[pos + 1]);
75 26 pos += 2;
76 }
77 hulls.push_back(std::move(hull));
78 }
79 return hulls;
80 10 }
81
82 } // namespace
83
84 ✗ std::size_t DoroginVBinImgConvHullALL::Index(int col, int row, int width) {
85
4/4
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 170 times.
✓ Branch 2 taken 164 times.
✓ Branch 3 taken 196 times.
 622 return (static_cast<std::size_t>(row) * static_cast<std::size_t>(width)) + static_cast<std::size_t>(col);
86 }
87
88
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 DoroginVBinImgConvHullALL::DoroginVBinImgConvHullALL(const InType &in) : work_(in) {
89 SetTypeOfTask(GetStaticTypeOfTask());
90
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 GetInput() = in;
91 10 }
92
93 15 bool DoroginVBinImgConvHullALL::ValidationImpl() {
94 const auto &in = GetInput();
95
2/4
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 15 times.
✗ Branch 3 not taken.
 15 if (in.width <= 0 || in.height <= 0) {
96 return false;
97 }
98 15 return in.pixels.size() == static_cast<std::size_t>(in.width) * static_cast<std::size_t>(in.height);
99 }
100
101 10 bool DoroginVBinImgConvHullALL::PreProcessingImpl() {
102 10 work_ = GetInput();
103 work_.components.clear();
104 work_.convex_hulls.clear();
105 ThresholdPixelsParallel();
106 10 return true;
107 }
108
109 ✗ void DoroginVBinImgConvHullALL::ThresholdPixelsParallel() {
110 10 auto &pixels = work_.pixels;
111 10 tbb::parallel_for(static_cast<std::size_t>(0), pixels.size(), [&](std::size_t idx) {
112
4/4
✓ Branch 0 taken 66 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 274 times.
✓ Branch 3 taken 164 times.
 864 pixels[idx] = IsForeground(pixels[idx]) ? static_cast<std::uint8_t>(255) : static_cast<std::uint8_t>(0);
113 });
114 ✗ }
115
116 6 void DoroginVBinImgConvHullALL::FloodFill(int seed_x, int seed_y, int width, int height,
117 std::vector<std::uint8_t> &visited, std::vector<Point> &component) {
118 std::queue<Point> q;
119 q.emplace(seed_x, seed_y);
120 6 visited[Index(seed_x, seed_y, width)] = 1;
121
2/2
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 6 times.
 98 while (!q.empty()) {
122 92 const Point cur = q.front();
123 q.pop();
124 component.push_back(cur);
125
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 92 times.
 460 for (const auto &[dx, dy] : kNeighbours) {
126 368 const int nx = cur.x + dx;
127
2/2
✓ Branch 0 taken 364 times.
✓ Branch 1 taken 4 times.
 368 const int ny = cur.y + dy;
128
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 360 times.
 364 if (!CellInImage(nx, ny, width, height)) {
129 282 continue;
130 }
131 const std::size_t ni = Index(nx, ny, width);
132
4/4
✓ Branch 0 taken 164 times.
✓ Branch 1 taken 196 times.
✓ Branch 2 taken 86 times.
✓ Branch 3 taken 78 times.
 360 if (visited[ni] != 0U || work_.pixels[ni] == 0) {
133 274 continue;
134 }
135
1/2
✓ Branch 1 taken 86 times.
✗ Branch 2 not taken.
 86 visited[ni] = 1;
136 q.emplace(nx, ny);
137 }
138 }
139 6 }
140
141 5 void DoroginVBinImgConvHullALL::CollectComponentsSequential() {
142 5 const int width = work_.width;
143 5 const int height = work_.height;
144
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 5 times.
 5 std::vector<std::uint8_t> visited(static_cast<std::size_t>(width) * static_cast<std::size_t>(height), 0);
145 work_.components.clear();
146
147
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 5 times.
 37 for (int row = 0; row < height; ++row) {
148
2/2
✓ Branch 0 taken 262 times.
✓ Branch 1 taken 32 times.
 294 for (int col = 0; col < width; ++col) {
149 const std::size_t idx = Index(col, row, width);
150
4/4
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 170 times.
✓ Branch 2 taken 86 times.
✓ Branch 3 taken 6 times.
 262 if (work_.pixels[idx] == 0 || visited[idx] != 0U) {
151 256 continue;
152 }
153 6 std::vector<Point> comp;
154
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 FloodFill(col, row, width, height, visited, comp);
155
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (!comp.empty()) {
156
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 work_.components.push_back(std::move(comp));
157 }
158 }
159 }
160 5 }
161
162
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 std::vector<Point> DoroginVBinImgConvHullALL::BuildHull(const std::vector<Point> &points) {
163
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (points.size() < 3) {
164 ✗ return points;
165 }
166 3 std::vector<Point> pts = points;
167 std::ranges::sort(pts, std::less<>{});
168 const auto uniq = std::ranges::unique(pts);
169 pts.erase(uniq.begin(), uniq.end());
170
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (pts.size() < 3) {
171 return pts;
172 }
173
174 3 std::vector<Point> lower;
175
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 std::vector<Point> upper;
176
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 lower.reserve(pts.size());
177
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 upper.reserve(pts.size());
178
179
2/2
✓ Branch 0 taken 89 times.
✓ Branch 1 taken 3 times.
 92 for (const auto &p : pts) {
180
4/4
✓ Branch 0 taken 151 times.
✓ Branch 1 taken 19 times.
✓ Branch 2 taken 81 times.
✓ Branch 3 taken 70 times.
 170 while (lower.size() >= 2 && Orient(lower[lower.size() - 2], lower.back(), p) <= 0) {
181 lower.pop_back();
182 }
183 lower.push_back(p);
184 }
185
2/2
✓ Branch 0 taken 89 times.
✓ Branch 1 taken 3 times.
 92 for (const auto &p : std::ranges::reverse_view(pts)) {
186
4/4
✓ Branch 0 taken 151 times.
✓ Branch 1 taken 19 times.
✓ Branch 2 taken 70 times.
✓ Branch 3 taken 81 times.
 170 while (upper.size() >= 2 && Orient(upper[upper.size() - 2], upper.back(), p) <= 0) {
187 upper.pop_back();
188 }
189 upper.push_back(p);
190 }
191 lower.pop_back();
192 upper.pop_back();
193
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 lower.insert(lower.end(), upper.begin(), upper.end());
194 return lower;
195 }
196
197 10 bool DoroginVBinImgConvHullALL::RunImpl() {
198 10 int rank = 0;
199 10 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
200
201 10 int ok = 0;
202
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank == 0) {
203
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 5 times.
 5 ok = ValidationImpl() ? 1 : 0;
204 }
205 10 MPI_Bcast(&ok, 1, MPI_INT, 0, MPI_COMM_WORLD);
206
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (ok == 0) {
207 return false;
208 }
209
210
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank == 0) {
211 5 CollectComponentsSequential();
212 5 auto &comps = work_.components;
213 5 auto &hulls = work_.convex_hulls;
214 5 hulls.resize(comps.size());
215 5 tbb::parallel_for(static_cast<std::size_t>(0), comps.size(), [&](std::size_t idx) {
216
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 const auto &comp = comps[idx];
217
3/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
✓ Branch 5 taken 6 times.
✗ Branch 6 not taken.
 6 hulls[idx] = (comp.size() < 3) ? comp : BuildHull(comp);
218 6 });
219 }
220
221 10 std::vector<int> packed;
222
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank == 0) {
223
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 10 packed = FlattenHulls(work_.convex_hulls);
224 }
225
226 10 int packed_len = static_cast<int>(packed.size());
227
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Bcast(&packed_len, 1, MPI_INT, 0, MPI_COMM_WORLD);
228
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank != 0) {
229
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 packed.resize(static_cast<std::size_t>(packed_len));
230 }
231
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (packed_len > 0) {
232
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Bcast(packed.data(), packed_len, MPI_INT, 0, MPI_COMM_WORLD);
233 }
234
235
3/6
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 5 times.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 10 work_.convex_hulls = RestoreHulls(packed);
236 work_.components.clear();
237
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Barrier(MPI_COMM_WORLD);
238
239
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 GetOutput() = work_;
240 return true;
241 }
242
243 10 bool DoroginVBinImgConvHullALL::PostProcessingImpl() {
244 10 return true;
245 }
246
247 } // namespace dorogin_v_bin_img_conv_hull
248