GCC Code Coverage Report

Directory: ./
File: tasks/paramonov_v_bin_img_conv_hul/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 91 95 95.8%
Functions: 15 17 88.2%
Branches: 80 114 70.2%
Line Branch Exec Source
1 #include "paramonov_v_bin_img_conv_hul/all/include/ops_all.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <iterator>
8 #include <stack>
9 #include <utility>
10 #include <vector>
11
12 #include "paramonov_v_bin_img_conv_hul/all/include/common.hpp"
13
14 namespace paramonov_v_bin_img_conv_hul_all {
15
16 namespace {
17 constexpr std::array<std::pair<int, int>, 4> kNeighbors = {{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}};
18
19 126 bool ComparePoints(const PixelPoint &a, const PixelPoint &b) {
20
2/2
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 34 times.
 126 if (a.row != b.row) {
21 92 return a.row < b.row;
22 }
23 34 return a.col < b.col;
24 }
25
26 int64_t SquaredDistance(const PixelPoint &a, const PixelPoint &b) {
27 auto dx = static_cast<int64_t>(a.col - b.col);
28 auto dy = static_cast<int64_t>(a.row - b.row);
29 84 return (dx * dx) + (dy * dy);
30 }
31
32 } // namespace
33
34
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 ConvexHullAll::ConvexHullAll(const InputType &input) {
35 SetTypeOfTask(GetStaticTypeOfTask());
36 GetInput() = input;
37 16 }
38
39 16 bool ConvexHullAll::ValidationImpl() {
40 const auto &img = GetInput();
41
2/4
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 16 times.
✗ Branch 3 not taken.
 16 if (img.rows <= 0 || img.cols <= 0) {
42 return false;
43 }
44
45 16 const size_t expected_size = static_cast<size_t>(img.rows) * static_cast<size_t>(img.cols);
46 16 return img.pixels.size() == expected_size;
47 }
48
49 16 bool ConvexHullAll::PreProcessingImpl() {
50 working_image_ = GetInput();
51 BinarizeImage();
52 GetOutput().clear();
53 16 return true;
54 }
55
56 16 bool ConvexHullAll::RunImpl() {
57 16 ExtractConnectedComponents();
58 16 return true;
59 }
60
61 16 bool ConvexHullAll::PostProcessingImpl() {
62 16 return true;
63 }
64
65 ✗ void ConvexHullAll::BinarizeImage(uint8_t threshold) {
66 const size_t size = working_image_.pixels.size();
67 auto &pixels = working_image_.pixels;
68
69
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 3024 times.
✓ Branch 3 taken 16 times.
 3040 for (size_t i = 0; i < size; ++i) {
70
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 2876 times.
✓ Branch 3 taken 148 times.
 5900 pixels[i] = pixels[i] > threshold ? uint8_t{255} : uint8_t{0};
71 }
72 ✗ }
73
74 22 void ConvexHullAll::FloodFill(int start_row, int start_col, std::vector<bool> &visited,
75 std::vector<PixelPoint> &component) const {
76 std::stack<PixelPoint> pixel_stack;
77 pixel_stack.emplace(start_row, start_col);
78
79 22 const int rows = working_image_.rows;
80 22 const int cols = working_image_.cols;
81
82
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 22 times.
 22 visited[PixelIndex(start_row, start_col, cols)] = true;
83
84
2/2
✓ Branch 0 taken 148 times.
✓ Branch 1 taken 22 times.
 170 while (!pixel_stack.empty()) {
85
1/2
✓ Branch 0 taken 148 times.
✗ Branch 1 not taken.
 148 PixelPoint current = pixel_stack.top();
86 pixel_stack.pop();
87
88 component.push_back(current);
89
90
2/2
✓ Branch 0 taken 592 times.
✓ Branch 1 taken 148 times.
 740 for (const auto &[dr, dc] : kNeighbors) {
91 592 int next_row = current.row + dr;
92 592 int next_col = current.col + dc;
93
94
4/8
✓ Branch 0 taken 592 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 592 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 592 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 592 times.
✗ Branch 7 not taken.
 592 if (next_row >= 0 && next_row < rows && next_col >= 0 && next_col < cols) {
95 size_t idx = PixelIndex(next_row, next_col, cols);
96
4/4
✓ Branch 0 taken 350 times.
✓ Branch 1 taken 242 times.
✓ Branch 2 taken 126 times.
✓ Branch 3 taken 224 times.
 592 if (!visited[idx] && working_image_.pixels[idx] == 255) {
97 visited[idx] = true;
98 pixel_stack.emplace(next_row, next_col);
99 }
100 }
101 }
102 }
103 22 }
104
105 16 void ConvexHullAll::ExtractConnectedComponents() {
106 16 const int rows = working_image_.rows;
107 16 const int cols = working_image_.cols;
108 16 const size_t total_pixels = static_cast<size_t>(rows) * static_cast<size_t>(cols);
109
110 16 std::vector<bool> visited(total_pixels, false);
111 auto &output_hulls = GetOutput();
112
113
2/2
✓ Branch 0 taken 184 times.
✓ Branch 1 taken 16 times.
 200 for (int row = 0; row < rows; ++row) {
114
2/2
✓ Branch 0 taken 3024 times.
✓ Branch 1 taken 184 times.
 3208 for (int col = 0; col < cols; ++col) {
115 size_t idx = PixelIndex(row, col, cols);
116
117
4/4
✓ Branch 0 taken 148 times.
✓ Branch 1 taken 2876 times.
✓ Branch 2 taken 22 times.
✓ Branch 3 taken 126 times.
 3024 if (working_image_.pixels[idx] == 255 && !visited[idx]) {
118 22 std::vector<PixelPoint> component;
119
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 FloodFill(row, col, visited, component);
120
121
1/2
✓ Branch 0 taken 22 times.
✗ Branch 1 not taken.
 22 if (!component.empty()) {
122
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 std::vector<PixelPoint> hull = ComputeConvexHull(component);
123 output_hulls.push_back(std::move(hull));
124 }
125 }
126 }
127 }
128 16 }
129
130 ✗ int64_t ConvexHullAll::Orientation(const PixelPoint &p, const PixelPoint &q, const PixelPoint &r) {
131 514 return (static_cast<int64_t>(q.col - p.col) * (r.row - p.row)) -
132
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 54 times.
 110 (static_cast<int64_t>(q.row - p.row) * (r.col - p.col));
133 }
134
135
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 PixelPoint ConvexHullAll::FindLowestPoint(const std::vector<PixelPoint> &points) {
136 16 return *std::ranges::min_element(points, ComparePoints);
137 }
138
139 16 std::vector<PixelPoint> ConvexHullAll::SortPointsByAngle(const std::vector<PixelPoint> &points,
140 const PixelPoint &lowest_point) {
141
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 std::vector<PixelPoint> sorted_points;
142
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 sorted_points.reserve(points.size() - 1);
143
144 16 std::ranges::copy_if(points, std::back_inserter(sorted_points), [&lowest_point](const PixelPoint &p) {
145
4/4
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 92 times.
✓ Branch 2 taken 34 times.
✓ Branch 3 taken 16 times.
 142 return (p.row != lowest_point.row) || (p.col != lowest_point.col);
146 });
147
148 316 std::ranges::sort(sorted_points, [&lowest_point](const PixelPoint &a, const PixelPoint &b) {
149 316 int64_t orient = Orientation(lowest_point, a, b);
150
2/2
✓ Branch 0 taken 232 times.
✓ Branch 1 taken 84 times.
 316 if (orient != 0) {
151 232 return orient > 0;
152 }
153 84 return SquaredDistance(a, lowest_point) < SquaredDistance(b, lowest_point);
154 });
155
156 16 return sorted_points;
157 }
158
159
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 std::vector<PixelPoint> ConvexHullAll::RemoveCollinearPoints(const std::vector<PixelPoint> &sorted_points,
160 const PixelPoint &lowest_point) {
161
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (sorted_points.empty()) {
162 ✗ return {};
163 }
164
165
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 std::vector<PixelPoint> unique_points;
166
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 unique_points.reserve(sorted_points.size());
167
168
2/2
✓ Branch 0 taken 126 times.
✓ Branch 1 taken 16 times.
 142 for (size_t i = 0; i < sorted_points.size(); ++i) {
169 126 bool is_last = (i == sorted_points.size() - 1);
170
4/4
✓ Branch 0 taken 110 times.
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 56 times.
✓ Branch 3 taken 54 times.
 126 bool is_collinear = !is_last && Orientation(lowest_point, sorted_points[i], sorted_points[i + 1]) == 0;
171
172
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 54 times.
 126 if (is_last || !is_collinear) {
173 unique_points.push_back(sorted_points[i]);
174 }
175 }
176
177 return unique_points;
178 }
179
180 4 std::vector<PixelPoint> ConvexHullAll::HandleCollinearCase(const std::vector<PixelPoint> &points,
181 const PixelPoint &lowest_point) {
182
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 std::vector<PixelPoint> collinear_hull;
183 collinear_hull.push_back(lowest_point);
184
185
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (!points.empty()) {
186 collinear_hull.push_back(points.back());
187 }
188
189
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (collinear_hull.size() == 2) {
190
3/4
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 2 times.
 4 bool need_swap = (collinear_hull[0].row > collinear_hull[1].row) ||
191
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 (collinear_hull[0].row == collinear_hull[1].row && collinear_hull[0].col > collinear_hull[1].col);
192 if (need_swap) {
193 std::swap(collinear_hull[0], collinear_hull[1]);
194 }
195 }
196
197 4 return collinear_hull;
198 }
199
200 12 std::vector<PixelPoint> ConvexHullAll::BuildHull(const std::vector<PixelPoint> &unique_points,
201 const PixelPoint &lowest_point) {
202
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<PixelPoint> hull;
203
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 hull.reserve(unique_points.size() + 1);
204 hull.push_back(lowest_point);
205 hull.push_back(unique_points[0]);
206
207
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 12 times.
 68 for (size_t i = 1; i < unique_points.size(); ++i) {
208 const auto &p = unique_points[i];
209
1/2
✓ Branch 0 taken 88 times.
✗ Branch 1 not taken.
 88 while (hull.size() >= 2) {
210 const auto &a = hull[hull.size() - 2];
211 const auto &b = hull.back();
212
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 56 times.
 88 if (Orientation(a, b, p) <= 0) {
213 hull.pop_back();
214 } else {
215 break;
216 }
217 }
218 hull.push_back(p);
219 }
220
221 12 return hull;
222 }
223
224
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 16 times.
 22 std::vector<PixelPoint> ConvexHullAll::ComputeConvexHull(const std::vector<PixelPoint> &points) {
225
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 16 times.
 22 if (points.size() <= 2) {
226 6 return points;
227 }
228
229 16 PixelPoint lowest_point = FindLowestPoint(points);
230 16 std::vector<PixelPoint> sorted_points = SortPointsByAngle(points, lowest_point);
231
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 std::vector<PixelPoint> unique_points = RemoveCollinearPoints(sorted_points, lowest_point);
232
233
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 12 times.
 16 if (unique_points.size() <= 1) {
234
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 return HandleCollinearCase(unique_points, lowest_point);
235 }
236
237
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 return BuildHull(unique_points, lowest_point);
238 }
239
240 } // namespace paramonov_v_bin_img_conv_hul_all
241