GCC Code Coverage Report

Directory: ./
File: tasks/dorogin_v_bin_img_conv_hull/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 82 87 94.3%
Functions: 9 11 81.8%
Branches: 68 88 77.3%
Line Branch Exec Source
1 #include "dorogin_v_bin_img_conv_hull/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <functional>
8 #include <ranges>
9 #include <stack>
10 #include <thread>
11 #include <utility>
12 #include <vector>
13
14 #include "dorogin_v_bin_img_conv_hull/common/include/common.hpp"
15
16 namespace dorogin_v_bin_img_conv_hull {
17
18 namespace {
19
20 constexpr std::uint8_t kThreshold = 128;
21
22 inline bool IsInside(int col, int row, int width, int height) {
23 5856 return col >= 0 && row >= 0 && col < width && row < height;
24 }
25
26 std::int64_t Cross(const Point &a, const Point &b, const Point &c) {
27 2416 const std::int64_t x1 = static_cast<std::int64_t>(b.x) - static_cast<std::int64_t>(a.x);
28 2416 const std::int64_t y1 = static_cast<std::int64_t>(b.y) - static_cast<std::int64_t>(a.y);
29 2416 const std::int64_t x2 = static_cast<std::int64_t>(c.x) - static_cast<std::int64_t>(a.x);
30 2416 const std::int64_t y2 = static_cast<std::int64_t>(c.y) - static_cast<std::int64_t>(a.y);
31
2/2
✓ Branch 0 taken 560 times.
✓ Branch 1 taken 648 times.
 1208 return (x1 * y2) - (y1 * x2);
32 }
33
34 } // namespace
35
36
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 DoroginVBinImgConvHullSTL::DoroginVBinImgConvHullSTL(const InType &in) : w_(in) {
37 SetTypeOfTask(GetStaticTypeOfTask());
38
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetInput() = in;
39 40 }
40
41 40 bool DoroginVBinImgConvHullSTL::ValidationImpl() {
42 const auto &in = GetInput();
43
2/4
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 40 times.
✗ Branch 3 not taken.
 40 if (in.width <= 0 || in.height <= 0) {
44 return false;
45 }
46 40 return in.pixels.size() == static_cast<std::size_t>(in.width) * static_cast<std::size_t>(in.height);
47 }
48
49 40 bool DoroginVBinImgConvHullSTL::PreProcessingImpl() {
50 40 w_ = GetInput();
51 ThresholdImage();
52 40 return true;
53 }
54
55 48 void DoroginVBinImgConvHullSTL::FillConvexHullsChunk(const std::vector<std::vector<Point>> &components,
56 std::vector<std::vector<Point>> &convex_hulls,
57 const std::size_t begin, const std::size_t end) {
58
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 48 times.
 96 for (std::size_t i = begin; i < end; ++i) {
59 const auto &comp = components[i];
60
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (comp.empty()) {
61 ✗ continue;
62 }
63
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 if (comp.size() <= 2) {
64 24 convex_hulls[i] = comp;
65 } else {
66 48 convex_hulls[i] = BuildHull(comp);
67 }
68 }
69 48 }
70
71 40 bool DoroginVBinImgConvHullSTL::RunImpl() {
72 40 FindComponents();
73
74 w_.convex_hulls.clear();
75 40 w_.convex_hulls.resize(w_.components.size());
76
77 40 auto &components = w_.components;
78 auto &convex_hulls = w_.convex_hulls;
79
80 40 const std::size_t n = components.size();
81 const std::size_t num_threads =
82
1/2
✓ Branch 2 taken 40 times.
✗ Branch 3 not taken.
 40 std::max(std::size_t{1}, static_cast<std::size_t>(std::thread::hardware_concurrency()));
83 40 const std::size_t chunk = (n + num_threads - 1) / num_threads;
84
85 40 std::vector<std::thread> threads;
86
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 threads.reserve(num_threads);
87
88
1/2
✓ Branch 0 taken 88 times.
✗ Branch 1 not taken.
 88 for (std::size_t thread_index = 0; thread_index < num_threads; ++thread_index) {
89 88 const std::size_t begin = thread_index * chunk;
90
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 40 times.
 88 if (begin >= n) {
91 break;
92 }
93
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 const std::size_t end = std::min(begin + chunk, n);
94
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 96 threads.emplace_back([&, begin, end]() { FillConvexHullsChunk(components, convex_hulls, begin, end); });
95 }
96
97
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 40 times.
 88 for (auto &worker : threads) {
98
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 worker.join();
99 }
100
101
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetOutput() = w_;
102 40 return true;
103 40 }
104
105 40 bool DoroginVBinImgConvHullSTL::PostProcessingImpl() {
106 40 return true;
107 }
108
109 ✗ std::size_t DoroginVBinImgConvHullSTL::Index(int col, int row, int width) {
110
4/4
✓ Branch 0 taken 736 times.
✓ Branch 1 taken 1360 times.
✓ Branch 2 taken 1568 times.
✓ Branch 3 taken 1312 times.
 4976 return (static_cast<std::size_t>(row) * static_cast<std::size_t>(width)) + static_cast<std::size_t>(col);
111 }
112
113 ✗ void DoroginVBinImgConvHullSTL::ThresholdImage() {
114 std::ranges::transform(w_.pixels, w_.pixels.begin(), [](std::uint8_t p) {
115
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 1360 times.
✓ Branch 3 taken 736 times.
 2096 return p > kThreshold ? static_cast<std::uint8_t>(255) : static_cast<std::uint8_t>(0);
116 });
117 ✗ }
118
119 48 void DoroginVBinImgConvHullSTL::ExploreComponent(int start_col, int start_row, int width, int height,
120 std::vector<bool> &visited, std::vector<Point> &component) {
121 std::stack<Point> stack;
122 stack.emplace(start_col, start_row);
123
124
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 visited[Index(start_col, start_row, width)] = true;
125
126 48 const std::array<int, 4> dx{1, -1, 0, 0};
127 48 const std::array<int, 4> dy{0, 0, 1, -1};
128
129
2/2
✓ Branch 0 taken 736 times.
✓ Branch 1 taken 48 times.
 784 while (!stack.empty()) {
130
1/2
✓ Branch 0 taken 736 times.
✗ Branch 1 not taken.
 736 Point p = stack.top();
131 stack.pop();
132
133 component.push_back(p);
134
135
2/2
✓ Branch 0 taken 2944 times.
✓ Branch 1 taken 736 times.
 3680 for (std::size_t dir = 0; dir < dx.size(); ++dir) {
136 2944 const int nx = p.x + dx.at(dir);
137
2/2
✓ Branch 0 taken 2912 times.
✓ Branch 1 taken 32 times.
 2944 const int ny = p.y + dy.at(dir);
138
139
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 2880 times.
 2912 if (!IsInside(nx, ny, width, height)) {
140 2256 continue;
141 }
142
143 const std::size_t idx = Index(nx, ny, width);
144
2/2
✓ Branch 0 taken 1568 times.
✓ Branch 1 taken 1312 times.
 2880 if (visited[idx]) {
145 1568 continue;
146 }
147
2/2
✓ Branch 0 taken 624 times.
✓ Branch 1 taken 688 times.
 1312 if (w_.pixels[idx] == 0) {
148 624 continue;
149 }
150
151 visited[idx] = true;
152 stack.emplace(nx, ny);
153 }
154 }
155 48 }
156
157 40 void DoroginVBinImgConvHullSTL::FindComponents() {
158 40 const int width = w_.width;
159 40 const int height = w_.height;
160
161
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 40 times.
 40 std::vector<bool> visited(static_cast<std::size_t>(width) * static_cast<std::size_t>(height), false);
162 w_.components.clear();
163
164
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 40 times.
 296 for (int row = 0; row < height; ++row) {
165
2/2
✓ Branch 0 taken 2096 times.
✓ Branch 1 taken 256 times.
 2352 for (int col = 0; col < width; ++col) {
166 const std::size_t idx = Index(col, row, width);
167
168
4/4
✓ Branch 0 taken 736 times.
✓ Branch 1 taken 1360 times.
✓ Branch 2 taken 688 times.
✓ Branch 3 taken 48 times.
 2096 if (w_.pixels[idx] == 0 || visited[idx]) {
169 2048 continue;
170 }
171
172 48 std::vector<Point> comp;
173
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ExploreComponent(col, row, width, height, visited, comp);
174
175
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 w_.components.push_back(std::move(comp));
176 }
177 }
178 40 }
179
180 24 std::vector<Point> DoroginVBinImgConvHullSTL::BuildHull(const std::vector<Point> &points) {
181 24 std::vector<Point> pts = points;
182
183 std::ranges::sort(pts, std::less<>{});
184 const auto uniq = std::ranges::unique(pts);
185 pts.erase(uniq.begin(), uniq.end());
186
187
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (pts.size() <= 2) {
188 ✗ return pts;
189 }
190
191 24 std::vector<Point> hull;
192
193
2/2
✓ Branch 0 taken 712 times.
✓ Branch 1 taken 24 times.
 736 for (const auto &p : pts) {
194
4/4
✓ Branch 0 taken 1208 times.
✓ Branch 1 taken 152 times.
✓ Branch 2 taken 648 times.
✓ Branch 3 taken 560 times.
 1360 while (hull.size() >= 2 && Cross(hull[hull.size() - 2], hull.back(), p) <= 0) {
195 hull.pop_back();
196 }
197 hull.push_back(p);
198 }
199
200 const std::size_t lsize = hull.size();
201
2/2
✓ Branch 0 taken 688 times.
✓ Branch 1 taken 24 times.
 712 for (int i = static_cast<int>(pts.size()) - 2; i >= 0; --i) {
202
4/4
✓ Branch 0 taken 1208 times.
✓ Branch 1 taken 128 times.
✓ Branch 2 taken 560 times.
✓ Branch 3 taken 648 times.
 1336 while (hull.size() > lsize && Cross(hull[hull.size() - 2], hull.back(), pts[static_cast<std::size_t>(i)]) <= 0) {
203 hull.pop_back();
204 }
205
2/2
✓ Branch 0 taken 664 times.
✓ Branch 1 taken 24 times.
 688 hull.push_back(pts[static_cast<std::size_t>(i)]);
206 }
207
208 hull.pop_back();
209 return hull;
210 }
211
212 } // namespace dorogin_v_bin_img_conv_hull
213