GCC Code Coverage Report

Directory: ./
File: tasks/kamalagin_a_binary_image_convex_hull/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 100 100 100.0%
Functions: 14 14 100.0%
Branches: 85 118 72.0%
Line Branch Exec Source
1 #include "kamalagin_a_binary_image_convex_hull/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <thread>
8 #include <utility>
9 #include <vector>
10
11 #include "kamalagin_a_binary_image_convex_hull/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace kamalagin_a_binary_image_convex_hull {
15
16 namespace {
17
18 constexpr std::array<std::pair<int, int>, 4> kFourNeighbors = {{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}};
19
20 int64_t Cross(const Point &o, const Point &a, const Point &b) {
21 264 return (static_cast<int64_t>(a.x - o.x) * (b.y - o.y)) - (static_cast<int64_t>(a.y - o.y) * (b.x - o.x));
22 }
23
24 int64_t DistSq(const Point &a, const Point &b) {
25 112 const int dx = a.x - b.x;
26 112 const int dy = a.y - b.y;
27 112 return (static_cast<int64_t>(dx) * dx) + (static_cast<int64_t>(dy) * dy);
28 }
29
30 24 size_t GrahamFindPivot(std::vector<Point> &pts) {
31 size_t pivot = 0;
32 const size_t n = pts.size();
33
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 24 times.
 128 for (size_t i = 1; i < n; ++i) {
34
4/6
✓ Branch 0 taken 104 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✓ Branch 3 taken 56 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 48 times.
 104 if (pts[i].y < pts[pivot].y || (pts[i].y == pts[pivot].y && pts[i].x < pts[pivot].x)) {
35 pivot = i;
36 }
37 }
38 24 return pivot;
39 }
40
41 24 void GrahamCollinearReduce(std::vector<Point> &pts) {
42 size_t m = 1;
43 const size_t n = pts.size();
44
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 24 times.
 104 for (size_t i = 2; i < n; ++i) {
45
4/4
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 56 times.
✓ Branch 2 taken 64 times.
✓ Branch 3 taken 24 times.
 144 while (m > 0 && Cross(pts[m - 1], pts[m], pts[i]) == 0) {
46 --m;
47 }
48 80 ++m;
49 80 pts[m] = pts[i];
50 }
51 24 pts.resize(m + 1);
52 24 }
53
54
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 void GrahamScan(std::vector<Point> &pts, Hull &out) {
55 out.push_back(pts[0]);
56
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
 24 if (pts.size() <= 2) {
57
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 if (pts.size() == 2) {
58 out.push_back(pts[1]);
59 }
60 16 return;
61 }
62 out.push_back(pts[1]);
63
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
 24 for (size_t i = 2; i < pts.size(); ++i) {
64
2/4
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
 16 while (out.size() >= 2 && Cross(out[out.size() - 2], out.back(), pts[i]) <= 0) {
65 out.pop_back();
66 }
67 out.push_back(pts[i]);
68 }
69 }
70
71
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 64 times.
 64 void GrahamHull(std::vector<Point> &pts, Hull &out) {
72 out.clear();
73 const size_t n = pts.size();
74
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 24 times.
 64 if (n <= 1) {
75
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (n == 1) {
76 out.push_back(pts[0]);
77 }
78 40 return;
79 }
80 24 const size_t pivot = GrahamFindPivot(pts);
81 std::swap(pts[0], pts[pivot]);
82 const Point &p0 = pts[0];
83 184 std::sort(pts.begin() + 1, pts.end(), [&p0](const Point &a, const Point &b) {
84 160 const int64_t c = Cross(p0, a, b);
85
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 112 times.
 160 if (c != 0) {
86 48 return c > 0;
87 }
88 112 return DistSq(p0, a) < DistSq(p0, b);
89 });
90 24 GrahamCollinearReduce(pts);
91 24 GrahamScan(pts, out);
92 }
93
94 64 void FloodFillComponent(const BinaryImage &img, int start_row, int start_col, std::vector<int> &label,
95 std::vector<Point> &component_pts) {
96 64 const int rows = img.rows;
97
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 64 times.
 64 const int cols = img.cols;
98 component_pts.clear();
99 64 std::vector<std::pair<int, int>> stack;
100
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 stack.emplace_back(start_row, start_col);
101 64 const size_t start_idx = img.Index(start_row, start_col);
102 64 label[start_idx] = 1;
103
2/2
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 64 times.
 232 while (!stack.empty()) {
104 const auto [cur_r, cur_c] = stack.back();
105 stack.pop_back();
106
1/4
✓ Branch 1 taken 168 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 168 component_pts.push_back(Point{.x = cur_c, .y = cur_r});
107
2/2
✓ Branch 0 taken 672 times.
✓ Branch 1 taken 168 times.
 840 for (const auto &[dr, dc] : kFourNeighbors) {
108 672 const int nr = cur_r + dr;
109 672 const int nc = cur_c + dc;
110
8/8
✓ Branch 0 taken 568 times.
✓ Branch 1 taken 104 times.
✓ Branch 2 taken 464 times.
✓ Branch 3 taken 104 times.
✓ Branch 4 taken 376 times.
✓ Branch 5 taken 88 times.
✓ Branch 6 taken 88 times.
✓ Branch 7 taken 288 times.
 672 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
111 384 continue;
112 }
113
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 48 times.
 288 const size_t nidx = (static_cast<size_t>(nr) * static_cast<size_t>(cols)) + static_cast<size_t>(nc);
114
4/4
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 104 times.
✓ Branch 3 taken 136 times.
 288 if (img.data[nidx] != 0 && label[nidx] == 0) {
115 104 label[nidx] = 1;
116
1/2
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
 104 stack.emplace_back(nr, nc);
117 }
118 }
119 }
120 64 }
121
122
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 void CollectComponents(const BinaryImage &img, std::vector<std::vector<Point>> &components) {
123 components.clear();
124 56 const int rows = img.rows;
125 56 const int cols = img.cols;
126 56 const size_t total = static_cast<size_t>(rows) * static_cast<size_t>(cols);
127 56 std::vector<int> label(total, 0);
128
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 56 times.
 160 for (int row = 0; row < rows; ++row) {
129
2/2
✓ Branch 0 taken 248 times.
✓ Branch 1 taken 104 times.
 352 for (int col = 0; col < cols; ++col) {
130 const size_t idx = img.Index(row, col);
131
4/4
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 80 times.
✓ Branch 2 taken 104 times.
✓ Branch 3 taken 64 times.
 248 if (img.data[idx] == 0 || label[idx] != 0) {
132 184 continue;
133 }
134
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 components.emplace_back();
135
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 FloodFillComponent(img, row, col, label, components.back());
136 }
137 }
138 56 }
139
140
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 void RunBinaryImageConvexHullStl(const BinaryImage &img, HullList &hulls) {
141 hulls.clear();
142 56 std::vector<std::vector<Point>> components;
143
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 CollectComponents(img, components);
144 56 const size_t count = components.size();
145
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 hulls.resize(count);
146
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 48 times.
 56 if (count == 0) {
147 return;
148 }
149
2/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 48 times.
✗ Branch 5 not taken.
 48 const auto requested = static_cast<size_t>(ppc::util::GetNumThreads());
150 const size_t num_threads = std::min<size_t>(std::max<size_t>(requested, 1), count);
151 48 const size_t chunk = count / num_threads;
152 48 const size_t remainder = count % num_threads;
153 48 std::vector<std::thread> threads;
154
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 threads.reserve(num_threads);
155 size_t start = 0;
156
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 48 times.
 108 for (size_t ti = 0; ti < num_threads; ++ti) {
157
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 const size_t end = start + chunk + (ti < remainder ? 1 : 0);
158
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 threads.emplace_back([&components, &hulls, start, end]() {
159
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 60 times.
 124 for (size_t i = start; i < end; ++i) {
160 64 GrahamHull(components[i], hulls[i]);
161 }
162 60 });
163 start = end;
164 }
165
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 48 times.
 108 for (auto &th : threads) {
166
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 th.join();
167 }
168 56 }
169
170 } // namespace
171
172
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 KamalaginABinaryImageConvexHullSTL::KamalaginABinaryImageConvexHullSTL(const InType &in) {
173 SetTypeOfTask(GetStaticTypeOfTask());
174 GetInput() = in;
175 56 GetOutput() = HullList{};
176 56 }
177
178 56 bool KamalaginABinaryImageConvexHullSTL::ValidationImpl() {
179 const auto &img = GetInput();
180
2/4
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 56 times.
✗ Branch 3 not taken.
 56 if (img.rows < 0 || img.cols < 0) {
181 return false;
182 }
183
3/4
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 48 times.
 56 if (img.rows == 0 || img.cols == 0) {
184 8 return img.data.empty();
185 }
186
2/4
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 if (img.rows > 8192 || img.cols > 8192) {
187 return false;
188 }
189 48 return (static_cast<size_t>(img.rows) * static_cast<size_t>(img.cols)) == img.data.size();
190 }
191
192
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 bool KamalaginABinaryImageConvexHullSTL::PreProcessingImpl() {
193 GetOutput().clear();
194 56 return true;
195 }
196
197 56 bool KamalaginABinaryImageConvexHullSTL::RunImpl() {
198 56 RunBinaryImageConvexHullStl(GetInput(), GetOutput());
199 56 return true;
200 }
201
202 56 bool KamalaginABinaryImageConvexHullSTL::PostProcessingImpl() {
203 56 return true;
204 }
205
206 } // namespace kamalagin_a_binary_image_convex_hull
207