GCC Code Coverage Report

Directory: ./
File: tasks/shkenev_i_constra_hull_for_binary_image/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 70 75 93.3%
Functions: 8 10 80.0%
Branches: 78 110 70.9%
Line Branch Exec Source
1 #include "shkenev_i_constra_hull_for_binary_image/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <queue>
8 #include <ranges>
9 #include <utility>
10 #include <vector>
11
12 #include "shkenev_i_constra_hull_for_binary_image/common/include/common.hpp"
13
14 namespace shkenev_i_constra_hull_for_binary_image {
15
16 namespace {
17
18 constexpr uint8_t kThreshold = 128;
19 constexpr std::array<std::pair<int, int>, 4> kDirs = {std::make_pair(1, 0), std::make_pair(-1, 0), std::make_pair(0, 1),
20 std::make_pair(0, -1)};
21
22 int64_t Cross(const Point &a, const Point &b, const Point &c) {
23 1552 int64_t abx = static_cast<int64_t>(b.x) - static_cast<int64_t>(a.x);
24 1552 int64_t aby = static_cast<int64_t>(b.y) - static_cast<int64_t>(a.y);
25 1552 int64_t bcx = static_cast<int64_t>(c.x) - static_cast<int64_t>(b.x);
26 1552 int64_t bcy = static_cast<int64_t>(c.y) - static_cast<int64_t>(b.y);
27 1552 return (abx * bcy) - (aby * bcx);
28 }
29
30 bool IsForeground(uint8_t pixel) {
31 return pixel > kThreshold;
32 }
33
34 bool IsInBounds(int x, int y, int width, int height) {
35 4016 return x >= 0 && x < width && y >= 0 && y < height;
36 }
37
38 } // namespace
39
40
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 ShkenevIConstrHullSeq::ShkenevIConstrHullSeq(const InType &in) : work_(in) {
41 SetTypeOfTask(GetStaticTypeOfTask());
42
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetInput() = in;
43 40 }
44
45 40 bool ShkenevIConstrHullSeq::ValidationImpl() {
46 const auto &in = GetInput();
47
2/4
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 40 times.
 40 bool dims = in.width > 0 && in.height > 0;
48 40 bool size = in.pixels.size() == static_cast<size_t>(in.width) * static_cast<size_t>(in.height);
49 40 return dims && size;
50 }
51
52 40 bool ShkenevIConstrHullSeq::PreProcessingImpl() {
53 40 work_ = GetInput();
54 ThresholdImage();
55 40 return true;
56 }
57
58 40 bool ShkenevIConstrHullSeq::RunImpl() {
59 40 FindComponents();
60
61 work_.convex_hulls.clear();
62 40 work_.convex_hulls.reserve(work_.components.size());
63
64
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 40 times.
 88 for (const auto &comp : work_.components) {
65
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (comp.empty()) {
66 ✗ continue;
67 }
68
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 if (comp.size() <= 2) {
69 24 work_.convex_hulls.push_back(comp);
70 } else {
71
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 48 work_.convex_hulls.push_back(BuildHull(comp));
72 }
73 }
74
75 40 GetOutput() = work_;
76 40 return true;
77 }
78
79 40 bool ShkenevIConstrHullSeq::PostProcessingImpl() {
80 40 return true;
81 }
82
83 ✗ size_t ShkenevIConstrHullSeq::Index(int x, int y, int width) {
84
3/4
✓ Branch 0 taken 504 times.
✓ Branch 1 taken 1312 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1984 times.
 3800 return (static_cast<size_t>(y) * static_cast<size_t>(width)) + static_cast<size_t>(x);
85 }
86
87 ✗ void ShkenevIConstrHullSeq::ThresholdImage() {
88
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 1816 times.
✓ Branch 3 taken 40 times.
 1856 for (auto &p : work_.pixels) {
89
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 1312 times.
✓ Branch 3 taken 504 times.
 3128 p = IsForeground(p) ? static_cast<uint8_t>(255) : static_cast<uint8_t>(0);
90 }
91 ✗ }
92
93 48 void ShkenevIConstrHullSeq::ExploreComponent(int start_col, int start_row, int width, int height,
94 std::vector<bool> &visited, std::vector<Point> &component) {
95 std::queue<Point> queue;
96 queue.emplace(start_col, start_row);
97
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 visited[Index(start_col, start_row, width)] = true;
98
99
2/2
✓ Branch 0 taken 504 times.
✓ Branch 1 taken 48 times.
 552 while (!queue.empty()) {
100 504 Point current = queue.front();
101 queue.pop();
102 component.push_back(current);
103
104
2/2
✓ Branch 0 taken 2016 times.
✓ Branch 1 taken 504 times.
 2520 for (auto [dx, dy] : kDirs) {
105 2016 int next_x = current.x + dx;
106
2/2
✓ Branch 0 taken 2000 times.
✓ Branch 1 taken 16 times.
 2016 int next_y = current.y + dy;
107
108
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 1984 times.
 2000 if (!IsInBounds(next_x, next_y, width, height)) {
109 1560 continue;
110 }
111
112 size_t next_idx = Index(next_x, next_y, width);
113
4/4
✓ Branch 0 taken 1000 times.
✓ Branch 1 taken 984 times.
✓ Branch 2 taken 544 times.
✓ Branch 3 taken 456 times.
 1984 if (visited[next_idx] || work_.pixels[next_idx] == 0) {
114 1528 continue;
115 }
116
117 visited[next_idx] = true;
118 queue.emplace(next_x, next_y);
119 }
120 }
121 48 }
122
123 40 void ShkenevIConstrHullSeq::FindComponents() {
124 40 int width = work_.width;
125 40 int height = work_.height;
126
127
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 40 times.
 40 std::vector<bool> visited(static_cast<size_t>(width) * static_cast<size_t>(height), false);
128 work_.components.clear();
129
130
2/2
✓ Branch 0 taken 248 times.
✓ Branch 1 taken 40 times.
 288 for (int row = 0; row < height; ++row) {
131
2/2
✓ Branch 0 taken 1816 times.
✓ Branch 1 taken 248 times.
 2064 for (int col = 0; col < width; ++col) {
132 size_t idx = Index(col, row, width);
133
4/4
✓ Branch 0 taken 504 times.
✓ Branch 1 taken 1312 times.
✓ Branch 2 taken 456 times.
✓ Branch 3 taken 48 times.
 1816 if (work_.pixels[idx] == 0 || visited[idx]) {
134 1768 continue;
135 }
136
137 48 std::vector<Point> component;
138
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ExploreComponent(col, row, width, height, visited, component);
139
140
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (!component.empty()) {
141
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 work_.components.push_back(std::move(component));
142 }
143 }
144 }
145 40 }
146
147
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 std::vector<Point> ShkenevIConstrHullSeq::BuildHull(const std::vector<Point> &points) {
148
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (points.size() <= 2) {
149 ✗ return points;
150 }
151
152 24 std::vector<Point> pts = points;
153
17/26
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 296 times.
✓ Branch 5 taken 112 times.
✓ Branch 6 taken 248 times.
✓ Branch 7 taken 64 times.
✓ Branch 8 taken 16 times.
✓ Branch 9 taken 8 times.
✓ Branch 10 taken 8 times.
✓ Branch 11 taken 8 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 8 times.
✓ Branch 14 taken 8 times.
✗ Branch 15 not taken.
✓ Branch 16 taken 8 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✓ Branch 20 taken 704 times.
✓ Branch 21 taken 400 times.
✓ Branch 22 taken 224 times.
✓ Branch 23 taken 32 times.
✓ Branch 24 taken 512 times.
✓ Branch 25 taken 240 times.
 2896 std::ranges::sort(pts, [](const Point &a, const Point &b) { return (a.x != b.x) ? (a.x < b.x) : (a.y < b.y); });
154
155 auto [first, last] = std::ranges::unique(pts);
156 pts.erase(first, last);
157
158
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (pts.size() <= 2) {
159 return pts;
160 }
161
162 24 std::vector<Point> lower;
163
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<Point> upper;
164
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 lower.reserve(pts.size());
165
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 upper.reserve(pts.size());
166
167
2/2
✓ Branch 0 taken 480 times.
✓ Branch 1 taken 24 times.
 504 for (const auto &p : pts) {
168
4/4
✓ Branch 0 taken 776 times.
✓ Branch 1 taken 120 times.
✓ Branch 2 taken 416 times.
✓ Branch 3 taken 360 times.
 896 while (lower.size() >= 2 && Cross(lower[lower.size() - 2], lower.back(), p) <= 0) {
169 lower.pop_back();
170 }
171 lower.push_back(p);
172 }
173
174
2/2
✓ Branch 0 taken 480 times.
✓ Branch 1 taken 24 times.
 504 for (const auto &p : std::ranges::reverse_view(pts)) {
175
4/4
✓ Branch 0 taken 776 times.
✓ Branch 1 taken 120 times.
✓ Branch 2 taken 360 times.
✓ Branch 3 taken 416 times.
 896 while (upper.size() >= 2 && Cross(upper[upper.size() - 2], upper.back(), p) <= 0) {
176 upper.pop_back();
177 }
178 upper.push_back(p);
179 }
180
181 lower.pop_back();
182 upper.pop_back();
183
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 lower.insert(lower.end(), upper.begin(), upper.end());
184 return lower;
185 }
186
187 } // namespace shkenev_i_constra_hull_for_binary_image
188