GCC Code Coverage Report

Directory: ./
File: tasks/egorova_l_binary_convex_hull/omp/src/ops_omp.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 69 75 92.0%
Functions: 9 10 90.0%
Branches: 71 172 41.3%
Line Branch Exec Source
1 #include "egorova_l_binary_convex_hull/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <cstdint>
8 #include <queue>
9 #include <utility>
10 #include <vector>
11
12 #include "egorova_l_binary_convex_hull/common/include/common.hpp"
13
14 namespace egorova_l_binary_convex_hull {
15
16 namespace {
17 struct Pixel {
18 int x;
19 int y;
20 336 Pixel(int x_coord, int y_coord) : x(x_coord), y(y_coord) {}
21 };
22
23 // Вспомогательная функция для проверки соседей
24 1344 inline void CheckNeighbor(const std::vector<uint8_t> &image, int width, int height, int next_x, int next_y, int label,
25 std::vector<int> &labels, std::queue<Pixel> &queue) {
26
4/8
✓ Branch 0 taken 1344 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1344 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1344 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1344 times.
✗ Branch 7 not taken.
 1344 if (next_x >= 0 && next_x < width && next_y >= 0 && next_y < height) {
27
2/2
✓ Branch 0 taken 848 times.
✓ Branch 1 taken 496 times.
 1344 const size_t next_index = (static_cast<size_t>(next_y) * static_cast<size_t>(width)) + static_cast<size_t>(next_x);
28
4/4
✓ Branch 0 taken 848 times.
✓ Branch 1 taken 496 times.
✓ Branch 2 taken 296 times.
✓ Branch 3 taken 552 times.
 1344 if (image[next_index] != 0 && labels[next_index] == 0) {
29 296 labels[next_index] = label;
30 queue.emplace(next_x, next_y);
31 }
32 }
33 1344 }
34 } // namespace
35
36 // ==================== Публичные методы ====================
37
38
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 BinaryConvexHullOMP::BinaryConvexHullOMP(const InType &in) {
39 SetTypeOfTask(GetStaticTypeOfTask());
40 GetInput() = in;
41 32 }
42
43 32 bool BinaryConvexHullOMP::ValidationImpl() {
44 const auto &input = GetInput();
45
3/6
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 32 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 32 times.
 32 return input.width > 0 && input.height > 0 && !input.data.empty() &&
46
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 input.data.size() == static_cast<size_t>(input.width) * static_cast<size_t>(input.height);
47 }
48
49
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 bool BinaryConvexHullOMP::PreProcessingImpl() {
50 GetOutput().clear();
51 32 return true;
52 }
53
54 32 bool BinaryConvexHullOMP::RunImpl() {
55 32 const int width = GetInput().width;
56 32 const int height = GetInput().height;
57 32 const auto &image = GetInput().data;
58
59 32 std::vector<std::vector<Point>> components = FindComponents(image, width, height);
60
61 auto &output = GetOutput();
62
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 output.resize(components.size());
63
64 32 omp_set_num_threads(omp_get_max_threads());
65
66 32 const int num_components = static_cast<int>(components.size());
67 32 #pragma omp parallel for schedule(dynamic, 1) default(none) shared(components, output, num_components)
68 for (int i = 0; i < num_components; ++i) {
69 if (components[i].empty()) {
70 continue;
71 }
72
73 std::vector<Point> hull;
74 BuildConvexHull(components[i], hull);
75
76 #pragma omp critical
77 {
78 output[i] = std::move(hull);
79 }
80 }
81
82 32 return true;
83 32 }
84
85 32 bool BinaryConvexHullOMP::PostProcessingImpl() {
86 32 return true;
87 }
88
89 // ==================== Приватные методы ====================
90
91 32 std::vector<std::vector<Point>> BinaryConvexHullOMP::FindComponents(const std::vector<uint8_t> &image, int width,
92 int height) {
93 32 const size_t image_size = static_cast<size_t>(width) * static_cast<size_t>(height);
94 32 std::vector<int> labels(image_size, 0);
95 int label_counter = 0;
96
97 32 std::vector<std::vector<Point>> components;
98
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 components.reserve(100);
99
100
2/2
✓ Branch 0 taken 460 times.
✓ Branch 1 taken 32 times.
 492 for (int row = 0; row < height; ++row) {
101
2/2
✓ Branch 0 taken 8100 times.
✓ Branch 1 taken 460 times.
 8560 for (int col = 0; col < width; ++col) {
102
2/2
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 7764 times.
 8100 const size_t index = (static_cast<size_t>(row) * static_cast<size_t>(width)) + static_cast<size_t>(col);
103
104
4/4
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 7764 times.
✓ Branch 2 taken 40 times.
✓ Branch 3 taken 296 times.
 8100 if (image[index] != 0 && labels[index] == 0) {
105 40 ++label_counter;
106 40 std::vector<Point> component_points;
107
108
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 ProcessComponent(image, width, height, col, row, label_counter, labels, component_points);
109
110
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (!component_points.empty()) {
111 components.push_back(std::move(component_points));
112 }
113 }
114 }
115 }
116
117 32 return components;
118 ✗ }
119
120 40 void BinaryConvexHullOMP::ProcessComponent(const std::vector<uint8_t> &image, int width, int height, int start_x,
121 int start_y, int label, std::vector<int> &labels,
122 std::vector<Point> &component_points) {
123
4/8
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 40 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 40 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 40 times.
 40 if (start_x < 0 || start_x >= width || start_y < 0 || start_y >= height) {
124 component_points.clear();
125 ✗ return;
126 }
127
128 std::queue<Pixel> queue;
129 queue.emplace(start_x, start_y);
130
131
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 const size_t start_index = (static_cast<size_t>(start_y) * static_cast<size_t>(width)) + static_cast<size_t>(start_x);
132
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 labels[start_index] = label;
133
134 component_points.clear();
135
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 component_points.reserve(1000);
136
137
2/2
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 40 times.
 376 while (!queue.empty()) {
138 336 Pixel current = queue.front();
139 queue.pop();
140
141
1/2
✓ Branch 1 taken 336 times.
✗ Branch 2 not taken.
 336 component_points.emplace_back(current.x, current.y);
142
143 // Явно перебираем все направления
144
1/2
✓ Branch 1 taken 336 times.
✗ Branch 2 not taken.
 336 CheckNeighbor(image, width, height, current.x + 1, current.y, label, labels, queue);
145
1/2
✓ Branch 1 taken 336 times.
✗ Branch 2 not taken.
 336 CheckNeighbor(image, width, height, current.x - 1, current.y, label, labels, queue);
146
1/2
✓ Branch 1 taken 336 times.
✗ Branch 2 not taken.
 336 CheckNeighbor(image, width, height, current.x, current.y + 1, label, labels, queue);
147
1/2
✓ Branch 1 taken 336 times.
✗ Branch 2 not taken.
 336 CheckNeighbor(image, width, height, current.x, current.y - 1, label, labels, queue);
148 }
149 }
150
151 ✗ int64_t BinaryConvexHullOMP::CrossProduct(const Point &a, const Point &b, const Point &c) {
152 720 const auto dx1 = static_cast<int64_t>(b.x - a.x);
153 720 const auto dy1 = static_cast<int64_t>(c.y - a.y);
154 720 const auto dx2 = static_cast<int64_t>(b.y - a.y);
155 720 const auto dy2 = static_cast<int64_t>(c.x - a.x);
156 720 return (dx1 * dy1) - (dx2 * dy2);
157 }
158
159
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 void BinaryConvexHullOMP::BuildConvexHull(std::vector<Point> &points, std::vector<Point> &hull) {
160 const size_t points_count = points.size();
161
162
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 if (points_count == 0) {
163 hull.clear();
164 ✗ return;
165 }
166
167
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 if (points_count <= 2) {
168 ✗ hull = points;
169 ✗ return;
170 }
171
172 std::ranges::sort(
173
9/78
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✓ Branch 67 taken 296 times.
✓ Branch 68 taken 80 times.
✓ Branch 69 taken 216 times.
✗ Branch 70 not taken.
✓ Branch 71 taken 80 times.
✓ Branch 72 taken 252 times.
✓ Branch 73 taken 296 times.
✓ Branch 74 taken 208 times.
✓ Branch 75 taken 88 times.
✗ Branch 76 not taken.
✓ Branch 77 taken 208 times.
 844 points, [](const Point &lhs, const Point &rhs) { return lhs.x < rhs.x || (lhs.x == rhs.x && lhs.y < rhs.y); });
174
175 // Нижняя оболочка
176 hull.clear();
177 40 hull.reserve(points_count + 1);
178
2/2
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 40 times.
 376 for (size_t i = 0; i < points_count; ++i) {
179
4/4
✓ Branch 0 taken 356 times.
✓ Branch 1 taken 208 times.
✓ Branch 2 taken 228 times.
✓ Branch 3 taken 128 times.
 564 while (hull.size() >= 2 && CrossProduct(hull[hull.size() - 2], hull.back(), points[i]) <= 0) {
180 hull.pop_back();
181 }
182 hull.push_back(points[i]);
183 }
184
185 // Верхняя оболочка
186 const size_t lower_hull_size = hull.size();
187
2/2
✓ Branch 0 taken 296 times.
✓ Branch 1 taken 40 times.
 336 for (size_t i = points_count - 1; i > 0; --i) {
188 296 const size_t idx = i - 1;
189
4/4
✓ Branch 0 taken 364 times.
✓ Branch 1 taken 156 times.
✓ Branch 2 taken 140 times.
✓ Branch 3 taken 224 times.
 520 while (hull.size() > lower_hull_size && CrossProduct(hull[hull.size() - 2], hull.back(), points[idx]) <= 0) {
190 hull.pop_back();
191 }
192 hull.push_back(points[idx]);
193 }
194
195
3/6
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 40 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 40 times.
✗ Branch 5 not taken.
 40 if (hull.size() > 1 && hull.front().x == hull.back().x && hull.front().y == hull.back().y) {
196 hull.pop_back();
197 }
198 }
199
200 } // namespace egorova_l_binary_convex_hull
201