GCC Code Coverage Report

Directory: ./
File: tasks/kamalagin_a_binary_image_convex_hull/omp/src/ops_omp.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 87 87 100.0%
Functions: 13 13 100.0%
Branches: 71 98 72.4%
Line Branch Exec Source
1 #include "kamalagin_a_binary_image_convex_hull/omp/include/ops_omp.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <utility>
8 #include <vector>
9
10 #include "kamalagin_a_binary_image_convex_hull/common/include/common.hpp"
11
12 namespace kamalagin_a_binary_image_convex_hull {
13
14 namespace {
15
16 constexpr std::array<std::pair<int, int>, 4> kFourNeighbors = {{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}};
17
18 int64_t Cross(const Point &o, const Point &a, const Point &b) {
19 132 return (static_cast<int64_t>(a.x - o.x) * (b.y - o.y)) - (static_cast<int64_t>(a.y - o.y) * (b.x - o.x));
20 }
21
22 int64_t DistSq(const Point &a, const Point &b) {
23 56 const int dx = a.x - b.x;
24 56 const int dy = a.y - b.y;
25 56 return (static_cast<int64_t>(dx) * dx) + (static_cast<int64_t>(dy) * dy);
26 }
27
28 12 size_t GrahamFindPivot(std::vector<Point> &pts) {
29 size_t pivot = 0;
30 const size_t n = pts.size();
31
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 12 times.
 64 for (size_t i = 1; i < n; ++i) {
32
4/6
✓ Branch 0 taken 52 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 28 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 24 times.
 52 if (pts[i].y < pts[pivot].y || (pts[i].y == pts[pivot].y && pts[i].x < pts[pivot].x)) {
33 pivot = i;
34 }
35 }
36 12 return pivot;
37 }
38
39 12 void GrahamCollinearReduce(std::vector<Point> &pts) {
40 size_t m = 1;
41 const size_t n = pts.size();
42
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 12 times.
 52 for (size_t i = 2; i < n; ++i) {
43
4/4
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 28 times.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 12 times.
 72 while (m > 0 && Cross(pts[m - 1], pts[m], pts[i]) == 0) {
44 --m;
45 }
46 40 ++m;
47 40 pts[m] = pts[i];
48 }
49 12 pts.resize(m + 1);
50 12 }
51
52
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 void GrahamScan(std::vector<Point> &pts, Hull &out) {
53 out.push_back(pts[0]);
54
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 12 if (pts.size() <= 2) {
55
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 if (pts.size() == 2) {
56 out.push_back(pts[1]);
57 }
58 8 return;
59 }
60 out.push_back(pts[1]);
61
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 12 for (size_t i = 2; i < pts.size(); ++i) {
62
2/4
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 8 times.
 8 while (out.size() >= 2 && Cross(out[out.size() - 2], out.back(), pts[i]) <= 0) {
63 out.pop_back();
64 }
65 out.push_back(pts[i]);
66 }
67 }
68
69
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 void GrahamHull(std::vector<Point> &pts, Hull &out) {
70 out.clear();
71 const size_t n = pts.size();
72
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 12 times.
 32 if (n <= 1) {
73
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (n == 1) {
74 out.push_back(pts[0]);
75 }
76 20 return;
77 }
78 12 const size_t pivot = GrahamFindPivot(pts);
79 std::swap(pts[0], pts[pivot]);
80 const Point &p0 = pts[0];
81 92 std::sort(pts.begin() + 1, pts.end(), [&p0](const Point &a, const Point &b) {
82 80 const int64_t c = Cross(p0, a, b);
83
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 56 times.
 80 if (c != 0) {
84 24 return c > 0;
85 }
86 56 return DistSq(p0, a) < DistSq(p0, b);
87 });
88 12 GrahamCollinearReduce(pts);
89 12 GrahamScan(pts, out);
90 }
91
92 32 void FloodFillComponent(const BinaryImage &img, int start_row, int start_col, std::vector<int> &label,
93 std::vector<Point> &component_pts) {
94 32 const int rows = img.rows;
95
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 const int cols = img.cols;
96 component_pts.clear();
97 32 std::vector<std::pair<int, int>> stack;
98
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 stack.emplace_back(start_row, start_col);
99 32 const size_t start_idx = img.Index(start_row, start_col);
100 32 label[start_idx] = 1;
101
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 32 times.
 116 while (!stack.empty()) {
102 const auto [cur_r, cur_c] = stack.back();
103 stack.pop_back();
104
1/4
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 84 component_pts.push_back(Point{.x = cur_c, .y = cur_r});
105
2/2
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 84 times.
 420 for (const auto &[dr, dc] : kFourNeighbors) {
106 336 const int nr = cur_r + dr;
107 336 const int nc = cur_c + dc;
108
8/8
✓ Branch 0 taken 284 times.
✓ Branch 1 taken 52 times.
✓ Branch 2 taken 232 times.
✓ Branch 3 taken 52 times.
✓ Branch 4 taken 188 times.
✓ Branch 5 taken 44 times.
✓ Branch 6 taken 44 times.
✓ Branch 7 taken 144 times.
 336 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
109 192 continue;
110 }
111
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 24 times.
 144 const size_t nidx = (static_cast<size_t>(nr) * static_cast<size_t>(cols)) + static_cast<size_t>(nc);
112
4/4
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 52 times.
✓ Branch 3 taken 68 times.
 144 if (img.data[nidx] != 0 && label[nidx] == 0) {
113 52 label[nidx] = 1;
114
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 stack.emplace_back(nr, nc);
115 }
116 }
117 }
118 32 }
119
120
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 void CollectComponents(const BinaryImage &img, std::vector<std::vector<Point>> &components) {
121 components.clear();
122 28 const int rows = img.rows;
123 28 const int cols = img.cols;
124 28 const size_t total = static_cast<size_t>(rows) * static_cast<size_t>(cols);
125 28 std::vector<int> label(total, 0);
126
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 28 times.
 80 for (int row = 0; row < rows; ++row) {
127
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 52 times.
 176 for (int col = 0; col < cols; ++col) {
128 const size_t idx = img.Index(row, col);
129
4/4
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 40 times.
✓ Branch 2 taken 52 times.
✓ Branch 3 taken 32 times.
 124 if (img.data[idx] == 0 || label[idx] != 0) {
130 92 continue;
131 }
132
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 components.emplace_back();
133
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 FloodFillComponent(img, row, col, label, components.back());
134 }
135 }
136 28 }
137
138
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 void RunBinaryImageConvexHullOmp(const BinaryImage &img, HullList &hulls) {
139 hulls.clear();
140 28 std::vector<std::vector<Point>> components;
141
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 CollectComponents(img, components);
142 28 const int count = static_cast<int>(components.size());
143
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 hulls.resize(components.size());
144 28 #pragma omp parallel for default(none) shared(components, hulls, count) schedule(dynamic)
145 for (int i = 0; i < count; ++i) {
146 const auto idx = static_cast<size_t>(i);
147 GrahamHull(components[idx], hulls[idx]);
148 }
149 28 }
150
151 } // namespace
152
153
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 KamalaginABinaryImageConvexHullOMP::KamalaginABinaryImageConvexHullOMP(const InType &in) {
154 SetTypeOfTask(GetStaticTypeOfTask());
155 GetInput() = in;
156 28 GetOutput() = HullList{};
157 28 }
158
159 28 bool KamalaginABinaryImageConvexHullOMP::ValidationImpl() {
160 const auto &img = GetInput();
161
2/4
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 28 times.
✗ Branch 3 not taken.
 28 if (img.rows < 0 || img.cols < 0) {
162 return false;
163 }
164
3/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 24 times.
 28 if (img.rows == 0 || img.cols == 0) {
165 4 return img.data.empty();
166 }
167
2/4
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 if (img.rows > 8192 || img.cols > 8192) {
168 return false;
169 }
170 24 return (static_cast<size_t>(img.rows) * static_cast<size_t>(img.cols)) == img.data.size();
171 }
172
173
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 bool KamalaginABinaryImageConvexHullOMP::PreProcessingImpl() {
174 GetOutput().clear();
175 28 return true;
176 }
177
178 28 bool KamalaginABinaryImageConvexHullOMP::RunImpl() {
179 28 RunBinaryImageConvexHullOmp(GetInput(), GetOutput());
180 28 return true;
181 }
182
183 28 bool KamalaginABinaryImageConvexHullOMP::PostProcessingImpl() {
184 28 return true;
185 }
186
187 } // namespace kamalagin_a_binary_image_convex_hull
188