GCC Code Coverage Report

Directory: ./
File: tasks/shkenev_i_constra_hull_for_binary_image/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 68 72 94.4%
Functions: 8 10 80.0%
Branches: 73 102 71.6%
Line Branch Exec Source
1 #include "shkenev_i_constra_hull_for_binary_image/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <array>
7 #include <cstddef>
8 #include <cstdint>
9 #include <queue>
10 #include <ranges>
11 #include <utility>
12 #include <vector>
13
14 #include "shkenev_i_constra_hull_for_binary_image/common/include/common.hpp"
15 #include "util/include/util.hpp"
16
17 namespace shkenev_i_constra_hull_for_binary_image {
18
19 namespace {
20
21 constexpr uint8_t kThreshold = 128;
22 constexpr std::array<std::pair<int, int>, 4> kDirs = {std::make_pair(1, 0), std::make_pair(-1, 0), std::make_pair(0, 1),
23 std::make_pair(0, -1)};
24
25 int64_t Cross(const Point &a, const Point &b, const Point &c) {
26 776 int64_t abx = static_cast<int64_t>(b.x) - static_cast<int64_t>(a.x);
27 776 int64_t aby = static_cast<int64_t>(b.y) - static_cast<int64_t>(a.y);
28 776 int64_t bcx = static_cast<int64_t>(c.x) - static_cast<int64_t>(b.x);
29 776 int64_t bcy = static_cast<int64_t>(c.y) - static_cast<int64_t>(b.y);
30 776 return (abx * bcy) - (aby * bcx);
31 }
32
33 bool IsForeground(uint8_t pixel) {
34 return pixel > kThreshold;
35 }
36
37 bool IsInBounds(int x, int y, int width, int height) {
38 2008 return x >= 0 && x < width && y >= 0 && y < height;
39 }
40
41 } // namespace
42
43
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 ShkenevIConstrHullOMP::ShkenevIConstrHullOMP(const InType &in) : work_(in) {
44 SetTypeOfTask(GetStaticTypeOfTask());
45
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 GetInput() = in;
46 20 }
47
48 20 bool ShkenevIConstrHullOMP::ValidationImpl() {
49 const auto &in = GetInput();
50
2/4
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 20 times.
 20 bool dims = in.width > 0 && in.height > 0;
51 20 bool size = in.pixels.size() == static_cast<size_t>(in.width) * static_cast<size_t>(in.height);
52 20 return dims && size;
53 }
54
55 20 bool ShkenevIConstrHullOMP::PreProcessingImpl() {
56 20 work_ = GetInput();
57 ThresholdImage();
58 20 return true;
59 }
60
61 20 bool ShkenevIConstrHullOMP::RunImpl() {
62 20 FindComponents();
63
64 work_.convex_hulls.clear();
65 20 work_.convex_hulls.resize(work_.components.size());
66
67 20 auto &components = work_.components;
68 auto &convex_hulls = work_.convex_hulls;
69
70 20 #pragma omp parallel for default(none) shared(components, convex_hulls) num_threads(ppc::util::GetNumThreads())
71 for (std::size_t i = 0; i < components.size(); ++i) {
72 const auto &comp = components[i];
73 if (comp.empty()) {
74 continue;
75 }
76 if (comp.size() <= 2) {
77 convex_hulls[i] = comp;
78 } else {
79 convex_hulls[i] = BuildHull(comp);
80 }
81 }
82
83 20 GetOutput() = work_;
84 20 return true;
85 }
86
87 20 bool ShkenevIConstrHullOMP::PostProcessingImpl() {
88 20 return true;
89 }
90
91 ✗ size_t ShkenevIConstrHullOMP::Index(int x, int y, int width) {
92
4/4
✓ Branch 0 taken 252 times.
✓ Branch 1 taken 656 times.
✓ Branch 2 taken 500 times.
✓ Branch 3 taken 492 times.
 1900 return (static_cast<size_t>(y) * static_cast<size_t>(width)) + static_cast<size_t>(x);
93 }
94
95 ✗ void ShkenevIConstrHullOMP::ThresholdImage() {
96 auto &pixels = work_.pixels;
97
98
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 908 times.
✓ Branch 3 taken 20 times.
 928 for (auto &pixel : pixels) {
99
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 656 times.
✓ Branch 3 taken 252 times.
 1564 pixel = IsForeground(pixel) ? static_cast<uint8_t>(255) : static_cast<uint8_t>(0);
100 }
101 ✗ }
102
103 24 void ShkenevIConstrHullOMP::ExploreComponent(int start_col, int start_row, int width, int height,
104 std::vector<uint8_t> &visited, std::vector<Point> &component) {
105 std::queue<Point> queue;
106 queue.emplace(start_col, start_row);
107 24 visited[Index(start_col, start_row, width)] = 1;
108
109
2/2
✓ Branch 0 taken 252 times.
✓ Branch 1 taken 24 times.
 276 while (!queue.empty()) {
110 252 Point current = queue.front();
111 queue.pop();
112 component.push_back(current);
113
114
2/2
✓ Branch 0 taken 1008 times.
✓ Branch 1 taken 252 times.
 1260 for (auto [dx, dy] : kDirs) {
115 1008 int next_x = current.x + dx;
116
2/2
✓ Branch 0 taken 1000 times.
✓ Branch 1 taken 8 times.
 1008 int next_y = current.y + dy;
117
118
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 992 times.
 1000 if (!IsInBounds(next_x, next_y, width, height)) {
119 780 continue;
120 }
121
122 size_t next_idx = Index(next_x, next_y, width);
123
4/4
✓ Branch 0 taken 500 times.
✓ Branch 1 taken 492 times.
✓ Branch 2 taken 228 times.
✓ Branch 3 taken 272 times.
 992 if (visited[next_idx] != 0 || work_.pixels[next_idx] == 0) {
124 764 continue;
125 }
126
127
1/2
✓ Branch 1 taken 228 times.
✗ Branch 2 not taken.
 228 visited[next_idx] = 1;
128 queue.emplace(next_x, next_y);
129 }
130 }
131 24 }
132
133 20 void ShkenevIConstrHullOMP::FindComponents() {
134 20 int width = work_.width;
135 20 int height = work_.height;
136
137
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 20 times.
 20 std::vector<uint8_t> visited(static_cast<size_t>(width) * static_cast<size_t>(height), 0);
138 work_.components.clear();
139
140
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 20 times.
 144 for (int row = 0; row < height; ++row) {
141
2/2
✓ Branch 0 taken 908 times.
✓ Branch 1 taken 124 times.
 1032 for (int col = 0; col < width; ++col) {
142 size_t idx = Index(col, row, width);
143
4/4
✓ Branch 0 taken 252 times.
✓ Branch 1 taken 656 times.
✓ Branch 2 taken 228 times.
✓ Branch 3 taken 24 times.
 908 if (work_.pixels[idx] == 0 || visited[idx] != 0) {
144 884 continue;
145 }
146
147 24 std::vector<Point> component;
148
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 ExploreComponent(col, row, width, height, visited, component);
149
150
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (!component.empty()) {
151
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 work_.components.push_back(std::move(component));
152 }
153 }
154 }
155 20 }
156
157
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 std::vector<Point> ShkenevIConstrHullOMP::BuildHull(const std::vector<Point> &points) {
158
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (points.size() <= 2) {
159 ✗ return points;
160 }
161
162 12 std::vector<Point> pts = points;
163
17/26
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 148 times.
✓ Branch 5 taken 56 times.
✓ Branch 6 taken 124 times.
✓ Branch 7 taken 32 times.
✓ Branch 8 taken 8 times.
✓ Branch 9 taken 4 times.
✓ Branch 10 taken 4 times.
✓ Branch 11 taken 4 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 4 times.
✓ Branch 14 taken 4 times.
✗ Branch 15 not taken.
✓ Branch 16 taken 4 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✓ Branch 20 taken 352 times.
✓ Branch 21 taken 200 times.
✓ Branch 22 taken 112 times.
✓ Branch 23 taken 16 times.
✓ Branch 24 taken 256 times.
✓ Branch 25 taken 120 times.
 1448 std::ranges::sort(pts, [](const Point &a, const Point &b) { return (a.x != b.x) ? (a.x < b.x) : (a.y < b.y); });
164
165 auto [first, last] = std::ranges::unique(pts);
166 pts.erase(first, last);
167
168
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (pts.size() <= 2) {
169 return pts;
170 }
171
172 12 std::vector<Point> lower;
173
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<Point> upper;
174
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 lower.reserve(pts.size());
175
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 upper.reserve(pts.size());
176
177
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 12 times.
 252 for (const auto &p : pts) {
178
4/4
✓ Branch 0 taken 388 times.
✓ Branch 1 taken 60 times.
✓ Branch 2 taken 208 times.
✓ Branch 3 taken 180 times.
 448 while (lower.size() >= 2 && Cross(lower[lower.size() - 2], lower.back(), p) <= 0) {
179 lower.pop_back();
180 }
181 lower.push_back(p);
182 }
183
184
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 12 times.
 252 for (const auto &p : std::ranges::reverse_view(pts)) {
185
4/4
✓ Branch 0 taken 388 times.
✓ Branch 1 taken 60 times.
✓ Branch 2 taken 180 times.
✓ Branch 3 taken 208 times.
 448 while (upper.size() >= 2 && Cross(upper[upper.size() - 2], upper.back(), p) <= 0) {
186 upper.pop_back();
187 }
188 upper.push_back(p);
189 }
190
191 lower.pop_back();
192 upper.pop_back();
193
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 lower.insert(lower.end(), upper.begin(), upper.end());
194 return lower;
195 }
196
197 } // namespace shkenev_i_constra_hull_for_binary_image
198