GCC Code Coverage Report

Directory: ./
File: tasks/egorova_l_binary_convex_hull/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 173 230 75.2%
Functions: 16 22 72.7%
Branches: 180 400 45.0%
Line Branch Exec Source
1 #include "egorova_l_binary_convex_hull/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <cstddef>
8 #include <cstdint>
9 #include <functional>
10 #include <limits>
11 #include <queue>
12 #include <utility>
13 #include <vector>
14
15 #include "egorova_l_binary_convex_hull/common/include/common.hpp"
16
17 namespace egorova_l_binary_convex_hull {
18
19 namespace {
20
21 struct Pix {
22 int px, py;
23 };
24
25 // Сериализация оболочек для MPI
26 16 std::vector<int> SerializeHulls(const std::vector<std::vector<Point>> &hulls) {
27
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 std::vector<int> buf;
28
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 buf.push_back(static_cast<int>(hulls.size()));
29
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 16 times.
 28 for (const auto &hull : hulls) {
30
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 buf.push_back(static_cast<int>(hull.size()));
31
2/2
✓ Branch 0 taken 37 times.
✓ Branch 1 taken 12 times.
 49 for (const auto &pp : hull) {
32
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 23 times.
 37 buf.push_back(pp.x);
33
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 1 times.
 37 buf.push_back(pp.y);
34 }
35 }
36 16 return buf;
37 }
38
39 32 std::vector<std::vector<Point>> DeserializeHulls(const std::vector<int> &buf) {
40
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 std::vector<std::vector<Point>> hulls;
41
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (buf.empty()) {
42 return hulls;
43 }
44 size_t pos = 0;
45 32 const int nn = buf[pos++];
46
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 hulls.resize(nn);
47
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 32 times.
 56 for (int ii = 0; ii < nn; ++ii) {
48
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 const int sz = buf[pos++];
49
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 hulls[ii].reserve(sz);
50
2/2
✓ Branch 0 taken 74 times.
✓ Branch 1 taken 24 times.
 98 for (int jj = 0; jj < sz; ++jj) {
51
1/2
✓ Branch 1 taken 74 times.
✗ Branch 2 not taken.
 74 hulls[ii].push_back({buf[pos], buf[pos + 1]});
52 74 pos += 2;
53 }
54 }
55 return hulls;
56 ✗ }
57
58 // Проверка соседа в BFS (локальная полоса)
59 336 inline void TryPushLocal(const std::vector<uint8_t> &image, int width, int local_rows, int row_start, int nx, int ny,
60 std::vector<uint8_t> &visited, std::queue<Pix> &bfs) {
61
3/4
✓ Branch 0 taken 336 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 325 times.
✓ Branch 3 taken 11 times.
 336 if (nx < 0 || nx >= width || ny < 0 || ny >= local_rows) {
62 return;
63 }
64 325 const size_t local_ni = ((static_cast<size_t>(ny) * static_cast<size_t>(width)) + static_cast<size_t>(nx));
65 325 const size_t global_ni =
66
2/2
✓ Branch 0 taken 208 times.
✓ Branch 1 taken 117 times.
 325 ((static_cast<size_t>(ny + row_start) * static_cast<size_t>(width)) + static_cast<size_t>(nx));
67
4/4
✓ Branch 0 taken 208 times.
✓ Branch 1 taken 117 times.
✓ Branch 2 taken 72 times.
✓ Branch 3 taken 136 times.
 325 if (image[global_ni] != 0 && visited[local_ni] == 0) {
68 72 visited[local_ni] = 1;
69 72 bfs.push({nx, ny});
70 }
71 }
72
73 // Один BFS, возвращает компоненту (в глобальных координатах)
74 12 std::vector<Point> BfsOneComponent(const std::vector<uint8_t> &image, int width, int local_rows, int row_start,
75 int start_x, int start_y, std::vector<uint8_t> &visited) {
76 12 std::vector<Point> comp;
77
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 comp.reserve(256);
78 std::queue<Pix> bfs;
79
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 bfs.push({start_x, start_y});
80
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 12 times.
 96 while (!bfs.empty()) {
81 84 const auto cur = bfs.front();
82 bfs.pop();
83
1/2
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
 84 comp.push_back({cur.px, cur.py + row_start});
84
1/2
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
 84 TryPushLocal(image, width, local_rows, row_start, cur.px + 1, cur.py, visited, bfs);
85
1/2
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
 84 TryPushLocal(image, width, local_rows, row_start, cur.px - 1, cur.py, visited, bfs);
86
1/2
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
 84 TryPushLocal(image, width, local_rows, row_start, cur.px, cur.py + 1, visited, bfs);
87
1/2
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
 84 TryPushLocal(image, width, local_rows, row_start, cur.px, cur.py - 1, visited, bfs);
88 }
89 12 return comp;
90 }
91
92 16 std::vector<std::vector<Point>> FindLocalComponents(const std::vector<uint8_t> &image, int width, int local_rows,
93 int row_start) {
94 16 std::vector<std::vector<Point>> comps;
95
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 std::vector<uint8_t> visited(((static_cast<size_t>(local_rows) * static_cast<size_t>(width))), 0);
96
97
2/2
✓ Branch 0 taken 115 times.
✓ Branch 1 taken 16 times.
 131 for (int ly = 0; ly < local_rows; ++ly) {
98 115 const int gy = row_start + ly;
99
2/2
✓ Branch 0 taken 2025 times.
✓ Branch 1 taken 115 times.
 2140 for (int col = 0; col < width; ++col) {
100 2025 const size_t local_idx = ((static_cast<size_t>(ly) * static_cast<size_t>(width)) + static_cast<size_t>(col));
101
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 1941 times.
 2025 const size_t global_idx = ((static_cast<size_t>(gy) * static_cast<size_t>(width)) + static_cast<size_t>(col));
102
4/4
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 1941 times.
✓ Branch 2 taken 72 times.
✓ Branch 3 taken 12 times.
 2025 if (image[global_idx] == 0 || visited[local_idx] != 0) {
103 2013 continue;
104 }
105 12 visited[local_idx] = 1;
106
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 comps.push_back(BfsOneComponent(image, width, local_rows, row_start, col, ly, visited));
107 }
108 }
109 16 return comps;
110 ✗ }
111
112 // Вычисление bounding box'ов всех оболочек
113 struct BBox {
114 std::vector<int> min_x, max_x, min_y, max_y;
115 };
116
117
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 BBox ComputeBBoxes(const std::vector<std::vector<Point>> &hulls) {
118 14 const int nn = static_cast<int>(hulls.size());
119 14 BBox bb;
120
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 bb.min_x.assign(nn, std::numeric_limits<int>::max());
121
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 bb.max_x.assign(nn, std::numeric_limits<int>::min());
122
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 bb.min_y.assign(nn, std::numeric_limits<int>::max());
123
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 bb.max_y.assign(nn, std::numeric_limits<int>::min());
124
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 14 times.
 38 for (int ii = 0; ii < nn; ++ii) {
125
2/2
✓ Branch 0 taken 74 times.
✓ Branch 1 taken 24 times.
 98 for (const auto &pp : hulls[ii]) {
126
4/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 50 times.
✓ Branch 2 taken 42 times.
✓ Branch 3 taken 32 times.
 98 bb.min_x[ii] = std::min(bb.min_x[ii], pp.x);
127 74 bb.max_x[ii] = std::max(bb.max_x[ii], pp.x);
128
4/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 50 times.
✓ Branch 2 taken 42 times.
✓ Branch 3 taken 32 times.
 98 bb.min_y[ii] = std::min(bb.min_y[ii], pp.y);
129 74 bb.max_y[ii] = std::max(bb.max_y[ii], pp.y);
130 }
131 }
132 14 return bb;
133 ✗ }
134
135 // Union-Find для объединения смежных по Y и пересекающихся по X оболочек
136 14 void UnionAdjacent(int nn, const BBox &bb, std::vector<int> &parent, const std::function<int(int)> &find) {
137
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 14 times.
 38 for (int ii = 0; ii < nn; ++ii) {
138
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 24 times.
 36 for (int jj = ii + 1; jj < nn; ++jj) {
139
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 12 times.
 24 if (find(ii) == find(jj)) {
140 ✗ continue;
141 }
142
3/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 8 times.
 12 const bool y_adj = (bb.max_y[ii] + 1 == bb.min_y[jj]) || (bb.max_y[jj] + 1 == bb.min_y[ii]);
143
4/4
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 6 times.
 12 const bool x_ovl = (bb.min_x[ii] <= bb.max_x[jj]) && (bb.min_x[jj] <= bb.max_x[ii]);
144
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (y_adj && x_ovl) {
145
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 8 parent[find(ii)] = find(jj);
146 }
147 }
148 }
149 14 }
150
151 14 std::vector<std::vector<Point>> MergeHulls(const std::vector<std::vector<Point>> &all_hulls) {
152 14 const int nn = static_cast<int>(all_hulls.size());
153 14 std::vector<int> parent(nn);
154
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 14 times.
 38 for (int ii = 0; ii < nn; ++ii) {
155 24 parent[ii] = ii;
156 }
157
3/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4 times.
 64 std::function<int(int)> find = [&](int ii) -> int { return parent[ii] == ii ? ii : (parent[ii] = find(parent[ii])); };
158
159
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 const BBox bb = ComputeBBoxes(all_hulls);
160
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 UnionAdjacent(nn, bb, parent, find);
161
162
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 std::vector<std::vector<Point>> groups(nn);
163
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 14 times.
 38 for (int ii = 0; ii < nn; ++ii) {
164 24 const int root = find(ii);
165
2/2
✓ Branch 0 taken 74 times.
✓ Branch 1 taken 24 times.
 98 for (const auto &pp : all_hulls[ii]) {
166
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 58 times.
 74 groups[root].push_back(pp);
167 }
168 }
169 14 return groups;
170 14 }
171
172 // Сборка всех оболочек со всех процессов через Allgatherv
173 16 std::vector<std::vector<Point>> GatherAllHulls(const std::vector<std::vector<Point>> &local_hulls, int p_count) {
174 16 std::vector<int> s_buf = SerializeHulls(local_hulls);
175 16 const int s_size = static_cast<int>(s_buf.size());
176
177
2/6
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 16 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 16 std::vector<int> r_sizes(p_count, 0);
178
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 MPI_Allgather(&s_size, 1, MPI_INT, r_sizes.data(), 1, MPI_INT, MPI_COMM_WORLD);
179
180
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<int> r_displs(p_count, 0);
181
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 for (int ii = 1; ii < p_count; ++ii) {
182 16 r_displs[ii] = r_displs[ii - 1] + r_sizes[ii - 1];
183 }
184
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 const int total_size = r_displs[p_count - 1] + r_sizes[p_count - 1];
185
186
2/6
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 16 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 16 std::vector<int> r_buf(total_size);
187
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 MPI_Allgatherv(s_buf.data(), s_size, MPI_INT, r_buf.data(), r_sizes.data(), r_displs.data(), MPI_INT, MPI_COMM_WORLD);
188
189 16 std::vector<std::vector<Point>> all_hulls;
190
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 all_hulls.reserve(64);
191
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 16 times.
 48 for (int ii = 0; ii < p_count; ++ii) {
192
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 if (r_sizes[ii] == 0) {
193 ✗ continue;
194 }
195
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 std::vector<int> ph(r_buf.begin() + r_displs[ii], r_buf.begin() + r_displs[ii] + r_sizes[ii]);
196
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 auto dec = DeserializeHulls(ph);
197
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 32 times.
 56 for (auto &hh : dec) {
198 all_hulls.push_back(std::move(hh));
199 }
200 32 }
201 16 return all_hulls;
202 ✗ }
203
204 // BFS для FindComponents (без полос)
205 ✗ inline void TryPushGlobal(const std::vector<uint8_t> &image, int width, int height, int nx, int ny,
206 std::vector<uint8_t> &visited, std::queue<Pix> &bfs) {
207 ✗ if (nx < 0 || nx >= width || ny < 0 || ny >= height) {
208 return;
209 }
210 ✗ const size_t ni = ((static_cast<size_t>(ny) * static_cast<size_t>(width)) + static_cast<size_t>(nx));
211 ✗ if (image[ni] != 0 && visited[ni] == 0) {
212 ✗ visited[ni] = 1;
213 ✗ bfs.push({nx, ny});
214 }
215 }
216
217 ✗ std::vector<Point> BfsComponentGlobal(const std::vector<uint8_t> &image, int width, int height, int start_x,
218 int start_y, std::vector<uint8_t> &visited) {
219 ✗ std::vector<Point> comp;
220 std::queue<Pix> bfs;
221 ✗ bfs.push({start_x, start_y});
222 ✗ while (!bfs.empty()) {
223 ✗ const auto cur = bfs.front();
224 bfs.pop();
225 ✗ comp.emplace_back(cur.px, cur.py);
226 ✗ TryPushGlobal(image, width, height, cur.px + 1, cur.py, visited, bfs);
227 ✗ TryPushGlobal(image, width, height, cur.px - 1, cur.py, visited, bfs);
228 ✗ TryPushGlobal(image, width, height, cur.px, cur.py + 1, visited, bfs);
229 ✗ TryPushGlobal(image, width, height, cur.px, cur.py - 1, visited, bfs);
230 }
231 ✗ return comp;
232 }
233
234 // BFS с labels (для ProcessComponent)
235 ✗ inline void TryPushLabels(const std::vector<uint8_t> &image, int width, int height, int nx, int ny, int label,
236 std::vector<int> &labels, std::queue<Pix> &bfs) {
237 ✗ if (nx < 0 || nx >= width || ny < 0 || ny >= height) {
238 return;
239 }
240 ✗ const size_t ni = ((static_cast<size_t>(ny) * static_cast<size_t>(width)) + static_cast<size_t>(nx));
241 ✗ if (image[ni] != 0 && labels[ni] == 0) {
242 ✗ labels[ni] = label;
243 ✗ bfs.push({nx, ny});
244 }
245 }
246
247 } // namespace
248
249
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 BinaryConvexHullALL::BinaryConvexHullALL(const InType &in) {
250 SetTypeOfTask(GetStaticTypeOfTask());
251 GetInput() = in;
252 16 }
253
254 16 bool BinaryConvexHullALL::ValidationImpl() {
255 16 int rank = 0;
256 16 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
257
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 if (rank == 0) {
258 const auto &in = GetInput();
259
3/6
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
 8 return in.width > 0 && in.height > 0 && !in.data.empty();
260 }
261 return true;
262 }
263
264
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 bool BinaryConvexHullALL::PreProcessingImpl() {
265 GetOutput().clear();
266 16 return true;
267 }
268
269 16 bool BinaryConvexHullALL::RunImpl() {
270 16 int rank = 0;
271 16 int p_count = 1;
272 16 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
273 16 MPI_Comm_size(MPI_COMM_WORLD, &p_count);
274
275 // Bcast размеров и изображения
276 16 int width = 0;
277 16 int height = 0;
278
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 if (rank == 0) {
279 8 width = GetInput().width;
280 8 height = GetInput().height;
281 }
282 16 MPI_Bcast(&width, 1, MPI_INT, 0, MPI_COMM_WORLD);
283 16 MPI_Bcast(&height, 1, MPI_INT, 0, MPI_COMM_WORLD);
284
285
2/4
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
 16 if (width <= 0 || height <= 0) {
286 GetOutput().clear();
287 ✗ return true;
288 }
289
290 16 std::vector<uint8_t> image;
291
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 if (rank == 0) {
292
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 image = GetInput().data;
293 } else {
294
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 image.resize((static_cast<size_t>(width) * static_cast<size_t>(height)));
295 }
296
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 MPI_Bcast(image.data(), static_cast<int>(image.size()), MPI_BYTE, 0, MPI_COMM_WORLD);
297
298 // Распределение строк
299 16 const int chunk = height / p_count;
300 16 const int rem = height % p_count;
301
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 1 times.
 16 const int row_start = ((rank * chunk) + std::min(rank, rem));
302
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 1 times.
 16 const int local_rows = chunk + ((rank < rem) ? 1 : 0);
303
304 // BFS локально + OpenMP для оболочек
305
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 std::vector<std::vector<Point>> local_comps = FindLocalComponents(image, width, local_rows, row_start);
306
2/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 16 times.
✗ Branch 5 not taken.
 16 std::vector<std::vector<Point>> local_hulls(local_comps.size());
307 16 const int n_local = static_cast<int>(local_comps.size());
308 16 #pragma omp parallel for schedule(dynamic, 1) default(none) shared(local_comps, local_hulls, n_local)
309 for (int ii = 0; ii < n_local; ++ii) {
310 BuildConvexHull(local_comps[ii], local_hulls[ii]);
311 }
312
313 // Allgatherv → каждый процесс получает все оболочки
314
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 std::vector<std::vector<Point>> all_hulls = GatherAllHulls(local_hulls, p_count);
315
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 14 times.
 16 if (all_hulls.empty()) {
316 GetOutput().clear();
317 2 return true;
318 }
319
320 // Union-find + финальные оболочки
321
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 std::vector<std::vector<Point>> groups = MergeHulls(all_hulls);
322 GetOutput().clear();
323
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 14 times.
 38 for (auto &group : groups) {
324
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 4 times.
 24 if (!group.empty()) {
325 20 std::vector<Point> hh;
326
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 BuildConvexHull(group, hh);
327 GetOutput().push_back(std::move(hh));
328 }
329 }
330 return true;
331 16 }
332
333 16 bool BinaryConvexHullALL::PostProcessingImpl() {
334 16 return true;
335 }
336
337 ✗ int64_t BinaryConvexHullALL::CrossProduct(const Point &a, const Point &b, const Point &c) {
338 245 return (((static_cast<int64_t>(b.x - a.x) * static_cast<int64_t>(c.y - a.y)) -
339
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 72 times.
 124 (static_cast<int64_t>(b.y - a.y) * static_cast<int64_t>(c.x - a.x))));
340 }
341
342
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 void BinaryConvexHullALL::BuildConvexHull(std::vector<Point> &points, std::vector<Point> &hull) {
343 hull.clear();
344
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (points.empty()) {
345 4 return;
346 }
347
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 126 times.
✓ Branch 68 taken 40 times.
✓ Branch 69 taken 86 times.
✗ Branch 70 not taken.
✓ Branch 71 taken 40 times.
✓ Branch 72 taken 92 times.
✓ Branch 73 taken 126 times.
✓ Branch 74 taken 86 times.
✓ Branch 75 taken 40 times.
✗ Branch 76 not taken.
✓ Branch 77 taken 86 times.
 344 std::ranges::sort(points, [](const Point &a, const Point &b) { return a.x < b.x || (a.x == b.x && a.y < b.y); });
348 const auto last_unique = std::ranges::unique(points).begin();
349 points.erase(last_unique, points.end());
350
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 28 times.
 32 if (points.size() < 3) {
351 hull.clear();
352
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 4 times.
 10 for (const auto &pp : points) {
353 hull.push_back(pp);
354 }
355 return;
356 }
357
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 std::vector<Point> res;
358
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 res.reserve(points.size() + 1);
359
2/2
✓ Branch 0 taken 152 times.
✓ Branch 1 taken 28 times.
 180 for (const auto &pp : points) {
360
4/4
✓ Branch 0 taken 121 times.
✓ Branch 1 taken 106 times.
✓ Branch 2 taken 75 times.
✓ Branch 3 taken 46 times.
 227 while (res.size() >= 2 && CrossProduct(res[res.size() - 2], res.back(), pp) <= 0) {
361 res.pop_back();
362 }
363 res.push_back(pp);
364 }
365 const size_t lower_size = res.size();
366
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 28 times.
 152 for (int ii = static_cast<int>(points.size()) - 2; ii >= 0; --ii) {
367
4/4
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 72 times.
✓ Branch 2 taken 52 times.
✓ Branch 3 taken 72 times.
 196 while (res.size() > lower_size && CrossProduct(res[res.size() - 2], res.back(), points[ii]) <= 0) {
368 res.pop_back();
369 }
370
1/2
✓ Branch 0 taken 124 times.
✗ Branch 1 not taken.
 124 res.push_back(points[ii]);
371 }
372
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (res.size() > 1) {
373 res.pop_back();
374 }
375 hull.swap(res);
376 }
377
378 ✗ std::vector<std::vector<Point>> BinaryConvexHullALL::FindComponents(const std::vector<uint8_t> &image, int width,
379 int height) {
380 ✗ std::vector<std::vector<Point>> components;
381 ✗ std::vector<uint8_t> visited(((static_cast<size_t>(width) * static_cast<size_t>(height))), 0);
382 ✗ for (int row = 0; row < height; ++row) {
383 ✗ for (int col = 0; col < width; ++col) {
384 ✗ const size_t idx = ((static_cast<size_t>(row) * static_cast<size_t>(width)) + static_cast<size_t>(col));
385 ✗ if (image[idx] == 0 || visited[idx] != 0) {
386 ✗ continue;
387 }
388 ✗ visited[idx] = 1;
389 ✗ components.push_back(BfsComponentGlobal(image, width, height, col, row, visited));
390 }
391 }
392 ✗ return components;
393 ✗ }
394
395 ✗ void BinaryConvexHullALL::ProcessComponent(const std::vector<uint8_t> &image, int width, int height, int start_x,
396 int start_y, int label, std::vector<int> &labels,
397 std::vector<Point> &component_points) {
398 ✗ if (start_x < 0 || start_x >= width || start_y < 0 || start_y >= height) {
399 component_points.clear();
400 ✗ return;
401 }
402 ✗ const size_t si = ((static_cast<size_t>(start_y) * static_cast<size_t>(width)) + static_cast<size_t>(start_x));
403 ✗ labels[si] = label;
404 std::queue<Pix> bfs;
405 ✗ bfs.push({start_x, start_y});
406 component_points.clear();
407 ✗ component_points.reserve(1000);
408 ✗ while (!bfs.empty()) {
409 ✗ const auto cur = bfs.front();
410 bfs.pop();
411 ✗ component_points.emplace_back(cur.px, cur.py);
412 ✗ TryPushLabels(image, width, height, cur.px + 1, cur.py, label, labels, bfs);
413 ✗ TryPushLabels(image, width, height, cur.px - 1, cur.py, label, labels, bfs);
414 ✗ TryPushLabels(image, width, height, cur.px, cur.py + 1, label, labels, bfs);
415 ✗ TryPushLabels(image, width, height, cur.px, cur.py - 1, label, labels, bfs);
416 }
417 }
418
419 } // namespace egorova_l_binary_convex_hull
420